Why Use B-Trees Over Binary Trees for Disk Indexing?

B-trees and B+ trees are favored over binary trees for indexing on-disk file system directories because they minimize expensive disk I/O operations. By packing many keys into a single node that matches the size of a disk block, these multi-way trees achieve a much higher branching factor and a dramatically shallower height than binary trees, allowing file systems to locate files in just a few disk reads.

The Cost of Disk I/O

In classical computing, accessing data in main memory (RAM) takes nanoseconds, whereas reading a block from a mechanical hard disk drive (HDD) or even a solid-state drive (SSD) takes microseconds to milliseconds. Storage devices read and write data in fixed-size chunks called blocks or pages, typically ranging from 4 KB to 64 KB.

When a file system traverses a tree index stored on disk, each node lookup that is not already cached in memory requires a separate disk read. Therefore, the primary performance bottleneck for on-disk indexing is not CPU comparison time, but the total number of disk block reads required to reach the target entry.

Branching Factor and Tree Height

A standard binary search tree (BST) has a branching factor of 2, meaning each node holds at most one key and two child pointers. For a directory containing \(N\) files, a balanced binary tree has a height of:

\[h \approx \log_2(N)\]

If a directory contains \(N = 1,000,000\) entries, a balanced binary tree requires roughly \(\log_2(1,000,000) \approx 20\) levels. Traversing from the root to a leaf could require up to 20 separate disk reads. Worse, each small binary node wastes most of the 4 KB disk block it occupies, leading to poor spatial locality.

In contrast, B-trees and B+ trees are multi-way search trees with a high branching factor \(B\) (often hundreds or thousands), chosen so that a single node fits neatly into one disk block. The height of a B-tree or B+ tree is:

\[h \approx \log_B(N)\]

With a branching factor of \(B = 500\), indexing \(1,000,000\) entries requires at most \(\log_{500}(1,000,000) \approx 3\) levels. Finding any file in that directory takes at most 3 disk reads—and often fewer if the root and upper levels are cached in RAM.

Why B+ Trees Excel for Directory Scans

While both B-trees and B+ trees reduce tree height, B+ trees are especially common in modern file systems (such as NTFS, XFS, ext4 with HTree variants, and Btrfs) for two additional reasons:

  • Higher fanout in internal nodes: In a B-tree, internal nodes store both keys and data pointers (or file records). In a B+ tree, internal nodes store only keys and child pointers, while all actual directory entries or file pointers reside in the leaf nodes. This allows internal nodes to hold more keys per block, further increasing \(B\) and reducing tree height.
  • Fast sequential range scans: In a B+ tree, all leaf nodes are linked together in a sequential linked list. Operations like listing a directory (ls or readdir) or finding all files matching a prefix can locate the first matching leaf and then scan sequentially across adjacent leaf blocks without traversing back up the tree.

Cache Efficiency and Write Amplification

Because B-trees and B+ trees have very few levels, the top levels of the tree easily fit in the operating system's page cache. In practice, the root node and the first level of internal nodes remain in memory, meaning a lookup often requires only a single disk read to fetch the leaf block.

Additionally, balancing a binary tree on disk after insertions or deletions can trigger frequent pointer updates scattered across many different disk blocks. B-trees and B+ trees amortize these structural changes: nodes are kept at least half full, and splits or merges occur relatively infrequently, keeping disk writes localized and predictable.