The same tree at 7 block sizes

The same tree at 7 block sizes

A tree over 262,143 keys, searched at 7 block sizes with the layout fixed. The B-tree was built with nodes of 64 elements and is at its best exactly there; away from it the nodes are the wrong size and it pays for it. The van Emde Boas layout is given neither B nor M, and tracks the best of the others across the whole range — which is the claim worth making about an algorithm with no parameters, and it is a claim about every level of a real memory hierarchy at once rather than about a chosen one.

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

1 essay calls oblivious-across-b. 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.