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 2 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

Named alongside it

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

B-treeDesign parameterInsertion orderNode fillPresortednessAmortisationBlock sizeBlock transferBulk loadingHonest limitMeasured countSpace accounting

All concepts