B-trees and the cost of a split
Everyone can draw a B-tree. Almost nobody can say what one insert actually costs, or why an index built from sorted keys wastes a third more space than the same index built from shuffled ones.
The B-tree is the most-drawn data structure in computing and one of the least understood past the picture. Everybody can sketch the boxes and the arrows. Far fewer people can answer the two questions that decide whether an index is fast or a liability: what does a single insert cost, and how much of the space you paid for is actually holding data.
Both answers are uncomfortable, and one of them is the opposite of what almost everyone guesses.[1]paperOrganization and Maintenance of Large Ordered Indexes
It grows from the top
A B+tree stores keys in pages. Every page holds up to fanout keys; leaves hold the data,
and interior pages hold only separators pointing at children.
Inserting means descending to the right leaf and putting the key in it. If that overflows the page, the page splits: half the keys move to a new sibling, and a separator is pushed up to the parent. If the parent overflows, it splits too, and so on upward.
The important consequence is what happens when the root splits. A new root is created above it, and every leaf becomes one level deeper simultaneously. That is the only way a B-tree ever gets taller, and it is why all leaves are always at the same depth - a property the widget checks on every single tick rather than asserting.
Height stays absurdly small. With 64 keys per page, a few thousand keys fit in three levels - and since real indexes use pages holding hundreds of keys, a billion-row table is still only four or five pages deep. This is the entire reason B-trees won: the height is set by the logarithm, and the base of that logarithm is however many keys you can fit in one disk page.[2]paperThe Ubiquitous B-Tree
A third of your index is empty
Here is the first uncomfortable number. Insert keys in random order, let the tree settle, and the pages end up about 69% full.
That is not an implementation detail or a tuning failure. It is ln 2, and it is what a B-tree converges to under random insertion - a result Yao proved for B-trees of arbitrary order, and which Comer’s survey records as the expected storage utilization.[2]paperThe Ubiquitous B-Tree
The mechanism is straightforward once you see it. A split leaves two pages each half full. Those pages then refill toward full before splitting again. Averaged over the life of the tree, pages sit between half full and full, and the average lands at ln 2 rather than at the 75% you might guess from splitting the difference.
Sorted input makes it worse
Now the part that catches people out.
If random insertion gives 69%, sorted insertion should surely be tidier - every key arrives in order, pages fill neatly left to right, nothing is wasted. That is the intuition, and it is exactly backwards.
Switch the widget’s insert order to sequential and utilization drops to 50%.
The reason is that every key now lands in the rightmost leaf. That leaf splits, and the left half - half full - is never touched again, because every subsequent key is larger than everything in it. The tree becomes a trail of abandoned half-empty pages behind a single active one.
In our runs at sixteen keys per page, the same 4000 keys took 395 pages inserted randomly and 561 inserted in order: 42% more space for identical data.
What one insert really costs
The second uncomfortable number is write amplification: pages actually written per key you asked to store.
It is never 1. Every insert rewrites its leaf, and every split additionally writes a new
sibling and updates a parent. In steady state a leaf splits roughly once every fanout/2
inserts, which gives a first-order estimate:
write amplification ≈ 1 + 4 / fanoutMeasured, at 4000 random keys: 2.40× at four keys per page, 1.29× at sixteen, 1.07× at sixty-four. Bigger pages amortise splits over more inserts, so amplification falls toward 1 - which is a large part of why real page sizes are kilobytes rather than bytes.
Against an LSM tree
This is the comparison the RUM conjecture is really about, and it is worth seeing under one slider rather than as two paragraphs of adjectives.
A B-tree writes in place: find the page, rewrite the page. An LSM tree appends and sorts it out later. That single difference is most of what separates the two families of storage engine.
B+tree
Writes in place: find the page, rewrite the page. Sixteen keys per page.
LSM tree
Appends, then rewrites in the background. Leveled compaction, fanout 4, three levels.
| Measure | B+tree | LSM tree | Gap |
|---|---|---|---|
| Write amplification | 1.28 | 5.59 | 4.4× |
Keys offered per tick.
What to remember
Three things are worth carrying into your next storage decision.
Height is logarithmic in the page fanout, so it is always small and almost never the problem. Space utilization is about 69% under random writes and 50% under sorted ones, which is a real capacity-planning number rather than trivia. And a logical insert is never one physical write, which is the thing that connects a B-tree to every other storage decision you will make.
The dial
The line - when someone asks
A B+tree keeps every key sorted across leaves that all sit at the same depth, and it grows only by splitting its root - which is why height stays at three or four even for billions of keys. The costs people forget are that one logical insert rewrites at least one page and occasionally a cascade of them, and that random insertion leaves pages only ln 2 - about 69% - full. Load the same keys in sorted order and it gets worse rather than better: splits then happen only at the rightmost page, the left half is abandoned half full and never revisited, and utilization settles at 50%.
Recall
Loading…
Where are you with this?
Saved on this device. Sign in to keep it across devices.
Sources
Primary
- [1]
- [2]
- [3]