B-Tree and B+ Tree

The B-tree, invented by Rudolf Bayer and Edward McCreight at Boeing Research Labs in 1972, is a self-balancing tree data structure designed specifically for systems that read and write large blocks of data. Unlike binary search trees where each node holds a single key, a B-tree node holds dozens to hundreds of keys sorted in order, with child pointers between them. This high fanout -- typically 100 to 500 children per node -- means that even billions of keys can be indexed in a tree just 3 or 4 levels deep. Every lookup, insertion, or deletion touches at most one node per level, yielding O(log n) performance with a very small constant factor in practice.

The page-oriented design of B-trees is what makes them the natural choice for databases. Operating systems and storage devices transfer data in fixed-size pages (commonly 4KB, 8KB, or 16KB). A B-tree node is sized to match exactly one page, so each node read or write corresponds to a single I/O operation. When a node overflows during insertion (exceeds the maximum number of keys), it splits into two nodes and propagates a median key up to the parent. When a node underflows during deletion, it merges with a sibling. These operations maintain the tree's balance guarantee: all leaf nodes are always at the same depth, ensuring consistent performance regardless of data distribution or insertion order.

The B+ tree variant, used by nearly every production database including PostgreSQL, MySQL InnoDB, and SQLite, refines the original B-tree design in two critical ways. First, data records (or pointers to data records) are stored only in leaf nodes; internal nodes contain only keys and child pointers. This maximizes the fanout of internal nodes because they do not waste space on data payloads, reducing tree height and therefore the number of I/O operations per lookup. Second, leaf nodes are linked together in a doubly-linked list, enabling efficient range scans -- once you find the starting key, you simply follow the leaf chain without revisiting internal nodes. This makes B+ trees excellent for queries with ORDER BY, BETWEEN, and inequality predicates.

Write amplification is the primary cost of B-tree-based storage. Every modification to a key potentially requires rewriting the entire page containing that key, plus any parent pages that need updating during splits. In the worst case, an insertion that triggers splits all the way to the root requires rewriting one page per tree level -- typically 3-4 pages. Database engines mitigate this through buffer pools (caching hot pages in memory), write-ahead logging (batching modifications), and delayed page splits. Despite this write overhead, B-trees remain the dominant index structure for read-heavy and mixed workloads because their read performance -- a single root-to-leaf traversal -- is extremely difficult to beat.

Imagine a library with 10 million books. The card catalog has a master index with 26 drawers labeled A-Z. Inside each drawer, divider cards split the space into finer ranges (Aa-Am, An-Az, etc.). Behind each divider are cards pointing to even more specific sub-ranges, until you reach the individual book cards at the bottom level. To find any book, you open at most 3-4 drawers/dividers -- you never scan all 10 million cards. This is exactly how a B+ tree works: internal nodes are the dividers (they only contain keys for navigation), leaf nodes are the actual book cards (they contain the data), and the leaves are linked together so you can flip through them in order for browsing by author or title.