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.
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.
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.
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.
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:
| n | sorted array | heap layout | van Emde Boas | heap vs. vEB |
|---|---|---|---|---|
| 16,383 | 80.6ns | 76.6ns | 94.5ns | 1.23× slower |
| 262,143 | 200.8ns | 136.8ns | 200.7ns | 1.47× slower |
| 1,048,575 | 245.7ns | 159.7ns | 341.8ns | 2.14× slower |
| 4,194,303 | 327.3ns | 227.2ns | 471.8ns | 2.08× slower |
| 16,777,215 | 593.2ns | 320.8ns | 663.9ns | 2.07× slower |
| 67,108,863 | 1,017.7ns | 392.7ns | 955.9ns | 2.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.
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.