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

Fanout — where it appears

How many children an internal node of a tree holds, which sets the base of the logarithm in its height. Choosing it to fill one transfer unit is what turns a binary search's log-two into a block-sized log-B, and giving some of it back is what buys a buffer.

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

1100ε — the exponent the fanout is B toelements written per key33445679ε = 1 — the B-tree ·fanout 256 · 3transfers a queryε = 0.5 · fanout 16 · 5a querythe number above eachpoint is what a querycostsB = 256, M = 16,384 (M/B = 64)131,072 random keys

One dial between two structures

A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.

applied · Transfer levels on the path (outline) · transfers actually paid (filled)B = 411 levels · 6.99 transfers · 16,384 blocks residentB = 166 levels · 3.23 transfers · 4,096 blocks residentB = 644 levels · 1.99 transfers · 1,024 blocks residentB = 2563 levels · 1.30 transfers · 256 blocks residentB = 10243 levels · 1.01 transfers · 64 blocks residentbinary search over the same 4,194,304 keys: 20 transfersB = 1024, M = 65,536 (M/B = 64)20× between binary search and the widest tree

A tree with nodes the size of a block

A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.

structures · Transfer 0%25%50%75%100%ln 2mean leaf fillrandom, even splits2,906 leavesrandom, rightmost-split rule2,949 leavesascending, even splits3,971 leavesascending, rightmost-split rule2,048 leavesdescending, even splits4,095 leavesdescending, rightmost-split rule4,095 leavesbulk-loaded from sorted keys2,048 leaves131,072 keys, leaves of 64each bar names its rule

The keys that arrive late

Insert 131,072 keys into a B+-tree in random order and its leaves end up 70.5% full; in ascending order, 51.6%; in descending order, 50.0%. The rule databases use to fix ascending inserts — split a full leaf at its right-hand end — fills them completely, and it does nothing for descending keys. Let one key in a hundred arrive late in an otherwise ascending stream and the rule's leaves fall from 100% to 53.4% full. How much of an index is empty is decided by the order its keys arrived in, and a trickle of disorder undoes the fix.

applied · Transfer

Named alongside it

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

B-treeBlock transferExternal-memory modelTree heightParameter choiceRegimeTrade offAccess patternAmortised analysisBinary searchBinary search treeBuffered tree

All concepts