Copy-on-Write B-Trees and the Bw-Tree

Introduction

Traditional B-trees perform in-place updates: when a key is inserted or a node splits, the affected pages are modified directly on disk.
This design creates tension with concurrency control and recovery.
Latches must protect pages during modification, and write-ahead logging is required to ensure atomicity.
Copy-on-write (CoW) B-trees and the Bw-tree represent two distinct strategies for eliminating in-place updates, each with different trade-offs in write amplification, concurrency, and cache behavior.

Both approaches share a core insight: if you never overwrite existing data, you simplify concurrency, recovery, and snapshot isolation.
Yet they achieve this goal through fundamentally different mechanisms.
The CoW approach is also known classically as shadow paging, a technique explored as far back as System R in the 1970s; modern systems such as LMDB, Btrfs, and ZFS have refined it for contemporary hardware.

Copy-on-Write B-Trees

A copy-on-write B-tree never modifies a page after it has been written.
Instead, any modification to a leaf node produces a new copy of that node.
Because the parent must now point to the new copy rather than the original, the parent is also copied, and this cascades up to the root.
Each logical update produces a new root pointer, and the old root (along with its unchanged subtree) remains valid as a consistent snapshot.

Mechanism

1. To update a key in leaf node L, allocate a new page L' containing the updated content.
2. Copy L's parent P into P', updating the pointer from L to L'.
3. Repeat up the tree until a new root R' is created.
4. Atomically swap the root pointer from R to R'.

The old tree remains fully intact and readable.
Readers that started before the swap continue to traverse the old root and see a consistent snapshot without acquiring any latches.
This property makes CoW B-trees naturally suited to MVCC and snapshot isolation.

Write Amplification

The primary cost is write amplification.
Every single-key update copies O(log n) pages, from the leaf to the root.
If the tree has height 4 (meaning 4 levels from leaf to root), and each page is 4 KB, a single key insertion writes 4 pages × 4 KB = 16 KB.
For write-heavy workloads, this is expensive.
Several systems mitigate this through batching: accumulating multiple updates and applying them in a single root-to-leaf sweep, amortizing the path-copy cost across many mutations.

Systems Using CoW B-Trees

LMDB uses a copy-on-write B+ tree as its sole storage structure.
Each transaction produces a new root, and the old root is reclaimed only when no readers reference it.
Because the previous consistent tree always remains intact until the new root is durably written and the root pointer is atomically updated (relying on fsync and the OS's mmap semantics for durability), LMDB does not require a write-ahead log.
This is a deliberate design choice: durability is achieved through careful ordering of writes and a double-buffered meta-page, not through a separate log.
Btrfs and ZFS use CoW B-trees at the filesystem level for similar reasons: atomic updates and cheap snapshots.

The Bw-Tree

The Bw-tree, developed at Microsoft Research, takes a different approach to avoiding in-place updates.
Rather than copying entire pages, it prepends small delta records to a page's logical state.
It replaces physical page pointers with a mapping table that is updated using atomic compare-and-swap (CAS) operations, eliminating latches entirely.

Architecture

The Bw-tree has three key structural components:

1. Mapping table. A fixed array that maps logical page identifiers (PIDs) to physical addresses. All references between nodes use PIDs, never raw pointers. To redirect access to a page, you only need to CAS the corresponding mapping table entry.

2. Delta chains. Instead of modifying a page in place, an update creates a small delta record (e.g., "insert key K with value V") and prepends it to the existing chain for that page. The delta record contains a pointer to the previous head of the chain, and the mapping table entry for the PID is CAS'd from the old head to the new delta record. No latch is needed: if the CAS fails, the operation retries.

3. Base pages. When a delta chain grows too long, the page is consolidated: the chain is walked, a new base page is constructed incorporating all deltas, and the mapping table entry is CAS'd to point to the new base page. This bounds the read cost of traversing a chain.

The storage and flush layer beneath the Bw-tree is called LLAMA (Log-Structured and Latch-free Access Method Aware).
LLAMA is responsible for batching delta records into sequential I/O, providing durability without random writes, and managing the physical layout on flash or disk.

Latch-Free Operations

The Bw-tree achieves latch-freedom through the indirection of the mapping table.
Consider an insert:

• The thread reads the mapping table entry for the target leaf PID, getting address A (the current chain head).
• It creates a delta record D pointing to A.
• It performs CAS(mapping_table[PID], A, D).
• If the CAS succeeds, the insert is complete. If it fails, another thread has modified the same page concurrently, and the operation retries from the beginning.

Structure modifications (splits and merges) use the same CAS mechanism but involve multiple steps, coordinated through a protocol that uses intermediate "split delta" or "merge delta" records to make the multi-step process visible to concurrent threads.

Walkthrough

Bw-Tree Insert Operation

function BwTreeInsert(tree, key, value):
    pid = tree.traverse(key)          // find leaf PID via tree traversal

    retry:
        current_addr = tree.mapping_table[pid]
        
        // Create delta record pointing to current chain head
        delta = new InsertDelta {
            key:    key,
            value:  value,
            next:   current_addr      // prepend to existing chain
        }
        
        // Attempt atomic install
        success = CAS(tree.mapping_table[pid], current_addr, &delta)
        
        if not success:
            goto retry                // another thread modified this page
        
        // Check if consolidation is needed
        if delta_chain_length(pid) > THRESHOLD:
            consolidate(pid)
        
        return OK

function consolidate(pid):
    current_addr = tree.mapping_table[pid]
    
    // Walk the delta chain to collect all records.
    // Because deltas are prepended (newest first), we collect them into
    // a list and then apply in reverse (oldest first) so that later
    // updates correctly overwrite earlier ones.
    deltas = []
    walk = current_addr
    while walk is not BasePage:
        deltas.append(walk.delta)
        walk = walk.next
    base_page = copy(walk)            // start from the existing base page
    for d in reverse(deltas):        // apply oldest delta first
        apply(d, base_page)
    
    // Install consolidated page
    CAS(tree.mapping_table[pid], current_addr, &base_page)
    // If CAS fails, another thread already modified the chain; skip consolidation

Bw-Tree Node Split (Simplified)

Splits require two atomic steps, each using CAS:

1. Split the leaf. Create a split delta on the original page P, indicating that keys above a separator K have moved to a new page Q. Install the split delta on P via CAS on mapping_table[P]. At this point, searches for keys > K that reach P will follow the split delta's pointer to Q.

2. Update the parent. Create an index entry delta on the parent page, adding the separator K and PID for Q. Install via CAS on the parent's mapping table entry.

If the thread fails between step 1 and step 2, other threads encountering the split delta on P can detect the incomplete split and help complete the split.
This cooperative completion protocol is essential to maintaining latch-freedom under structure modifications.

Comparison

Property	CoW B-Tree	Bw-Tree
Write amplification	High (full path copy)	Low (small deltas)
Read amplification	Low (standard page reads)	Variable (delta chain traversal)
Concurrency control	Snapshot via old roots	Latch-free via CAS + mapping table
Recovery / Durability	No WAL needed (old tree intact; durability via careful write ordering)	Requires LLAMA flush layer for durability
Snapshot support	Natural (old roots)	Requires epoch-based reclamation
Implementation complexity	Low	High

The CoW B-tree trades write bandwidth for simplicity.
The Bw-tree trades implementation complexity for high concurrency and low write amplification, but its read path degrades if consolidation falls behind.

Practical Considerations

Delta chain length and read performance. In the Bw-tree, every read must traverse the delta chain before reaching the base page.
Empirical studies have shown that cache misses along the delta chain can significantly degrade performance.
The chain is a linked list of small, separately allocated records which is hostile to CPU cache prefetching.
Some reimplementations of the Bw-tree (notably the OpenBw-Tree, described in Wang et al. 2018) found that the overhead of delta chains and CAS retries under high contention could negate the benefits of latch-freedom.

Garbage collection and epoch management. Both designs must reclaim old versions.
CoW B-trees must track which roots are still referenced by active readers and free unreachable pages.
The Bw-tree uses epoch-based reclamation: threads register their epoch upon entering the tree, and memory from delta records, and old base pages is freed only when no thread is in an epoch that could reference them.

Write batching in CoW trees. Systems like LMDB mitigate write amplification by committing entire transactions as a batch, producing a single new root per transaction rather than per key.
If a transaction touches many keys across the tree, the path copies overlap, and the amortized cost per key drops substantially.

Flash and log-structured storage. The Bw-tree was originally designed with flash storage in mind.
Its delta records map naturally to a log-structured store (LLAMA) where sequential writes are preferred.
The flush layer can batch deltas into sequential I/O, avoiding the random-write penalty that flash storage imposes.

Key Points

• Copy-on-write B-trees (also called shadow-paging B-trees) create new copies of every node along the root-to-leaf path on each update, providing natural snapshot isolation at the cost of write amplification.
• The Bw-tree avoids both in-place updates and full-page copies by prepending small delta records and using a mapping table with CAS for latch-free concurrency.
• CoW B-trees eliminate the need for write-ahead logging because the previous consistent tree remains intact until the new root is durably written and the root pointer is atomically swapped.
• Bw-tree delta chains degrade read performance if consolidation does not keep pace with updates, due to pointer chasing and cache-unfriendly memory access patterns.
• Both structures require epoch-based or reference-counted garbage collection to reclaim old versions safely in the presence of concurrent readers.
• Write batching in CoW B-trees (committing many keys per root swap) and consolidation thresholds in the Bw-tree are critical tuning parameters that govern practical performance.
• The Bw-tree's latch-free design targets high-core-count hardware where traditional latch-based B-trees suffer from contention, but empirical results (Wang et al. 2018) show that the benefit depends heavily on workload and implementation quality.
• Delta records in the Bw-tree are prepended (newest first); correct consolidation requires applying them in reverse chronological order to reconstruct accurate page state.

References

Levandoski, J., Lomet, D., and Sengupta, S. "The Bw-Tree: A B-tree for New Hardware Platforms." Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE), 2013.

Chu, H. "MDB: A Memory-Mapped Database and Backend for OpenLDAP." Proceedings of the LDAPCon, 2011.

Graefe, G. "A Survey of B-Tree Locking Techniques." ACM Transactions on Database Systems, 35(3), 2010.

Wang, Z., Pavlo, A., Lim, H., Leis, V., Zhang, H., Kaminsky, M., and Andersen, D. "Building a Bw-Tree Takes More Than Just Buzz Words." Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data, 2018.

Rodeh, O. "B-trees, Shadowing, and Clones." ACM Transactions on Storage, 3(4), 2008.