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

Tree height — where it appears

The longest root-to-leaf path, which bounds a search and which for a randomised structure is a distribution rather than a number. For a randomised structure it is a distribution rather than a number, and the tail of that distribution is what a worst-case guarantee would have to cover.

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

sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

structures · Structure Sorted array (binary search)2 blocksLevel order4 blocksvan Emde Boas2 blocksmemory address, left to right · alternating outlines are blocksB = 8, M = 64 (M/B = 8)4 blocks against 2, for the same 6 comparisons

Two searches, one comparison count

Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.

machine · Machine 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.

Block transferB-treeBinary searchExternal-memory modelFanoutAmortised analysisBinary search treeCost modelParameter choiceRegimeTrade offWorst case

All concepts