Lines Matching refs:tree
258 on the filesystem. At the super-block level, littlefs is a CObW tree of blocks
575 [B-trees][wikipedia-B-tree], which can not be traversed with constant RAM, and
576 [B+-trees][wikipedia-B+-tree], which are not possible to update with COW
897 through every block on storage and check each one against our filesystem tree;
1485 directory pointers in our metadata pairs, which gives us a directory tree, much
1513 [RAM]. The directory tree is a tree, and the unfortunate fact is you can't
1514 traverse a tree with constant RAM.
1516 Fortunately, the elements of our tree are metadata pairs, so unlike CTZ
1518 thread a linked-list through our tree, explicitly enabling cheap traversal
1546 whenever we want to manipulate the directory tree, multiple pointers need to be
1556 that maintain a filesystem tree threaded with a linked-list for traversal.
1558 Adding a directory to our tree:
1688 In addition to normal directory tree operations, we can use orphans to evict
1815 while manipulating the directory tree (foreshadowing!).
1838 - Some filesystems propagate COW operations up the tree until a common parent
1839 is found. Unfortunately this interacts poorly with our threaded tree and
2119 [wikipedia-B-tree]: https://en.wikipedia.org/wiki/B-tree
2120 [wikipedia-B+-tree]: https://en.wikipedia.org/wiki/B%2B_tree