van Emde Boas Layout

Pick a block size B = 2^k−1. Somewhere in the vEB recursion is the level whose subtrees have height k = lg(B+1): those chunks are contiguous in memory — each is exactly one block — so a search reads only one per chunk. The shading below is that level, and it changes as you change B.

B-piece: a height-k recursive subtree = one block B-piece on the search path (a block loaded) search path / node visited

Choose k and the number of recursion levels, pick a key, and press Run. Watch the search cross only one shaded chunk at a time.

vEB block loads (I/Os) —

Block B=2^k−1, k

Recursion levels

Key (rank)

—

Delay 600ms

Height is fixed to h = k·2^j so the recursion halves cleanly onto the height-k level and every B-piece is uniform (2^k−1 = B nodes) and block-aligned — the cleanest case, using B = 2^k−1 (not a power of two). The path has length h = log₂N but enters a new B-piece only every k levels, so it touches h/k = log_BN chunks — that is the O(log_BN) bound. For a general B each chunk still fits in ≤ 2 blocks.