Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Index maintenance — where it appears

The work an index does to stay correct and compact as keys are inserted, moved and removed, as distinct from the work of answering queries. Splits, redistributions and rewritten separators are its units, and it is usually paid in pages written at insertion time.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Also named here as node fill — the same set of essays touches all of them, so they are one junction rather than several.

50%60%70%80%90%100%0%1%2%5%10%25%50%share of keys arriving latemean leaf filleven splitsrightmost-split rulesibling first, two into threeln 2131,072 keys, leaves of 64late keys arrive at a random later point

The sibling a full leaf asks first

The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.

applied · Transfer 6080100how far a full leaf looks for room, in siblingsmean leaf fill, per cent12481664randomascendingdescendingascending, 1% late131,072 keys · leaves of 64 · fan-out 64a reach of 1 is the adjacent-sibling rule

A key passed along the row

A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.

applied · Transfer 2122232451015pages written per key insertedleaves in the finished tree, in hundreds1241664target 1target 2target 8fixed reach (digits:siblings)reach following the walks131,072 keys, leaves of 64, fan-out 64window of 64 overflows

A reach that follows the stream

A full B+-tree leaf that passes keys along its siblings wants a short reach on random insertion and the whole parent on a nearly ordered stream, and a tree is never told which it is receiving. Let the reach double after every 64 overflows whose walks averaged two siblings or less and halve otherwise, and it finds the whole parent on every ordered stream. On random keys it lands on the fixed reaches' own frontier. On a stream that turns from random to ordered halfway it beats every fixed reach, by 57 leaves at the same writes. It notices a turn to random in 62 insertions and a turn to order in 779. Below a target of 1.75 siblings it thrashes on ordered keys.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

B-treeDesign parameterInsertion orderNode fillPresortednessBlock transferHonest limitMeasured countTrade offWrite amplificationAmortisationBlock size

All concepts