jonnify·persistence /echo-persistence/cubdb/the-immutable-btree

Module 4 · Dive 4.2

The immutable B-tree.

Inside the file is a B-tree, and it is copy-on-write. Changing a key does not edit a node in place; it writes new copies of the nodes along the path from the root to that leaf, and a new root. Everything off the path — and the entire old tree — stays exactly as it was. Update a key and watch which nodes are new and which are shared.

§1

A new path, a shared rest

interactive
Copy-on-write update. Root v0 over three leaves. Update one leaf’s range: a new leaf and a new root v1 appear, v1 sharing the two untouched leaves; v0 still reaches the original.
root v0 9 | 19
readout · Update a key. CubDB writes a new copy of that leaf and a new root; the other two leaves are shared by reference. The old root still reaches the original leaf — both versions are valid, which is what makes a snapshot free.
§2

Why this is the whole game

store.design.md

Copy-on-write is what links Dive 4.1 to the next module. Because an update only ever adds nodes — the path copies plus a root — it appends cleanly to the file, and because the old root is undisturbed, the version it names is still a complete, readable tree. A snapshot, then, is nothing but a retained root: no copy, no freeze. The work per write is the tree’s height, not its size, so it stays cheap as the data grows. Module 5 takes this single fact — old roots stay valid — and builds MVCC and time travel out of it.

§3

References & sources