A tree with nodes the size of a block

A binary search tree makes one comparison per level and descends one level per comparison. That is the whole of its design, it is optimal in comparisons, and it is the structure this site measured in the tree that is a list.

It also touches one node per level, each node is somewhere unrelated to the last, and in the model of one access, eight kilobytes that means one transfer per level. Over four million keys that is 22 transfers to find one.

A B-tree asks a different question. Not how few comparisons but how few transfers, and since a transfer moves B elements whether or not they are wanted, the answer is to want them: make the node exactly one block, put B−1 keys in it, and resolve log₂ B comparisons for the price of one transfer.

The fanout is not a taste #

Textbook treatments of the B-tree usually introduce a parameter t, the minimum degree, and leave it abstract. That is the right thing to do for a proof and it hides the only interesting fact about the structure: t is not chosen for balance, it is read off the hardware.

A node is one block. If the block is 4 kilobytes and a key with its child pointer is 16 bytes, the node holds 256 of them, and the fanout is 256 because that is what fits. Change the page size and the fanout changes; the algorithm did not change and its complexity class did.

That is the phase’s second theme — the model has parameters — in its most direct form. Every other structure on this site has a shape decided by its own logic: a heap is binary because sift-down is, a skip list’s height distribution comes from a coin. A B-tree’s shape is decided by a number in a datasheet.

The consequence is a base change in a logarithm, and it is worth writing the arithmetic out because the sizes involved make it look like a mistake. Over four million keys:

Twenty-two transfers become three. Nothing about the number of keys changed and nothing about the comparisons being made changed very much — the B-tree still performs about log₂ n key comparisons in total, because a search inside a node is itself a binary search. All that changed is how many of those comparisons share a transfer.

The measured cost is below the height, and that is not a rounding #

The interesting column in the figure is not the height, it is the gap between the height and what a search actually paid: 3 levels and 1.01 transfers at B = 1024, 4 and 1.99 at B = 64.

The reason is the shape of the tree. A B-tree over n keys at fanout B has n/B leaves, n/B² nodes above them, and so on: the level sizes fall geometrically, so the whole top of the tree is tiny. At B = 1024 over four million keys there are 4,096 leaves, four nodes above them and a root: the whole tree above the leaves is five blocks, in a memory holding 64. It never leaves, and only the leaf is ever fetched.

There is a second reason the measured column is what it is, and it is the reason the figure averages over 200 queries rather than reporting one. A single cold search pays the full height; the second search pays less because the first left the top of the tree behind it; and by the twentieth the internal nodes are all resident and every query costs exactly one transfer for its leaf. The average over 200 is therefore dominated by the steady state and reports very nearly the leaf cost alone, which is the right thing to report for an index that serves queries continuously and the wrong thing for one queried once.

Which number is correct depends on the workload rather than on the structure, and quoting either without saying which was measured is the omission this site keeps finding in benchmarks.

That is why a database’s index is described as “warm” and why the first query after a restart is slow in a way that has nothing to do with the algorithm. It is also a case where the measurement disagrees with the derivation in the direction of being better, which is rarer than the reverse and is worth pausing on: the derived cost is the height, the measured cost is the height minus however many levels fit in memory, and the second is the one a user experiences.

Against binary search, honestly #

The comparison this essay exists to make is not flattering to the B-tree in every column, and the site’s habit is to print the column where it loses.

Binary search over a sorted array of four million keys performs 22 comparisons. The B-tree at fanout 1024 performs about 30: ten per level for the internal binary search within each node, over three levels. It does more comparison work, and by the counter this site used for its first three phases it is the worse algorithm.

It moves an eighth of the data.

Two counters, opposite rankings, and neither of them is wrong. This is the fourth time that sentence has been the point of an essay here — after one run, two counts, the frontier between time and space and the branch the machine guesses — and the reason it keeps recurring is that a single quantity called “the running time” does not exist. There is a vector of resources, and which component dominates is a fact about the machine and the data size, not about the algorithm.

The B-tree also spends space the array does not: internal nodes are pure overhead, about 1/B of the data at each level, so a fanout of 256 costs under half a percent. That is the space-is-the-other-axis thread’s accounting, and here it is a rounding error, which is itself informative — the structure that wins on transfers does not pay for it in slots.

What the fanout costs at the other end #

Raising the fanout cannot be free or every tree would have a fanout of a million, and the figure shows where it stops paying: between B = 256 and B = 1024 the height does not move at all. Both are 3.

The reason is that the height is ⌈log_B n⌉ and a logarithm’s base buys progressively less. Going from 2 to 16 removes sixteen levels; from 16 to 64 removes two; from 256 to 1024 removes none, and the whole benefit of the last step is the 0.29 transfers the resident set gains. Meanwhile the cost inside the node rises: a search within a node of 1,024 keys is ten comparisons rather than eight, and if the node search is linear rather than binary — which it is in several real implementations, because a linear scan of a cached page is fast and simple — the internal cost rises linearly in B while the height falls logarithmically.

So there is an optimum, it is not at either end, and it is not derivable from the algorithm. It is where the block size lands, which is why real fanouts cluster around a few hundred: that is what a 4-kilobyte or 16-kilobyte page holds. A parameter chosen by a filesystem in the 1980s is still the reason the structure has the shape it has, which is the threshold is the algorithm thread from the practice phase, arriving from a completely different direction. There, a constant somebody typed decided a library sort’s behaviour. Here a constant nobody typed — it came from the hardware — decides a structure’s complexity class.

The two effects also interact in a way worth naming. A larger node means fewer levels resident for the same memory, because the resident count is M/B: at B = 1024 the memory holds 64 blocks, at B = 64 it holds 1,024. The wide tree keeps fewer nodes and needs fewer; the narrow tree keeps more and needs more. Those two very nearly cancel over the range measured here, and that near-cancellation is why the measured column falls so much more smoothly than the height column does.

What a B-tree is not, and the two properties that are missing here #

Everything above measures searching a static tree, and a real B-tree is defined by what it does when the data changes: nodes split when they overflow and merge when they underflow, and the invariant that every node other than the root is at least half full is what makes the height bound a guarantee rather than a hope. None of that is measured here.

That is a deliberate boundary and it is worth being explicit about, because it is the same boundary the probe formula nobody checks drew for hash tables: this site measures structures under construction and lookup, and not under a lifecycle of mixed operations over time. A structure’s behaviour under a workload — inserts interleaved with deletes and queries, over hours, with the shape of the data drifting — is a different subject with a different instrument, and it is where storage engines in real systems actually spend their difficulty.

What can be said with the instrument here is the half that the splitting exists to protect: the height, the fanout, and the transfers a search of a tree of that shape costs. The writes nobody counted takes the other half as far as this model honestly reaches, which is to insertion cost and no further.

The second missing property is the one every implementation has and no analysis mentions. A real B-tree stores keys in the internal nodes and records only in the leaves — a B⁺-tree — and links the leaves together, so a range scan walks the leaf list sequentially at n/B rather than descending the tree once per key. A range query is the operation an index is most often actually asked for, and it is the one where the sorted array is competitive, because a sorted array is already a linked list of leaves with no pointers.

The one number a B-tree analysis usually omits #

Every treatment of this structure quotes the height and stops, and the figure above shows why that is only half of a cost. The other half is what fraction of the height is resident, and it is not a property of the tree — it is the ratio of two quantities the tree knows nothing about.

The whole top of a B-tree above the leaves is n/B² blocks, so it fits in memory exactly when M/B ≥ n/B², that is when M ≥ n/B. Four million keys at B = 1024 need 4,096 elements of memory to keep every internal node resident; the figure gives it 65,536, which is sixteen times more than enough. At B = 64 the same tree needs 65,536 and gets exactly that, which is why the measured cost there is 1.99 rather than 1.

That inequality is the useful sentence in the whole essay, because it is the one an operator can act on: an index is one transfer per query when memory holds n/B elements, and it degrades to the full height when it does not. It also explains a behaviour that looks pathological from outside — an index that has been serving one transfer per lookup for months suddenly serving four, with no code change and no query change, because the table grew past the point where its internal nodes fit. Nothing about the algorithm changed. A ratio crossed.

The degradation is a staircase, and its treads are a factor of B wide #

The residency inequality deserves one more turn, because as stated it says when an index costs one transfer and not what it costs when it does not — and the answer is the reason a large index behaves so much better than its height suggests.

Every level of the tree is a factor of $B$ smaller than the one below it, so residency is lost one level at a time and each loss adds exactly one transfer. The cost is therefore

$$1 + \left\lceil \log_B \frac{n}{M} \right\rceil$$

which is a staircase in $n$ with treads a factor of $B$ wide. At $B = 1024$ and $M = 65{,}536$, a table serving one transfer a query can grow a thousandfold before it serves two, and another thousandfold before it serves three. The behaviour that looks pathological from outside — an index that quietly went from one transfer to two — is a step function whose next step is a very long way off.

That also sharpens the inequality itself, which is right to within its own tail, and this essay’s own $B = 64$ row sits inside the tail.

The rule says the top fits when $M \ge n/B$, obtained by counting the level directly above the leaves at $n/B^2$ blocks. But there are levels above that, and they sum geometrically: the true block count above the leaves is $\frac{n}{B^2}\cdot\frac{B}{B-1}$, which is a factor $1 + 1/(B-1)$ larger. At $B = 64$ over four million keys that is 1,040 blocks against a memory holding 1,024 — short by sixteen blocks, or 1.6%, and the earlier claim that the tree “needs 65,536 and gets exactly that” is what the leading term says rather than what the tree has. The parent level is resident, the grandparent level is not quite, and the measured 1.99 is the leaf plus one that could have been avoided by a memory a fiftieth larger.

Two things worth carrying from that.

The first is that a criterion which drops a geometric tail is exact everywhere except at its own boundary, which is precisely where anyone consults it. At $B = 1024$ the same tree has five blocks above its leaves against sixty-four resident, and no amount of care about the tail changes the answer. The correction only ever matters within a factor of $1 + 1/(B-1)$ of the crossing, and a structure sized to sit there has been sized to sit on a cliff — which is the cliff where the data stops fitting’s subject, arriving here as an operational rule rather than a curve.

The second is that the staircase makes the fanout decision a different question from the height table above. Between $B = 256$ and $B = 1024$ the height does not move, so by height the larger block buys nothing; by residency it multiplies the size a table may reach before it costs a second transfer by four. The column that stops moving is not the column that decides, and where a crossing moved to is the habit of checking which of two quantities the decision actually turns on before reading the one that is easier to tabulate.

The gap between the height and the measured cost is the whole subject, and it is a function of how much of the tree fits in memory — so three more sizes, spanning sixteenfold.

Sixteen times the keys through the same memory is the first of the two ways to make the resident fraction smaller, and it is the one a growing dataset performs on its own.

The other way is to shrink the memory, which is what happens when a machine runs anything else at the same time, and the two are not interchangeable — one moves the height and one does not.

Why this structure and not a hash index #

A hash index answers an exact-match query in about one transfer regardless of n, which is better than a B-tree’s three, and hash indexes exist in every database for exactly that reason.

They cannot answer anything else. A B-tree’s keys are in order, so it answers a range, a prefix, a nearest-neighbour-below, and a sorted scan without sorting. The B-tree is not the fastest structure for the query it is usually benchmarked on; it is the fastest structure that answers the other four, and that is the reason it has been the default index of every relational database since 1970 rather than a curiosity.

There is a second reason, and it is a transfer argument rather than an interface one. A hash index’s one transfer is a transfer to a random block, every time, by construction — a hash function that clustered would not be a hash function. So a hash index cannot warm: a table of ten thousand blocks in a memory holding a thousand hits 10% of the time however long it runs, because the accesses are uniform over the whole table by design. A B-tree’s accesses are not uniform. Its root is touched by every query, its second level by every query, and only the leaf is fresh — the access distribution is as skewed as the structure is deep, and skew is exactly what a cache converts into hits.

The structure with the worse worst case has the better measured case, because its cost is concentrated on blocks it revisits. That is the same argument expected is not average makes about a distribution rather than a mean, applied to the distribution of addresses rather than of costs.

Comparing the two on lookups alone therefore measures the one operation on which the choice does not turn, which is a specific and common way for a benchmark to be exactly wrong — the same shape as measuring Robin Hood hashing by its mean probe count in the probe nobody waits for, where the quantity reported is provably the one the technique does not move.