keys
0
Lesson 02 · The read-optimized workhorse
B-tree mechanics: splits, fill factor, and the UUID tax
The field guide showed the B-tree from the outside: a sorted, shallow tree reaching any key in a handful of page hops. This lesson goes inside: because the interesting behavior (and the production incidents) live in what happens on insert, when a page runs out of room. One rule generates everything: keys must stay sorted, and each node is one fixed-size page. When a page is full and a key must land in it, the page splits: half the keys move to a new page, and the parent gains a separator. Do it yourself:
Grow a tree by hand
Insert keys, cause splits, raise the roof
A tiny B-tree: max 4 keys per page. Insert in the given order and watch for the two big events: a leaf split and: when splits cascade to the root: the tree gaining a level.
pages
1
height
1
splits so far
0
Notice the economics of what you built. Splits are rare: most inserts land in a page with room: but each one costs three page writes (two halves + parent) and, over time, determines the tree's shape. And the tree got taller only when the root itself split: height grows logarithmically, which is the entire read-side promise. Real trees have ~200–400 keys per page, so height 3–4 covers millions to billions of rows. Now for where insert order becomes destiny:
The experiment every DBA has run: sequential vs random keys
Load 1,000 rows with two primary key strategies
Same rows, same tree. Left button: auto-increment ids (1, 2, 3, ...). Right: UUIDs (uniform random). Watch where inserts land, how full pages end up, and how much of the tree each workload keeps hot.
pages created
:
avg fill factor
:
pages touched by inserts
:
cache behavior
:
:
The mechanism, spelled out: sequential keys mean every insert lands on the rightmost leaf: one hot page in cache, filled to 100%, split cleanly when full (engines even special-case this: a rightmost split leaves the old page full instead of half). Random keys land anywhere: every page is an insert target, so the whole index is the working set (Lesson 1's buffer pool weeps), pages hover near half-full after splits (~50–70% fill), and the same row count needs ~40% more pages: which also means ~40% more pages for every range read forever after. This is the "UUID tax," and it's why UUIDv7 (time-ordered UUIDs) exists: globally unique and roughly sequential: the fix that keeps both properties.
Clustered vs secondary: where the row actually lives
InnoDB / SQL Server (clustered): the PK B-tree's leaves ARE the rows.
secondary index leaf: (email) → PK value → second B-tree descent
PostgreSQL (heap tables): all indexes are secondary.
index leaf: (email) → (page #, item #) directly into the heap
Two consequences worth carrying: in clustered designs, the primary key choice is the physical row order: the UUID tax above hits the whole table, not just an index, and every secondary lookup pays two tree descents (so fat PKs bloat every index). In heap designs, updates that move a row must update every index... unless the engine can pull a trick: PostgreSQL's HOT (heap-only tuple) updates keep the new version in the same page precisely to skip index maintenance, which is why leaving free space per page (fillfactor 90) on update-heavy tables is a real tuning lever. Fill factor: the same dial, turned deliberately.
Range scans, the B-tree's other superpower: leaves are linked left-to-right, so BETWEEN, ORDER BY ... LIMIT, and prefix matches are one descent plus a sequential walk along the leaf chain: the access pattern Lesson 1's page economics love most. This is exactly what hashing gave up (field guide, lesson 2), and it's why "B-tree" is the default index type everywhere: it's the only structure that's decent at everything: point reads, ranges, sorted output, uniqueness enforcement: while LSM (next lesson) beats it at precisely one thing, and pays for it.
Check yourself
1. A B-tree of height 3 holds 50M keys. After doubling to 100M keys, how does point-lookup cost change?
Height grows with log₃₀₀(n): heights 1→2→3→4 cover roughly 300 → 90k → 27M → 8B keys. Doubling within a tier costs nothing; crossing a tier adds one page read (and the upper levels are essentially always cached, so even that is nearly free). This absorption is why B-tree reads feel scale-proof: and why the pain concentrates on the write side instead.
2. A high-insert table with a random-UUID primary key (InnoDB, clustered) shows: buffer pool churn, ~55% average page fill, and insert throughput degrading as the table grows. Which change fixes all three at once, and why?
All three symptoms are one disease: uniform-random insert targets. Time-ordering the key collapses the insert working set from O(all pages) to O(1). More indexes multiply the write cost (each is another tree to maintain); bigger pages just make each random touch more expensive. The lab's two buttons, as a production decision.
3. In a clustered-index engine, why does choosing a 36-byte string UUID primary key make every other index on the table bigger and slower?
The clustered design's hidden coupling: the PK is the address, and every secondary index is a book of addresses. PK width is thus multiplied across the entire index set: one of those decisions that looks free in the schema review and costs a fleet of RAM two years later. (PostgreSQL's heap design dodges this particular coupling; its pointers are fixed-size TIDs.)