For decades, the B-tree has been the default index structure in databases. PostgreSQL, MySQL, Oracle, SQL Server—they all reach for a B-tree when you run CREATE INDEX. Despite newer alternatives like LSM trees, fractal trees, and learned indexes, the B-tree holds on with remarkable tenacity. Understanding why requires understanding what the structure actually optimizes for.

The Problem B-Trees Solve

A naive index might be a sorted array: fast binary search, O(log n) lookup. The problem is writes. Insert an element in the middle and you’re shuffling half the array. For an on-disk structure accessed via a storage system that reads and writes in fixed-size pages—typically 4 KB to 16 KB—this is catastrophic.

B-trees solve this by storing many keys per node rather than one. A typical database page holds hundreds of keys alongside pointers to child pages. Because each node is sized to match a storage page, a single I/O operation reads or writes an entire node. And because the tree stays shallow—a million-entry index might be only three or four levels deep—finding any record requires at most a handful of page reads.

This page alignment is the core insight. The B-tree was designed in 1970 explicitly around disk characteristics. Half a century later, SSDs have different performance profiles than spinning disks, but they still operate on pages, and the I/O amplification tradeoffs haven’t changed enough to dislodge B-trees from their dominant position.

B-Tree vs. B+ Tree: The Practical Distinction

Most databases actually use a B+ tree variant, though the distinction often goes unmentioned in documentation. In a pure B-tree, internal nodes store both keys and data pointers. In a B+ tree, internal nodes store only keys used for routing, while all data pointers live in the leaf nodes. The leaf nodes are also linked together in a doubly-linked list.

This matters enormously for range queries. In a B+ tree, once you find the start of a range, you walk the leaf list forward—sequential I/O, cache-friendly, fast. In a pure B-tree, you’d have to traverse back up and down the tree for each additional row. Every database system that advertises efficient range scans is using a B+ tree internally.

How Splits and Merges Maintain Balance

What makes B-trees attractive beyond reads is that they maintain balance automatically. When a node fills up, it splits: roughly half the keys go left, half go right, and the median key is pushed up to the parent. This can cascade up to the root, but it’s bounded and predictable.

Deletions can trigger the inverse: if a node drops below the minimum fill threshold (typically half capacity), it can absorb a sibling or redistribute keys. In practice, many production systems skip aggressive merging and allow underflowed pages, running periodic compaction instead. PostgreSQL’s VACUUM takes this approach—it’s cheaper to tolerate some fragmentation than to maintain perfect fill ratios on every delete.

The write amplification of B-trees is real. Each insert may rewrite an entire page even if only one key changed. This is the core argument for LSM trees in write-heavy workloads: LSM trees append to immutable structures and defer the cost to read time. B-trees pay at write time, which suits read-heavy workloads well.

Why Nothing Has Replaced Them

Learned indexes, which substitute the B-tree’s hierarchical structure with a model that predicts record positions directly, have shown promise in research. Fractal tree indexes reduce write amplification by buffering changes in internal nodes. Neither has displaced B-trees in mainstream databases.

The reason is operational: B-trees are predictable. Their worst-case behavior is well understood. They perform adequately across a wide range of workloads without tuning. And decades of engineering have hardened B-tree implementations against edge cases—concurrent access patterns, crash recovery tied into write-ahead logging, careful handling of page splits under contention.

When a newer index structure outperforms a B-tree on a narrow benchmark, it typically trades away the generality that makes B-trees useful as a default. Committing to a specialized structure means knowing your workload precisely and staying committed to that characterization over the system’s lifetime. B-trees work well enough across enough situations that you don’t have to make that bet—which is exactly why they’ve outlasted so many proposed successors.