LESSON 26.1
B-trees
The structure behind almost every relational index. Pages and fan-out, how lookups and range scans work, how writes stay durable with a write-ahead log, and what page splits cost.
7 min read
B-trees have been the default on-disk index for over 50 years. PostgreSQL, MySQL's InnoDB, SQL Server, Oracle and SQLite all use them. Understanding them explains why indexes speed up reads, slow down writes, and why some key choices are much cheaper than others.
Pages and fan-out
A B-tree (strictly, a B+ tree in most databases) stores keys in fixed-size pages, typically 4–16 KB (8 KB in Postgres, 16 KB in InnoDB).
- Leaf pages hold keys in sorted order, with the row or a pointer to it. Leaves are linked to their neighbors for fast range scans.
- Internal pages hold separator keys and pointers to child pages. A page holds hundreds of entries, so the tree is very wide and very shallow.
- A lookup starts at the root and follows one pointer per level down to a leaf.
- Fan-out per page
- ~100–500
- Levels for 1 billion keys
- ~4
- Pages read per lookupupper levels stay in memory
- ~4, usually 1–2 from disk
- Range scan
- find the first leaf, then follow sibling links
Writes
- Find the leaf where the key belongs.
- Append a record of the change to the write-ahead log (WAL) and flush it. Now the change is durable.
- Modify the page in memory (the buffer pool); it's written back to disk later, during checkpoints.
- If the leaf is full, split it into two half-full pages and add a separator to the parent, which may split in turn.
Because pages are updated in place, a B-tree always has exactly one current location for each key. That makes reads simple and predictable, and it's why B-trees suit transactions: locks can be taken on keys and ranges.
Costs to know
- Write amplification. Changing a 100-byte row can mean writing an 8 KB page, plus the WAL record, plus a full-page image after each checkpoint in some databases.
- Random I/O. Inserts with random keys touch pages all over the tree. Increasing keys (sequence ids, time-ordered ids like UUIDv7 or ULID) keep inserts on the rightmost pages, which stay in memory.
- Fragmentation. Splits leave pages half full; deletes leave gaps. Space is reclaimed by vacuuming or rebuilding.
- Every index is another tree. A table with five indexes does at least six tree updates per insert.
Indexes in practice
Clustered (InnoDB primary key)
- Rows stored in key order in the leaves
- Range scans on the key are sequential
- Secondary indexes point to the primary key, adding a second lookup
Pick it when: MySQL tables; choose a compact, increasing key.
Heap + separate indexes (Postgres)
- Any index points straight to the row location
- Rows aren't in index order
- Updates may touch every index
Pick it when: Postgres tables; covering indexes avoid heap reads.
Composite index (a, b)
- Serves filters on a, or a and b, and sorting by b within a
- Doesn't help filters on b alone
Pick it when: Queries with a fixed leading column.
Try it
URL Shortener HLD
Choose keys and indexes for a high-traffic lookup table.