B-Trees: More Than I Thought I'd Want to Know

>From there, you can build the file's representation in RAM with much fewer random-traversals than the FAT32 linked-list approach.

You can do same thing in FAT by reading whole cluster map at the start. Wiki: "Other high-level mechanisms may read in and process larger parts or the complete FAT on startup or on demand when needed and dynamically build up in-memory tree representations of the volume's file structures different from the on-disk structures." This passage references OS/2 documentation, but its unclear to me if OS/2 employed such optimizations. Later NT builds might have this, as Iv seen large files allocated into empty space in the middle of a disk instead of forcing writes into first available gap.

>B-Trees mitigate the random-reads associated with fragmentation. There are much fewer seeks from a b-tree based representation than a FAT/linked-list style representation

after reading whole cluster map you have same representation in RAM, there is no information disparity. Its less elegant, slower to initialize and wasteful - 2TB FAT32 partition with 32KB clusters means >250MB cluster map on disk. But at the end of the day disk will have to perform same random seeks to read already fragmented file. The magic bullet for fragmentation is a map of free sectors letting OS pre plan where to put files in a smart way, and even NTFS doesnt use fancy data structures for that. NTFS $BITMAP is a https://en.wikipedia.org/wiki/Free_space_bitmap. exFAT has a nice feature of marking unfragmented files in the Directory entry removing the need for FAT traversal altogether.

>Consider this scenario. You have a FAT/Linked list of the following: 0 -> 10 -> 5 -> 7 -> 2 -> 1 So you need to move-head to 0, read, move-head to 10, read, move-head to 5, read, (etc. etc.). That's 6 times you move the head randomly.

or whole FAT table is cached in ram and there is no difference :)

One of the "rules of thumb" of optimising high-fanout B-trees larger than memory is to generally put values in the leaves, because the benefit of being able to keep more pointers cached in memory in compact internal nodes to help locate values in fewer I/O steps outweighs the benefit of having an arbitrary and small subset of larger values in the internal nodes. But if you have particularly well-chosen larger values in the internal nodes, and a low-entropy access pattern, perhaps the rule of thumb doesn't apply then.

There are quite a few B-tree modifications where separate small trees or logs or both are maintained to improve performance, but these are generally to optimise writes, which can be sorted and distributed in batches to reduce random access block I/O, rather than to optimise frequently accessed reads by acting as an on-storage persistent cache.

On fanout:

High fanout is generally used with storage devices, because low fanout always increases the overhead.

For example on NVMe SSDs I've used, reading or writing any block smaller than 4096 bytes takes the same time as 4096 bytes. On HDDs the equivalent number is much larger due to seek time.

So lowering fanout below 4096 bytes per block would just increase the number of block I/Os per tree operation. without reducing the time per I/O.

On COW:

You're right about the rewriting, although it's worth knowing that times have changed: On NVMe you have durable write atomicity guarantees so you don't need to COW as much to have the same storage guarantees. Inside the NVMe of course it may be doing COW on hidden page remappings to provide this atomicity, or it may use other techniques (e.g. a supercapacitor to ensure writes always complete) but from the outside you can simply overwrite blocks or parts of blocks in place.

This adds quite a saving to safe tree updates, and it also reduces padding required in write-ahead logs at durable commit points, including the in-block logs used in several B-tree optimisations (e.g. see bcache on Linux).

Even with COW, it isn't always necessary to update the path to the root by rewriting parent blocks in general. To avoid a parent block write, sometimes it's faster to log an update to the parent's pointer entry, either in an actual logical log somewhere, or using a separate logical to physical page mapping table, or by using pointer-to-log entries that are resolved at read time.

If it's an in-memory B-tree, a COW strategy doesn't need to rewrite parent blocks at all. It can update the pointers in place directly with atomic pointer updates, although some implementations prefer a logical-to-physical page mapping table instead and to atomically update the table.