Persistent Data Structures, in depth: path copying, fat nodes, persistent segment trees, wide tries and the amortization trap

Kinds of persistence

The kinds differ in what they allow and what they cost.

• Partially persistent: every version can be read, only the newest updated. Versions form a line. Database snapshots and time-travel queries usually need only this.
• Fully persistent: every version can be read and updated, so updating an old version creates a branch and versions form a tree, like Git branches.
• Confluently persistent: versions can also be combined, such as concatenating two lists, so versions form a directed acyclic graph. This is the hardest to make efficient.

Purely functional code, where no node is mutated after creation, is automatically fully persistent. A useful mental model: a version is just a pointer to a root, and persistence is the promise that everything reachable from it stays as it was.

Three techniques and their costs

Driscoll, Sarnak, Sleator and Tarjan's 1989 paper "Making Data Structures Persistent" describes the three classic techniques for pointer-based structures.

1. Path copying. Never modify a node; copy it, then copy its parent so the parent points at the copy, up to the root. The new root is the new version. A balanced tree copies O(log n) nodes per update.
2. Fat nodes. Each field stores a history of (version, value) pairs. Updates append in O(1) space, but every read searches the history, adding an O(log m) factor for m versions.
3. Node copying. Give each node a few spare modification slots and copy it only when they fill. For nodes with a bounded number of incoming pointers this gives partial persistence with O(1) amortized extra time and space per update; node splitting extends it to full persistence.

Path copying usually wins: no version bookkeeping inside nodes, easy to reason about, and its O(log n) cost is what you already pay to walk the tree.

Path copying in a binary search tree

Here is path copying on an unbalanced binary search tree. Nodes are immutable named tuples, and insert returns a new root, rebuilding only the nodes on the search path. _replace creates a new tuple that shares every field it does not change, so the untouched child subtree is shared, not copied.

from typing import NamedTuple, Optional


class Node(NamedTuple):
    key: int
    left: Optional["Node"]
    right: Optional["Node"]


def insert(root, key):
    """Path copying: rebuild only the nodes on the search path."""
    if root is None:
        return Node(key, None, None)
    if key < root.key:
        return root._replace(left=insert(root.left, key))
    if key > root.key:
        return root._replace(right=insert(root.right, key))
    return root  # already present: share the whole version


def keys(root):
    return [] if root is None else keys(root.left) + [root.key] + keys(root.right)


v0 = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    v0 = insert(v0, k)
v1 = insert(v0, 45)
print("v0:", keys(v0))
print("v1:", keys(v1))
print("shared right subtree:", v0.right is v1.right)

Running it, plus a helper that counts distinct node objects reachable from both roots, prints:

v0: [20, 30, 40, 50, 60, 70, 80]
v1: [20, 30, 40, 45, 50, 60, 70, 80]
shared right subtree: True
distinct nodes across both versions: 11

Version v0 still has seven keys after v1 was created. The insert copied 50, 30 and 40 and created 45, so two versions cost 11 nodes instead of 15. In a balanced million-key tree, one update copies about 20 nodes. Rotations touch only nodes near the search path, so red-black trees, AVL trees and treaps are made persistent the same way; the treap deep dive covers the split and merge operations that make treaps especially convenient.

The persistent segment tree

The best-known algorithmic use of persistence is the persistent segment tree. Take an array a and the query "what is the k-th smallest value in a[l..r]?". Sort the distinct values and give each a rank. Build a segment tree over ranks that counts how many elements fall in each rank range. Then insert the array elements one at a time, keeping every version: version i holds counts for the prefix a[0..i-1]. Each insert is a point update, so path copying adds only O(log n) nodes.

The key insight is that counts subtract. For any rank range, count in version r+1 minus count in version l is the number of elements of a[l..r] in that range. So we can walk both versions down together: if the left children hold at least k elements of the subarray, go left; otherwise subtract that count from k and go right. A query is O(log n), and building costs O(n log n) time and space. If you are new to segment trees, read the segment tree guide first.

import bisect


class PersistentSegTree:
    """Count tree over value ranks; one new version per inserted element."""

    def __init__(self, size):
        self.size = size
        # Node 0 is the shared empty tree: its children point at itself.
        self.left, self.right, self.count = [0], [0], [0]

    def _new(self, l, r, c):
        self.left.append(l)
        self.right.append(r)
        self.count.append(c)
        return len(self.count) - 1

    def insert(self, root, pos):
        """Return a new root equal to `root` plus one at `pos`; `root` is untouched."""
        def go(node, lo, hi):
            if lo == hi:
                return self._new(0, 0, self.count[node] + 1)
            mid = (lo + hi) // 2
            if pos <= mid:
                return self._new(go(self.left[node], lo, mid), self.right[node], self.count[node] + 1)
            return self._new(self.left[node], go(self.right[node], mid + 1, hi), self.count[node] + 1)
        return go(root, 0, self.size - 1)

    def kth(self, old, new, k):
        """k-th smallest (1-based) rank among elements inserted between versions old and new."""
        lo, hi = 0, self.size - 1
        while lo < hi:
            mid = (lo + hi) // 2
            in_left = self.count[self.left[new]] - self.count[self.left[old]]
            if k <= in_left:
                old, new, hi = self.left[old], self.left[new], mid
            else:
                k -= in_left
                old, new, lo = self.right[old], self.right[new], mid + 1
        return lo


def build(a):
    values = sorted(set(a))
    tree = PersistentSegTree(len(values))
    roots = [0]
    for x in a:
        roots.append(tree.insert(roots[-1], bisect.bisect_left(values, x)))
    return values, tree, roots


def range_kth(values, tree, roots, l, r, k):
    """k-th smallest of a[l..r], 0-based inclusive indices."""
    return values[tree.kth(roots[l], roots[r + 1], k)]

Two implementation choices matter. Nodes live in parallel arrays and are addressed by index, which avoids per-object overhead and makes the memory cost explicit. And node 0 is a shared empty tree whose children point back at itself, so version 0 costs one node instead of a full empty tree.

Worked example: range k-th smallest

Take a = [5, 1, 4, 1, 9, 2, 6]. The distinct sorted values are [1, 2, 4, 5, 6, 9], so ranks run 0 to 5. Seven inserts create versions 1 to 7, each sharing everything except one root-to-leaf path with its predecessor. A small driver builds the tree for this array, runs four queries checked against sorted slices, then runs a random checker. This is its actual output:

values: [1, 2, 4, 5, 6, 9]
nodes: 27 for 7 inserts
kth(a[0..6], k=4) = 4  brute: 4
kth(a[1..4], k=2) = 1  brute: 1
kth(a[2..5], k=1) = 1  brute: 1
kth(a[3..6], k=3) = 6  brute: 6
random checks passed

Trace the second query, the 2nd smallest of a[1..4] = [1, 4, 1, 9], which compares version 5 (the first five elements) with version 1 (the first one). The root's left half covers ranks 0 to 2, values 1, 2 and 4. Version 5 has three elements there (1, 4 and 1) and version 1 has none, so k=2 fits and we go left. Within ranks 0 to 2, the left child covers ranks 0 to 1 and holds both 1s, so we go left again, and rank 0 alone holds both, so the answer is value 1. Three steps, without touching the array.

The 27 nodes are one shared empty node plus 26 created by seven inserts of three or four nodes each: the O(n log n) space bound in miniature. The last line comes from 2,000 random arrays with 20 random queries each, all compared against a sorted slice. Keep a checker like that, because sharing bugs are silent: mutating one node corrupts every version that shares it.

Wide tries: how real libraries do it

Binary trees make poor general-purpose immutable collections: log₂ n levels means many pointer hops and copied nodes. Production libraries use wide tries. Clojure's and Scala's persistent vectors branch 32 ways on the bits of the index, so a million elements need four levels and an update copies four small arrays. Hash array mapped tries (HAMTs), described by Phil Bagwell in 2001, implement persistent maps and sets with a 32-bit bitmap per node and a compact array of only the children that exist. Transients let one owner mutate freshly created nodes during a batch and then freeze the result, giving bulk-load speed without exposing mutation.

Why amortized bounds break

Persistence breaks amortized analysis. In the classic two-list queue, pushes go onto rear, pops come off front, and an empty front is refilled by reversing rear. Each element is reversed once, so operations are O(1) amortized.

Now keep versions. Take a version q with empty front and n elements in rear. Popping q costs O(n), prepaid by n cheap pushes. But you can pop q again, a million times, and each pop repeats the same reverse, because q never changes. The credit is spent once; the expensive work is repeated. Chris Okasaki's fixes use lazy evaluation with memoization, so a shared expensive step is computed once, or real-time structures with worst-case bounds. The rule: check that any amortized bound survives reusing an old version.

Persistence in systems

Persistence is everywhere in systems, usually under another name.

• Git stores commits as immutable trees of content-addressed objects; changing one file creates new objects only along its path. That is path copying with hashes as pointers.
• Copy-on-write B-trees in LMDB and Btrfs never overwrite a live page. A write copies the leaf and its ancestors, then atomically swaps the root, so readers keep a consistent snapshot without locks.
• Multi-version concurrency control keeps old row versions for snapshot readers: partial persistence with garbage collection. The immutable sorted runs in the LSM tree follow the same principle.

Memory and version retention

Every retained version pins every node it can reach. With garbage collection, a cache or closure holding an old root keeps a whole history alive; with an arena like the segment tree above, nothing is freed until the arena is dropped, so size it at about n times (ceil(log₂ n) + 1) nodes. Choose a retention policy explicitly: all versions, the last k, or only those referenced by open snapshots.

Failure modes

Trade-offs and alternatives

Offline problems often have cheaper answers. If all queries are known in advance, range k-th smallest also yields to a merge-sort tree, a wavelet tree, or the Mo's algorithm family. If you only undo recent changes, a rollback log, as in union-find with rollback, uses less memory. Choose persistence for online access to many past versions, cheap snapshots for concurrent readers, or lock-free sharing across threads; avoid it when only the latest state matters, because a mutable array beats a 32-way trie on every operation it supports.

What to do next

1. Write down which kind you need: partial, full or confluent. Most needs are partial.
2. Start with path copying over a balanced or wide structure; measure before trying anything fancier.
3. Make nodes immutable in the type system so sharing bugs cannot happen silently.
4. Implement the persistent segment tree above for range k-th smallest, with a brute-force random checker.
5. Test every amortized bound by operating repeatedly on an expensive old version.
6. Document a version-retention policy and monitor live versions or arena size.
7. Benchmark your language's immutable collections against mutable baselines before building your own.