Paper: The Bw-Tree: A B-tree for New Hardware Platforms — Levandoski, Lomet & Sengupta, ICDE 2013

The Bw-Tree is a B+-tree variant from Microsoft Research designed for modern hardware: multi-core CPUs and flash storage. It achieves very high throughput by being entirely latch-free and avoiding update-in-place, which together eliminate thread blocking and CPU cache invalidation.

# Background: Two Hardware Problems

Traditional B-tree designs were built for single-core CPUs and magnetic disks. Two hardware shifts break their assumptions:

1. Multi-core CPUs mandate high concurrency. Traditional B-trees protect pages with latches (short-held reader/writer locks). As core count grows, latch contention becomes the bottleneck — blocking increases as concurrency increases.

2. Flash storage penalises random writes. Flash must erase a block before writing; random writes are 3× slower than sequential writes. A log-structured write path that batches sequential I/Os is far more efficient on flash.

The Bw-tree addresses both: latch-free design for multi-core, log-structured storage for flash.

# Core Architecture

The Bw-tree is an Atomic Record Store (ARS) — it supports keyed reads and writes with logarithmic access. It is structured in three layers:

Bw-Tree Layer   ← tree search/update logic, in-memory pages only
Cache Layer     ← mapping table, brings pages from flash to RAM
Flash Layer     ← log-structured store (LSS), manages flash writes + GC

The key abstraction enabling everything else is the mapping table.

# Innovation 1: The Mapping Table

Every Bw-tree node has a logical Page ID (PID). The mapping table translates a PID to either:

• A memory pointer (page is in RAM), or
• A flash offset (page is on disk).

All inter-node pointers store PIDs, never raw memory addresses. This indirection means a page can move in memory or be swapped to/from flash without updating any tree node — only the mapping table entry changes.

# Innovation 2: Delta Updating (Latch-Free Updates)

Traditional B-trees update pages in-place, requiring a latch to exclude concurrent readers. The Bw-tree never modifies a page’s memory contents. Instead:

1. Allocate a new delta record $D$ describing the change (insert/update/delete).

2. $D$ physically points to the current page state $P$.

3. Atomically install $D$ as the new page state using compare-and-swap (CAS) on the mapping table entry:

   • CAS checks that the entry still holds $P$’s address.
   • If yes, writes $D$’s address — $D$ is now “live”.
   • If no (another thread beat us), retry.

Mapping Table
┌────┬──────┐       Before:  LPID → P
│LPID│ ptr  │──→ D ──→ Page P
└────┴──────┘       After:   LPID → D → Page P

After several updates, a delta chain forms: a linked list of deltas prepended to a base page. Searches traverse the chain first, then fall through to the base page.

# Leaf-Level Delta Types

At leaf pages, three delta types exist:

• Insert delta: new key-record pair.

• Modify delta: updated record for an existing key.

• Delete delta: records only the key being removed.

Each delta carries a Log Sequence Number (LSN) for transactional recovery.

# Page Consolidation

Delta chains degrade search performance as they grow. When a chain exceeds a threshold length, any accessor thread consolidates:

1. Allocate a new base page with all deltas applied (deleted records discarded).

2. Install the new page via CAS on the mapping table.

3. If CAS fails (another thread consolidated first), discard and move on — no retry needed.

4. Request garbage collection of the old page state.

# Innovation 3: Elastic (Logical) Pages

Bw-tree pages are logical — they have no fixed physical location or size. A “page” is the base page plus its delta chain, and it grows simply by prepending more deltas. Pages are split or merged only when a size threshold is crossed, not on every insert.

This flexibility is what makes delta updating practical: there is no upper-bound pressure on page size between consolidations.

# Innovation 4: Latch-Free Structure Modification Operations (SMOs)

Page splits and merges (SMOs) modify multiple pages simultaneously, which seems to require a latch. The Bw-tree decomposes each SMO into a sequence of individually atomic CAS operations.

# Node Split (Two Phases)

The Bw-tree uses the B-link technique — each node has a side link to its right sibling — to decompose a split into two independent half-steps:

Phase 1 — Child split (half split):

1. Allocate a new right sibling page $Q$ with the upper half of $P$’s records (installed directly into the mapping table, no CAS needed since $Q$ is invisible until Phase 2).

2. Prepend a split delta to $P$ containing the separator key $K_P$ and a logical pointer to $Q$. Install via CAS.

At this point the tree is valid: searches for keys $> K_P$ follow the side link from $P$ to $Q$.

Phase 2 — Parent update:

3. Prepend an index entry delta to the parent $O$ with the new separator key and pointer to $Q$. Install via CAS.

# Node Merge (Three Phases)

Merges require three atomic steps:

1. Post a remove node delta on the node $R$ being merged away — blocks further access to $R$.

2. Post a node merge delta on the left sibling $L$ — physically points to $R$’s contents, logically absorbing $R$ into $L$.

3. Post an index term delete delta on the parent — removes $R$’s separator key entry.

# Innovation 5: Epoch-Based Garbage Collection

In a latch-free system, you cannot immediately free memory after a CAS swap — other threads may still hold a pointer to the old state (e.g., mid-search). The epoch mechanism solves this:

• Threads join an epoch when starting an operation.

• Threads exit the epoch when done.

• Memory is only reclaimed after all threads that were active when the memory was freed have since exited their epoch.

This is equivalent to read-copy-update (RCU) and ensures safe memory reclamation without any exclusive locks.

# Innovation 6: Log-Structured Store (LSS) for Flash

The cache layer flushes pages to the LSS for durability and memory pressure. The LSS writes sequentially in large batches — ideal for flash.

Incremental flushing: when flushing a page, only the deltas added since the last flush are marshalled to the LSS. The previously-flushed LSN is recorded in a flush delta on the page. This minimises write amplification since only changed records are written, not the full page state.

# Performance Results

Experiments on a 4-core (8 logical) Intel Xeon W3550 at 3.07 GHz with 24 GB RAM. Three workloads: Xbox LIVE (27M get-set ops), deduplication trace, and synthetic 8-byte integer keys.

Bw-Tree vs BerkeleyDB (traditional B-tree with page-level latching):

Bw-Tree vs latch-free skip list:

The 3.7–4.4× advantage over the skip list is primarily cache efficiency: Bw-tree search spends most time doing binary search on a contiguous base page, hitting L1/L2 cache ~90% of the time. The skip list must chase pointers through each level, resulting in ~75% L1/L2 hit rate and frequent cache misses.

Latch-free failure rates (CAS retries): record updates fail at <0.02% across all workloads. Split and consolidate failures are higher (~1–9%) since they compete with faster record updates, but are still manageable.

# Key Takeaways

The central insight is that the mapping table provides one indirection level that buys you everything: latch-free CAS updates, elastic pages, and decoupled flash placement.