The Real Complexity of Fusion Trees

Introduction

Every computer-science student learns the same fact early: searching a sorted list of $n$ items takes $O(\log n)$ comparisons. That is not a gap in our cleverness — it is a proven lower bound. Any algorithm that can only ask "is $x < y$ ?" must make at least $\log_2 n$ such questions in the worst case.

But that lower bound has a fine print: it counts comparisons, not CPU operations. A real processor has something extra — it can manipulate whole words of $w$ bits in a single clock cycle. Can we exploit that?

In 1990 Michael Fredman and Dan Willard answered with a resounding yes. Their fusion tree stores $n$ integers in $O(n)$ space and answers predecessor queries in $O(\log_w n)$ time — a factor of $\log w$ faster than binary search, legally, because the proof never assumed word-level tricks were free. On a 64-bit machine that collapses 64 potential comparison levels into one. It was the first data structure to beat the comparison lower bound for integer searching.

Try It: Word-Parallel Search

The demo below builds a sorted set of integers stored in a fusion tree node. Each node holds up to $w^{1/5}$ keys (here $w = 32$ , so up to 2 keys per node for clarity). Enter a query value and watch how the tree locates the predecessor — the largest stored key that is $\leq$ the query — in $O(\log_w n)$ steps rather than $O(\log n)$ .

<p class="hint">A <b>fusion tree</b> stores sorted integers and finds the predecessor
(largest key &le; query) by packing all branch-keys of a node into one 32-bit word
and comparing them <em>in parallel</em> with a single subtract. That is the bit trick
that beats O(log n). Enter a query and press <b>Search</b>.</p>
<div class="controls">
  <label>Keys (comma-separated integers 1–127):
    <input id="keys-input" type="text" value="3, 10, 17, 28, 42, 55, 60, 77, 88, 99, 110, 120" />
  </label>
  <label>Query (0–127):
    <input id="query-input" type="number" min="0" max="127" value="62" />
  </label>
  <div class="btns">
    <button id="build-btn" type="button">Build Tree</button>
    <button id="search-btn" type="button">Search</button>
    <button id="reset-btn" type="button" class="ghost">Reset</button>
  </div>
</div>
<div id="tree-vis"></div>
<div class="status" id="status">Build the tree first.</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .7rem; }
label { display: flex; flex-direction: column; gap: .2rem; font-size: .85rem; color: #555; }
input[type=text], input[type=number] {
  padding: .3rem .5rem; border: 1px solid #bbb; border-radius: 6px;
  font-size: .9rem; width: 100%; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#tree-vis { overflow-x: auto; min-height: 60px; margin: .5rem 0; }
svg.tree { display: block; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.log { font: .78rem ui-monospace, monospace; color: #555; line-height: 1.5;
       max-height: 90px; overflow-y: auto; border-top: 1px solid #e0e4e8;
       padding-top: .3rem; white-space: pre-wrap; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Fusion Tree demo ───────────────────────────────────────────
// B-ary search tree (B=4) whose inner nodes use WORD-PARALLEL comparison:
// pack all B-1 separators into a single 32-bit word (8 bits per key, values 0-127)
// then one subtract+mask finds how many separators are <= the query —
// replacing B-1 sequential comparisons with ONE word operation.
// This is the essence of Fredman & Willard (1990).

const B     = 4;          // branching factor; each slot = 8 bits → 4 slots in 32 bits
const BITS  = 8;          // bits per slot
const HIGH  = 0x80;       // sentinel bit per slot (bit 7)
const MASK  = 0xFF;       // slot mask

// ── Node ─────────────────────────────────────────────────────────────────────────────
class FNode {
  constructor(keys) {
    this.keys     = keys.slice();  // separator keys (inner) or values (leaf)
    this.children = [];            // FNode[] — empty for leaves
    this.isLeaf   = true;
  }
}

// ── Build B-ary tree from sorted array ──────────────────────────────────────────────
// Separator convention: sep[i] = first key of child[i+1]
// → child[i] holds keys in [sep[i-1], sep[i]-1], with sep[-1]=-∞, sep[B-1]=+∞
function buildTree(sorted) {
  if (sorted.length <= B) {
    const n = new FNode(sorted); n.isLeaf = true; return n;
  }
  const chunkSize = Math.ceil(sorted.length / B);
  const node = new FNode([]); node.isLeaf = false;
  for (let i = 0; i < sorted.length; i += chunkSize) {
    const chunk = sorted.slice(i, i + chunkSize);
    node.children.push(buildTree(chunk));
    if (i > 0) node.keys.push(chunk[0]);   // first key of each non-first chunk
  }
  return node;
}

// ── Word-parallel rank: count how many branchKeys[i] <= q in ONE subtract ──
// Pack all B-1 seps into consecutive 8-bit slots of a 32-bit word.
// Replicate (HIGH | q) into each slot of qpacked.
// After (qpacked - packed): slot i keeps HIGH iff branchKeys[i] <= q (no borrow).
// Result = number of slots where HIGH survived = number of seps <= q.
function sketchRank(branchKeys, q) {
  let packed = 0;
  for (let i = 0; i < branchKeys.length; i++)
    packed = (packed | ((branchKeys[i] & MASK) << (i * BITS))) >>> 0;

  const qSlot = q & 0x7F;   // cap at 127 so we stay below HIGH bit
  let qpacked = 0;
  for (let i = 0; i < B; i++)
    qpacked = (qpacked | ((HIGH | qSlot) << (i * BITS))) >>> 0;

  // One subtract — the whole point of the word trick
  const diff = (qpacked - packed) >>> 0;

  let rank = 0;
  for (let i = 0; i < branchKeys.length; i++)
    if ((diff >>> (i * BITS)) & HIGH) rank++;   // HIGH survived → sep[i] <= q

  logMsg("    " + fmt('word-parallel: packed=0x%packed% qpacked=0x%qpacked% diff=0x%diff% → rank=%rank%', { packed: packed.toString(16).padStart(8,'0'), qpacked: qpacked.toString(16).padStart(8,'0'), diff: diff.toString(16).padStart(8,'0'), rank: rank }));
  return rank;
}

// ── Predecessor search ────────────────────────────────────────────────────────
let steps = 0;
function predecessor(node, q, depth) {
  steps++;
  if (node.isLeaf) {
    let pred = null;
    for (const k of node.keys) if (k <= q) pred = k;
    logMsg("  " + fmt('leaf %stringify%  → pred=%pred%', { stringify: JSON.stringify(node.keys), pred: pred }));
    return pred;
  }
  logMsg(fmt('depth=%depth%  seps=%stringify% q=%q%', { depth: depth, stringify: JSON.stringify(node.keys), q: q }));
  const rank = sketchRank(node.keys, q);
  logMsg("    " + fmt('→ child[%rank%]', { rank: rank }));
  return predecessor(node.children[rank], q, depth + 1);
}

// ── Visualization ───────────────────────────────────────────────────────────────────────
let tree = null;
const logEl  = () => document.getElementById('log');
const statEl = () => document.getElementById('status');

function logMsg(m) { logEl().textContent += m + '\n'; logEl().scrollTop = logEl().scrollHeight; }
function clearLog() { logEl().textContent = ''; }
function setStatus(t, cls) { statEl().textContent = t; statEl().className = 'status ' + (cls || ''); }

// BFS layout
function layout(root) {
  const nodes = [], edges = [];
  let id = 0;
  function visit(n, depth, parentId) {
    const nid = id++;
    nodes.push({ id: nid, node: n, depth, parentId, x: 0, y: 0 });
    for (const c of n.children) visit(c, depth + 1, nid);
  }
  visit(root, 0, null);
  const leaves = nodes.filter(n => n.node.isLeaf);
  const xMap = {};
  leaves.forEach((l, i) => { xMap[l.id] = i; });
  function cx(nid) {
    const nd = nodes[nid];
    if (nd.node.isLeaf) return xMap[nid];
    const kids = nodes.filter(c => c.parentId === nid).map(c => c.id);
    const avg = kids.reduce((s, k) => s + cx(k), 0) / kids.length;
    xMap[nid] = avg; return avg;
  }
  cx(0);
  const nLeaves = Math.max(leaves.length, 1);
  const maxDepth = Math.max(...nodes.map(n => n.depth)) + 1;
  const W = Math.max(320, nLeaves * 60 + 40);
  const H = maxDepth * 72 + 40;
  nodes.forEach(n => {
    n.x = 20 + xMap[n.id] * (W - 40) / Math.max(nLeaves - 0.5, 1);
    n.y = 28 + n.depth * 72;
  });
  for (const n of nodes)
    if (n.parentId !== null)
      edges.push({ x1: nodes[n.parentId].x, y1: nodes[n.parentId].y + 18,
                   x2: n.x, y2: n.y - 18 });
  return { nodes, edges, W, H };
}

function renderTree(root, pathSet) {
  const { nodes, edges, W, H } = layout(root);
  const NS = 'http://www.w3.org/2000/svg';
  const svg = document.createElementNS(NS, 'svg');
  svg.setAttribute('width', W); svg.setAttribute('height', H); svg.setAttribute('class', 'tree');

  for (const e of edges) {
    const l = document.createElementNS(NS, 'line');
    ['x1','y1','x2','y2'].forEach(a => l.setAttribute(a, e[a]));
    l.setAttribute('stroke', '#cdd9e3'); l.setAttribute('stroke-width', '1.5');
    svg.appendChild(l);
  }
  for (const n of nodes) {
    const inPath = pathSet && pathSet.has(n.id);
    const label  = n.node.keys.join(', ') || '—';
    const rw = Math.min(32, 12 + label.length * 5.5), rh = 16;
    const rect = document.createElementNS(NS, 'rect');
    rect.setAttribute('x', n.x - rw); rect.setAttribute('y', n.y - rh);
    rect.setAttribute('width', rw * 2); rect.setAttribute('height', rh * 2);
    rect.setAttribute('rx', 8);
    rect.setAttribute('fill',   inPath ? '#1d3557' : (n.node.isLeaf ? '#e8eef3' : '#f0f4f8'));
    rect.setAttribute('stroke', inPath ? '#1d3557' : '#adb1b8');
    rect.setAttribute('stroke-width', '1.5');
    const text = document.createElementNS(NS, 'text');
    text.setAttribute('x', n.x); text.setAttribute('y', n.y + 4);
    text.setAttribute('text-anchor', 'middle');
    text.setAttribute('font-size', '10'); text.setAttribute('font-family', 'ui-monospace, monospace');
    text.setAttribute('fill', inPath ? '#fff' : '#1d3557');
    text.textContent = label.length > 14 ? label.slice(0, 13) + '…' : label;
    svg.appendChild(rect); svg.appendChild(text);
  }
  document.getElementById('tree-vis').innerHTML = '';
  document.getElementById('tree-vis').appendChild(svg);
}

// Collect path node ids during a silent search pass
function searchPath(root, q) {
  const path = [];
  let id = 0;
  function assignId(n) { const nid = id++; n._id = nid; for (const c of n.children) assignId(c); }
  assignId(root);
  function walk(n) {
    path.push(n._id);
    if (n.isLeaf) return;
    let rank = 0;
    for (const k of n.keys) if (k <= q) rank++;
    if (rank < n.children.length) walk(n.children[rank]);
  }
  walk(root);
  return new Set(path);
}

function getKeys() {
  return [...new Set(
    document.getElementById('keys-input').value
      .split(',').map(s => parseInt(s.trim(), 10))
      .filter(n => !isNaN(n) && n >= 1 && n <= 127)
  )].sort((a, b) => a - b);
}

document.getElementById('build-btn').addEventListener('click', () => {
  const keys = getKeys();
  if (keys.length < 2) { setStatus('Enter at least 2 integers (1–127).', 'bad'); return; }
  tree = buildTree(keys);
  renderTree(tree, null);
  const depth = Math.ceil(Math.log(keys.length) / Math.log(B));
  setStatus(fmt('Tree built: %length% keys, B=%B%, depth≈%depth% (vs log₂=%ceil% for binary search). Now search.', { length: keys.length, B: B, depth: depth, ceil: Math.ceil(Math.log2(keys.length)) }), '');
  clearLog();
  logMsg(fmt('Keys: %keys%', { keys: keys.join(', ') }));
  logMsg(fmt('B=%B%  slot width=%BITS%b  word=32b  depth≈log_%B%(n)', { B: B, BITS: BITS }));
});

document.getElementById('search-btn').addEventListener('click', () => {
  if (!tree) { setStatus('Build the tree first.', 'bad'); return; }
  const q = parseInt(document.getElementById('query-input').value, 10);
  if (isNaN(q) || q < 0 || q > 127) { setStatus('Enter a query between 0 and 127.', 'bad'); return; }
  clearLog(); steps = 0;
  logMsg(fmt('Searching predecessor of %q% …', { q: q }));
  const pred = predecessor(tree, q, 0);
  renderTree(tree, searchPath(tree, q));
  if (pred === null)
    setStatus(fmt('No predecessor (query %q% is below all keys). %steps% node visit(s).', { q: q, steps: steps }), 'bad');
  else
    setStatus(fmt('Predecessor of %q% = %pred%  |  %steps% node visit(s), O(log₄ n) steps.', { q: q, pred: pred, steps: steps }), 'ok');
});

document.getElementById('reset-btn').addEventListener('click', () => {
  tree = null;
  document.getElementById('tree-vis').innerHTML = '';
  setStatus('Build the tree first.', ''); clearLog();
});

<p class="hint">A <b>fusion tree</b> stores sorted integers and finds the predecessor
(largest key &le; query) by packing all branch-keys of a node into one 32-bit word
and comparing them <em>in parallel</em> with a single subtract. That is the bit trick
that beats O(log n). Enter a query and press <b>Search</b>.</p>
<div class="controls">
  <label>Keys (comma-separated integers 1–127):
    <input id="keys-input" type="text" value="3, 10, 17, 28, 42, 55, 60, 77, 88, 99, 110, 120" />
  </label>
  <label>Query (0–127):
    <input id="query-input" type="number" min="0" max="127" value="62" />
  </label>
  <div class="btns">
    <button id="build-btn" type="button">Build Tree</button>
    <button id="search-btn" type="button">Search</button>
    <button id="reset-btn" type="button" class="ghost">Reset</button>
  </div>
</div>
<div id="tree-vis"></div>
<div class="status" id="status">Build the tree first.</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .7rem; }
label { display: flex; flex-direction: column; gap: .2rem; font-size: .85rem; color: #555; }
input[type=text], input[type=number] {
  padding: .3rem .5rem; border: 1px solid #bbb; border-radius: 6px;
  font-size: .9rem; width: 100%; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#tree-vis { overflow-x: auto; min-height: 60px; margin: .5rem 0; }
svg.tree { display: block; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.log { font: .78rem ui-monospace, monospace; color: #555; line-height: 1.5;
       max-height: 90px; overflow-y: auto; border-top: 1px solid #e0e4e8;
       padding-top: .3rem; white-space: pre-wrap; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Fusion Tree demo ───────────────────────────────────────────
// B-ary search tree (B=4) whose inner nodes use WORD-PARALLEL comparison:
// pack all B-1 separators into a single 32-bit word (8 bits per key, values 0-127)
// then one subtract+mask finds how many separators are <= the query —
// replacing B-1 sequential comparisons with ONE word operation.
// This is the essence of Fredman & Willard (1990).

const B     = 4;          // branching factor; each slot = 8 bits → 4 slots in 32 bits
const BITS  = 8;          // bits per slot
const HIGH  = 0x80;       // sentinel bit per slot (bit 7)
const MASK  = 0xFF;       // slot mask

// ── Node ─────────────────────────────────────────────────────────────────────────────
class FNode {
  constructor(keys) {
    this.keys     = keys.slice();  // separator keys (inner) or values (leaf)
    this.children = [];            // FNode[] — empty for leaves
    this.isLeaf   = true;
  }
}

// ── Build B-ary tree from sorted array ──────────────────────────────────────────────
// Separator convention: sep[i] = first key of child[i+1]
// → child[i] holds keys in [sep[i-1], sep[i]-1], with sep[-1]=-∞, sep[B-1]=+∞
function buildTree(sorted) {
  if (sorted.length <= B) {
    const n = new FNode(sorted); n.isLeaf = true; return n;
  }
  const chunkSize = Math.ceil(sorted.length / B);
  const node = new FNode([]); node.isLeaf = false;
  for (let i = 0; i < sorted.length; i += chunkSize) {
    const chunk = sorted.slice(i, i + chunkSize);
    node.children.push(buildTree(chunk));
    if (i > 0) node.keys.push(chunk[0]);   // first key of each non-first chunk
  }
  return node;
}

// ── Word-parallel rank: count how many branchKeys[i] <= q in ONE subtract ──
// Pack all B-1 seps into consecutive 8-bit slots of a 32-bit word.
// Replicate (HIGH | q) into each slot of qpacked.
// After (qpacked - packed): slot i keeps HIGH iff branchKeys[i] <= q (no borrow).
// Result = number of slots where HIGH survived = number of seps <= q.
function sketchRank(branchKeys, q) {
  let packed = 0;
  for (let i = 0; i < branchKeys.length; i++)
    packed = (packed | ((branchKeys[i] & MASK) << (i * BITS))) >>> 0;

  const qSlot = q & 0x7F;   // cap at 127 so we stay below HIGH bit
  let qpacked = 0;
  for (let i = 0; i < B; i++)
    qpacked = (qpacked | ((HIGH | qSlot) << (i * BITS))) >>> 0;

  // One subtract — the whole point of the word trick
  const diff = (qpacked - packed) >>> 0;

  let rank = 0;
  for (let i = 0; i < branchKeys.length; i++)
    if ((diff >>> (i * BITS)) & HIGH) rank++;   // HIGH survived → sep[i] <= q

  logMsg("    " + fmt('word-parallel: packed=0x%packed% qpacked=0x%qpacked% diff=0x%diff% → rank=%rank%', { packed: packed.toString(16).padStart(8,'0'), qpacked: qpacked.toString(16).padStart(8,'0'), diff: diff.toString(16).padStart(8,'0'), rank: rank }));
  return rank;
}

// ── Predecessor search ────────────────────────────────────────────────────────
let steps = 0;
function predecessor(node, q, depth) {
  steps++;
  if (node.isLeaf) {
    let pred = null;
    for (const k of node.keys) if (k <= q) pred = k;
    logMsg("  " + fmt('leaf %stringify%  → pred=%pred%', { stringify: JSON.stringify(node.keys), pred: pred }));
    return pred;
  }
  logMsg(fmt('depth=%depth%  seps=%stringify% q=%q%', { depth: depth, stringify: JSON.stringify(node.keys), q: q }));
  const rank = sketchRank(node.keys, q);
  logMsg("    " + fmt('→ child[%rank%]', { rank: rank }));
  return predecessor(node.children[rank], q, depth + 1);
}

// ── Visualization ───────────────────────────────────────────────────────────────────────
let tree = null;
const logEl  = () => document.getElementById('log');
const statEl = () => document.getElementById('status');

function logMsg(m) { logEl().textContent += m + '\n'; logEl().scrollTop = logEl().scrollHeight; }
function clearLog() { logEl().textContent = ''; }
function setStatus(t, cls) { statEl().textContent = t; statEl().className = 'status ' + (cls || ''); }

// BFS layout
function layout(root) {
  const nodes = [], edges = [];
  let id = 0;
  function visit(n, depth, parentId) {
    const nid = id++;
    nodes.push({ id: nid, node: n, depth, parentId, x: 0, y: 0 });
    for (const c of n.children) visit(c, depth + 1, nid);
  }
  visit(root, 0, null);
  const leaves = nodes.filter(n => n.node.isLeaf);
  const xMap = {};
  leaves.forEach((l, i) => { xMap[l.id] = i; });
  function cx(nid) {
    const nd = nodes[nid];
    if (nd.node.isLeaf) return xMap[nid];
    const kids = nodes.filter(c => c.parentId === nid).map(c => c.id);
    const avg = kids.reduce((s, k) => s + cx(k), 0) / kids.length;
    xMap[nid] = avg; return avg;
  }
  cx(0);
  const nLeaves = Math.max(leaves.length, 1);
  const maxDepth = Math.max(...nodes.map(n => n.depth)) + 1;
  const W = Math.max(320, nLeaves * 60 + 40);
  const H = maxDepth * 72 + 40;
  nodes.forEach(n => {
    n.x = 20 + xMap[n.id] * (W - 40) / Math.max(nLeaves - 0.5, 1);
    n.y = 28 + n.depth * 72;
  });
  for (const n of nodes)
    if (n.parentId !== null)
      edges.push({ x1: nodes[n.parentId].x, y1: nodes[n.parentId].y + 18,
                   x2: n.x, y2: n.y - 18 });
  return { nodes, edges, W, H };
}

function renderTree(root, pathSet) {
  const { nodes, edges, W, H } = layout(root);
  const NS = 'http://www.w3.org/2000/svg';
  const svg = document.createElementNS(NS, 'svg');
  svg.setAttribute('width', W); svg.setAttribute('height', H); svg.setAttribute('class', 'tree');

  for (const e of edges) {
    const l = document.createElementNS(NS, 'line');
    ['x1','y1','x2','y2'].forEach(a => l.setAttribute(a, e[a]));
    l.setAttribute('stroke', '#cdd9e3'); l.setAttribute('stroke-width', '1.5');
    svg.appendChild(l);
  }
  for (const n of nodes) {
    const inPath = pathSet && pathSet.has(n.id);
    const label  = n.node.keys.join(', ') || '—';
    const rw = Math.min(32, 12 + label.length * 5.5), rh = 16;
    const rect = document.createElementNS(NS, 'rect');
    rect.setAttribute('x', n.x - rw); rect.setAttribute('y', n.y - rh);
    rect.setAttribute('width', rw * 2); rect.setAttribute('height', rh * 2);
    rect.setAttribute('rx', 8);
    rect.setAttribute('fill',   inPath ? '#1d3557' : (n.node.isLeaf ? '#e8eef3' : '#f0f4f8'));
    rect.setAttribute('stroke', inPath ? '#1d3557' : '#adb1b8');
    rect.setAttribute('stroke-width', '1.5');
    const text = document.createElementNS(NS, 'text');
    text.setAttribute('x', n.x); text.setAttribute('y', n.y + 4);
    text.setAttribute('text-anchor', 'middle');
    text.setAttribute('font-size', '10'); text.setAttribute('font-family', 'ui-monospace, monospace');
    text.setAttribute('fill', inPath ? '#fff' : '#1d3557');
    text.textContent = label.length > 14 ? label.slice(0, 13) + '…' : label;
    svg.appendChild(rect); svg.appendChild(text);
  }
  document.getElementById('tree-vis').innerHTML = '';
  document.getElementById('tree-vis').appendChild(svg);
}

// Collect path node ids during a silent search pass
function searchPath(root, q) {
  const path = [];
  let id = 0;
  function assignId(n) { const nid = id++; n._id = nid; for (const c of n.children) assignId(c); }
  assignId(root);
  function walk(n) {
    path.push(n._id);
    if (n.isLeaf) return;
    let rank = 0;
    for (const k of n.keys) if (k <= q) rank++;
    if (rank < n.children.length) walk(n.children[rank]);
  }
  walk(root);
  return new Set(path);
}

function getKeys() {
  return [...new Set(
    document.getElementById('keys-input').value
      .split(',').map(s => parseInt(s.trim(), 10))
      .filter(n => !isNaN(n) && n >= 1 && n <= 127)
  )].sort((a, b) => a - b);
}

document.getElementById('build-btn').addEventListener('click', () => {
  const keys = getKeys();
  if (keys.length < 2) { setStatus('Enter at least 2 integers (1–127).', 'bad'); return; }
  tree = buildTree(keys);
  renderTree(tree, null);
  const depth = Math.ceil(Math.log(keys.length) / Math.log(B));
  setStatus(fmt('Tree built: %length% keys, B=%B%, depth≈%depth% (vs log₂=%ceil% for binary search). Now search.', { length: keys.length, B: B, depth: depth, ceil: Math.ceil(Math.log2(keys.length)) }), '');
  clearLog();
  logMsg(fmt('Keys: %keys%', { keys: keys.join(', ') }));
  logMsg(fmt('B=%B%  slot width=%BITS%b  word=32b  depth≈log_%B%(n)', { B: B, BITS: BITS }));
});

document.getElementById('search-btn').addEventListener('click', () => {
  if (!tree) { setStatus('Build the tree first.', 'bad'); return; }
  const q = parseInt(document.getElementById('query-input').value, 10);
  if (isNaN(q) || q < 0 || q > 127) { setStatus('Enter a query between 0 and 127.', 'bad'); return; }
  clearLog(); steps = 0;
  logMsg(fmt('Searching predecessor of %q% …', { q: q }));
  const pred = predecessor(tree, q, 0);
  renderTree(tree, searchPath(tree, q));
  if (pred === null)
    setStatus(fmt('No predecessor (query %q% is below all keys). %steps% node visit(s).', { q: q, steps: steps }), 'bad');
  else
    setStatus(fmt('Predecessor of %q% = %pred%  |  %steps% node visit(s), O(log₄ n) steps.', { q: q, pred: pred, steps: steps }), 'ok');
});

document.getElementById('reset-btn').addEventListener('click', () => {
  tree = null;
  document.getElementById('tree-vis').innerHTML = '';
  setStatus('Build the tree first.', ''); clearLog();
});

Result

Console

Notice: the classic binary search makes one comparison per level, visiting $\log_2 n$ nodes. The fusion tree sketches all branch-keys in a node into a single integer and finds the right child with bitwise arithmetic — one CPU instruction covers what binary search does in $\log w$ comparisons. That is the comparison-bound loophole Fredman and Willard exploited.

The Real Complexity

How does a fusion tree actually beat the comparison bound?

The comparison lower bound says any decision tree that only branches on $x < y$ needs $\Omega(\log n)$ leaves to distinguish $n$ keys. This is a genuine theorem — you cannot escape it inside the comparison model.
The word-RAM model adds one extra assumption: the computer can manipulate $w$ -bit integers in $O(1)$ time. This is what every real CPU does, and it breaks the proof.
Sketching. A fusion tree node holds $B = w^{1/5}$ keys. The crucial trick is to sketch all $B$ branch-keys into a single $w$ -bit integer by extracting only the $B^4$ bits that distinguish them. The sketch of a query can then be compared to all $B$ sketches simultaneously using one multiply-and-mask sequence — $O(1)$ word operations.
Finding the right child. After the parallel comparison, a single rank operation (also $O(1)$ words) tells you which child to descend into. Each node reduces the problem by a factor of $B = w^{1/5}$ , so the tree has depth $\log_B n = \log n / \log w = \log_w n$ .
Result (proven, 1990). Fredman and Willard showed that $n$ integers in the word-RAM model support predecessor queries in $\Theta(\log_w n)$ time and $O(n)$ space. This is optimal for the word-RAM model; later work (Beame & Fich, 2002) proved no polynomial-space structure can do better for predecessor search.

The status: proven — Fredman & Willard (1990). Not an open problem, not a conjecture. A clean separation between two computational models with a matching lower bound from Beame & Fich.

Compare this to the sorting lower bound: sorting by comparisons also hits $\Omega(n \log n)$ , but integer sorting can exploit word tricks too — radix sort runs in $O(n \log_w n)$ , the same gain fusion trees give for search.

Where It Matters

Word-level parallelism is not just an academic curiosity — it powers real systems:

Integer sorting: packing the fusion-tree idea into sorting gives $O(n \log_w n)$ integer sort — faster than comparison-based $O(n \log n)$ sorts on large integers.
IP routing tables: routers must find the longest-prefix match for a 32- or 128-bit address among millions of rules. Predecessor structures on tries exploit exactly the same word tricks to keep lookups fast.
Compressed indexes: suffix arrays and BWT-based full-text indexes use predecessor search internally; word-parallel variants speed up genomic search engines.
Competitive programming: when the key universe is bounded integers and $n$ is large, replacing a std::set (binary search tree, $O(\log n)$ ) with a van Emde Boas tree or a fusion-tree-inspired structure can make the difference between TLE and AC.
Theory of lower bounds: fusion trees are the canonical example showing that the comparison model and the word-RAM model are genuinely different — a lesson that echoes through the study of P vs NP and the search for lower bounds everywhere in complexity theory.

Once you understand fusion trees, you understand why the comparison lower bound is a theorem about one model, not about all computers.

Conclusion

Fusion trees deliver a humbling reminder: the theorems we trust are theorems about a model, and reality sometimes offers a richer model than the one we assumed.

The $O(\log n)$ comparison bound is true and important. But the moment you let a CPU do what CPUs actually do — crunch 64 bits in one clock — the bound dissolves. Fredman and Willard turned that loophole into a provably optimal data structure, and Beame & Fich later confirmed that $\Theta(\log_w n)$ is the best any polynomial-space structure can do in the word-RAM model.

So the next time a textbook tells you "search is $O(\log n)$ ", ask: $\log n$ what? Comparisons? Yes. Word operations? Not necessarily. The distinction between models is where the most interesting separations in all of P vs NP research live, and fusion trees are one of the clearest places to see it.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fusion-trees/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Fusion Trees

When one CPU word does the work of many comparisons