B-trees

In 1970, two Boeing researchers — Rudolf Bayer and Edward McCreight — were thinking about magnetic disks. Disks were slow. Every access needed a seek — the read head physically moving to the right track — costing 10-20ms. Memory was tiny. To index a large data set on disk, you needed a data structure that would let you find any record with as few disk seeks as possible.

Their answer: a tree structure where every node holds many keys, not just one or two. Each disk block became a tree node. A single seek loaded 100 keys instead of one. The tree grew wide instead of tall — a database of 1 billion rows needed only 4-5 seeks to reach any record. Bayer and McCreight called it the B-tree.

54 years later, the B-tree still runs the world. Every serious relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite, LMDB — stores its indexes as B-trees (or the closely-related B+tree variant). Every unique constraint, every foreign key check, every ORDER BY, every WHERE clause on an indexed column ultimately walks a B-tree. If you understand one on-disk data structure deeply, make it this one.

The insight — wide nodes, shallow tree

A binary tree is the wrong shape for disk. A perfectly balanced binary tree with 1 billion keys is 30 levels deep. Fetching a key means 30 seeks — 30 × 10ms = 300ms. Unacceptable. The B-tree solves this by putting many keys per node (typically 100-500 keys per 8 KB page). With 200 keys per node, 1 billion records fits in ⌈log₂₀₀(10⁹)⌉ ≈ 4 levels. Total: 4 seeks. That's the difference between a database and a toy.

The nodes are disk blocks — the smallest unit the OS reads from or writes to the disk. Standard block size is 4 KB or 8 KB. Every node access = one block read = one disk seek. The database keeps a small buffer pool of recently-used nodes in memory (Postgres's shared_buffers, InnoDB's buffer pool) so hot nodes stay hot. The root and top levels stay cached always; only leaves might miss.

Interactive: walk a B-tree search

A B-tree search is trivially simple. Start at root. Compare target key to node's separators. Pick the right child. Recurse until you hit a leaf. Watch it live:

The magic — how inserts stay balanced

The hard part isn't search. It's inserts. If every insert appends to the same leaf, the tree becomes a list and search degrades to O(N). B-trees stay balanced through one rule: when a node gets full, split it into two and push the middle key up to the parent. If the parent overflows, split it too, recursively.

The tree grows in height only when the root splits. This means the tree stays balanced automatically — no manual rebalancing, no O(N log N) worst case. Every insert, delete, or search costs O(log_M N) where M is the fanout. In practice for real databases, that's 4-6 disk seeks worst case, even for petabyte databases.

B+tree — the variant everyone actually uses

Real databases don't use plain B-trees. They use B+trees, a small but critical modification:

• Internal nodes store only keys (used to guide the search).
• Leaf nodes store all the data (or pointers to data rows).
• Leaves are linked together in a doubly-linked list — so scanning "all records in order" is a single linear walk without going back up the tree.

This is a massive win for range queries. SELECT * FROM users WHERE age BETWEEN 25 AND 40: find 25 in the leaves (O(log N) seeks), then just walk right until you pass 40. A million-row range scan reads sequentially from disk — orders of magnitude faster than random access.

Concurrency — the tricky part

With one thread it's simple. In production, hundreds of connections read and write concurrently. Two threads can't both split the same node — corruption. The classical solution: latch coupling. Acquire a lock on the root, descend to child, release the parent lock, acquire the child lock, and so on. If the child needs to split, upgrade back up the tree.

Modern databases use fancier techniques — optimistic latching, Blink-trees (Lehman & Yao 1981) that allow lock-free reads, copy-on-write B-trees (LMDB) that write new pages instead of modifying in place. The details matter for databases at high concurrency; for the mental model, know that B-tree implementations are highly optimized for parallel access.

B-tree vs LSM-tree — the fundamental storage-engine choice

The trade-off is stark. B-trees are read-optimized: point lookups and range scans are cheap. Writes are expensive because they require in-place page updates and journal writes for durability. LSM-trees flip it: writes are cheap (append to a log-structured memtable, flush sequentially), reads are more expensive (may need to check multiple SSTables). Pick B-tree for read-heavy OLTP, LSM for write-heavy workloads.

Applied in real systems

Key takeaways

• B-tree = wide, shallow, self-balancing tree designed for block-based disk storage. 4-6 levels for billion-row datasets.
• Every relational database uses B+trees (Postgres, MySQL, Oracle, SQL Server, SQLite, LMDB) for indexes. 54 years old, still winning.
• B+tree vs B-tree: B+ stores data only in leaves + links leaves in a list. Makes range scans a linear walk. Always the practical choice.
• Node size = disk block size (typically 8 KB). Each seek fetches ~200-500 keys. Trade-off: bigger blocks = shallower tree but more wasted read for point lookups.
• Inserts stay balanced via node splitting. The tree grows in height only when the root splits. O(log N) guaranteed.
• Concurrency is hard. Latch coupling, Blink- trees, copy-on-write are the industrial techniques. Modern databases are highly optimized.
• B-tree vs LSM-tree is the fundamental storage-engine choice: read-optimized (B+tree) vs write- optimized (LSM). Pick based on workload.

References

• Bayer & McCreight (1972) — Organization and Maintenance of Large Ordered Indices. Acta Informatica.
• Comer (1979) — The Ubiquitous B-tree. ACM Computing Surveys.
• Lehman & Yao (1981) — Efficient Locking for Concurrent Operations on B-trees (Blink-trees).
• Graefe (2011) — Modern B-tree Techniques. Foundations and Trends in Databases.
• Kleppmann (2017) — Designing Data-Intensive Applications, Chapter 3.
• Petrov (2019) — Database Internals. Chapter 2 has the best modern treatment.