A key passed along the row

The sibling a full leaf asks first measured a rule borrowed from the B*-tree. When a leaf overflows, it offers a key to the leaf on either side before splitting. If both neighbours are full, it splits two full leaves into three. On random insertion that took leaves from 70.5% full to 84.3%, 2,429 leaves where even splits left 2,906, for 1.45 key moves per key inserted. It also survived the case that defeats the rule databases usually use: a stream that is ascending except for one key in a hundred arriving late.

It left one rule unexplored, and it named it. A leaf in a parent with sixty-four children has up to sixty-three candidates with room, all reachable without leaving the parent. Asking only the two adjacent ones is a choice, and the obvious alternative is a chain. Walk outwards until a leaf with room is found, and pass one key along each full leaf on the way. Every step is one key moved and one separator rewritten. A long chain is expensive, and it defers a split further than asking the neighbours can.

Reach, and what it fills #

The rule is the adjacent rule with one parameter, the reach: how many siblings away, in either direction, a full leaf may look. With a reach of one it is exactly the adjacent rule, and the measurement checks that it builds the identical tree. A reach of 64 covers the whole parent.

The two ordered streams give the sharpest result on the plate. Ascending and descending insertion go from 67.2% full to 100.0% when the reach goes from one sibling to two. The tree has 2,048 leaves where the adjacent rule left 3,048. That is exactly $131{,}072 / 64$, every leaf full.

The mechanism is visible in what the adjacent rule does on an ordered stream. Every insertion lands at the same end of the tree. When the end leaf overflows, its one neighbour is full, because it was filled a moment ago, so the rule splits two full leaves into three, each two-thirds full. The next overflow happens at the new end leaf. Its neighbour is again full, and the two two-thirds-full leaves behind it are one step out of reach. The adjacent rule never goes back to them, and every leaf it leaves behind stays two-thirds full.

With a reach of two, the overflowing leaf sees past its full neighbour to a two-thirds-full leaf and passes keys back into it until it too is full. The row fills from behind, and each split leaves nothing permanently short. The keys that arrive late found that the rule systems adopt for ascending keys, keeping the left node full on a split, gets 100% on an ascending stream and 50% on a descending one. A reach of two gets 100% on both.

Random insertion climbs steadily instead of jumping: 88.5% at a reach of two, 92.6% at four, 95.3% at eight, 98.9% across the whole parent. The nearly ascending stream follows a similar curve, a little below random at every reach.

What the reach costs #

A chain that passes a key along $d$ leaves writes each of those leaves and the parent whose separators it changed. The currency a store pays is pages written, so the cost here counts pages: the leaf each insertion lands in, each leaf a key is passed into, each leaf a split creates, and each parent whose separators change.

The two kinds of stream separate completely here.

On random insertion the reach is expensive, and more so the further it goes. Doubling the reach from four to eight adds 1.4 pages a key and 2.7 points of fill. Going from 16 to 64 adds 10 pages a key for 1.7 points. At the widest reach a random insertion writes seventeen pages, eleven times what the adjacent rule writes.

On an ordered or nearly ordered stream the reach is almost free. A nearly ascending stream writes 2.249 pages a key at a reach of one and 2.364 across the whole parent, 5% more for 13.5 more points of fill. The ordered streams pay 0.64 pages a key once, going from one sibling to two, for 33 points of fill. After that nothing changes, because nothing more is available to fill.

The difference is in how far keys actually travel.

On random insertion, once the leaves have been filled towards full by earlier redistributions, the nearest leaf with room is usually far away. The walk lengths spread across the whole parent, thinning only slowly with distance, and the mean is sixteen. The rule has made the tree full, and a full tree is exactly the state in which there is no nearby room. The chain’s cost comes from its own success. Each point of fill it adds makes the next insertion search further.

On a nearly ascending stream, 88% of redistributions stop at the first sibling. The late keys land among leaves that ordered insertion already left with some room, the room is near, and the few long walks are the rare late key landing in a stretch that has already been filled. The longest, 49 siblings, is three times random insertion’s mean walk, but it is one walk in tens of thousands, and the mean barely notices it.

The trade, point by point #

Leaves saved and pages written are different currencies. A leaf saved is a page less in the index for its whole life, read by every range scan and cached by every lookup. A page written is paid once, at insertion. Which one matters more depends on the ratio of reads to writes, and nothing here measures that. The shape of the trade can be drawn without choosing a ratio.

On random insertion the curve bends early. The adjacent rule saves 477 leaves for 0.55 more pages a key. The next doubling saves 116 for 0.56 pages. From four to eight saves 63 for 1.42, and from sixteen to sixty-four saves 36 for 10.1. Each further doubling of the reach buys fewer leaves than the one before, at a higher price. A reach of two or four is where the trade is still reasonable for a write-heavy index. Beyond eight it only makes sense for an index that is written once and read for years.

On the nearly ascending stream the curve is almost vertical. The whole parent in reach saves 337 leaves beyond the adjacent rule, 14%, for 0.11 more pages a key. For this kind of stream there is no real trade: widen the reach to the parent and take the leaves.

That kind of stream is common. Keys generated by a clock or a counter arrive almost in order, with some late arrivals from delayed writers or retried transactions. The writes nobody counted measured how a store’s structure multiplies each logical write into several physical ones. Here the multiplier depends on the order the keys arrive in, and it is small exactly for the order that is common.

Against the rule systems already use #

The comparison that matters in practice is not with even splits but with the rightmost rule. On a split caused by the largest key in a leaf, that rule keeps the left leaf full, and it is what indexes use to cope with ascending keys. It costs almost nothing: it moves no keys between leaves, and it writes 1.03 to 1.06 pages a key on every order measured here.

On a perfectly ascending stream it is unbeatable. It fills every leaf, 2,048 of them, at 1.031 pages a key, where a chain of reach two reaches the same 2,048 leaves at 2.686. On anything else it collapses. On a descending stream it leaves leaves 50.0% full and 4,095 of them. On the stream with 1% of keys late it leaves 53.4% full and 3,835 leaves, the failure the sibling a full leaf asks first set out to repair. On random insertion it is 69.4%, no better than an even split.

The chain across the whole parent on that late stream ends with 2,096 leaves where the rightmost rule ends with 3,835, 45% fewer, for 1.3 more pages a key. And the leaf count crosses a threshold that the fill percentage hides. With a fan-out of 64, a tree of 3,835 leaves needs four levels, and a tree of 2,096 needs three. The rightmost rule’s tree on the nearly ascending stream is a level taller than the chain’s, and a level is one more page read on every lookup for the life of the index. That is paid on reads for as long as the index exists. The chain’s extra writes are paid once, at insertion.

A stream that is ascending except for its late keys is the one where a run is a property of the input found that “nearly sorted” needs a measurement before it means anything. Here the measurement is the share of late keys, and one per cent is enough to take the rightmost rule from the best rule on the plate to one of the worst.

What a fuller leaf is worth to a scan #

A leaf saved is a page less in the index, and the saving compounds for any query that reads many leaves. A range scan over 1% of these keys, 1,311 of them, reads about as many leaves as it takes to hold 1,311 keys at the tree’s fill. At the 70.5% of even splits on random insertion that is 30 leaves. At the adjacent rule’s 84.3% it is 25, at a reach of four’s 92.6% it is 23, and at the whole parent’s 98.9% it is 21. Those are arithmetic from the fills, not timed scans. The difference between the adjacent rule and a reach of four is two pages a scan, paid on every scan, against 1.4 pages written a key, paid once per insertion.

Whether that trade is worth taking is a ratio of scans to insertions, and it depends on the workload. One dial between two structures found the same kind of ratio deciding between a B-tree and a log-structured store, and the block that is not a block listed what a model of pages leaves out of a real machine. That list applies to every page count here: read-ahead makes a sequential scan of adjacent leaves cheaper than its page count suggests, and a chain’s writes to adjacent leaves are sequential too.

As close as a bulk load, without the sort #

The best a B±tree of these keys can look is the tree built by loading them already sorted, every leaf full: 2,048 leaves and three levels. Getting there needs the keys sorted first, and for an index that is being built from a stream there is no “first”. The keys arrive, and they have to be findable as they do.

A chain across the whole parent on the nearly ascending stream ends 2.3% above that bound, 2,096 leaves, and on random insertion 1.1% above it, 2,071 leaves. On the ordered streams a reach of two reaches it exactly. So an incremental rule that looks far enough recovers almost the whole of what a bulk load gives. On the nearly ordered stream it does that for 2.36 pages a key. On random insertion the price is 17.

A bulk load pays for sorting instead. Runs twice as long as memory measured the external sort that loading a large index needs, with its merge passes counted in blocks. For keys that arrive nearly in order that sort is cheap too, because the runs are long. That is the same observation from the other side: when the order is nearly right, both the sort and the chain have little to do. The chain’s advantage is that it never stops the index to do it.

The separator every step rewrites #

Each step of a chain rewrites a separator in the parent, and that has a consequence the page counts understate. The parent is written once per redistribution however many separators change, so its page count stays low. But every separator change is a change a concurrent reader might see halfway. A B±tree that allows concurrent readers during an insertion has to lock or version every leaf a chain touches, and the parent.

A walk of one sibling locks two leaves and a parent, the same footprint as a split. A walk of sixteen locks seventeen leaves. On random insertion at the widest reach, that is the typical redistribution. The adjacent rule’s footprint is fixed. The chain’s grows with the reach, and on random insertion so does the time an insertion holds its locks. Nothing here measures concurrency. It is the reason a real index would cap the reach even where writes are cheap, and the walk histogram is the quantity a cap would be chosen from: on the nearly ascending stream about 99% of walks are four siblings or fewer.

What is settled and what is not #

Settled by building each tree and checking every separator and every key’s order: with leaves of 64 and a fan-out of 64, a reach of one reproduces the adjacent rule exactly. A reach of two fills ascending and descending insertion completely, 2,048 leaves for 131,072 keys, for 2.69 pages a key against 2.05. On random insertion fill rises from 84.3% to 98.9% as the reach goes from one to 64, and pages a key rise from 1.59 to 17.07, with the mean walk reaching sixteen siblings. On a stream with 1% of keys late, fill rises from 84.2% to 97.7% while pages a key rise from 2.25 to 2.36.

Not settled:

Reach across parents. Every chain stops at the parent’s edge. A leaf at the edge of its parent has room on one side only, and a chain that crossed into a neighbouring parent would update two parents and a grandparent. Nothing here measures how much of the fill that is left comes from leaves stranded at parent boundaries.

Deletions. Every workload inserts only. A chain fills leaves close to full, and a tree close to full has no slack for the next wave of inserts after deletions have scattered holes through it. How a chain-filled tree ages under mixed traffic is a separate measurement.

Reads. A fuller tree has fewer leaves to scan and to cache, and the value of that depends on a workload’s reads. The leaf counts here are what a range scan would pay, but no scan is timed.

Still open: a reach that follows the stream #

The two orders ask for opposite reaches. Random insertion wants a small one, because long walks cost more than the leaves they save. A nearly ascending stream wants the whole parent, because walks are short however far the leaf may look. A tree does not know which stream it is receiving, but the walks it has already made tell it. A run of short walks means room is near, and a run of long walks means the neighbourhood is full.

The measurement that follows gives the tree an adaptive reach. It keeps a running mean of recent walk lengths, widens the reach while walks stay short, and narrows it when they lengthen. It measures fill and pages per key on the four orders here and on a stream that changes from random to ascending halfway. The prediction is that the adaptive tree tracks the better fixed reach on each pure stream within a few per cent, and that on the changing stream it beats both fixed reaches. The number to watch is how long it takes to notice the change, measured in insertions.