Persistent Copy-on-Write B+ Tree Snapshot Engine (C++)

A from-scratch persistent B+ tree: every write path-copies only the root-to-leaf spine it touches, snapshots are O(1) to take, old snapshots stay fully readable and correct forever (until dropped), and unreachable nodes are reclaimed automatically via a hand-rolled intrusive refcount -- no separate GC pass. Benchmarked against a naive "linear delta chain" baseline to make the payoff concrete and measured, not asserted.

Architecture

   put(k, v) ──► walk root→leaf, allocate a COPY of every node on that
                 path only; every untouched sibling subtree is SHARED
                 (one atomic refcount bump, not a deep copy) ──► new root

   snapshot() ──► copy one NodePtr (one atomic increment) ──► O(1), no
                 tree data duplicated

   get(snap,k) ─► pure traversal of immutable, already-reachable nodes;
                 no locking needed at all

File	What it is
include/pbtree/node.hpp	Node/LeafNodeT/InternalNodeT + a hand-rolled intrusive-refcounted NodePtr<T>
include/pbtree/btree.hpp	The persistent B+ tree itself: path-copying insert, split logic, O(1) snapshot, lock-free reads
include/pbtree/delta_chain.hpp	The benchmark's baseline: a naive versioned store as a linked list of diffs
tests/test_correctness.cpp	Splits, MVCC isolation, 1,500-snapshot validation, GC reclamation proof
tests/test_concurrency.cpp	Multi-reader/single-writer isolation + refcount thread-safety stress test
bench/benchmark.cpp	The tree-vs-delta-chain latency/storage/memory comparison

Build & run

make test              # correctness + concurrency, ~65k checks
make test-sanitized    # same tests under ASan+UBSan and ThreadSanitizer
make bench             # the benchmark below

No external dependencies (no gtest, no cmake) -- just g++ and make.

Design decisions worth explaining out loud

• Intrusive refcounting instead of std::shared_ptr<Node>. A node's refcount lives inside the node itself (one allocation, not two), and it makes the "reference-counted garbage collection" claim an actual, readable piece of code (NodePtr's incref/decref_raw in node.hpp) instead of something borrowed wholesale from the standard library. Reclamation cascades naturally: deleting an InternalNode destroys its vector<NodePtr<Node>> children, which decrefs each child, which may cascade further -- exactly the subtree that just became unreachable, and no further. Verified concretely in test_gc_reclaims_unreachable_nodes (drop an old snapshot, watch the live node count actually go down) and stress-tested for thread-safety under ThreadSanitizer in test_concurrent_snapshot_churn_is_safe.
• No leaf sibling pointers. Classic mutable B+ trees chain leaves together for fast range scans. In a persistent tree that's a trap: updating a leaf's sibling pointer means copying the sibling too, which cascades sideways across the whole leaf level on every write, defeating path-copying entirely. This implementation omits sibling pointers and does range scans via a full recursive traversal instead (O(N) rather than O(log_B N + result size)) -- a deliberate, documented trade-off, not an oversight. Point lookups (what the benchmark focuses on, and what a KV-store workload dominated by) are unaffected.
• Single-writer, multi-reader concurrency, not lock-free MVCC. put() is serialized by one mutex; reads against any snapshot need no locking at all because the nodes they touch can never change. This is a real, common trade-off (SQLite's default mode works this way) chosen for correctness-simplicity over write throughput; a lock-free multi- writer design would need something like an atomic compare-and-swap on the head pointer plus a retry loop, which is a meaningfully bigger project on its own.
• No delete. The resume scope was insert + snapshot + path-copying; delete would need underflow/merge/rebalance logic symmetric to the split logic here, which is real additional complexity intentionally left out. Overwriting a key's value is fully supported.

Correctness: validated across 1,500 snapshots

test_thousands_of_snapshots_stay_isolated takes a snapshot after every single put for 1,500 puts, then checks that:

• a key written once at the very start is visible, with its original value, in all 1,500 snapshots (proof that ~1,500 splits along the way never corrupted data outside the path being modified), and
• every sampled snapshot sees exactly the keys written up to that point -- no leakage of later writes into older snapshots.

All 65,000+ checks across the correctness and concurrency suites pass clean, including under AddressSanitizer, UndefinedBehaviorSanitizer, and ThreadSanitizer (zero findings) -- the C++ equivalent of the -race rigor applied to the companion Raft project.

Benchmark: tree vs. linear delta chain

Setup per row: write one target key once, then write versions - 1 more unrelated keys, then measure the average cost (over 2,000 trials) of looking up the target key in the final snapshot.

  versions |   tree GET(ns)  chain GET(ns) |   tree PUT(ns)  chain PUT(ns) | tree nodes  chain len |    tree ~bytes   chain ~bytes
----------------------------------------------------------------------------------------------------------------------------------
        10 |            8.8           16.4 |          135.3           82.3 |          2         10 |            128            640
       100 |            9.2          156.1 |          253.0           48.2 |          9        100 |            576           6400
      1000 |           10.7         4794.1 |          473.1           52.5 |         69       1000 |           4416          64000
      5000 |           10.4        25079.7 |          643.8           56.2 |        334       5000 |          21376         320000
     20000 |           12.2       424794.0 |          861.5           71.1 |       1331      20000 |          85184        1280000
     50000 |           12.7      1088271.7 |          871.1           71.1 |       3322      50000 |         212608        3200000

(Real output from make bench on this machine; re-running will vary slightly with load but the shape is stable.)

Reading it:

• GET stays flat on the tree (8.8ns → 12.7ns, a ~1.4x change) while it grows linearly on the chain (16.4ns → 1,088,271.7ns) as versions goes from 10 to 50,000 -- at 50,000 versions the tree is ~85,700x faster for this lookup. That gap is O(log_B N) vs O(S), exactly the property a persistent tree is built to have.
• PUT is more expensive on the tree at every row (allocating O(log_B N) new nodes vs. the chain's O(1) append) -- the honest other half of the trade-off. Copy-on-write isn't free; it spends write cost to buy read cost, and this table shows both sides rather than only the flattering one.
• Storage: the tree's node count grows with the number of distinct keys (sublinearly per key, due to fanout), while the chain's length grows with the number of writes 1:1 -- at 50,000 versions the tree holds 3,322 nodes vs. the chain's 50,000 version records.

Known limitations

• No delete/rebalancing (see above).
• Range scans are unpruned (O(N), see above) -- fine for the point- lookup-heavy access pattern this project targets, not for a range-scan-heavy one.
• Single-writer: write throughput is bounded by one mutex, not by CPU core count. Reads scale perfectly across cores (no locking at all).
• The benchmark's "bytes" columns are a rough estimate (fixed struct size × count); they don't account for std::vector's own heap buffers inside each node, which would add a modest constant factor on top.