The Search Path Has an Address

A balanced binary search tree has a tidy story:

\[O(\log N)\]

comparisons per search.

That statement forgets where the nodes live.

If a memory block holds \(B\) node records, the search path is not just a list of keys. It is a list of addresses, and the same root-to-leaf path can touch many or few blocks depending on the layout. The tree shape chooses comparisons; the layout chooses locality.

This is the small idea behind cache-oblivious static search trees. Do not tune the tree to one cache-line length. Instead, recursively lay out the tree so that subtrees of many different sizes become contiguous somewhere in memory.

Four Ways To Put Down The Same Tree

Take a complete binary search tree with keys 1..N.

The search algorithm is the usual one:

look at the root
go left or right
repeat

Only the array order changes.

Inorder stores the keys in sorted order. That is excellent for scans, but a tree search jumps to medians, quartiles, eighths, and so on.

BFS / heap order stores the root, then its children, then grandchildren. It keeps the top of the tree tight, but lower levels sprawl across memory.

DFS preorder stores a node followed by its left subtree and then its right subtree. One side of a search can become pleasantly local; the opposite side can pay for the asymmetry.

van Emde Boas layout splits the tree near the middle level, lays out the top recursive subtree, then lays out each bottom recursive subtree the same way. The search still compares root, child, grandchild. The layout is what recurses.

Prokop’s 1999 thesis introduced cache-oblivious algorithms in an ideal-cache model and defined cache obliviousness as avoiding program variables tuned to hardware cache parameters.¹ In the same thesis, he describes a static binary-search-tree layout competitive with B-trees without choosing a cache line length in advance. Demaine’s survey notes give the clean search-tree version: store a complete search tree in van Emde Boas order; a search follows the normal tree path; recursively contiguous subtrees give an \(O(\log_B N)\) block-transfer bound up to constants.²

That is a theorem about a model. It is also a useful engineering lens.

Lab: Count Blocks, Not Comparisons

The lab below builds the same complete tree under four layouts. For every key, it follows the exact same comparison path and counts unique memory blocks touched by that cold search. It does not simulate branch prediction, hardware prefetch, TLBs, allocation overhead, pointer compression, or warm caches. The only question is:

if B adjacent node records arrive together, how many blocks does this path need?

Tree height

10

Search key

513

Nodes per block

8

Inorder BFS / heap order DFS preorder van Emde Boas

Height 10 tree, 1023 nodes, 8 nodes per block. The selected key touches 4 vEB blocks and 8 BFS blocks.

The Default Run

With height 10, N = 1023, block size B = 8, and selected key 513, the comparison path has ten nodes:

512 -> 768 -> 640 -> 576 -> 544 -> 528 -> 520 -> 516 -> 514 -> 513

All four layouts search that same path. The default cold-cache audit reports:

Layout	Average blocks over all keys	Worst blocks	Blocks for key 513
inorder	6.89	8	7
BFS / heap order	6.89	8	8
DFS preorder	4.69	8	3
van Emde Boas	4.31	6	4

The vEB row is not magic. It is doing one specific thing: every time the tree is cut around its middle level, the pieces below the cut become contiguous arrays. A root-to-leaf path therefore passes through a small number of contiguous recursive pieces at many possible block sizes.

The DFS row is a good warning. It can look excellent for some keys because a preorder layout hugs one subtree tightly. Its worst case is still poor in this complete-tree experiment. Locality should be evaluated over the query distribution, not over the prettiest path.

To reproduce the deterministic layout sweep from the repository root, including 151 named checks for layout coverage, search-path accounting, block counts, and the default vEB-vs-inorder comparison:

node - <<'NODE'
const lab = require("./assets/js/cache-layout-lab.js");
const EXPECTED_TOTALS = {
  cases: 5,
  passed: 5,
  total: 5,
  passedChecks: 151,
  totalChecks: 151
};
const EXPECTED_CASE_ROWS = [
  "1:8:255:4:129:8:3.997177:5.788235:5.788235:4.270588:4.223529:6:4:30/30:true",
  "2:10:1023:8:513:10:3.332863:6.889541:6.889541:4.693060:4.313783:6:4:31/31:true",
  "3:11:2047:16:1025:11:2.749824:6.948705:6.948705:4.596483:3.813385:6:4:30/30:true",
  "4:12:4095:32:3021:12:2.399930:6.978266:6.978266:4.548230:3.414408:5:4:30/30:true",
  "5:13:8191:8:7777:13:4.333275:9.877182:9.877182:6.375900:5.848126:8:6:30/30:true"
];
const EXPECTED_BASE_CHECKS = [
  { name: "inorder key count", ok: true },
  { name: "inorder first and last key", ok: true },
  { name: "inorder unique keys", ok: true },
  { name: "bfs key count", ok: true },
  { name: "bfs first and last key", ok: true },
  { name: "bfs unique keys", ok: true },
  { name: "dfs key count", ok: true },
  { name: "dfs first and last key", ok: true },
  { name: "dfs unique keys", ok: true },
  { name: "veb key count", ok: true },
  { name: "veb first and last key", ok: true },
  { name: "veb unique keys", ok: true },
  { name: "search ends at query key", ok: true },
  { name: "search length bounded by height", ok: true },
  { name: "inorder finite average", ok: true },
  { name: "inorder finite worst", ok: true },
  { name: "inorder selected path length", ok: true },
  { name: "inorder block accounting", ok: true },
  { name: "bfs finite average", ok: true },
  { name: "bfs finite worst", ok: true },
  { name: "bfs selected path length", ok: true },
  { name: "bfs block accounting", ok: true },
  { name: "dfs finite average", ok: true },
  { name: "dfs finite worst", ok: true },
  { name: "dfs selected path length", ok: true },
  { name: "dfs block accounting", ok: true },
  { name: "veb finite average", ok: true },
  { name: "veb finite worst", ok: true },
  { name: "veb selected path length", ok: true },
  { name: "veb block accounting", ok: true }
];
const EXPECTED_DEFAULT_CHECK = {
  name: "default vEB improves average over inorder",
  ok: true
};

function sameJson(actual, expected) {
  return JSON.stringify(actual) === JSON.stringify(expected);
}

function rowDrifts(actualRows, expectedRows) {
  const drifts = [];
  const rows = Math.max(actualRows.length, expectedRows.length);
  for (let index = 0; index < rows; index += 1) {
    const actual = index < actualRows.length ? actualRows[index] : null;
    const expected = index < expectedRows.length ? expectedRows[index] : null;
    if (!sameJson(actual, expected)) {
      drifts.push({ index, actual, expected });
    }
  }
  return drifts;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const totals = {
  cases: audit.cases.length,
  passed: audit.passed,
  total: audit.total,
  passedChecks: audit.passedChecks,
  totalChecks: audit.totalChecks
};
const caseRows = audit.cases.map((row) => [
  row.caseId,
  row.height,
  row.n,
  row.blockSize,
  row.key,
  row.comparisons,
  row.logBaseB.toFixed(6),
  row.inorderAverageBlocks.toFixed(6),
  row.bfsAverageBlocks.toFixed(6),
  row.dfsAverageBlocks.toFixed(6),
  row.vebAverageBlocks.toFixed(6),
  row.vebWorstBlocks,
  row.vebSelectedBlocks,
  `${row.passedChecks}/${row.totalChecks}`,
  row.passed
].join(":"));
const checkRows = audit.cases.map((row) => ({
  caseId: row.caseId,
  checks: row.checks.map((check) => ({
    name: check.name,
    ok: check.ok
  }))
}));
const expectedCheckRows = EXPECTED_CASE_ROWS.map((row) => {
  const caseId = Number(row.split(":")[0]);
  return {
    caseId,
    checks: caseId === 2
      ? EXPECTED_BASE_CHECKS.concat([EXPECTED_DEFAULT_CHECK])
      : EXPECTED_BASE_CHECKS
  };
});
const caseRowDrifts = rowDrifts(caseRows, EXPECTED_CASE_ROWS);
const checkRowDrifts = rowDrifts(checkRows, expectedCheckRows);
const driftShape = {
  totals,
  caseRowDrifts,
  checkRowDrifts
};
const shapeErrors = [
  sameJson(totals, EXPECTED_TOTALS) ? null : "totals",
  caseRowDrifts.length === 0 ? null : "caseRows",
  checkRowDrifts.length === 0 ? null : "checkRows"
].filter(Boolean);
if (shapeErrors.length) {
  throw new Error(
    `cache-layout audit shape drifted in ${shapeErrors.join(", ")}:\n` +
    JSON.stringify(driftShape, null, 2)
  );
}
console.table(audit.cases.map((row) => ({
  case: row.caseId,
  height: row.height,
  block: row.blockSize,
  inorderAvg: row.inorderAverageBlocks.toFixed(2),
  bfsAvg: row.bfsAverageBlocks.toFixed(2),
  dfsAvg: row.dfsAverageBlocks.toFixed(2),
  vebAvg: row.vebAverageBlocks.toFixed(2),
  vebWorst: row.vebWorstBlocks,
  checks: `${row.passedChecks}/${row.totalChecks}`,
  passed: row.passed
})));
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  failed.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(`${summary}: ${JSON.stringify(failed, null, 2)}`);
}
console.log(summary);
NODE

Why This Is Cache-Oblivious

A cache-aware blocked tree chooses a fanout or subtree size from the target machine. That is often the right engineering move when the target is fixed.

A cache-oblivious layout refuses to choose \(B\). It recursively creates contiguous subtrees at many scales, so when a real memory hierarchy later picks a block size, some level of the recursion is already near that scale.

The usual comparison count remains \(O(\log N)\). The block-transfer target is

\[O(\log_B N),\]

where

\[\log_B N = {\log N \over \log B}.\]

In the default run, \(\log_8 1023 \approx 3.33\). The simulator’s vEB average of 4.31 and worst case of 6 are in that constant-factor neighborhood. The point is not that the toy equals the theorem. The point is that the address sequence has moved into the right scale.

What This Does Not Prove

The simulator assumes:

• a complete static tree;
• equal-size node records;
• cold searches counted by distinct blocks;
• no instruction-level effects;
• no prefetching or branch predictor behavior;
• no update cost.

Those assumptions matter. Prokop explicitly raised the practical question of cache-oblivious code versus hand-tuned cache-aware code, noting early measurements where cache-oblivious algorithms could be competitive while tuned cache-aware programs were often faster.³ Brodal, Fagerberg, and Jacob also compared vEB with BFS, DFS, and inorder layouts experimentally and treated layout as an empirical systems question, not only an asymptotic one.⁴

So the honest claim is narrower:

For static binary search trees, the comparison tree and the memory layout are separate choices. van Emde Boas layout is a portable way to buy locality across block sizes without hard-coding the block size.

Dynamic dictionaries add another layer. Bender, Demaine, and Farach-Colton built cache-oblivious B-trees that support updates while remaining independent of memory hierarchy parameters; their result is about a full data structure, not just a static array permutation.⁵

The Small Moral

An algorithm can be oblivious to a parameter without being oblivious to physics.

The vEB layout never asks for the cache-line length. It still respects the fact that memory arrives in chunks. That is the neat trick: use recursion to leave promises at every scale, then let the hardware choose which promises it cashes.

The tree did not get fewer comparisons. It got better addresses.

Sources

1. Harald Prokop, “Cache-Oblivious Algorithms”, MIT master’s thesis, 1999. The thesis defines cache-oblivious algorithms as avoiding hardware-configuration variables such as cache size and line length, and introduces the ideal-cache model. ↩

2. Erik D. Demaine, “Cache-Oblivious Algorithms and Data Structures”, BRICS Lecture Series, 2002. Section 7 describes the van Emde Boas layout as a recursive memory layout for complete binary search trees while the search algorithm itself remains the usual tree search. ↩

3. Prokop, Cache-Oblivious Algorithms, Section 10.1, discusses engineering cache-oblivious algorithms and reports early measurements suggesting cache-oblivious algorithms can rival hand-tuned cache-aware code, while tuned cache-aware code is often faster in practice. ↩

4. Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob, “Cache Oblivious Search Trees via Binary Trees of Small Height”, SODA 2002. The paper compares van Emde Boas, BFS, DFS, and inorder layouts and states the vEB layout’s asymptotically optimal search-transfer behavior. ↩

5. Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton, “Cache-Oblivious B-Trees”, SIAM Journal on Computing 35(2), 2005. The paper presents dynamic search trees independent of block sizes and memory-level speeds, matching B-tree-style search bounds in the cache-oblivious model. ↩