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.
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. 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.
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. 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.