4.3 B-Trees
Introduced 1970; called "ubiquitous" less than 10 years later. They remain the standard index implementation in almost all relational databases, and many nonrelational ones.
Similarity to SSTables: keys sorted → efficient key-value lookups and range queries. Where it ends: very different design philosophy.
| Log-structured | B-tree | |
|---|---|---|
| Unit | variable-size segments, several MB+ | fixed-size blocks or pages |
| Mutability | written once, then immutable | may overwrite a page in place |
| Page size | — | traditionally 4 KiB; PostgreSQL uses 8 KiB, MySQL 16 KiB |
Pages reference each other by page number — like a pointer, but on disk. If all pages are in one file, page number × page size = byte offset.
3.1 The lookup
Branching factor = number of child-page references in one page. Typically several hundred (it depends on the space needed for page references and range boundaries).
The tree stays balanced: a B-tree with n keys always has depth O(log n). Most databases fit in a B-tree three or four levels deep.
Worked example from the book: a four-level tree of 4 KiB pages with branching factor 500 stores up to 500⁴ × 4 KiB ≈ 250 TB.
(This structure is technically a B+ tree, but the book doesn't distinguish it from other B-tree variants.)
3.2 Writes and page splits
- Update an existing key: find the leaf page containing it, overwrite that page on disk with a version containing the new value.
- Add a new key: find the page whose range encompasses it and add it. If there isn't enough free space, split the page into two half-full pages and update the parent to account for the new subdivision.
Deleting keys (which may require nodes to be merged) is more complex.
3.3 Making B-trees reliable
The basic write operation is to OVERWRITE A PAGE ON DISK. It's assumed the overwrite doesn't change the page's location, so all references to it remain intact. This is in stark contrast to LSM-trees, which only append and eventually delete, never modifying files in place.
Two ways this goes wrong:
| Failure | Result |
|---|---|
| Crash mid-split (several pages must be written at once) | Corrupted tree — e.g. an orphan page that is not a child of any parent |
| Hardware can't atomically write an entire page | Torn page — partially written |
The fix: a write-ahead log (WAL). An append-only file to which every B-tree modification must be written BEFORE it is applied to the tree pages. On restart after a crash, the log restores the B-tree to a consistent state. (In filesystems the equivalent is called journaling.)
Performance interaction: implementations don't immediately write every modified page to disk — they buffer pages in memory first. The WAL is what makes that safe. As long as data has been written to the WAL and flushed with fsync, it will be durable.
3.4 B-tree variants worth knowing
| Variant | Idea |
|---|---|
| Copy-on-write (LMDB) | Instead of overwriting + WAL, write the modified page to a different location and create a new version of the parent pages pointing at it. Also useful for concurrency control (→ snapshot isolation, Ch 8) |
| Key abbreviation | Don't store the entire key. Interior keys need only enough information to act as boundaries between ranges. Packing more keys per page → higher branching factor → fewer levels |
| Sequential leaf layout | Lay out leaf pages in sequential order on disk to speed up range scans and reduce seeks. Difficult to maintain as the tree grows |
| Sibling pointers | Each leaf page references its left and right siblings, so you can scan keys in order without jumping back to parent pages |