Search tools and guides ⌘K
II · Trees, with shape

B-tree / B+ tree

The shape of a database index.

1971 · Rudolf Bayer & Edward McCreight · Boeing
The story

Designed at Boeing Scientific Research Labs to keep an index page-resident on disk. The "B" stands for nothing definitive: Bayer, balanced, Boeing, broad. Bayer himself never said. Every relational database since uses a B+tree variant. SQLite's author Richard Hipp once said: "B-trees are the only data structure that matters."

How it works

Each node holds many keys (typically 100–500), all leaves at the same depth. The fan-out keeps the tree shallow — billions of records in just 4 levels. B+trees push all data to leaves and link them, so range scans are sequential disk reads.

Where it lives

PostgreSQL, MySQL InnoDB, SQLite, Oracle, SQL Server, every B-tree-based KV store. Filesystems: ext4 HTree, NTFS, HFS+, BTRFS, ReFS, ZFS.

The key insight

When your index doesn't fit in RAM, only B-trees stay sane. A 100-million-row index is 20 levels deep in a binary tree; 4 levels in a B+tree with fanout 200. That's the difference between 20 disk seeks and 4.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
III Consistent hashing Hashing that survives node changes. III Perfect hashing Zero collisions, by design. IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted.
← All data structures