nakst wrote:
Korona wrote:
I think you have to accept that you need to look at each component of the path. IMHO that is not the goal that a single global B-tree tries to solve. Rather, I'd see them as a solution to fragmentation problem: if you store one B-tree per directory, you end of with lots of wasted blocks (because all directory entries fit into the root of the B-tree).
Does the root of the B-tree have to be in a separate block to the rest of the directory metadata? With 1KB directory entries, I have roughly 900 bytes of leftover space for inline data, in which I could fit about 28 keys (with an 8 byte hash). Looking at my Linux partition, 90% of folders have less than 28 files. So maybe a B-tree per directory isn't that much of a problem?
Yeah, but the idea would be to not require a full block per directory, exactly because most folders do not contain many files.
nakst wrote:
Korona wrote:
The directory-move problem is solved by the "order by depth, then path" strategy that I described above.
I don't understand how this works, sorry. Surely you still have to move all the keys to a different place in the tree, and update their path?
If you tree is ordered by path depth first (i.e. number of slashes in a path) and the path itself second, all entries from a given directory are next to each other. The other would be:
foo/bar1
foo/bar2
foo/baz/bazbar1
foo/baz/bazbar2
and so on. Because the entries are adjacent in the tree, to move the full directory (including subdirectories), you only have to: (1) find the B-tree node that contains the first file in the directory, (2) find the B-tree node that contains the last file in the directory, (3) move the entries out of the first and last block to their new location and (4) rewrite the blocks in between the first and the last block, without actually copying data. You could store path names relative to some (suitably chosen) parent B-tree node to compress the paths and avoid making changes to the paths during a move.
I did not look into this in detail though, so those are only some rough suggestions. It might make sense to look into btrfs that does store the whole FS in a single B-tree.