Semicolony home
Search guides and simulators ⌘K
II · Trees, with shape

B-tree / B+ tree

The shape of a database index.

Main article: B-tree simulator and visualizer

1970 · Rudolf Bayer & Edward McCreight · Boeing
The story

Designed at Boeing Scientific Research Labs to keep an index page-resident on disk. The paper first appeared as a Boeing report in 1970 and was published in Acta Informatica in 1972. The authors never said what the "B" stands for; Bayer, balanced, Boeing and broad have all been suggested. Most relational databases now use a B+ tree variant for their indexes.

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; embedded key-value stores such as LMDB and BoltDB. File systems: NTFS, HFS+, APFS, Btrfs, XFS, and the HTree directory index in ext4.

The key insight

A B-tree is built for data that lives on disk, where each read fetches a whole page. A balanced binary tree over 100 million keys is about 27 levels deep; a B+ tree with 200 keys per node needs 4. That is the difference between 27 page reads and 4, and the top levels are usually cached, so most lookups touch only one or two pages on disk.

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 Set membership in a few bits per item. 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

Published