B-tree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike a binary search tree, which organizes exactly two children per node, a B-tree permits a variable number of children within a fixed range, with each node sized to match the block size of the underlying storage medium. This design is not an optimization — it is a physical adaptation. The B-tree was invented in 1970 by Rudolf Bayer and Edward McCreight at Boeing Research Labs, and its defining insight was that the cost of accessing a node from disk dwarfs the cost of scanning within it. A B-tree therefore maximizes the data payload per disk access, turning the memory hierarchy from an adversary into an ally.

From Binary Trees to Block-Oriented Trees

A binary search tree achieves O(log n) lookup by halving the search space at each level. But on disk, each node traversal requires a random seek — a mechanical operation that takes milliseconds. A binary tree with a million keys requires roughly twenty disk accesses in the worst case. At one millisecond per seek, that is twenty milliseconds per lookup: unacceptable for a database serving thousands of queries per second.

The B-tree solves this by increasing the branching factor. Instead of two children, a node may have hundreds. The search still discards a large fraction of the remaining keys at each level, but now each level corresponds to a single disk block. A B-tree with a branching factor of 500 can store 125 million keys in just three levels. Three disk accesses instead of twenty. The logarithm is still logarithmic, but the base of the logarithm is the block size, not two. This is the difference between a mathematical structure and a systems structure: the B-tree is not merely a sorted tree; it is a sorted tree whose geometry is calibrated to the physical geometry of the disk.

B-trees in Practice: Databases and File Systems

Virtually every database index is a B-tree or a variant. InnoDB uses B+ trees — a B-tree variant where all data resides in the leaf nodes, and internal nodes contain only keys for navigation. This design amortizes the cost of range scans, because leaf nodes are linked in sequential order, allowing a query to traverse a range without returning to the root. The query optimizer of a relational database chooses between B-tree indexes and hash indexes based on workload, but B-trees are the default because they handle both point lookups and range queries efficiently.

The B-tree also underlies most modern file systems. NTFS uses B-trees for directory indexing. Ext4 uses B-trees (in the form of Htree structures) for large directories. Even the virtual memory subsystem of Linux and other operating systems uses tree-like structures to map virtual addresses to physical pages. The B-tree is not a data structure of a single domain; it is the universal bridge between the logical world of sorted keys and the physical world of block-addressable storage.

Variants and Descendants

The B+ tree, mentioned above, is the most common variant in databases. The B* tree maintains higher occupancy by redistributing keys between siblings before splitting, reducing wasted space. The LSM-tree (Log-Structured Merge-tree) takes a different approach: instead of updating a B-tree in place, it buffers writes in a log and periodically merges sorted runs into larger sorted structures. LSM-trees are the foundation of NoSQL stores like LevelDB and RocksDB, and they represent a deliberate rejection of the B-tree model in favor of sequential write performance on solid-state drives. The B-tree and the LSM-tree are not merely competing data structures; they are competing philosophies of how to reconcile random access with physical storage.

The B-tree is the most successful compromise between mathematics and physics in all of computing. It is not elegant — a B-tree is full of special cases, boundary conditions, and implementation-specific heuristics for splitting, merging, and rebalancing. It is not pure — its performance depends on block size, cache line size, prefetch behavior, and disk geometry, all of which vary across hardware. But it is effective in a way that purer structures are not. The B-tree teaches that the best systems are not those that ignore physical reality in pursuit of logical beauty, but those that embed physical reality into their logical structure. Any data structure that pretends memory is uniform — that treats a cache line and a disk block as equivalent — is not an abstraction but a delusion. The B-tree is honest about the substrate it runs on, and that honesty is why it endures.