Search cost against fanout, n = 4,194,304

Search cost against fanout, n = 4,194,304

A B-tree over 4,194,304 keys at 5 block sizes. The outline is the tree's height — the number of nodes on a root-to-leaf path — and the filled bar is the transfers a search actually paid, averaged over 200 random queries. The two differ because the top levels of the tree are few enough blocks to stay in memory: at B = 1024 the height is 3 and the measured cost is 1.01. Binary search over the same keys costs 20 transfers, and its cost does not depend on B at all.

Drawn at 700 × 380, wide on the page. Everything above is what btree-shape returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

5 essays call btree-shape. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.