Introduction

Every database query eventually reaches an index — a structure that lets the engine skip straight to the right rows instead of scanning millions of them. For decades, the workhorse index has been the B-tree: a balanced tree whose branching factor is tuned to fill a disk block, keeping the tree shallow and lookups fast.

But in-memory databases and flash storage changed the game. The bottleneck shifted from disk access to CPU cache contention and thread synchronization. A classic B-tree protects each node with a latch (a short-lived lock): while one thread writes a node, every other thread that needs it waits. On a chip with 48 cores, that queue becomes the new slow path.

In 2013, researchers at Microsoft Research — Justin Levandoski, David Lomet, and Sudipta Sengupta — published a structure that eliminates latches almost entirely: the Bw-Tree (Buzzword-Tree). Instead of updating a node in place, it appends a small delta record in front of it and then swaps a single pointer with a CPU atomic instruction. Readers see either the old state or the new one; they never catch a half-written node. The result is an index that scales nearly linearly with thread count, now powering SQL Server Hekaton and other production systems.

Try It: Delta Updates

The demo below shows a single Bw-Tree node. A mapping table translates the node's logical ID to the physical address of its current head. Every write prepends a tiny delta record and atomically updates that pointer — readers that started before the update still follow the old pointer and see the old state.

<p class="hint">A Bw-Tree node is a <b>chain of delta records</b> prepended in front of a base page. Each insert adds one delta atomically — readers walk the chain without waiting.</p>
<div class="panel">
  <div class="map-row">
    <span class="label">Mapping table</span>
    <span id="map-ptr" class="ptr-box">→ base page</span>
  </div>
  <div id="chain" class="chain"></div>
</div>
<div class="status" id="status">Click Insert key to add delta records.</div>
<div class="btns">
  <button id="btn-insert" type="button">Insert key</button>
  <button id="btn-read" type="button">Read node</button>
  <button id="btn-consolidate" type="button" class="ghost" disabled>Consolidate</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="read-result" class="read-result" style="display:none"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.panel { border: 1px solid #cdd9e3; border-radius: 10px; padding: .7rem 1rem; background: #f7fafc; margin-bottom: .6rem; }
.map-row { display: flex; align-items: center; gap: .6rem; margin-bottom: .6rem; font-size: .85rem; }
.label { font-weight: 600; color: #1d3557; }
.ptr-box { background: #1d3557; color: #fff; border-radius: 6px; padding: .2rem .6rem; font: 600 .82rem ui-monospace, monospace; transition: background .25s; }
.ptr-box.flash { background: #0a7d33; }
.chain { display: flex; flex-direction: column; gap: 5px; }
.node-block { display: flex; align-items: center; gap: .5rem; }
.node-block .arrow { color: #888; font-size: 1.1rem; line-height: 1; }
.record { border-radius: 8px; padding: .32rem .7rem; font: 600 .82rem ui-monospace, monospace;
          border: 1.5px solid; min-width: 130px; }
.record.delta { background: #fff3cd; border-color: #f0ad4e; color: #7a4c00; }
.record.delta.new-flash { animation: pop .35s ease; }
.record.base { background: #e8eef3; border-color: #cdd9e3; color: #1d3557; }
.record.consolidated { background: #d4edda; border-color: #72b483; color: #155724; }
@keyframes pop { 0%{transform:scale(1.18);opacity:.6} 100%{transform:scale(1);opacity:1} }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }
.read-result { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px;
               padding: .5rem .8rem; font: .82rem ui-monospace, monospace; line-height: 1.7; }
.read-result .rk { color: #1d3557; font-weight: 700; }
.read-result .rv { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bw-Tree single-node simulation.
// A node is a linked list: [delta_n] -> [delta_n-1] -> ... -> [base_page]
// Each insert prepends a delta record and does an atomic CAS on the mapping table.
// Consolidation merges all records into a fresh base page.
// Readers walk the chain from head to tail, taking the first (newest) value for each key.

const KEYS = ['apple','banana','cherry','date','elderberry','fig','grape','honeydew'];
let keyIdx = 0;
let chain = []; // [{type:'base'|'delta', key, value}]
let opCount = 0;
const CONSOLIDATE_THRESHOLD = 5;

function basePage() {
  return { type: 'base', key: 'base', value: '{apple:1, banana:2}' };
}

function reset() {
  keyIdx = 0; opCount = 0;
  chain = [basePage()];
  render();
  document.getElementById('read-result').style.display = 'none';
  setStatus('Click Insert key to add delta records.', '');
  document.getElementById('btn-consolidate').disabled = true;
}

function insertKey() {
  const key = KEYS[keyIdx % KEYS.length];
  const value = Math.floor(Math.random() * 900) + 100;
  keyIdx++;
  opCount++;
  // Prepend delta to front of chain (newest first)
  const delta = { type: 'delta', key, value, isNew: true };
  chain.unshift(delta);
  render();
  // Flash mapping table ptr
  const ptr = document.getElementById('map-ptr');
  ptr.classList.add('flash');
  setTimeout(() => ptr.classList.remove('flash'), 350);
  setStatus(fmt('CAS: mapping table now points to delta[%key%] → ...', { key: key }), 'info');
  document.getElementById('btn-consolidate').disabled = chain.filter(r => r.type === 'delta').length < CONSOLIDATE_THRESHOLD;
  setTimeout(() => { if (chain[0]) chain[0].isNew = false; }, 400);
}

function readNode() {
  // Walk chain newest→oldest; first value per key wins (MVCC-style)
  const seen = {};
  for (const record of chain) {
    if (record.type === 'base') {
      // parse base page entries not already seen
      const pairs = record.value.replace(/[{}]/g, '').split(',').map(s => s.trim());
      for (const pair of pairs) {
        const [k, v] = pair.split(':').map(s => s.trim());
        if (k && !(k in seen)) seen[k] = v;
      }
    } else {
      if (!(record.key in seen)) seen[record.key] = record.value;
    }
  }
  const lines = Object.entries(seen).map(([k, v]) =>
    '<span class="rk">' + k + '</span>: <span class="rv">' + v + '</span>'
  ).join('<br>');
  const steps = chain.length;
  const result = document.getElementById('read-result');
  result.innerHTML = fmt('<b>Read result</b> (walked %steps% record%v%):<br>%lines%', { steps: steps, v: steps > 1 ? 's' : '', lines: lines });
  result.style.display = 'block';
  setStatus(fmt('Read complete — no lock acquired, %steps% record(s) scanned.', { steps: steps }), 'ok');
}

function consolidate() {
  // Merge all deltas + base into a single new base page
  const seen = {};
  for (const record of chain) {
    if (record.type === 'base') {
      const pairs = record.value.replace(/[{}]/g, '').split(',').map(s => s.trim());
      for (const pair of pairs) {
        const [k, v] = pair.split(':').map(s => s.trim());
        if (k && !(k in seen)) seen[k] = v;
      }
    } else {
      if (!(record.key in seen)) seen[record.key] = record.value;
    }
  }
  const newBase = '{' + Object.entries(seen).map(([k, v]) => k + ':' + v).join(', ') + '}';
  const oldLen = chain.length;
  chain = [{ type: 'consolidated', key: 'base', value: newBase }];
  opCount = 0;
  render();
  document.getElementById('btn-consolidate').disabled = true;
  document.getElementById('read-result').style.display = 'none';
  setStatus(fmt('Consolidated %oldLen% records into one fresh base page via CAS.', { oldLen: oldLen }), 'ok');
}

function render() {
  const chainEl = document.getElementById('chain');
  chainEl.innerHTML = '';
  const ptrEl = document.getElementById('map-ptr');
  if (chain.length === 0) { ptrEl.textContent = '→ (empty)'; return; }
  const headLabel = chain[0].type === 'delta'
    ? fmt('→ delta[%key%]', { key: chain[0].key })
    : (chain[0].type === 'consolidated' ? '→ consolidated base' : '→ base page');
  ptrEl.textContent = headLabel;

  for (let i = 0; i < chain.length; i++) {
    const r = chain[i];
    const row = document.createElement('div');
    row.className = 'node-block';
    if (i > 0) {
      const arr = document.createElement('span');
      arr.className = 'arrow'; arr.textContent = '↓';
      row.appendChild(arr);
    }
    const rec = document.createElement('div');
    let cls = 'record ';
    if (r.type === 'delta') cls += 'delta' + (r.isNew ? ' new-flash' : '');
    else if (r.type === 'consolidated') cls += 'consolidated';
    else cls += 'base';
    rec.className = cls;
    if (r.type === 'delta') rec.textContent = fmt('Δ insert %key% = %value%', { key: r.key, value: r.value });
    else if (r.type === 'consolidated') rec.textContent = fmt('base* %value%', { value: r.value });
    else rec.textContent = fmt('base %value%', { value: r.value });
    row.appendChild(rec);
    chainEl.appendChild(row);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls;
}

document.getElementById('btn-insert').addEventListener('click', insertKey);
document.getElementById('btn-read').addEventListener('click', readNode);
document.getElementById('btn-consolidate').addEventListener('click', consolidate);
document.getElementById('btn-reset').addEventListener('click', reset);

reset();
Result
Console

Click Insert key to add a new delta record to the node's chain. Click Read node to walk the chain and reconstruct the current state — notice it never blocks even while a write is in progress. Once the chain grows long enough, click Consolidate to merge all deltas into a fresh base page, exactly as the Bw-Tree does in the background.

The Real Mechanics

The Bw-Tree achieves lock-freedom through four interlocking ideas:

  • Mapping table. Every node has a stable logical ID. The mapping table converts that ID into the current physical address of the node's head. Because all threads share one small table, a single atomic write to one table slot redirects all future readers.
  • Delta records. Instead of modifying a base page, a writer allocates a small record that says "insert key K with value V" (or "delete K", or "split here"). It prepends this record to the node's chain and then performs a compare-and-swap (CAS) on the mapping table: "if the pointer is still P, change it to delta_record → P". If another writer raced ahead first, the CAS fails and the writer retries — no lock needed.
  • Wait-free reads. A reader loads the current head pointer, then walks the delta chain from newest to oldest, merging as it goes. Because it follows a snapshot of the pointer it already loaded, a concurrent writer's CAS cannot corrupt the read. Reads are truly non-blocking.
  • Consolidation. Delta chains grow with each write. Periodically a thread consolidates: it reads the full chain, builds a clean base page, and CAS-swaps the mapping table entry to point at the new page. Old pages and deltas become garbage and are reclaimed by an epoch-based scheme similar to read-copy-update (RCU).

The correctness guarantee mirrors non-convex optimization's local vs global distinction: each CAS either wins cleanly or fails and retries, so no partial state is ever visible. The tree's overall shape is maintained by SMO (Structure Modification Operations) — splits and merges that propagate upward atomically through the same CAS mechanism.

Where It Matters

Lock-free indexing is not just a research curiosity — it sits inside production software handling millions of transactions per second:

  • SQL Server Hekaton: Microsoft's in-memory OLTP engine (shipped in SQL Server 2014) uses the Bw-Tree as its primary index structure. Hekaton powers latency-sensitive workloads where traditional disk-based tables would create intolerable lock contention.
  • Silo and ERMIA: academic in-memory database prototypes that share the insight that a well-designed lock-free index lets the rest of the engine focus on transaction ordering rather than index synchronization.
  • Flash storage: because the Bw-Tree never overwrites an existing page (it always appends new records), it maps naturally onto flash memory's write-once erase-in-large-blocks constraint, wearing pages evenly.
  • Learned indexes and hybrids: newer structures like PGM-Index and ALEX borrow the idea of separating the logical address space from the physical location, a principle the Bw-Tree pioneered in the context of pattern matching at index scale.

The broader lesson is that eliminating shared mutable state — the core principle behind the Bw-Tree — is one of the most powerful scalability levers in systems design. The same idea appears in persistent data structures, functional programming, and multi-version concurrency control (MVCC) in databases.

Conclusion

The Bw-Tree's central insight is elegantly simple: never modify shared data in place. Instead, describe each change as a tiny immutable record, prepend it atomically, and let readers walk the chain at their leisure. The mapping table acts as a single indirection layer that makes the whole structure composable and correct without a single lock.

That simplicity hides genuine engineering depth — handling tree splits and merges lock-free, collecting garbage safely across threads, and keeping delta chains short enough that reads stay fast. But the core idea is accessible: a CAS instruction and a linked list of changes are all it takes to let 48 cores read and write the same index simultaneously, each seeing a consistent view, none ever waiting for another.

Lock-free data structures represent one of the deepest connections between algorithm design and hardware reality — a reminder that the best abstractions are often the ones that match the guarantees the machine already provides.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

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