van Emde Boas Layout

Why van Emde Boas Layout Matters

A balanced binary search tree takes only logarithmically many comparisons, yet each comparison can force a fetch from a different memory block. The logical path may be short while its records are scattered. Breadth-first storage places upper levels together but spreads deeper path segments across progressively wider levels.

The van Emde Boas layout, usually abbreviated vEB layout, is a recursive order for storing tree nodes in an array. Split the tree near the middle of its height, store the top piece recursively, then store the bottom pieces recursively from left to right. Nearby stages of a search become grouped at several scales without choosing a target block size.

This lesson builds a static perfect binary search tree from sorted unique keys, stores the same tree in breadth-first and vEB orders, remaps its child links, and compares exact point searches using a read-only block-cache simulator. The comparison paths and membership answers stay the same. The physical positions and transfer counts change.

The idea supports static search indexes and is a building block in cache-oblivious search structures. It extends the earlier B/B+ tree lesson's emphasis on comparisons per transfer, while using binary nodes arranged recursively instead of selecting a page-sized fanout. You will see the entire layout construction, every record and link, all accesses of a small query batch, and three runnable implementations.

Keep the names distinct. A vEB layout is a memory arrangement for a normal search tree. A van Emde Boas integer dictionary is a different data structure with universe-based recursion and different operations/bounds. This lesson's binary search still performs $O(\log N)$ comparisons; it does not acquire an $O(\log\log U)$ search bound merely from its layout name.

Core Concepts and Terminology

The input is a strictly increasing sequence of $N$ integer keys. To keep topology, rounding, and the proof explicit, the executable lesson accepts an empty sequence or a perfect binary tree size $$ N=2^h-1,\qquad 0\le h\le10. $$ Here height $h$ counts node levels: a singleton has height one, and an empty tree height zero. Every internal node has two children and every leaf has the same depth. This restriction belongs to the supplied implementation, not to the full range of vEB-layout techniques. General-size adaptations are discussed later.

The sorted input defines the logical BST: its middle key is the root, with recursively chosen middles of the left and right halves. An inorder traversal returns the original sorted sequence. For keys $1$ through $15$, the root is $8$, its children are $4,12$, and its leaves are the odd keys.

Logical identity and physical position are separate. Assign a node its one-based heap ID: root $1$, left child $2i$, right child $2i+1$. This is a convenient construction label, not a vEB navigation formula. Physical positions are zero-based array indices. If ids[p]=i, the inverse map satisfies position[i]=p. Breadth-first storage has position[i]=i-1; vEB storage generally does not.

Each stored record contains (key,left,right), where child fields are physical positions or $-1$ for absence. The output layout includes the reordered records and their logical IDs. A query returns exact membership plus its visited keys, positions, block IDs, hit/miss events, and new block reads. No updates or range-query interface are implemented.

Recursive pieces and the chosen convention. For $h\gt1$, choose $$ t=\lfloor h/2\rfloor,\qquad b=h-t=\lceil h/2\rceil. $$ The top $t$ levels contain $2^t-1$ nodes. Below them are $2^t$ bottom trees, each of height $b$ and size $2^b-1$. Their sizes add to the original: $$ (2^t-1)+2^t(2^b-1)=2^{t+b}-1=N. $$ Recursively lay out the top first, then the bottom trees in left-to-right order. A height-one piece emits its single node. Floor/ceiling conventions differ across presentations, so odd-height permutations must be compared against the stated rule. In this lesson, height three splits as top one and bottom two.

A recursive piece need not contain every descendant of its root in the original tree: the top piece is truncated at the cut. Each piece generated by this layout recursion occupies one contiguous interval. This does not mean every ordinary rooted BST subtree is contiguous in the final array. For example, the left subtree of key eight includes physical position one and positions three through eight, with key twelve at position two between them.

The memory observer. Let $B$ be records per transfer block and $Q$ the number of resident blocks. Physical position $p$ maps to block $\lfloor p/B\rfloor$ and slot $p\bmod B$. Each record has three logical eight-byte fields, so blocks transfer $24B$ modeled bytes and cache payload capacity is $24BQ$ bytes. These are accounting widths, not Python object sizes, Java object overhead, or C++ sizeof(Node). The simulator counts one node-record access per visited node; its key and child fields are read from the fetched record.

The cache is fully associative and uses LRU replacement. A hit makes the block most recent. A miss copies its $B$ records into a cache payload, evicting the least recent block if necessary. The final partial block is padded with dummy records, but searches never visit padding. Search is read only, so all evictions are clean and $$ \text{transfers}=\text{block reads},\qquad \text{accesses}=\text{hits}+\text{block reads}. $$ Construction, initial backing storage, trace arrays, instructions, metadata, and temporary scalar work are outside this query-data cache model. Each layout starts with its own cold cache. By default, queries retain cache contents across the batch; optional cold_each=True clears residents before each query without resetting accumulated counters. Clearing for a new experiment is not counted as a capacity eviction.

Theory versus the observer. The classical static-layout search bound is $O(1+\log_{B+1}N)$ transfers for fixed-size records under suitable two-level caching assumptions. Bender, Demaine, and Farach-Colton, Section 2.1, discuss the layout and search analysis; their later dynamic structures require additional machinery. Our finite LRU counts are direct measurements of a specified model, not a claim that every query strictly improves over every other layout.

How van Emde Boas Layout Works, Step by Step

1. Build the logical tree. For a sorted interval [lo,hi), put its middle key at the supplied heap ID. Recurse on the left and right halves with IDs $2i$ and $2i+1$. An empty interval returns. This temporary heap-indexed key array defines the BST, independently of physical placement.
2. Emit the layout permutation. For a nonempty height-one piece, append its root ID. Otherwise compute $t=\lfloor h/2\rfloor$ and $b=h-t$, emit the top piece rooted at the same ID with height $t$, then emit every bottom piece with height $b$ from left to right.
3. Find bottom roots without traversing keys. Appending all $t$-bit left/right path suffixes to a heap ID root gives consecutive IDs

$$ \text{root}\cdot2^t,\;\ldots,\;(\text{root}+1)2^t-1. $$ The code iterates over this half-open range using shifts. These are logical IDs; it never applies this formula to physical positions. Emitting the top piece stops at its assigned height and does not follow edges into the bottom pieces. 4. Build the inverse map. After all $N$ IDs have been emitted, assign position[id]=p for each array position $p$. Do not try to resolve a later child's physical address before the complete mapping is available. 5. Materialize records. For each ID in the emitted order, store its key and the mapped positions of its two logical children. A child with ID greater than $N$ becomes $-1$. The root's position is zero in both supported layouts; an empty tree has no root. 6. Search using remapped links. Start at position zero. Load the current record through the observer, compare the target with its key, and return success on equality. Otherwise follow the stored left or right position. A $-1$ link means failure without another memory access. Physical adjacency is irrelevant to choosing a child. 7. Account for the cache boundary. Begin a separate cold cache for each layout. Retain residents across queries unless cold-per-query mode was requested. Record the difference in cumulative reads before and after each query. No flush is needed because searches never dirty records.

For the diagram's height-four tree, the first top piece emits heap IDs $1,2,3$, which hold keys $8,4,12$. The bottom roots are IDs $4,5,6,7$, holding keys $2,6,10,14$. Each height-two bottom piece emits its root, left leaf, and right leaf. This is a split of levels, not a split into equal halves of the sorted key array.

Construction and navigation never inspect block size or capacity. The observer receives $B,Q$ only after the layout has been chosen. Changing the cache geometry changes the measured events, while the IDs, records, membership answers, and visited key paths stay fixed.

flowchart TD
    A["Validate sorted unique keys and perfect size"] --> B["Assign keys to logical heap IDs"]
    B --> C["Emit layout IDs; then build inverse positions"]
    C --> D["Store key and remapped child positions"]
    D --> E["For each query: start at root, or null if empty"]
    E --> F{"Current position null?"}
    F -->|Yes| G["Report absent; proceed to next query"]
    F -->|No| H["Load record through block cache"]
    H --> I{"Target equals key?"}
    I -->|Yes| J["Report present; proceed to next query"]
    I -->|No| K["Follow stored left or right position"]
    K --> F
    C -.-> L{"Emit: height one?"}
    L -->|Yes| M["Append logical root ID; return"]
    L -->|No| N["Recursively emit top, then bottom pieces left to right; return"]

Worked Example with a Full Trace

Use sorted keys $[1,2,\ldots,15]$, height $h=4$, blocks of $B=3$ records, and a cache of $Q=2$ blocks. Query the sequence $[1,7,15,0,8,1]$ with residents retained between queries. Both layouts start cold and use the same logical tree.

Complete construction trace. The root call emits the height-two top piece, then four height-two bottom pieces. Each height-two call emits its root as a height-one piece, then its two leaf pieces. The six internal layout calls are the height-four root call and those five height-two calls; fifteen height-one calls append the fifteen nodes. Thus there are twenty-one layout calls in this example. The emitted chunks are:

Reading the rows in order gives every appended prefix. The resulting ID permutation is $$ [1,2,3,4,8,9,5,10,11,6,12,13,7,14,15]. $$ After the inverse map is complete, the final records are as follows. Left/right fields are physical positions, and $-1$ means null. Record position is also its append ordinal minus one, so the table lists all fifteen emitted values and all resolved links.

For example, logical ID five is key six. Its vEB position is six, with children at positions seven and eight. Key four at position one therefore stores right child six, even though the breadth-first formula would choose position four.

Every query access. In the next table, M means a miss that reads one full block; H means a hit. The cache state is least to most recent. A victim is a clean block removed to make room; a dash means no victim. Each visited record is loaded once. Queries restart at the root, and finding a null link after the last record adds no access.

The first search loads block zero for keys eight and four, then block one for keys two and one. It succeeds with two reads and leaves [0,1] resident. Query seven reuses block zero, fills block two, evicts block one, and succeeds after reading keys eight, four, six, seven. Query fifteen fills block four and evicts block two. Query zero returns absent after comparing eight, four, two, one; following one's null left link costs no extra transfer.

Query eight then hits the root block and returns immediately. The last query one hits every visited block. Its path has four comparisons and zero new reads, illustrating why comparisons and transfers are different measures. The returned memberships are $$ [\text{true},\text{true},\text{true},\text{false},\text{true},\text{true}]. $$ For the breadth-first baseline, the per-query block sequences are $[0,0,1,2]$, $[0,0,1,3]$, $[0,0,2,4]$, $[0,0,1,2]$, $[0]$, and $[0,0,1,2]$. The corresponding event strings are MHMM, MHMM, MHMM, MHMM, M, and HHMM, giving reads $[3,3,3,3,1,2]$. Both layouts perform twenty-one node accesses, but BFS has fifteen reads and thirteen evictions; vEB has five reads and three evictions. All evictions are clean, and both peak at two resident blocks.

At seventy-two logical bytes per read, those totals are $1080$ bytes for BFS and $360$ for vEB. This particular warm batch saves ten block reads. It is a model result for the stated query order and geometry, not a universal speedup or a measurement of hardware runtime. These five vEB clusters happen to align exactly with the three-record blocks; the general layout definition does not require that alignment.

Implementation in Python, C++, and Java

Each panel is a complete program implementing the same perfect BST, layout convention, physical-link remapping, read-only LRU cache, query batch, and output. Run Python normally, compile C++ as C++17, or save the Java panel as Main.java and run Main. Each prints the vEB permutation, per-query paths and events, and total block transfers for both layouts.

Public input contract. build(keys,veb) returns the reordered records and heap IDs. run(keys,queries,block_nodes,frames,veb,cold_each) builds the layout, then performs the batch. Python and C++ default to vEB layout and a warm shared batch; Java requires both boolean options explicitly. False for veb selects breadth-first order of the same logical BST.

Keys must be strictly increasing integers within $[-10^6,10^6]$. Accepted key counts are $0,1,3,7,\ldots,1023$. The batch has at most $128$ query targets, each in the same integer range. Require $1\le B\le64$ and $1\le Q\le128$. Both input containers remain unchanged. The contract expects a non-null flat list/vector/array; unrelated container objects and null references are outside it.

Invalid cache limits produce PARAMETER. The builder next rejects unsupported key counts as SIZE, invalid key values as VALUE, and duplicate/descending keys as ORDER. The batch then rejects excessive query count or invalid query values as QUERY. Thus a malformed tree is reported before a malformed query when both are present. Numeric size bounds are checked before shifts or child-address construction.

Python additionally requires exact integer parameter/key/query types and exact booleans for both modes; booleans and floats are rejected as keys/targets. Invalid parameter/mode types give PARAMETER. C++ uses long long keys/targets, int indices, and bool options; Java uses long keys/targets, int indices, and boolean options. Bounds make every shift and physical position safe in these programs.

Read one record per node. The cache fetches a block payload containing copies of records, then returns the selected record. Its key comparison and child selection use that record without additional node accesses. A final partial block is padded to $B$ records so every miss represents the same modeled transfer size. Construction and printing do not go through the query cache. Stored child positions are included in the record footprint; a lookup does not consult the temporary heap-ID or inverse-position arrays.

Empty input yields no records and every query returns false with an empty path and zero accesses/reads. An empty query batch likewise performs zero reads even if a layout was built. A singleton visits its one node; equality succeeds, while a different target follows a null link and fails. In cold-per-query mode, clearing residents preserves aggregate counters and the batch peak, and does not increment capacity-eviction count.

The programs deliberately expose extra trace information for instruction. An ordinary point lookup can return only a boolean and use constant scalar working storage. The layout is static: changing the keys/topology calls for rebuilding or a separately designed dynamic structure.

from dataclasses import dataclass
from collections import OrderedDict


@dataclass(frozen=True)
class Node:
    key: int
    left: int
    right: int


@dataclass
class Layout:
    nodes: list
    ids: list


@dataclass
class Query:
    found: bool
    keys: list
    positions: list
    blocks: list
    events: str
    reads: int


@dataclass
class Result:
    layout: Layout
    queries: list
    accesses: int
    hits: int
    reads: int
    evictions: int
    peak_blocks: int


def build(keys, veb=True):
    if type(veb) is not bool:
        raise ValueError("PARAMETER")
    n = len(keys)
    if n > 1023 or ((n + 1) & n) != 0:
        raise ValueError("SIZE")
    if any(type(x) is not int or not -1000000 <= x <= 1000000 for x in keys):
        raise ValueError("VALUE")
    if any(keys[i - 1] >= keys[i] for i in range(1, n)):
        raise ValueError("ORDER")
    heap = [0] * (n + 1)

    def assign(lo, hi, node):
        if lo == hi:
            return
        mid = (lo + hi) // 2
        heap[node] = keys[mid]
        assign(lo, mid, 2 * node)
        assign(mid + 1, hi, 2 * node + 1)

    assign(0, n, 1)
    ids = []

    def emit(root, height):
        if height == 1:
            ids.append(root)
            return
        top = height // 2
        bottom = height - top
        emit(root, top)
        for child in range(root << top, (root + 1) << top):
            emit(child, bottom)

    if n:
        if veb:
            emit(1, (n + 1).bit_length() - 1)
        else:
            ids = list(range(1, n + 1))
    position = [-1] * (n + 1)
    for p, node in enumerate(ids):
        position[node] = p
    nodes = [Node(heap[node], position[2 * node] if 2 * node <= n else -1,
                  position[2 * node + 1] if 2 * node + 1 <= n else -1)
             for node in ids]
    return Layout(nodes, ids)


class Cache:
    def __init__(self, nodes, block_nodes, frames):
        self.nodes, self.block_nodes, self.frames = nodes, block_nodes, frames
        self.blocks = OrderedDict()
        self.accesses = self.hits = self.reads = self.evictions = self.peak_blocks = 0

    def load(self, position):
        assert 0 <= position < len(self.nodes)
        self.accesses += 1
        block = position // self.block_nodes
        if block in self.blocks:
            self.hits += 1
            self.blocks.move_to_end(block)
        else:
            self.reads += 1
            if len(self.blocks) == self.frames:
                self.blocks.popitem(last=False)
                self.evictions += 1
            start = block * self.block_nodes
            payload = [Node(v.key, v.left, v.right)
                       for v in self.nodes[start:start + self.block_nodes]]
            payload += [Node(0, -1, -1)] * (self.block_nodes - len(payload))
            self.blocks[block] = payload
            self.peak_blocks = max(self.peak_blocks, len(self.blocks))
        return self.blocks[block][position % self.block_nodes]


def run(keys, queries, block_nodes, frames, veb=True, cold_each=False):
    if (type(block_nodes) is not int or type(frames) is not int
            or type(veb) is not bool or type(cold_each) is not bool
            or not 1 <= block_nodes <= 64 or not 1 <= frames <= 128):
        raise ValueError("PARAMETER")
    layout = build(keys, veb)
    if (len(queries) > 128 or
            any(type(x) is not int or not -1000000 <= x <= 1000000 for x in queries)):
        raise ValueError("QUERY")
    cache = Cache(layout.nodes, block_nodes, frames)
    answers = []
    for target in queries:
        if cold_each:
            cache.blocks.clear()
        before = cache.reads
        path, positions, blocks, events = [], [], [], []
        p = 0 if layout.nodes else -1
        found = False
        while p != -1:
            old_reads = cache.reads
            node = cache.load(p)
            path.append(node.key)
            positions.append(p)
            blocks.append(p // block_nodes)
            events.append('M' if cache.reads != old_reads else 'H')
            if target == node.key:
                found = True
                break
            p = node.left if target < node.key else node.right
        answers.append(Query(found, path, positions, blocks, ''.join(events),
                             cache.reads - before))
    return Result(layout, answers, cache.accesses, cache.hits, cache.reads,
                  cache.evictions, cache.peak_blocks)


def compact(values):
    return '[' + ','.join(map(str, values)) + ']'


def show(label, result):
    print(f"{label} accesses={result.accesses} hits={result.hits} "
          f"block_reads={result.reads} transfers={result.reads} "
          f"evictions={result.evictions} peak_blocks={result.peak_blocks}")


def main():
    keys = list(range(1, 16))
    queries = [1, 7, 15, 0, 8, 1]
    bfs = run(keys, queries, 3, 2, False)
    veb = run(keys, queries, 3, 2, True)
    assert [q.found for q in bfs.queries] == [q.found for q in veb.queries]
    print("nodes=15 height_levels=4 block_nodes=3 cache_blocks=2 cold_each=false")
    print("record_bytes=24 block_bytes=72 cache_bytes=144 equal=true")
    print("veb_heap_ids=" + compact(veb.layout.ids))
    print("veb_keys=" + compact([n.key for n in veb.layout.nodes]))
    for target, a, b in zip(queries, bfs.queries, veb.queries):
        print(f"q={target} found={str(b.found).lower()} keys={compact(b.keys)} "
              f"veb_positions={compact(b.positions)} veb_blocks={compact(b.blocks)} "
              f"veb_events={b.events} bfs_reads={a.reads} veb_reads={b.reads}")
    show("bfs", bfs)
    show("veb", veb)


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <list>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
using Word = long long;
struct Node { Word key; int left, right; };
struct Layout { vector<Node> nodes; vector<int> ids; };
struct Query {
    bool found;
    vector<Word> keys;
    vector<int> positions, blocks;
    string events;
    int reads;
};
struct Result {
    Layout layout;
    vector<Query> queries;
    int accesses, hits, reads, evictions, peak_blocks;
};
Layout build(const vector<Word>& keys, bool veb = true) {
    if (keys.size() > 1023) throw invalid_argument("SIZE");
    int n = static_cast<int>(keys.size());
    if (((n + 1) & n) != 0) throw invalid_argument("SIZE");
    for (Word x : keys) if (x < -1000000 || x > 1000000) throw invalid_argument("VALUE");
    for (int i=1;i<n;++i) if (keys[i-1]>=keys[i]) throw invalid_argument("ORDER");
    vector<Word> heap(n+1);
    function<void(int,int,int)> assign = [&](int lo,int hi,int node) {
        if (lo == hi) return;
        int mid = (lo+hi)/2;
        heap[node] = keys[mid];
        assign(lo,mid,2*node); assign(mid+1,hi,2*node+1);
    };
    assign(0,n,1);
    vector<int> ids;
    function<void(int,int)> emit = [&](int root,int height) {
        if (height == 1) { ids.push_back(root); return; }
        int top = height/2, bottom = height-top;
        emit(root,top);
        for (int child=(root<<top);child<((root+1)<<top);++child) emit(child,bottom);
    };
    int height=0;
    for (int size=n+1;size>1;size/=2) ++height;
    if(n) {
        if(veb) emit(1,height);
        else for(int i=1;i<=n;++i) ids.push_back(i);
    }
    vector<int> position(n+1,-1);
    for(int p=0;p<n;++p) position[ids[p]]=p;
    vector<Node> nodes;
    for(int id:ids) nodes.push_back(Node{heap[id],2*id<=n?position[2*id]:-1,
                                       2*id+1<=n?position[2*id+1]:-1});
    return {move(nodes),move(ids)};
}
struct Block {
    vector<Node> payload;
    list<int>::iterator position;
};
struct Cache {
    const vector<Node>& nodes;
    int block_nodes, frames;
    list<int> lru;
    unordered_map<int,Block> blocks;
    int accesses=0, hits=0, reads=0, evictions=0, peak_blocks=0;
    Cache(const vector<Node>& n,int b,int q):nodes(n),block_nodes(b),frames(q) {}
    Cache(const Cache&)=delete;
    Cache& operator=(const Cache&)=delete;
    void clear() { blocks.clear(); lru.clear(); }
    Node load(int p) {
        assert(p>=0 && p<static_cast<int>(nodes.size()));
        ++accesses;
        int id=p/block_nodes;
        auto it=blocks.find(id);
        if(it!=blocks.end()) { ++hits; lru.splice(lru.end(),lru,it->second.position); }
        else {
            ++reads;
            if(static_cast<int>(blocks.size())==frames) {
                blocks.erase(lru.front()); lru.pop_front(); ++evictions;
            }
            int start=id*block_nodes;
            vector<Node> payload(block_nodes,Node{0,-1,-1});
            copy(nodes.begin()+start,nodes.begin()+min(start+block_nodes,static_cast<int>(nodes.size())),payload.begin());
            lru.push_back(id);
            it=blocks.emplace(id,Block{move(payload),prev(lru.end())}).first;
            peak_blocks=max(peak_blocks,static_cast<int>(blocks.size()));
        }
        return it->second.payload[p%block_nodes];
    }
};
Result run(const vector<Word>& keys,const vector<Word>& queries,int block_nodes,
           int frames,bool veb=true,bool cold_each=false) {
    if(block_nodes<1 || block_nodes>64 || frames<1 || frames>128)
        throw invalid_argument("PARAMETER");
    Layout layout=build(keys,veb);
    if(queries.size()>128) throw invalid_argument("QUERY");
    for(Word x:queries) if(x < -1000000 || x > 1000000) throw invalid_argument("QUERY");
    Cache cache(layout.nodes,block_nodes,frames);
    vector<Query> answers;
    for(Word target:queries) {
        if(cold_each) cache.clear();
        int before=cache.reads, p=layout.nodes.empty()?-1:0;
        Query answer{false, {}, {}, {}, "", 0};
        while(p!=-1) {
            int old_reads=cache.reads;
            Node node=cache.load(p);
            answer.keys.push_back(node.key); answer.positions.push_back(p);
            answer.blocks.push_back(p/block_nodes);
            answer.events += cache.reads!=old_reads?'M':'H';
            if(target==node.key) { answer.found=true; break; }
            p=target<node.key?node.left:node.right;
        }
        answer.reads=cache.reads-before; answers.push_back(move(answer));
    }
    return {move(layout),move(answers),cache.accesses,cache.hits,cache.reads,cache.evictions,cache.peak_blocks};
}
template<class T> string compact(const vector<T>& values) {
    string s="[";
    for(size_t i=0;i<values.size();++i) { if(i)s+=','; s+=to_string(values[i]); }
    return s+"]";
}
void show(const string& label,const Result& r) {
    cout<<label<<" accesses="<<r.accesses<<" hits="<<r.hits<<" block_reads="<<r.reads
        <<" transfers="<<r.reads<<" evictions="<<r.evictions<<" peak_blocks="<<r.peak_blocks<<'\n';
}
int main() {
    vector<Word> keys; for(int i=1;i<=15;++i)keys.push_back(i);
    vector<Word> queries{1,7,15,0,8,1};
    Result bfs=run(keys,queries,3,2,false),veb=run(keys,queries,3,2,true);
    for(size_t i=0;i<queries.size();++i) assert(bfs.queries[i].found==veb.queries[i].found);
    cout<<"nodes=15 height_levels=4 block_nodes=3 cache_blocks=2 cold_each=false\n"
        <<"record_bytes=24 block_bytes=72 cache_bytes=144 equal=true\n"
        <<"veb_heap_ids="<<compact(veb.layout.ids)<<'\n';
    vector<Word> layout_keys;for(Node n:veb.layout.nodes)layout_keys.push_back(n.key);
    cout<<"veb_keys="<<compact(layout_keys)<<'\n';
    for(size_t i=0;i<queries.size();++i) {
        const Query& a=bfs.queries[i];const Query& b=veb.queries[i];
        cout<<"q="<<queries[i]<<" found="<<(b.found?"true":"false")<<" keys="<<compact(b.keys)
            <<" veb_positions="<<compact(b.positions)<<" veb_blocks="<<compact(b.blocks)
            <<" veb_events="<<b.events<<" bfs_reads="<<a.reads<<" veb_reads="<<b.reads<<'\n';
    }
    show("bfs",bfs);show("veb",veb);
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;

public class Main {
    static final class Node {
        final long key;
        final int left,right;
        Node(long k,int l,int r) { key=k;left=l;right=r; }
    }
    static final class Layout {
        final Node[] nodes;
        final int[] ids;
        Layout(Node[] n,int[] i) { nodes=n;ids=i; }
    }
    static final class Query {
        boolean found;
        final List<Long> keys=new ArrayList<>();
        final List<Integer> positions=new ArrayList<>(),blocks=new ArrayList<>();
        String events="";
        int reads;
    }
    static final class Result {
        final Layout layout;
        final List<Query> queries;
        final int accesses,hits,reads,evictions,peakBlocks;
        Result(Layout l,List<Query> q,Cache c) {
            layout=l;queries=q;accesses=c.accesses;hits=c.hits;reads=c.reads;
            evictions=c.evictions;peakBlocks=c.peakBlocks;
        }
    }
    static void assign(long[] keys,long[] heap,int lo,int hi,int node) {
        if(lo==hi)return;
        int mid=(lo+hi)/2;heap[node]=keys[mid];
        assign(keys,heap,lo,mid,2*node);assign(keys,heap,mid+1,hi,2*node+1);
    }
    static void emit(int root,int height,List<Integer> ids) {
        if(height==1) { ids.add(root);return; }
        int top=height/2,bottom=height-top;
        emit(root,top,ids);
        for(int child=(root<<top);child<((root+1)<<top);++child)emit(child,bottom,ids);
    }
    static Layout build(long[] keys,boolean veb) {
        int n=keys.length;
        if(n>1023 || ((n+1)&n)!=0) throw new IllegalArgumentException("SIZE");
        for(long x:keys) if(x < -1000000 || x > 1000000) throw new IllegalArgumentException("VALUE");
        for(int i=1;i<n;++i)if(keys[i-1]>=keys[i])throw new IllegalArgumentException("ORDER");
        long[] heap=new long[n+1];assign(keys,heap,0,n,1);
        List<Integer> order=new ArrayList<>();
        int height=0;for(int size=n+1;size>1;size/=2)++height;
        if(n!=0) {
            if(veb)emit(1,height,order);
            else for(int i=1;i<=n;++i)order.add(i);
        }
        int[] ids=new int[n],position=new int[n+1];Arrays.fill(position,-1);
        for(int p=0;p<n;++p) { ids[p]=order.get(p);position[ids[p]]=p; }
        Node[] nodes=new Node[n];
        for(int p=0;p<n;++p) {
            int id=ids[p];
            nodes[p]=new Node(heap[id],2*id<=n?position[2*id]:-1,2*id+1<=n?position[2*id+1]:-1);
        }
        return new Layout(nodes,ids);
    }
    static final class Cache {
        final Node[] nodes;
        final int blockNodes,frames;
        final LinkedHashMap<Integer,Node[]> blocks=new LinkedHashMap<>(16,0.75f,true);
        int accesses,hits,reads,evictions,peakBlocks;
        Cache(Node[] n,int b,int q) { nodes=n;blockNodes=b;frames=q; }
        Node load(int p) {
            if(p<0 || p>=nodes.length)throw new AssertionError("position");
            ++accesses;
            int id=p/blockNodes;Node[] payload=blocks.get(id);
            if(payload!=null)++hits;
            else {
                ++reads;
                if(blocks.size()==frames) { blocks.remove(blocks.keySet().iterator().next());++evictions; }
                payload=new Node[blockNodes];int start=id*blockNodes;
                for(int i=0;i<blockNodes;++i) {
                    Node v=start+i<nodes.length?nodes[start+i]:new Node(0,-1,-1);
                    payload[i]=new Node(v.key,v.left,v.right);
                }
                blocks.put(id,payload);peakBlocks=Math.max(peakBlocks,blocks.size());
            }
            return payload[p%blockNodes];
        }
    }
    static Result run(long[] keys,long[] queries,int blockNodes,int frames,boolean veb,boolean coldEach) {
        if(blockNodes<1 || blockNodes>64 || frames<1 || frames>128)throw new IllegalArgumentException("PARAMETER");
        Layout layout=build(keys,veb);
        if(queries.length>128)throw new IllegalArgumentException("QUERY");
        for(long x:queries)if(x < -1000000 || x > 1000000)throw new IllegalArgumentException("QUERY");
        Cache cache=new Cache(layout.nodes,blockNodes,frames);List<Query> answers=new ArrayList<>();
        for(long target:queries) {
            if(coldEach)cache.blocks.clear();
            int before=cache.reads,p=layout.nodes.length==0?-1:0;Query answer=new Query();StringBuilder events=new StringBuilder();
            while(p!=-1) {
                int oldReads=cache.reads;Node node=cache.load(p);
                answer.keys.add(node.key);answer.positions.add(p);answer.blocks.add(p/blockNodes);
                events.append(cache.reads!=oldReads?'M':'H');
                if(target==node.key) { answer.found=true;break; }
                p=target<node.key?node.left:node.right;
            }
            answer.events=events.toString();answer.reads=cache.reads-before;answers.add(answer);
        }
        return new Result(layout,answers,cache);
    }
    static String compact(List<?> a) { return a.toString().replace(" ",""); }
    static void show(String label,Result r) {
        System.out.println(label+" accesses="+r.accesses+" hits="+r.hits+" block_reads="+r.reads
            +" transfers="+r.reads+" evictions="+r.evictions+" peak_blocks="+r.peakBlocks);
    }
    public static void main(String[] args) {
        long[] keys=new long[15];for(int i=0;i<15;++i)keys[i]=i+1;
        long[] queries={1,7,15,0,8,1};
        Result bfs=run(keys,queries,3,2,false,false),veb=run(keys,queries,3,2,true,false);
        for(int i=0;i<queries.length;++i)if(bfs.queries.get(i).found!=veb.queries.get(i).found)throw new AssertionError("search");
        System.out.println("nodes=15 height_levels=4 block_nodes=3 cache_blocks=2 cold_each=false");
        System.out.println("record_bytes=24 block_bytes=72 cache_bytes=144 equal=true");
        System.out.println("veb_heap_ids="+Arrays.toString(veb.layout.ids).replace(" ",""));
        List<Long> layoutKeys=new ArrayList<>();for(Node n:veb.layout.nodes)layoutKeys.add(n.key);
        System.out.println("veb_keys="+compact(layoutKeys));
        for(int i=0;i<queries.length;++i) {
            Query a=bfs.queries.get(i),b=veb.queries.get(i);
            System.out.println("q="+queries[i]+" found="+b.found+" keys="+compact(b.keys)
                +" veb_positions="+compact(b.positions)+" veb_blocks="+compact(b.blocks)
                +" veb_events="+b.events+" bfs_reads="+a.reads+" veb_reads="+b.reads);
        }
        show("bfs",bfs);show("veb",veb);
    }
}

Expected standard output, identical in all three languages:

• nodes=15 height_levels=4 block_nodes=3 cache_blocks=2 cold_each=false
• record_bytes=24 block_bytes=72 cache_bytes=144 equal=true
• veb_heap_ids=[1,2,3,4,8,9,5,10,11,6,12,13,7,14,15]
• veb_keys=[8,4,12,2,1,3,6,5,7,10,9,11,14,13,15]
• q=1 found=true keys=[8,4,2,1] veb_positions=[0,1,3,4] veb_blocks=[0,0,1,1] veb_events=MHMH bfs_reads=3 veb_reads=2
• q=7 found=true keys=[8,4,6,7] veb_positions=[0,1,6,8] veb_blocks=[0,0,2,2] veb_events=HHMH bfs_reads=3 veb_reads=1
• q=15 found=true keys=[8,12,14,15] veb_positions=[0,2,12,14] veb_blocks=[0,0,4,4] veb_events=HHMH bfs_reads=3 veb_reads=1
• q=0 found=false keys=[8,4,2,1] veb_positions=[0,1,3,4] veb_blocks=[0,0,1,1] veb_events=HHMH bfs_reads=3 veb_reads=1
• q=8 found=true keys=[8] veb_positions=[0] veb_blocks=[0] veb_events=H bfs_reads=1 veb_reads=0
• q=1 found=true keys=[8,4,2,1] veb_positions=[0,1,3,4] veb_blocks=[0,0,1,1] veb_events=HHHH bfs_reads=2 veb_reads=0
• bfs accesses=21 hits=6 block_reads=15 transfers=15 evictions=13 peak_blocks=2
• veb accesses=21 hits=16 block_reads=5 transfers=5 evictions=3 peak_blocks=2

Complexity, Correctness, and Invariants

Construction cost. Input validation and temporary heap assignment each take $\Theta(N)$ work. Layout emission appends every node once. At an internal emission call, the top and bottom pieces partition its nodes, and its loop performs one iteration per bottom child call. The recursion tree has $N$ singleton leaves and at least three children at every internal call, so its number of calls and total loop iterations are $O(N)$. The inverse map and record-materialization passes are linear. Total construction is $\Theta(N)$ work for all valid positive sizes; no sorting is performed because sorted input is required.

Temporary heap keys, output permutation, inverse positions, and records use $\Theta(N)$ space. Heap-key assignment has an $O(h)$ stack. Layout-emission height halves at each nesting level, giving $O(\log h)=O(\log\log(N+1))$ stack for that phase; these are different recursions. Overall construction stack is $O(h)=O(\log(N+1))$. The temporary construction arrays can be discarded after records are materialized; this demonstration retains logical IDs for inspection.

Comparisons and query work. For $N\gt0$, $h=\log_2(N+1)$. A successful root query visits one node; an unsuccessful query visits $h$ nodes before a null link. A deepest successful query also visits $h$ nodes. Thus best-case lookup work is $\Theta(1)$ and worst-case work is $\Theta(h)$. If a successful key is chosen uniformly from the $N$ stored keys, the expected number of visited nodes is $$ \frac{\sum_{d=1}^{h}d\,2^{d-1}}{2^h-1} =\frac{(h-1)2^h+1}{2^h-1} =\Theta(h). $$ Here $d$ is node depth counted from one. Other query distributions can have different averages. The logical path, number of comparisons, and membership result are identical for BFS and vEB storage.

Why the layout helps transfers. For $B\ge2$, conceptually cut layout recursion when a piece first fits in at most $B$ records. Its parent's height exceeded $\log_2(B+1)$; halving height leaves a piece with $\Omega(\log B)$ levels, up to rounding constants. The piece is contiguous and spans at most two blocks, including an unaligned start. A root-to-leaf path passes through $O(1+h/\log B)$ such pieces, each needing $O(1)$ reads if enough frames retain those blocks. This yields $$ O\left(1+\frac{h}{\log_2(B+1)}\right) =O(1+\log_{B+1}N). $$ The algorithm never sees this analysis cutoff. The cache-oblivious data-structures chapter by Brodal and Fagerberg, Section 38.2, presents this static-layout argument. For $B=1$, the bound becomes $O(1+\log_2N)$, consistent with one cold read per visited node. A constant number of frames suffices for this path argument; the matrix-transpose tall-cache condition $M=\Omega(B^2)$ is not a requirement of this elementary static-tree proof.

A cold root query has exactly one read. For arbitrary cold paths, vEB has the stated upper bound under the cache assumptions; worst-case comparison-based search requires $\Omega(1+\log_{B+1}N)$ transfers in the standard model. This is an asymptotic worst-case optimality statement, not an exact minimum for each query. Warm lookups can have zero misses. The simulator allows one frame too, but the proof that an unaligned two-block piece stays resident assumes at least two; do not silently apply its retention argument to every accepted setting.

Finite simulator accounting. Let $V$ be total visited nodes over a batch, $R$ reads, and $H$ hits. Then $$ V=H+R,\qquad 0\le R\le V,\qquad T=R. $$ For a nonempty warm batch on a nonempty tree, $R\ge1$. There are $D=\lceil N/B\rceil$ distinct backing blocks, but this is not a compulsory number of reads: the batch may touch only the root. If $Q\ge D$, a warm run reads each accessed block at most once, so $R$ equals the number of distinct blocks touched. With cold-per-query mode, this reasoning restarts for each query. Clearing residents adds neither reads nor clean-capacity evictions by itself.

Space and observer overhead. The stored layout occupies $\Theta(N)$ records; a pointer-following membership search needs $O(1)$ additional control space. The demonstration retains query traces of total length $V$, so result storage is $O(N+V+k)$ for $k$ queries, excluding cached payload. Cache payload is at most $BQ$ records with $O(Q)$ LRU metadata. Padding costs at most $B-1$ extra records per cached final block; there is only one such backing block. Under expected constant-time hash access, payload copies give observer work $O(V+BR)$ beyond construction, validation, and printing. This simulation cost differs from real uninstrumented search time.

Permutation and contiguity invariant. An emission call receives one logical piece and outputs exactly its nodes, once each, consecutively. A singleton does so directly. For a larger piece, top and bottom pieces are disjoint and cover it, as the size identity shows; recursively outputting them consecutively preserves both coverage and contiguity. All child heights are smaller, so recursion terminates. At the root, ids is a permutation of IDs $1$ through $N$.

Link-remapping invariant. For each logical child ID $j$, the stored child field equals position[j], and ids[position[j]]=j. Thus following a physical link reaches exactly the same logical child as in the BST. Missing logical children map to $-1$. Every reachable record remains in its original key interval, so a comparison safely discards the opposite subtree. Equality returns true; reaching null means no remaining node can match. Read-only cache payloads are copies of immutable backing records, so replacement changes traffic without changing navigation or answers.

Variants, Pitfalls, and Optimizations

Do not reuse heap formulas after moving nodes. The logical relation $i\mapsto2i,2i+1$ remains useful during construction. Physical vEB positions generally do not follow it. The root happens to have children at positions one and two in this sample, which can hide the bug. At position one, key four's right child is position six, key six; applying $2p+2$ incorrectly selects position four, key one. The diagram shows this first wrong edge.

State height and rounding conventions. Height counted in edges is one less than this lesson's node-level height. Mixing them changes the cut and bottom-root count. Floor top/ceiling bottom is used consistently here, including height three. Other implementations assign the extra level differently or choose power-of-two cut heights for dynamic stability. Different valid conventions can produce different permutations; compare the defining rules before comparing arrays.

The top piece is itself recursive. Storing the top levels breadth first and only recursing on the bottom is not the same general layout. Nor is simply writing root, entire left subtree, entire right subtree. Some small heights happen to match preorder, so height four and several odd heights are useful tests. Every top and bottom piece must use the chosen recursive rule.

Contiguous piece does not mean aligned block. A piece of at most $B$ records can straddle two blocks. Reserving only one frame can break the simple within-piece retention argument. Adding padding to every piece can alter footprint and layout properties; padding to an observed block size would introduce a cache-aware choice. Our sample's three-record pieces align by coincidence, and only the cache's final block is padded for transfer accounting.

Arbitrary sizes need an explicit policy. The executable builder rejects counts such as two or fourteen. One extension embeds a balanced arbitrary-size tree in a perfect skeleton, tracks absent nodes with validity information, and searches only valid logical nodes. Another recursively splits actual truncated levels and records exact subtree sizes. Removing dummy slots or changing packing requires remapping links and reconsidering the locality argument. Do not feed an incomplete tree to the perfect-tree root-range formula and assume missing IDs will take care of themselves.

Layout is static; updates are additional work. Inserting a new key into this array is not just appending a record. Logical balancing, physical placement, and all affected child positions must remain coherent. Rebuilding from sorted keys is a simple $\Theta(N)$ option for infrequent batch updates within supported sizes. Dynamic cache-oblivious trees add techniques such as packed-memory arrays and controlled rebuilding; their update bounds do not follow from static vEB placement alone.

Do not assume physical order is sorted. Scanning this array returns $8,4,12,2,1,3,\ldots$, not keys in increasing order. A sorted range result requires inorder/tree navigation or a separate representation. The code implements membership only and makes no linked-leaf scan guarantee. If ordered scans dominate, a sorted array or a page-oriented leaf organization can be more appropriate.

Pointer and record representation matter. Explicit child positions make the lesson clear but consume space; implicit vEB navigation can remove those fields at the cost of additional index logic. Real key-only Eytzinger arrays may use fewer bytes per node than this three-field teaching record. Comparing their timings requires accounting for that representation difference, prefetch behavior, alignment, branches, and compiler choices. An extra external ID-to-position lookup on every query step would introduce a memory stream absent from our simulator.

Cache bounds are not a performance ranking. Khuong and Morin's Array Layouts for Comparison-Based Searching compares sorted, Eytzinger, B-tree, and vEB arrangements and reports that tuned Eytzinger search often performed best for larger arrays on their tested hardware. That result illustrates the roles of prefetching and implementation details; it does not invalidate a vEB transfer bound. Our experiment measures a single fully associative LRU level, without hardware prefetch, set conflicts, TLB effects, branch prediction, or instruction costs.

Make cold/warm comparisons fair. A repeated target may become free of block reads under a warm policy. Reordering queries changes recency and potentially totals. Start both layouts cold, give them identical queries/capacity/block sizes, and keep the same reset policy. Use output and path checks before timing; neither a favorable miss count nor a familiar layout name establishes correctness.

Practice Problems and Real-World Use

Validate the layout before looking at misses. Check that logical IDs form a permutation, each key is preserved, every non-null child position points to the intended logical child, inorder traversal reproduces the original sorted input, and there are no cycles or out-of-range links. Test the root, every leaf on small trees, internal keys, absent targets between keys, and targets below/above the stored range.

For an independent oracle, use ordinary binary search on the original sorted keys for membership and comparison paths. Generate the expected permutation by recursively cutting explicit level lists rather than reusing the implementation's heap-ID range arithmetic. Replay physical block IDs with timestamps rather than the implementation's LRU container. Include a block size that does not divide the record count, one frame, a cache large enough for all blocks, an empty batch, and both cold/warm policies.

All three implementations passed $3246$ shared inputs per language: $3228$ valid workloads, containing $78168$ queries, and $18$ rejected inputs. The tests compare every record and remapped link, the entire heap-ID permutation, membership, visited key/position/block sequences, every hit/miss event, per-query reads, and all aggregate counters. They cover every supported height through ten, randomized sorted key sets, exhaustive small key subsets, missing targets, empty trees/batches, partial blocks, cache limits, and invalid sizes/order/values/queries. Independent checks also verified contiguity for $2937$ recursive pieces, layout independence in $40$ cache-geometry comparisons, and $24$ Python type rejections. C++ ran with address and undefined-behavior sanitizers. Standalone sample output is byte-identical across the three languages.

Static indexes with many searches between rebuilds are a natural setting for exploring this tradeoff. Keep a conventional sorted representation as a correctness and timing baseline, and account for index-construction cost over the full workload. If updates, ordered scans, concurrent writes, or variable-sized payloads dominate, the physical layout is only one part of the design.

For further study, the static-search discussion in Brodal and Fagerberg explains the recursive-cluster proof, Bender–Demaine–Farach-Colton develops dynamic cache-oblivious search structures, and Khuong–Morin supplies an empirical comparison of practical array layouts. Read their model and representation assumptions alongside their bounds or timing results.