The Bw-Tree

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.

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">{{hint}}</p>
<div class="panel">
  <div class="map-row">
    <span class="label">{{label_mapping_table}}</span>
    <span id="map-ptr" class="ptr-box">{{ptr_base_page}}</span>
  </div>
  <div id="chain" class="chain"></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="btn-insert" type="button">{{btn_insert}}</button>
  <button id="btn-read" type="button">{{btn_read}}</button>
  <button id="btn-consolidate" type="button" class="ghost" disabled>{{btn_consolidate}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_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; }

// Code not found

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 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.

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.

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.