B-tree
Searching a billion sorted keys one comparison at a time is thirty steps, and if every step is a read from disk then a lookup is thirty reads. The B-tree does not search more cleverly. It makes the node wider: hundreds of keys in the block you were going to fetch anyway, so the same billion rows sit four levels down instead of thirty. Everything here is arithmetic on that one idea, and every number is computed rather than quoted.
New to disk-based indexes? Start here
Reading from a disk is not like reading from memory. You cannot usefully fetch one byte: a block device deals in sectors and an index manager organises them into a page, a few kilobytes, and the cost is almost entirely in making the trip rather than in how much comes back. A structure stored on a disk is therefore judged on one number -- how many trips a lookup takes.
That is why the tree you were taught is the wrong shape here. A binary tree asks one yes-or-no question per node, so it needs about thirty of them to narrow down a billion things, and thirty trips is a disaster.
A B-tree keeps the same idea and changes one parameter: put hundreds of keys in each node instead of one, so a single trip narrows the search hundreds of times over instead of twice. Nothing about the searching is cleverer. The node just got wider.
Fast and forgetful, or slow and permanent
Memory is quick and loses everything when the power goes. A disk keeps what it was given and is slower by a factor with several zeroes in it. Parts that are both do exist and none has been cheap or plentiful: battery-backed memory modules are still made, and the fastest persistent part on the market was discontinued.
So nearly every design in this topic is buying one with the other. Keep it in the fast part and you are quick until the lights go out. Write it to the slow part first and you are safe but waiting. The machines here are the arrangements people found in between, and each of them is honest about which half it gave up.
The machine for this idea on its own is Write-Ahead Log, if you would rather press it than read about it.
Depth, fanout, and why a wider node beats a cleverer search
1 A billion rows, and the depth a binary tree would need for them
A tree holding one key per node has to be about thirty levels deep to hold a billion of them, because each level only doubles what the last one held. Nothing is wrong with that until you notice that each level is a separate read.
- rows to index
- 1,000,000,000
- levels, one key per node
- 30
- reads to find one row
- 30 reads
2 Fanout: how many keys fit in one page of disk
A disk does not hand you a key, it hands you a page. So the question is not how clever the search is, it is how many keys fit in the page you were going to read anyway. That number is the fanout, and it is the whole machine.
- keys per page
- 340 keys
- the arithmetic
- 8 KiB less a header and one pointer, divided by 16 and 8
3 The same billion rows, four reads deep
With that fanout every level multiplies rather than doubles. Here is each level and how many rows it can reach, until one of them reaches a billion.
| level | nodes | rows it can reach |
|---|---|---|
| 1 | 1 | 340 |
| 2 | 340 | 115,600 |
| 3 | 115,600 | 39,304,000 |
| 4 | 39,304,000 | 13,363,360,000 — reaches a billion |
- levels needed
- 4
- reads to find one row
- 4 reads
- reads saved against one key per node
- 26
4 Raise the fanout and watch the tree refuse to get taller
Drag the page size up and the tree gets shorter, and then stops getting shorter. That is the part worth taking away: depth is a logarithm, so doubling the fanout does not halve the depth, it removes at most one level at the already-large fanouts here. Fanout is enormously worth having and very quickly stops being worth more.
At 8 KiB a page and 16 bytes a key, 340 keys fit in one page, so 1,000,000,000 rows are 4 levels deep instead of 30. That is 26 fewer reads. Doubling the page from here removes at most one more level, because depth is a logarithm and the base is the only thing you are changing.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| a billion rows are 4 reads deep with an 8 KiB page and a 16 byte key | yes | fanout 340, and 340 to the 4 exceeds a billion |
| counting levels by multiplication agrees: 4 | yes | multiplying the fanout up reaches 1.336e+10 at level 4 |
| a binary tree over the same billion rows is 30 levels, not 4 | yes | one key per node against 340, which is the entire difference |
| doubling the page to 16 KiB doubles the fanout to 681 | yes | the node is the unit of I/O, so a wider node is free depth |
| at 4 KiB the same billion rows are 5 deep, so the headline depends on the page size | yes | fanout 169 at 4 KiB against 340 at 8, and Postgres uses 8 |
| every one of the 4 levels is listed, and the first to hold a billion is level 4 | yes | L1 3.4e+2, L2 1.2e+5, L3 3.9e+7, L4 1.3e+10 |
What is real here, and what is not
The fanout here is arithmetic, not a measurement of any database
A page holds a header, n keys and n+1 pointers, and this divides what is left by the size of one key and one pointer. The number printed above is therefore KEYS per page, and the branching factor is one more than it: a node holding 340 keys has 341 children, which is what Bayer and McCreight say. The levels below are counted with the key figure, which understates capacity slightly and is deliberate: four levels holds a billion rows either way, and the conservative number is the one worth printing. Real implementations differ: they compress keys, they store variable-length keys, they leave slack for inserts, and they keep the root and often the level below it in memory. Those change the number. None of them changes the shape, which is that depth is a logarithm of the row count in a base you get to choose.
Reads are counted as one per level, which is the pessimistic case
In practice the root is almost always already in memory and so is much of the level beneath it, so a lookup against a warm cache costs fewer disk reads than the depth suggests. This counts levels rather than pretending to model a buffer pool, and says so here rather than quietly subtracting.
Nothing here inserts, splits or rebalances
The B-tree's real difficulty is staying balanced while rows arrive and leave, which is what most of Bayer and McCreight is about. This page is about the shape a balanced one has, and it shows no splits at all.