Copy-on-write B-trees combine the venerable B-tree indexing structure with a functional programming technique that never modifies data in place. Instead of overwriting nodes during updates, the database creates new versions of modified nodes, leaving old versions intact. This seemingly wasteful approach powers some of the most sophisticated features in modern storage engines: instant snapshots, lock-free readers, and crash-safe writes.

Why Not Modify in Place

Traditional B-trees update nodes directly. Insert a key, and the database writes the new value into an existing leaf node, then propagates changes up the tree if splits occur. This works, but creates coordination problems. Readers must lock nodes to prevent seeing torn writes. Writers compete for the same hot pages near the root. Crash recovery requires write-ahead logs and careful orchestration.

Copy-on-write sidesteps these issues by treating the tree as immutable. Every modification produces a new root pointer. Readers holding an old root see a consistent snapshot from that moment in time, even as writers continue building new versions. No read locks, no coordination, no torn state.

The Mechanics of Path Copying

When you insert or update a key, the database doesn’t touch the existing tree. It allocates a new leaf node containing the change, then walks back up the path to the root, creating new copies of each ancestor that needs to point to the updated child. Unchanged subtrees are shared between versions—only the spine from leaf to root gets duplicated.

This means a single key change touches O(log n) nodes, the height of the tree, rather than just one leaf. But modern SSDs handle sequential writes efficiently, and the append-only pattern eliminates random seeks. The database batches changes, amortizing the copying cost across multiple keys in a single transaction.

Snapshots Without Scanning

Because every version of the tree remains accessible through its root pointer, snapshots are trivial. Store the root pointer at a point in time, and you have a complete, consistent view of the entire database at that moment. No background scanning, no copy-on-write at the block layer, no freezing the system.

Databases like LMDB and Btrfs use this property heavily. LMDB exposes snapshot semantics directly: begin a read transaction, and you get a frozen view immune to concurrent writes. Btrfs creates filesystem snapshots in milliseconds by recording a root pointer and marking the tree copy-on-write.

The cost is storage. Old versions accumulate until explicitly freed. Databases typically tie snapshots to transaction lifetimes, reclaiming space once all readers referencing an old root have closed. Long-running read transactions can pin large amounts of dead data.

Crash Recovery by Design

Copy-on-write trees naturally resist corruption. The database writes new nodes to disk, waits for durability, then atomically updates the root pointer with a single write. If the system crashes mid-transaction, the old root remains valid—the partial write is simply unreachable garbage. No log replay, no complex recovery protocol.

This doesn’t eliminate write-ahead logs entirely. Databases still need logs to sequence transactions and ensure durability before acknowledging writes. But the tree structure itself never enters an inconsistent state. Btrfs and ZFS rely on this property to maintain filesystem integrity without fsck.

Concurrency Without Blocking

Writers never block readers because they never overwrite shared data. A reader captures the current root pointer and traverses the tree, knowing that every node it touches will remain unchanged. Writers simultaneously build new versions, copying only the path they modify.

This makes copy-on-write B-trees especially attractive for workloads with high read concurrency and occasional writes. Analytical databases and time-series stores use them to serve queries against a stable snapshot while background processes compact and merge new data.

The tradeoff appears under write-heavy workloads. Every update duplicates the path to the root, creating more I/O than in-place updates. Space amplification increases if the system can’t reclaim old nodes fast enough. Write amplification becomes a tuning challenge, particularly on flash storage where physical write limits matter.

Space Reclamation and Compaction

Unreachable nodes must eventually be freed. Databases track reference counts or use epoch-based reclamation to identify when a node version is no longer visible to any transaction. LMDB reclaims pages when the oldest reader advances. Btrfs maintains a log of stale blocks and runs background cleanup.

Compaction poses additional challenges. LSM-trees already copy data during merge; adding copy-on-write B-trees on top creates layered amplification. Some systems compromise, using copy-on-write for metadata and indexes while applying different strategies to data blocks.

Where It Fits

Copy-on-write B-trees excel when you need strong consistency guarantees, lock-free concurrency, and efficient snapshots. They fit naturally into storage engines designed for analytical workloads, embedded databases, and filesystems prioritizing data integrity over raw write throughput. The pattern trades write amplification for simplicity and isolation, a bargain that makes sense when reads dominate and snapshots are first-class features.