Cairn
data structures · trees · O(log n) search (O(log_B n) memory blocks touched, in the idealized cache model, for any block size B)

↩ back to Array-Backed Trees

Van Emde Boas Layout

Not to be confused with the Van Emde Boas Tree elsewhere on this site — a completely different structure for integer predecessor queries. This page is about something else that happens to share the name: a way of arranging any static complete binary tree in memory. The binary heap, Fenwick tree, and segment tree all store a conceptual tree in a flat array using the same trick: root at index 0, and node i's children at 2i+1 and 2i+2. That placement is simple and needs no extra storage, but it says nothing about which array positions end up near each other in actual memory — and for a tree too big to fit in cache, that turns out to matter. The van Emde Boas layout (named by later researchers after the recursive halving trick the other Van Emde Boas tree uses, though it was Harald Prokop's 1999 thesis that actually introduced this layout) rearranges the same tree so that every root-to-leaf path stays within a shrinking sequence of contiguous memory blocks — without the algorithm ever being told how big a "block" is on the machine running it. That's the cache-oblivious part: unlike a B-tree, which is deliberately sized to match a known disk-page or cache-line size, this layout is supposed to get a comparable benefit at every level of the memory hierarchy at once, for any block size, without being tuned to one.

Try it

Both rows below hold the same 15-node complete binary search tree (keys 0 through 14), stored two different ways. The top row is the plain heap layout. The bottom row is the van Emde Boas layout — note how its values aren't in heap order at all; they're grouped into clusters of 3 (the thick borders), each cluster one small subtree laid out contiguously. Pick a target and step through the search on both at once. Watch which row crosses into a new cluster more often — that's the real quantity the layout is trying to minimize, standing in here for "new cache line" at a scale small enough to see by eye.

heap layout (array index 0..14)
van Emde Boas layout (array index 0..14) — thick border = new cluster
Pick a key and press Search, then step through it.

Why it works

The construction is one recursive rule, applied to a complete binary tree of height h: split it into a top subtree of height ⌈h/2⌉ and, for each of the top subtree's bottom-level slots, a separate bottom subtree of height ⌊h/2⌋. Lay the top subtree's nodes out first (recursively, the same way), then lay out each bottom subtree in turn (also recursively), one full block at a time. A tree of height 4 splits into a height-2 top tree (3 nodes) and four height-2 bottom trees (3 nodes each) — exactly the 5 clusters of 3 the demo above draws.

The payoff shows up once you count memory blocks instead of comparisons. Fix any block size B — the algorithm never gets told what it is. Once the recursive split has halved the height enough times that a subtree's node count drops to around B, that whole subtree fits in one block, by construction (it was laid out contiguously). A root-to-leaf search crosses into a new block only when it crosses into a new one of those subtrees, and there are only O(log_B n) of them to cross on any path — compared to the heap layout's O(log n) blocks touched once n is large enough that each level's address range no longer fits in the same block. Nothing in the construction above ever refers to B; the bound holds for whatever block size a given cache, page, or disk happens to use, which is the whole reason this class of technique is called cache-oblivious rather than cache-aware.

Reference implementation

Because the layout gives up the heap layout's free 2i+1/2i+2 child arithmetic, every node has to carry its two children's array positions explicitly. The recursive layout itself is a one-time permutation, computed from a node's position in the conceptual heap-indexed tree to its real position in the flat array:

// Position of the i-th node (0-indexed, left-to-right) at `depth` levels below
// `root` in the conceptual heap-indexed tree.
function descendant(root, depth, i) {
  let idx = root;
  for (let b = depth - 1; b >= 0; b--) {
    idx = 2 * idx + 1 + ((i >> b) & 1);
  }
  return idx;
}

// Fills map[heapIndex] = flatIndex for every node of the complete subtree of
// `height` rooted at heapIndex, starting at flat offset `offset`. Returns the
// next free offset.
function vebLayout(heapIndex, height, offset, map) {
  if (height === 0) return offset;
  if (height === 1) { map[heapIndex] = offset; return offset + 1; }
  const topHeight = Math.ceil(height / 2);
  const bottomHeight = height - topHeight;
  offset = vebLayout(heapIndex, topHeight, offset, map);     // top subtree first
  const numSlots = 1 << topHeight;
  for (let i = 0; i < numSlots; i++) {
    offset = vebLayout(descendant(heapIndex, topHeight, i), bottomHeight, offset, map);
  }
  return offset;
}

Building the actual search structure means walking the same conceptual tree once more, placing each node's value and its two children's flat positions (via the map above) at that node's own flat offset — the demo above and the benchmark below both build exactly this, padded to 4 integers per node (value, left, right, unused) so a node's offset is a cheap bit shift (flatIndex << 2) rather than a multiply by 3.

Pitfalls

The textbook win didn't show up, measured in JavaScript. The argument above is real and has been demonstrated in native code elsewhere, so the expectation going into this page was straightforward: build the plain heap layout and this layout over the same large complete tree, run random-key searches against both, and watch the recursive layout pull ahead once n outgrows cache. Built both (plus plain sorted-array binary search as a third baseline) as flat Int32Arrays, self-tested against an exhaustive scan first (every key, every layout, 0 mismatches at n = 4,095), then benchmarked real search time (median of 7 timed batches of 200,000 random-key queries each, after a warm-up pass) from n = 16,383 up to n = 67,108,863 — the array layout alone is over 1GB at the largest size, far past any real CPU's cache:

nsorted arrayheap layoutvan Emde Boasheap vs. vEB
16,38380.6ns76.6ns94.5ns1.23× slower
262,143200.8ns136.8ns200.7ns1.47× slower
1,048,575245.7ns159.7ns341.8ns2.14× slower
4,194,303327.3ns227.2ns471.8ns2.08× slower
16,777,215593.2ns320.8ns663.9ns2.07× slower
67,108,8631,017.7ns392.7ns955.9ns2.44× slower

The heap layout won at every size tested, not just the small ones where cache effects shouldn't matter yet — and the gap widens and settles around 2×-2.4× once n passes roughly a million, rather than closing. Run twice independently (different process, different random queries) to check it wasn't noise: same shape both times, gap stabilizing in the same 2×-2.4× range. The van Emde Boas layout also never built a reliable lead over plain sorted-array binary search either — the ratio between them bounced from 0.67× to 1.11× across the two runs with no consistent direction, nowhere near a clear win.

Checked one obvious confound before trusting any of this: padding each node to 4 integers (value, left, right, unused) so its own offset is a bit shift instead of a multiply by 3 was meant to rule out "the gap is just multiply-vs-shift arithmetic, not memory behavior" — and it made the gap wider, not narrower, ruling that explanation out rather than confirming it. The most likely real explanation is structural, not a benchmarking mistake: the heap layout's child address is computed (one shift, one add, no extra memory read), while this layout — having given up that arithmetic relationship on purpose — has to store and fetch an explicit child pointer at every level, on a node that's already 4× the heap layout's bytes. Every level of every search, on every layout, also revisits the same small set of near-root addresses regardless of which key is being searched for — those addresses are the ones most likely to stay hot in cache across a whole benchmark run regardless of layout, which may simply erase most of the advantage this specific construction is designed to provide at the scales reachable here. This result is specific to a garbage-collected, JIT-compiled runtime measuring wall-clock time, not a claim that the underlying cache-complexity argument in Why it works is wrong — the demo above still shows the real, construction-level property (fewer cluster crossings) exactly as designed, and the published results this layout is based on were measured in native code with direct control over memory layout that a JavaScript typed array doesn't give you. Reported here because the site's own rule is to measure before stating a comparative claim, not to only report the measurements that confirm the expected story.

Complexity

Time: O(log n) per search, identical to every other layout of the same tree — the layout changes where memory gets touched, not how many comparisons a search makes. Memory transfers: O(log_B n) in the idealized cache model, for any block size B, against the heap layout's O(log n) — the whole point of the construction, confirmed structurally by the demo's cluster-crossing count, even though it didn't translate into a measured wall-clock win above. Space: exactly 4n integers in the implementation above (value plus two child pointers plus one pad slot) against n for either the heap or sorted-array layout — a real, standing 4× memory cost for a property that, per the measurements above, didn't pay for itself at any size tested in this environment. The structure is also static: nothing above supports inserting or deleting a key without rebuilding the layout from scratch, unlike a balanced BST or a B-tree.

See Same Big-O, Different Speed for the site's broader take on cache locality separating structures with identical asymptotic bounds, and Choosing a Search Tree for how this entry's very different trade-offs sit alongside the rest of the site's eighteen other Array-Backed Trees and Node-Linked Trees structures.