The sibling a full leaf asks first

The keys that arrive late measured how full a B±tree’s leaves end up, and found the answer is decided by the order the keys arrived in. Inserted at random, the leaves end 70.5% full — the classical $\ln 2$. Ascending, 51.6%. Descending, 50.0%. The rule real databases use for ascending inserts, splitting a full leaf at its right-hand end rather than down the middle, fills ascending leaves completely and does nothing at all for descending ones.

And it is brittle. Let one key in a hundred arrive late in an otherwise ascending stream and the rightmost rule’s leaves fall from 100% to 53.4% — worse than even splits on the same stream.

The damage comes from one event: a full leaf split into two halves that will never be refilled. The classical answer is to avoid producing half-full nodes at all. A B*-tree asks a sibling first: when a leaf overflows, push a key into a neighbour that has room, and only when both neighbours are full split the two of them into three, each about two-thirds full. This page builds that and measures it on the same streams.

What it does to a trickle of disorder #

The two lines cross at the first per cent, and they never cross back.

With one key in a hundred arriving late, redistribution holds 84.2% where the rightmost rule holds 53.4% — a tree of 2,437 leaves against 3,838, which is 36% less index to read, write and cache. The improvement is not marginal and it is not at a corner of the parameter space; a trickle of disorder is the ordinary condition of an index on a table with a serial key and any updates at all.

And the shape of the redistribution line is the finding worth carrying. It is lowest at zero late keys — 67.2%, worse than the rightmost rule’s 100% — and jumps to 84.2% as soon as one key in a hundred is out of order. The rule that repairs late arrivals is better with late arrivals than without them.

That reads like a mistake and is not. On a perfectly ascending stream every insertion goes to the rightmost leaf, and that leaf’s left sibling is full while its right sibling does not exist. There is nothing to redistribute into, so every overflow is a two-into-three split, which leaves nodes two-thirds full and nothing better. A trickle of late keys lands in leaves all over the tree, and those leaves have siblings with room; a redistribution then fills a sibling rather than making a new node, which is precisely what the rightmost rule cannot do, because the sibling it would have to write to is not the one it is splitting.

The three orders #

Read down the redistribution column and the rule’s character is plain. It is the only one of the three that never falls below two thirds on any order, and the only one that treats ascending and descending alike — 67.2% for both, to a tenth of a per cent, because neither has a sibling with room and both therefore go through the same two-into-three split every time.

It is also the only rule that beats $\ln 2$ on random insertions, and by a wide margin: 84.3% against 70.5%. Random insertion is the case the rightmost rule was never about, and it is the case most of an index’s life is spent in.

The classical analysis puts a B*-tree’s random-insertion limit at about 81% against $\ln 2$ for plain splits. This measures 84.3%, above that, and the reason is a difference in the rule rather than in the arithmetic: the classical rule redistributes only when a split would otherwise happen and moves enough keys to balance the two nodes, while this one pushes a single key into whichever sibling has room and only balances when it must. Moving one key is the smallest repair that fixes the overflow, so it defers splits longer.

The difference between the two histograms is where the rule’s gain lives, and it is not where a reader would expect. Redistribution does not make the full leaves fuller — both distributions reach 64 — it removes the empty half of the range. The even-split tree’s leaves start at 32 because a split produces two halves of a full node; redistribution’s start at 43 because the only thing that ever produces a new leaf is a two-into-three split, and three nodes from 129 keys is 43 each. The floor moved and the ceiling did not, and the mean moved with the floor: 32 to 43 at the bottom, 45.1 to 54.0 in the mean, 64 at the top either way.

That is also why the classical 81% and this 84.3% are both right. A rule that splits two into three has a hard floor of two-thirds; how far above it the mean sits depends on how long redistribution defers the next split, and moving one key at a time defers it longest. The floor is the theorem and the mean is the implementation.

That histogram is the rule’s signature and is worth setting against the even-split rule’s, which spreads from 32 to 64. A rule that splits two nodes into three has a much narrower distribution of fills than one that splits one into two, because it starts from more keys, and a narrower distribution is worth something on its own: an index whose leaves are all within eight keys of each other has a predictable size, and one whose leaves run from half to full does not.

The two orders that cannot redistribute #

Ascending and descending insertion both give 67.2% under redistribution, to a tenth of a per cent, on trees of 3,048 leaves and 3,046 two-into-three splits each. Two arrival orders that no other rule treats alike produce, under this one, the same tree.

The reason is that redistribution is unavailable to both. On an ascending stream the overflowing leaf is always the rightmost, whose left sibling is full and whose right sibling does not exist. On a descending stream it is always the leftmost, with the mirror problem. Every overflow is therefore a two-into-three split, and a tree built entirely from two-into-three splits sits at the floor.

So the rule’s symmetry between ascending and descending is the symmetry of its failure, not of its success — which is worth knowing, because the rightmost-split rule’s asymmetry (100% ascending, 50% descending) is usually described as the thing to fix, and fixing it by making both 67.2% is only half of what the plate on late arrivals shows. The whole of it is that a stream with any disorder at all lets redistribution work, and 1% of keys out of order takes it from 67.2% to 84.2% while taking the rightmost rule from 100% to 53.4%.

Four leaves and a tenth of a key separate that tree from the random-insertion one. A rule whose result is indistinguishable between a nearly-sorted stream and a shuffled one has removed the arrival order from the answer, which is precisely what the rightmost rule failed to do and what the keys that arrive late set out as the problem.

What it costs #

Nothing about this is free, and the currency is the one the writes nobody counted is about.

An even split writes one new node and rewrites one. A redistribution writes two nodes — the overflowing leaf and the sibling — and updates a separator in the parent. A two-into-three split writes three nodes and inserts a separator. Counted as keys moved between leaves, on 131,072 keys:

• random: 190,241 moves, 1.45 a key, from 34,809 redistributions and 2,427 two-into-three splits;
• ascending: 261,966 moves, 2.00 a key, from 63,976 redistributions and 3,046 splits;
• one per cent late: 234,102 moves, 1.79 a key, from 77,914 redistributions and 2,435 splits.

So the rule costs about one and a half to two extra key movements per key inserted, against a plain split’s amortised one movement per key. Roughly double the write traffic during building, for between 20% and 60% fewer leaves afterwards.

Whether that is a good trade depends on the ratio of insertions to queries over the index’s life, and it is the same shape of trade one dial between two structures drew between a B-tree and a log-structured store: write amplification against read cost, with the crossing decided by the workload rather than by the structure. An index built once and read for months should redistribute. An index rewritten as fast as it is read should not, and should probably not be a B-tree.

The separator updates are the part of the cost that is easy to forget and hard to avoid. Every redistribution moves a key across a boundary between two leaves, so the parent’s separator for that boundary is now wrong and has to be rewritten — 34,809 of them on the random stream, 77,914 on the stream with one per cent late. A separator update is small, the parent is certainly in memory, and a structure that got it wrong would still hold every key and would no longer be able to find them. So every tree on this page is verified by reading its leaves left to right and requiring them to come out sorted, and by requiring every separator to equal the first key of the subtree it stands in front of — rather than by counting the keys and calling that correct, which a tree with a stale separator would pass.

There is one asymmetry worth naming in the rule’s favour. The moves are writes to nodes that are already in memory — a redistribution touches the overflowing leaf, which was just written to, and one sibling, which the parent points at. A plain split allocates a new node somewhere else. So counting key movements overstates the difference in transfers, and this page does not count transfers.

The rule read as an amortisation #

There is a way of stating what redistribution does that makes both its gain and its cost obvious, and it is the way what amortised means states a dynamic array’s doubling.

A plain split is a structure that pays nothing until it pays a lot: every insertion is one write, until the one that overflows a leaf and writes two nodes. The cost is small and even, and the fill is what the evenness buys — a leaf that has just split is half empty and will stay half empty if nothing else arrives near it.

Redistribution moves work forward. It pays a little on many insertions — 34,809 redistributions over 131,072 random keys, so about one insertion in four moves a key to a sibling — in order to pay the large cost less often: 2,427 two-into-three splits against the plain rule’s 2,905 splits. The amortised write cost goes up by about half and the number of nodes goes down by a sixth.

That framing says what to watch for, which is the tail rather than the mean. A redistribution is a write to a node the parent already points at; a chain of them is not possible here because only one key moves and only into an adjacent sibling. So the worst insertion under this rule writes three nodes — the two-into-three split — where the worst under a plain split writes two, and no insertion is worse than that. The rule raises the mean cost and barely moves the worst, which is the opposite of the usual amortisation complaint and is worth having.

Why the height is the other half #

The fill numbers on the first two plates carry a consequence the bars do not show. A tree of 2,429 leaves and a tree of 3,971 leaves are not merely different sizes; at a fan-out of 64 they can be different heights, and a height is a transfer on every query.

At 131,072 keys the redistribution tree on random insertions is 2,429 leaves and three levels; the even-split tree on ascending insertions is 3,971 leaves and four. Every point lookup on the second pays one more transfer than every lookup on the first, for the whole life of the index, because of the order the keys happened to arrive in and the rule that responded to it. A tree with nodes the size of a block measured a B-tree’s height as the whole of its query cost; this is that cost being set by an insertion rule.

What is not measured here #

Redistribution at the leaves only. The internal levels keep the ordinary even split. The leaves hold the keys and are what the fill measures, and mixing two rules at two levels would make the measurement about the mixture. A full B*-tree redistributes everywhere, which would raise the fan-out of the internal nodes and occasionally remove a level; nothing here bounds that.

One key at a time. A leaf pushes one key into a sibling, which is the smallest repair. The classical rule moves enough to balance the two, which produces a different fill distribution and more moves per redistribution. Which of the two is better is a sweep this page does not run.

Left before right. A leaf asks its left sibling first and its right second. On an ascending stream that is the worse order — the left sibling is the one just filled — and on a random stream it makes no difference the measurement can see. The choice is arbitrary and it is not swept.

No deletions. Every tree here is built by insertion and never shrinks. A B*-tree’s merging rule on deletion is the mirror of its splitting rule and has its own fill floor, and the promise that does not survive the tree is the general warning that a structure’s guarantees under one operation are not its guarantees under another.

Keys moved, not transfers. The cost above is keys moved between leaves. A transfer model would charge per block touched, would forgive the moves that stay inside a node already fetched, and would charge the parent’s separator update that this count ignores.

Building, not maintaining. Every measurement is of a tree built from empty. An index that has been running for a year is not the tree its arrival order built; it is that tree after deletions, page splits from updates and whatever the storage engine did to it. What the generated collection was right about is the standing caution about measuring an instrument rather than a subject, and a freshly built tree is an instrument.

One fan-out. Leaves of 64 keys and 64 children a node throughout. The two-into-three split’s 2/3 floor is independent of the fan-out; the redistribution’s effect on the fill is not obviously so, since a wider leaf has more room to absorb a pushed key before it too overflows.

Still open: asking a sibling that is not adjacent #

The rule here asks the two leaves either side of the overflowing one, which are the two the parent can reach without descending anywhere else. A leaf at the edge of its parent’s children has only one such sibling, and a leaf that is an only child has none — which is why the ascending stream’s redistributions do so little.

There is a wider version. The parent knows all its children, and a leaf overflowing in a parent with sixty-four children has up to sixty-three candidates with room, all of them reachable without leaving the node. Moving a key two positions along requires moving a key at every position between, which is a chain of single moves and a separator update for each — expensive per repair, and it defers a split much longer.

The measurement that follows implements the chain: on overflow, walk outwards from the leaf until a sibling with room is found, and shift one key along each step of the way. It asks how far a chain typically has to walk on each of the four arrival orders, how much further the fill rises above 84.3%, and where the extra moves overtake the leaves they save — which is the same crossing this page drew between 1.45 moves a key and 36% fewer leaves, at a different point on the same curve.