Persistent Data Structures

An ordinary structure is ephemeral: an update destroys the version before it. Insert a key into a mutable tree and the earlier tree exists nowhere. A persistent structure keeps it, so every update produces a new version and the old one stays queryable.

What varies is how much is allowed. Under partial persistence any version can be read but only the newest updated, so versions form a line. Under full persistence any version can be updated, so they form a tree. Under confluent persistence two versions can be merged, so they form a DAG. Copying the whole structure per update achieves all three at O(n) time and space, and every technique below exists to avoid that copy.

Path copying is what falls out of immutability. To change a node, copy it with the new contents, then copy each ancestor so it points at the copy. Nodes off that path are reattached by pointer and never read. In a balanced tree such as a red-black tree the path is O(log n) long, so an update allocates O(log n) nodes and the old root remains valid. The rope and the zipper both work this way.

The constraint is structural. The rebuilt nodes must form a path, which requires every node to have exactly one parent. Add a parent pointer, or share a node between two positions, and the set of nodes reaching a change can be the whole structure.

The alternative is to let a node hold every value it has ever had. A fat node stores, per field, the sequence of values written to it, each stamped with the version that wrote it. Nothing is overwritten and nothing is copied, so an update appends one entry and costs O(1) space whatever the shape of the structure.

Reads pay for that. Following a pointer as of version i binary-searches the field's version list for the latest entry at or before i, so every step of every query carries an O(log m) factor in the number of versions. The scheme also needs versions to be totally ordered, which under full persistence means maintaining an order over a tree of them.

Node copying, from Driscoll, Sarnak, Sleator, and Tarjan in 1989, removes that read penalty. Each node carries its fields plus a fixed number of spare modification slots, each holding a field name, a version, and a value. An update writes a spare slot in O(1), and readers of older versions still see the original fields.

When the slots fill, the node is copied with the values current at the newest version and empty slots again, and every node pointing at it must be repointed — which may consume a slot there and cascade upward. Because each copy restores empty capacity, the amortized cost is O(1) space per update with O(1) worst-case slowdown, for any structure whose nodes have bounded in-degree.

Full persistence costs more than partial because the versions form a tree rather than a line. Node copying extends to it by maintaining a linear order over that tree, using a structure that answers whether one version precedes another in constant time and admits new versions between existing ones. With that order, the same slot-and-copy accounting applies and the bounds match: O(1) amortized space, O(1) slowdown.

Purely functional path copying gives full persistence with no version stamps at all, because nothing is mutated and every root is as updatable as any other. It pays O(log n) space per update rather than O(1) amortized, which is the price of having no bookkeeping to maintain.

Confluent persistence adds an operation combining two versions into one, such as concatenating two versions of a sequence. The history becomes a DAG, and a node can then be reachable along exponentially many paths from a version's root.

Concatenating a version with itself doubles its logical length, so after k such operations the structure describes a sequence of length 2^k having performed only k updates. Any scheme naming positions by path from the root inherits that blowup. Fiat and Kaplan gave the general treatment, with costs depending on the depth of the version DAG rather than the update count. This is the setting the finger tree operates in whenever two versions are joined.

Persistence breaks amortized analysis as usually practised. An amortized bound lets cheap operations build credit that an expensive one spends, which assumes each version is used once so the credit is consumed and does not return.

Take the version sitting immediately before an expensive operation and run that operation on it repeatedly. Each run starts from the same saved state and pays full cost, spending credit accumulated once many times over. A queue built from two lists with an O(n) reversal is O(1) amortized used ephemerally, and O(n) per operation when the version before the reversal is reused. This applies to any bound proved by the banker's or physicist's method.

Okasaki's answer is lazy evaluation with memoization. Suspend the expensive operation rather than running it, and let the first forcing pay the cost and cache the result. Reusing an old version finds the shared suspension already forced, so the second use reads the memoized value instead of repeating the work.

That restores the accounting: the banker's method is restated to assign debits to suspensions, discharged by the operations performed before a suspension is forced. Because memoization makes the payment happen at most once however many versions share it, the bound survives arbitrary reuse. Converting these amortized bounds to worst-case ones needs scheduling — forcing a fixed amount per operation so none inherits a large debt.

Storage engines reach path copying from another direction and call it copy-on-write. A B-tree is updated by writing a modified copy of the target page to free space, then copies of its ancestors, up to a root pointer switched in one atomic write. Before the switch the on-disk structure is the old version entirely; after it, the new one.

Rodeh's treatment of shadowing sets out the discipline, including the requirement that nodes be reachable by one path only, enforced by splitting and merging on the way down. ZFS and Btrfs build on that model, so a snapshot is a retained root. The cost is write amplification: updating one record rewrites every page on its path.

Keeping versions means keeping their nodes. A node is unreachable only when no retained root reaches it, which is a property of the whole version set, so reclamation needs reference counting or a tracing collector. Dropping a version frees only the nodes unique to it.

Memory therefore follows retained history rather than live data, and space grows even when the newest version is small. Systems that expose snapshots expose their lifetime too: a filesystem snapshot pins the blocks it references, and a long-lived LMDB read transaction pins the pages of its root. Reference counting is the usual choice because path copying never creates a cycle.

Persistence gives a snapshot for the cost of an update, readers that never coordinate with writers because nothing is mutated in place, undo as a retained pointer, and versions that can cross threads without synchronisation. For a structure of O(log n) depth, path copying delivers all of it for O(log n) allocation per update.

The costs are allocation on every write, memory held by retained versions, and worse locality than a mutable array. The binding constraint is that persistence is a property of the whole structure: it rules out parent pointers, rules out sharing a node between two positions in one version, and invalidates amortized bounds proved for ephemeral use.

Clojure's core collections are persistent by default, so an update returns a new collection sharing structure with the old; its maps and sets are hash-array mapped tries paying the path-copying cost on every assoc. Git's object model is the same technique over a directory tree: a commit that changes one file writes a new blob plus new tree objects along the path to it, sharing every unchanged subtree by hash, so checking out an old commit is a read rather than a restore.

On the storage side, ZFS and Btrfs implement copy-on-write B-trees so a snapshot is a retained root, and LMDB uses one to give lock-free readers a stable view without a write-ahead log. CouchDB takes the append-only form, writing updates to the end of the file so old roots stay readable in place.

A persistent structure keeps old versions queryable after an update. Path copying rebuilds the path to the change and shares the rest, at O(log n) space per update. Fat nodes record every write with a version stamp for O(1) space and an O(log m) read slowdown. Node copying combines both for O(1) amortized space and O(1) slowdown on any bounded in-degree structure.

Full persistence requires ordering a tree of versions, and confluent persistence admits merges that make a version's logical size exponential in the update count. Amortized bounds proved for ephemeral use do not survive, and laziness with memoization is what restores them. An old version costs whatever later updates copied away from it, and nothing more.