The keys that arrive late

A tree with nodes the size of a block priced a B-tree by its height: with nodes holding as many keys as fit in one block transfer, a search costs $\log_B n$ transfers rather than $\log_2 n$, and the top levels of the tree are few enough blocks to live in memory. That analysis, like most, drew the tree full. Every node held $B$ keys, and $n$ keys needed $n/B$ leaves.

A B-tree that grows by insertion is not full. When a leaf overflows it splits into two, each about half full, and it fills again only if later keys land in it. So how full the leaves are at any moment depends on where the keys that arrived after each split went — which is a fact about the order the keys arrived in, not about the keys or the tree. This page builds the same 131,072 keys into a B±tree with real splits, in several orders and under two split rules, and counts what is empty.

The same keys in seven trees #

The trees have leaves of 64 keys and internal nodes of 64 children. Two split rules are compared. Even splits divide an overflowing node into two halves, the textbook rule. The rightmost-split rule keeps a full leaf full and starts a new leaf with the one key that overflowed, when that key was the largest in the leaf — the case of a key appended at the right-hand end — and splits evenly otherwise. It is the rule systems adopt so that ascending keys, which are common, do not leave a trail of half-empty leaves.

The leaf count runs from 2,048 to 4,095, a factor of two, for the same keys in the same kind of tree. Three things decide where a tree lands.

Random order settles near ln 2. Keys inserted in random order leave the leaves 70.5% full with even splits, within about a point of $\ln 2 = 69.3\%$, which is the limit a classical analysis of random insertion into B-trees gives. The rightmost rule changes almost nothing here, 69.4%, because a random key is rarely the largest in its leaf.

Monotone order halves the tree. Ascending keys with even splits fill each leaf, split it in two, and then never touch the left half again — every later key is larger and goes right — so the tree is a chain of half-full leaves, 51.6% on average. Descending keys do the same thing from the other end, 50.0%. Both need twice the leaves of a full tree and a fourth level.

The two monotone fills are not both a half, and the difference is exact. A leaf of 64 overflows when its 65th key arrives and splits at the 33rd. On an ascending stream the left half keeps the 33 smallest keys and every later key is larger, so the left half holds 33 keys forever: 33 of 64 is 51.6%. On a descending stream the new key is the smallest, the left half again keeps the 33 smallest — now including the newcomer — and every later key is smaller still, so it is the right half, with 32 keys, that is abandoned: 32 of 64 is 50.0%. The whole of the gap between the two bars is one key per leaf, left on one side of the split rather than the other.

The rightmost rule fixes one direction only. Ascending keys under it fill every leaf completely, 2,048 leaves, the same as a tree loaded from sorted keys in one pass. Descending keys under it are exactly as bad as under even splits, because the key that overflows a leaf in a descending stream is the smallest in it, not the largest, and the rule does not fire.

What a random tree’s leaves look like #

The distribution fills the whole range a split allows, from 32 to 64, and it is not flat. A leaf receives insertions in proportion to the range of keys it covers, which grows with the number it holds, so a nearly full leaf fills and splits sooner than a nearly empty one grows; and every split turns one full leaf into two half-full ones. In steady state that leaves more leaves near the bottom of the range than near the top — 1,784 of the 2,906 hold fewer than 48 keys and 1,122 hold 48 or more — and a mean below the midpoint, at 45.1 keys.

The ascending tree’s histogram is nearly a single bar. Every leaf but the rightmost was split once, when it overflowed, and received nothing afterwards, so it holds half of 65 keys — 33 — for the rest of the tree’s life. Of the 3,971 leaves, 3,970 hold fewer than 48 keys; the one that holds more is the rightmost, still being filled.

What empty space costs #

A half-full tree is a tree with twice the blocks, and every quantity measured in blocks follows.

A range scan reads twice as many leaves. Reading $k$ consecutive keys touches about $k/(\text{fill} \times 64)$ leaves, so the ascending tree with even splits pays 1.94 times what the bulk-loaded tree pays for the same range, and the random tree 1.42 times. The index that is not worth reading found that an index’s advantage over a scan is a count of blocks, and a half-full index spends twice the blocks reaching the same run of keys before it has fetched a single row.

A point search pays for an extra level. At 131,072 keys the bulk-loaded tree and the full ascending tree are three levels high and the half-full trees are four. A tree with nodes the size of a block found that the top levels of a tree live in memory, so the extra level is paid in the part that does not — which is where a transfer costs most.

The cache holds half as much of the index. A buffer pool of a fixed number of blocks holds a fixed number of leaves, and half-full leaves are half as many keys. The space the model does not see is the site’s general warning about space an analysis charges nothing for; the empty half of a leaf is a clean case of it, because it is invisible to every count of operations and visible in every count of blocks.

Where the extra level arrives #

A factor of two in leaves is a factor the tree’s fan-out absorbs slowly, so the question of when it costs a level is a question about size.

The three lines are parallel on a logarithmic plot, which says the ratios do not change with size: random insertion needs about 1.43 times the leaves of a full tree at every size drawn, and ascending insertion about 1.94 times. What changes is where each tree crosses the size at which one more level is needed. A root of 64 children over leaves of 64 keys holds a full tree of 4,096 keys in two levels, and a third level holds 262,144. The bulk-loaded tree is two levels at 4,096 keys, where the half-full trees are already three. At 131,072 keys the ascending tree has 3,971 leaves — more than the 4,096 children two levels of internal nodes can address once those nodes are themselves only half full — and it needs a fourth level that the bulk-loaded tree will not need until it holds a quarter of a million keys.

So a half-full tree pays its extra level early, over a range of sizes about as wide as the factor it wastes. For most of the size axis the two trees have the same height and differ only in leaves; near each boundary the emptier tree is one transfer taller on every search.

The same trade as a growing array #

The empty half of a leaf is not a defect in the B-tree. It is the price of making insertion cheap, and choosing a growth factor measured the same price in a simpler structure. A dynamic array that doubles when it fills leaves 39% of its allocation empty on average, and one that grows by an eighth leaves 10% empty and pays nearly five times as much per append. The space is spent so that most appends touch nothing but the next free slot.

A leaf split is a local doubling. It turns one full block into two half-full ones so that the next 64 insertions into that range are free of any restructuring, and the fill that results is set by where those insertions actually land — which is the whole difference between a random stream, whose insertions spread across old leaves and refill them, and a monotone one, whose insertions all land in the newest leaf and leave the old halves empty forever. The array has no such difference, because an array is only ever appended to at its end. A B-tree is appended to wherever the keys fall, and the order of arrival decides whether the space reserved by a split is ever used.

What amortised means drew the sawtooth under a dynamic array’s constant amortised cost. The B-tree’s version is a set of teeth, one per leaf, and a leaf that is never inserted into again is a tooth that never comes down.

A trickle of late keys #

The rightmost-split rule looks like a complete fix for the commonest bad order. Keys that grow — timestamps, sequence numbers, identifiers issued in order — arrive ascending, and under the rule they fill the tree as tightly as a bulk load. Real ascending streams are rarely perfectly ascending, though. Events are written out of order by clocks that disagree, batches are retried, and records arrive late.

One key in a hundred arriving late takes the rightmost rule’s tree from 100% full to 53.4%, which is barely better than even splits and a long way from the ln 2 of random order. At one in twenty the rule is worse than even splits.

The mechanism is in the leaves a late key lands on. When a key arrives late, the stream has already moved past its value, and the leaf it belongs in is an old one — full, because the rule filled it. The late key overflows that leaf, and since it is not the largest key in it, the rule does not apply and the leaf splits evenly into two halves. Neither half will ever receive another key, because the stream has moved on. So a late key that overflows a full leaf converts it into two half-full ones permanently, and about 1,300 late keys among 131,072 are enough to leave most of the tree’s leaves in that state: at 53.4% full, the tree has nearly twice the leaves the rule would otherwise have given it.

Even splits degrade more gently because they had nothing to lose: their leaves were half full already, and a late key landing in a half-full leaf just fills it a little. As the share of late keys rises towards a half, both rules climb towards the random-order ln 2, because a stream that is half late is closer to random than to ascending.

Late keys are not an exotic condition in the data that most wants the rightmost rule. Keys generated from time are ascending only as far as the clocks and the delivery agree: a record written by a machine whose clock runs a little behind, a batch that is retried after a failure, an event held in a queue while a network partition heals — each arrives with a key smaller than keys already in the index. None of those is rare in a system of any size, and one in a hundred is a modest rate for them.

This is the same shape a worst case ten positions wide found for first-element quicksort, turned around. There, sorted input was an expensive peak that a few displaced elements destroyed. Here, sorted input is a cheap peak — the rightmost rule’s perfect fill — and a few displaced elements destroy that instead. In both cases a property measured on exactly ordered data tells almost nothing about data that is nearly ordered, which is what real data is.

What an index designer can take from this #

Measure the order the keys arrive in, not only the keys. A run is a property of the input argued that “nearly sorted” should be a measured quantity; for an index the relevant measure is how often a key lands anywhere but the right-hand end, and one per cent is already enough to matter.

The rightmost rule is a fix for a perfect stream. On streams with any late arrivals it buys nearly nothing, and the fill it promises is not the fill the tree has.

Size the space for the arrival order, not for the count. A tree expected to take random insertions will settle near ln 2 however it starts, and a tree expected to take a perfectly ascending stream can be kept full by the rightmost rule. A stream that is ascending with a trickle of late arrivals is the case neither rule serves, and it is the commonest case for keys generated from time. For that stream, the plates say the realistic fill is a little over half, and every estimate of the index’s size, height and cache footprint should be made at that figure rather than at the full-node figure the analysis uses.

Rebuilding is the only fix measured here that does not depend on order. A tree loaded from sorted keys is full whatever order the keys first arrived in, which is why systems periodically rebuild indexes and why a rebuild of a heavily updated index can halve its size. The writes nobody counted priced the other side of that bargain: a B-tree that writes its leaves in place pays a block per key inserted, and a rebuild is a whole pass of writes paid at once to recover space.

What the model leaves out #

No deletions. Deleting keys empties leaves further, and most B-trees merge or redistribute only below some threshold, so a tree with deletions can be emptier than any on these plates.

No redistribution before splitting. A B*-tree, before splitting a full node, first tries to move keys into a sibling with room, and splits two full nodes into three rather than one into two. That raises random-order fill well above ln 2 and changes how late keys hurt, and it is not measured here.

Keys are fixed-size. Real leaves hold variable-length keys and fill by bytes rather than by count, so “full” is fuzzier and a split point chosen by count can leave unequal halves in bytes.

Still open: splitting two full nodes into three #

The damage on this page comes from one event — a full leaf split into two halves that will never be refilled — and the classical answer to that event is to avoid producing half-full nodes at all. A B*-tree redistributes into a sibling first and, when both are full, splits the two into three nodes each two-thirds full. For random insertion the same kind of analysis puts its limit at about 81%, against ln 2 for plain splits.

What is not known from that limit is how redistribution behaves on the orders that matter here. On a perfectly ascending stream the right-hand sibling is empty and redistribution may do nothing; on a stream with late arrivals, a late key’s full leaf has full siblings, and a two-into-three split leaves nodes two-thirds full rather than half — which would recover a third of what the rightmost rule lost. The measurement that follows builds the same trees with redistribution and two-into-three splits under the same arrival orders and asks how much of the fill late keys destroy then, and what the extra sibling reads and writes cost in transfers.