One dial between two structures

Two structures were set beside each other in the writes nobody counted and the gap between them was enormous. A B-tree, taking sixteen thousand random keys, wrote 49.3 elements’ worth of blocks for every key it stored. A log-structured store, taking the same keys, wrote 2.0. Every counter this collection had before that measurement reported the two as identical work.

They were presented there as two designs, because that is how they are presented everywhere: an in-place tree for reading and a log-structured store for writing, and an architect chooses. That framing is wrong in a specific and useful way. They are not two designs. They are the two ends of one design, the thing that separates them is a single exponent, and every intermediate setting of it exists and can be measured.

What a buffer does to an insertion #

A B-tree insertion is a descent and a write. It reads one node per level to find the right leaf, then dirties that leaf. The leaf is one block, the block holds B keys, and — this is the whole of the amplification — the leaf is almost certainly evicted before another key lands in it, so one key costs one whole block written. At B = 256 that is 256 elements moved to store one, and the measurement above says 226 because a few leaves do get hit twice.

The buffered version changes one thing. An arriving key is not sent to its leaf. It is written into a buffer in the root, along with every other key that has arrived recently, and it stays there until the buffer is full. When it is full, the root is read once and its contents are partitioned among the root’s children, one block written per child touched. Each key has moved down exactly one level, and the cost of moving it was shared with every other key in the buffer.

That is the entire idea, and the arithmetic falls out of it immediately. It is also the same move sorting what will not fit makes for a different problem: batch the work so that one transfer serves many elements rather than one, and accept that an individual element’s journey becomes longer in exchange for its share of the journey becoming smaller. If a buffer holds about B messages and a flush touches about f children, then f blocks were written to move B messages one level: a cost of f/B blocks per message per level. A B-tree’s cost is one block per key, full stop. So the ratio between them is f/B times the height, and both of those are controlled by the same choice.

Let f = B^ε. The height of a tree with fanout f over n keys is log_f n = (1/ε)·log_B n, and the cost per insertion is that height times B^ε/B:

$$\text{insert} \approx \frac{1}{\varepsilon}\cdot\frac{\log_B n}{B^{1-\varepsilon}} \qquad \text{query} = \frac{1}{\varepsilon}\cdot\log_B n$$

At ε = 1 the second factor of the insertion cost is B⁰/B = 1/B blocks per level… except that at ε = 1 there is no buffer at all — a node whose pivots fill its block has nothing left to buffer with — so the key descends immediately and pays the whole leaf. The formula and the structure agree at the boundary only if the boundary is read carefully, which is the kind of thing worth checking rather than asserting.

A worked instance makes the sharing concrete. Take a block of two hundred and fifty-six elements and a fanout of sixteen. The root’s buffer holds two hundred and forty pending keys; when it fills, the root is read once and sixteen children are written, so 240 keys moved one level for seventeen transfers — about fourteen keys per transfer. A B-tree at the same block size moves one key per transfer, all the way down. The buffered tree then has to repeat that at every level, five of them here rather than three, and the product of those two effects is the whole result.

The endpoint is the B-tree, to the transfer #

The claim that these are one structure is easy to make and easy to make loosely. The version that can be checked is stronger: the general implementation, run at ε = 1, must produce the same transfer counts as the special one, not similar ones.

It does, and it did not on the first attempt. The first version charged a write for every child a flush touched and then charged again when that child flushed onward — so at ε = 1, where a buffer holds one message and nothing ever rests anywhere, it reported a write per level per key and an amplification of 100 on a structure whose defining characteristic is that it writes one block per key. The repair is to charge a block only when messages stay in it. With that, the two implementations agree to the transfer, and the gate holds them to it.

That is the same discipline the writes nobody counted needed when its first amplification measurement came out at zero, and it is the recurring lesson of this field: the code constructing the case is as likely to be wrong as the code being measured, and it is far less likely to be checked.

There is a second reason to insist on the endpoint rather than on a family resemblance, and it is about what a measurement is for. A plate showing a buffered tree beating a B-tree proves very little on its own, because two implementations by two authors differ in a hundred ways and any of them could be the cause. A plate showing one implementation, at two settings of one named parameter, is a controlled comparison: everything except that parameter is byte-for-byte the same code. Fitting a class to measurements makes the same demand of a growth curve, and the discipline is identical — an experiment that varies two things at once has measured neither.

What the exponent costs, stated as a rate #

A dial is only interesting if both directions are priced, and the query side is the one that is easy to forget because it does not appear in a write-amplification measurement at all.

A point query descends the tree, and a buffered tree is taller than a B-tree over the same keys, because its fanout is smaller. Worse, a query cannot stop at the leaf: a key may still be sitting in a buffer somewhere on the path, so every node on the descent must be examined for it. That costs nothing extra in transfers — the node was read anyway — but it means the descent cannot be shortened.

So the trade is height against writes, and at B = 256 over 131,072 keys it runs:

Those are transfers rather than durations, which is the standing caveat of this field and is stated once here rather than after every number: the count is not the time, and the four orders of magnitude between the cheapest and dearest kinds of transfer are why nothing on this page is converted into one.

The row worth staring at is the second. At ε = 0.85 the tree is the same height as the B-tree — three transfers to a query, identical — and it writes a third less. That is not a trade at all; it is a strictly better structure at these parameters, obtained by giving up a hundred and forty-five pivots per node that the fanout did not need.

The direction of that dependence is the useful part. The amplification a B-tree suffers is proportional to B, and the amplification a buffered tree suffers is proportional to B^ε. So a hardware trend towards larger transfer units — which is what every generation of storage device has produced — makes the in-place tree worse and the buffered tree better, at the same time, on the same device. A structure chosen for one block size is a structure chosen for one era.

Where the analysis stops describing the measurement #

The curve turns back up. At ε = 0.34 the amplification is 59.6 and at ε = 0.25 it is 90.9, both worse than the 44.7 at ε = 0.5, and the formula above says they should be better. This is drawn rather than clipped, because it is a real property of the structure at a real size and not an artefact.

The amortised argument assumes a buffer fills. A tree of fanout four over 131,072 keys has nine levels and its bottom internal level holds tens of thousands of nodes — more nodes near the leaves than there are keys to distribute among them. Those buffers never fill: each one receives a handful of messages over the whole run and then has to be drained anyway, at the price of a whole block, to answer the first query. The per-message cost of a flush that moves eight messages instead of two hundred and fifty is thirty times higher, and no amount of asymptotic reasoning about large n changes what happens at this one.

The general statement is the one this collection keeps arriving at from different directions. An amortised bound is a promise about a long enough sequence, and whether a given sequence is long enough is a question about the parameters rather than about the bound. Choosing a growth factor makes the same point about an array that doubles; here the sequence that has to be long enough is not the whole run but the run through each individual node, and there are exponentially many nodes competing for it.

So the honest reading of the plate is: the dial works over roughly ε ∈ [0.5, 1] at these sizes, its useful range widens as n grows, and the minimum is a measured location rather than a limit.

Which end of the dial a system is on is a statement about its workload #

Nothing above says what ε should be, and that is not an omission. The exponent is a function of the ratio of writes to reads in the workload, and no property of the data structure can supply it.

The arithmetic is one line. If a workload performs w insertions for every r queries, the total transfers are w·insert(ε) + r·query(ε), and minimising that is a one-dimensional search over a curve this site can draw for any B, M and n. A write-heavy log takes ε small. A read-heavy index takes ε at one. A store that must serve both takes something in between, and the something is the number a real system’s tuning guide contains without explaining.

This is the same shape as the threshold somebody chose — a number in a source file that decides more about the behaviour than the complexity analysis does — with one difference worth naming. A sort’s cutoff is a constant chosen once by whoever shipped it. This one is a parameter of the workload, so it cannot be chosen once, and a structure that fixes it has made a decision on the operator’s behalf and hidden it inside a name.

There is one more asymmetry in the trade and it belongs on the query side. A buffered tree’s insertions are sequential in their effect: a flush writes a small set of sibling blocks, which is a short burst of nearby addresses. A B-tree’s insertions are scattered by construction, since a random key lands in a random leaf. Nothing in a transfer count distinguishes those — one access, eight kilobytes established that a transfer is a transfer whatever its address — and every real device charges less for the first than for the second. The count understates the buffered end again.

What the counters can and cannot say about this #

Three qualifications, in the order they would bite.

The query cost here is a count of transfers and not of anything else. A descent is a dependent chain: every node’s address comes from the node above it, so none of the reads can be issued in parallel. The block that is not a block argues this at length, and it applies asymmetrically here — the extra levels a buffered tree adds are all on the dependent chain, so two extra transfers on a query cost rather more than two transfers’ worth of time. The dial’s query side is understated by this model.

A range query is a different question and the model here does not ask it. Both structures answer point queries in the counts above. A scan over a key range is where the in-place tree is at its best and the log-structured end at its worst, because the log-structured end has the range spread across every level of its hierarchy. Nothing in a write-amplification figure sees that, and a system chosen on these numbers alone would be chosen on half the evidence.

And the buffers are memory. A tree whose internal nodes carry buffers has a larger working set than one whose internal nodes carry only pivots, so at a fixed M fewer of its top levels stay resident. The measurements above charge that honestly — the resident set is simulated, not assumed — but the effect is worth naming, because it is the mechanism by which the trade could stop being a trade at a small enough memory. It is the same edge the cliff where the data stops fitting measures for a working set that outgrows a cache, one level of the hierarchy down, and it arrives suddenly for the same reason.

None of the three changes the direction of the result. All three change how much to trust the second decimal place, which is the standing caution of this whole field and the reason the count is not the time exists.

What was actually gained, stated narrowly #

It would be easy to read the plate as “buffered trees are better”, and that is not what was measured.

What was measured is that a family of structures exists between two that are usually presented as alternatives, that it is parameterised by one number, and that the number is not in either structure’s description. The B-tree and the log-structured store are the endpoints, and the reason they are the ones with names is historical rather than technical: one was designed for disks in 1970 and the other for disks in 1996, and nobody was obliged to notice that the second is the first with the fanout turned down and the leftover space put to work.

The strongest form of the claim is the one the gate holds: at ε = 1 the general implementation reproduces the special one transfer for transfer. Whatever else is true, these are not two things.

That matters beyond this pair, because the same shape recurs whenever a field has two named designs and a space between them. What O notation does not say is about a class discarding a constant; this is a class discarding a parameter, which is worse, because a constant at least leaves a number behind to be measured and a parameter that nobody names leaves nothing. Both structures here are $O(\log_B n)$ for a query and both are described that way, and the description is true of every point on the curve — including the points where the amplification differs by a factor of seven.

The counters that make the difference visible are the ones this field added rather than the ones it inherited. Comparisons cannot see it, since neither structure compares anything the other does not. Auxiliary space cannot see it, since measuring what an algorithm keeps counts what is held rather than what is moved. Only a count that charges for a block, and charges separately for a dirty one on the way out, distinguishes 226 from 45.

Where this ladder goes from here: the sizes nothing here chose #

Three questions this rung opened and did not answer, in the order they are worth taking.

The buffer’s size is a second dial and it has been held fixed. Every measurement above spends all of a node’s non-pivot space on the buffer. It need not: a node could reserve some of its block for a Bloom filter over the keys below it, which would let a query skip subtrees it cannot be in and would take some of the space the buffer is using. That is a three-way division of one block — pivots, buffer, filter — and only one of its axes has been swept here.

The flush policy is a choice this made without saying so. The implementation flushes a full buffer to every child at once. The published analyses flush to whichever single child has the most pending messages, which pays one read and one write to move a larger batch. The two have the same asymptotic cost and different constants, and the constants are what this field is about — so the difference is measurable and unmeasured.

And the turn at the bottom of the curve is a finding without an explanation with a number in it. The account above — that deep buffers never fill because there are more nodes than keys to fill them — is the right shape and is not yet a formula. The quantity that would settle it is the expected number of messages a node at level ℓ receives over a run of n insertions, which is computable in closed form and would say exactly where the minimum sits as a function of n, B and ε. That is a small piece of arithmetic and it would turn the most interesting part of this plate from an observation into a prediction the next rung could check.