The idea: never change a node, copy the path
A persistent data structure keeps every old version. An update does not change anything in place: it returns a new version, and whoever still holds an old version still sees exactly what was there. The trick that makes this cheap is path copying: in a tree, an insert or delete only has to copy the nodes on the path from the root to the change. Everything else is shared between the old and the new version.
On the canvas every node is drawn once, in the colour of the version that created it. A box vN holds the root of version N: to read a version, start at its box and follow pointers down. A green pointer goes from a newer node into an older one: that is where sharing happens. A copy is drawn right next to its original, so you can see both.
Path copying step by step
- Walk down from the root of the version you start from, as in a plain binary search tree.
- Every node you pass will get a new child pointer, and nodes can't change, so each one is copied.
- Each copy points to the same children as its original, except the one pointer on the path, which goes to the next copy (or to the new leaf).
- The copy of the root is the root of the new version.
So an update makes depth + 1 new nodes, O(log n) in a balanced tree, instead of copying all n nodes (Demo: insert 40, copy the path). The old root still points to the old children, so the old version is untouched (Demo: the old version is still readable: 40 is ✗ in v0 and ✓ in v1).
Counting shared and new nodes
The top line of the canvas counts the nodes in memory and compares them with keeping every version as a full copy. The Versions list gives each version's new and shared nodes.
| Demo | New version | New | Shared | Memory vs full copies |
|---|---|---|---|---|
| insert 40 | v1 = v0 + 40 | 4 | 4 | 11 vs 15 |
| three updates | v2 = v1 + 70 | 4 | 5 | |
| v3 = v2 − 12 | 2 | 6 | 17 vs 32 | |
| branch from v0 | v2 = v0 + 30 | 4 | 4 | 15 vs 23 |
| delete 25 | v1 = v0 − 25 | 2 | 4 | 9 vs 13 |
The more versions you keep, the bigger the saving: each version costs only its path, not its size.
Delete and the two-children case
Deleting a leaf copies the path above it; the parent's copy simply has an empty pointer there. Deleting a node with one child copies the path above it, and the parent's copy points straight to that child, which is shared. A node with two children is replaced by its successor, the smallest key in its right subtree: the new version gets a fresh node holding the successor's key, the path down to the successor is copied too, and the old node stays where it was for the old version (Demo: delete 25, a node with two children: a new 37 with the old 12 on its left).
Versions, branches and garbage
An update can start from any version, not just the newest. Inserting into v0 after v1 exists gives v2, a sibling of v1: the versions form a tree, like branches in Git (Demo: branch from v0, like Git). A structure where you can update any version is fully persistent; if only the newest can be updated it is partially persistent.
Old nodes are freed only when no version reaches them. Demo: drop v0, free its garbage removes v0's root: 50, 25 and 37 are freed, while 12, 62, 75 and 88 stay because v1 still points to them. In Clojure, Scala and JavaScript the garbage collector does this; Rust's im crate and C++ libraries use reference counts; Git does it in git gc.
Git trees: path copying by hash
A Git commit points to a root tree, a tree lists blobs and subtrees by their hash, and every object is immutable and named by its content (Git objects). Changing one file makes a new blob, so its directory gets a new tree, and so does every directory above it up to the root: exactly path copying. Every other tree and blob is reused by hash, so a commit that changes one file in a big repository writes only a handful of new objects.
Git shares by hash rather than by pointer, so two identical subtrees made at different times are also one object. The idea is the same as in CRDTs and other replicated data: immutable pieces can be copied and compared freely.
Immutable maps: Clojure, Scala, Immutable.js
Clojure's PersistentHashMap and PersistentVector, Scala's immutable HashMap and Vector, and Immutable.js's Map and List are trees with up to 32 children per node (a hash array mapped trie, HAMT). Five bits of the key's hash pick the child at each level, so a map of a million keys is only about 4 levels deep. assoc or map.set(k, v) copies the 3 or 4 nodes on the path and shares everything else, just like the BST on this page.
Because old versions never change, they are safe to share between threads without locks, cheap to keep for undo or time travel (React and Redux compare references to see what changed), and cheap to compare: if two roots are the same pointer, the two maps are equal.
Costs and other techniques
Path copying costs O(depth) time and memory per update, and a tree must stay balanced for that to be O(log n): real persistent maps use red-black trees, AVL trees, B-trees, finger trees or HAMTs. Driscoll, Sarnak, Sleator and Tarjan (1989) showed that fat nodes (a node keeps a small list of timestamped changes) and node copying bring the extra space down to O(1) per update. Clojure's transients skip the copies while one owner builds a structure, then freeze it.
What the page leaves out
The page uses a plain unbalanced BST of keys without values, at most 20 nodes and 10 versions. It leaves out balancing (a persistent red-black tree copies the rotated nodes too), the HAMT bitmap and node layout, transients, fat nodes and node copying, confluent persistence (merging two versions), and the details of Git's packfiles and garbage collection.