go-btree-copy-on-write-page-split-rebalance
Done. The problem is diagnosed, solved, and verified.
Solution location
- ~/solution.md — the self-contained deliverable (title, root-cause analysis, the complete fix, verification section)
- ~/cowbtree/{go.mod, btree.go, btree_test.go} — the working module (the code blocks in the markdown are byte-identical to these verified files)
What was built — a Bolt-style copy-on-write B+tree in Go 1.26 (generics, no dependencies):
- COW + atomic snapshots: every mutation clones the root-to-leaf path, rewires only the clones, and publishes an immutable (root, version) pair with a single atomic store. Readers are wait-free and always traverse a frozen, consistent snapshot; never see in-place mutation.
- Insert: preemptive splits of full children (with correct leaf-vs-branch balanced split — promoted key is keys[minKeys] for branches), root growth by splitting a full root.
- Delete: preemptive rebalance — borrow from a fat sibling, else merge with a sibling (pulling the separator down) — plus root shrink by collapsing a single-child root. All leaves stay at equal depth.
- Exact separator maintenance: separators equal the exact subtree maximum; max is threaded down (curMax) and new max returned up on every insert/delete, so routing never goes stale.
- Linearizability: single-writer mutex; every op returns the version it published; the checker replays the write log and verifies each concurrent read/scan exactly against its snapshot version.
Verification
- Reference-model randomized insert/delete/scan equivalence (maxKeys ∈ {3,5,9}), an exhaustive structural invariant checker (balance, capacities, sortedness, exact separators), growth/shrink stress, and a concurrent readers+writers linearizability checker — all passing under go test -race -count=5 (36s, no races, no violations).
Notably, the invariant checker caught three real bugs during development (branch-split promotion index sharing a child between halves, internal borrowRight key placement corrupting separators, and nil-slice splicing when splitting branches/leaves); all are fixed and documented in §3.4 of the markdown.
# Evidence - Problem class: go-btree-copy-on-write-page-split-rebalance - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-01T22:21:08.143Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a copy-on-write B+tree (Bolt-style): every mutation clones the path from root to the touched leaf and atomically swaps the root pointer so pages visible to concurrent readers are never mutated in place. Handle node split at full capacity, underflow rebalance and merge after deletes, and root-split growth, keeping the tree perfectly balanced throughout. Validate with randomized insert/delete/scan sequences against a sorted in-memory reference plus a linearizability checker under concurrent readers and writers.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-btree-copy-on-write-page-split-rebalance", "provider": "openrouter", "solved_at": "2026-09-01T22:21:08.147Z", "version": "1.26"}Done. The problem is diagnosed, solved, and verified.
Solution location
- ~/solution.md — the self-contained deliverable (title, root-cause analysis, the complete fix, verification section)
- ~/cowbtree/{go.mod, btree.go, btree_test.go} — the working module (the code blocks in the markdown are byte-identical to these verified files)
What was built — a Bolt-style copy-on-write B+tree in Go 1.26 (generics, no dependencies):
- COW + atomic snapshots: every mutation clones the root-to-leaf path, rewires only the clones, and publishes an immutable (root, version) pair with a single atomic store. Readers are wait-free and always traverse a frozen, consistent snapshot; never see in-place mutation.
- Insert: preemptive splits of full children (with correct leaf-vs-branch balanced split — promoted key is keys[minKeys] for branches), root growth by splitting a full root.
- Delete: preemptive rebalance — borrow from a fat sibling, else merge with a sibling (pulling the separator down) — plus root shrink by collapsing a single-child root. All leaves stay at equal depth.
- Exact separator maintenance: separators equal the exact subtree maximum; max is threaded down (curMax) and new max returned up on every insert/delete, so routing never goes stale.
- Linearizability: single-writer mutex; every op returns the version it published; the checker replays the write log and verifies each concurrent read/scan exactly against its snapshot version.
Verification
- Reference-model randomized insert/delete/scan equivalence (maxKeys ∈ {3,5,9}), an exhaustive structural invariant checker (balance, capacities, sortedness, exact separators), growth/shrink stress, and a concurrent readers+writers linearizability checker — all passing under go test -race -count=5 (36s, no races, no violations).
Notably, the invariant checker caught three real bugs during development (branch-split promotion index sharing a child between halves, internal borrowRight key placement corrupting separators, and nil-slice splicing when splitting branches/leaves); all are fixed and documented in §3.4 of the markdown.
# Evidence - Problem class: go-btree-copy-on-write-page-split-rebalance - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-01T22:21:08.143Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a copy-on-write B+tree (Bolt-style): every mutation clones the path from root to the touched leaf and atomically swaps the root pointer so pages visible to concurrent readers are never mutated in place. Handle node split at full capacity, underflow rebalance and merge after deletes, and root-split growth, keeping the tree perfectly balanced throughout. Validate with randomized insert/delete/scan sequences against a sorted in-memory reference plus a linearizability checker under concurrent readers and writers.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-btree-copy-on-write-page-split-rebalance", "provider": "openrouter", "solved_at": "2026-09-01T22:21:08.147Z", "version": "1.26"}