Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Immutable and persistent data structures

What does path copying cost, and why does the same mechanism run MVCC and table time travel?

A persistent data structure (in this sense, not "stored on disk") never changes in place. An update returns a new version and leaves the old version intact.

The mechanism: structural sharing

To update one node in a tree of depth d, copy the path from the root to that node and share every untouched subtree with the old version. Cost: O(d) space and time per update, instead of O(1). Benefit: every reader holding an old root sees a complete, consistent snapshot with zero synchronization, forever.

# A persistent binary search tree: insert returns a NEW root.
class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        return Node(node.key, insert(node.left, key), node.right)   # copy this node, share the right subtree
    if key > node.key:
        return Node(node.key, node.left, insert(node.right, key))   # copy this node, share the left subtree
    return node                                                      # already present: share everything

v1 = insert(insert(insert(None, 50), 30), 70)
v2 = insert(v1, 20)     # v1 is unchanged; v2 shares the node 70 with v1
insert(v1, 20)2 nodes copied · 1 shared

For a (Hash Array Mapped , a trie keyed by hash bits) with 32-way branching, the depth is : four levels at a million entries, six at a billion. So an update copies four to six nodes. Each node holds up to 32 pointers (about 256 bytes), so an update copies roughly 5 × 256 B ≈ 1.3 KB instead of changing 8 bytes. This is the basis of the persistent maps and vectors in Clojure and Scala.

The constant factor is real: persistent structures run roughly 2–10× slower and larger than mutable equivalents on a single thread. If you have one thread and no need for snapshots, they are a pure loss. It is important to say this plainly before describing why they win.

Why they win

Immutability converts a concurrency problem into a memory-management problem.

  • Readers synchronize on nothing.
  • Writers coordinate only on one root-pointer swap: a single from the old root to the new root.

This is the most extreme possible use of "do not mutate".

But the garbage is now yours. Every superseded version keeps its copied path alive, and you must decide when old versions become unreachable. That is the topic of safe reclamation. structures and safe reclamation are one topic split across two pages, and neither makes sense alone.

The same idea at every scale

The same mechanism appears at very different scales.

  • MVCC is persistence applied to a table. (multi-version concurrency control) means readers see the row versions that were valid when their snapshot began, while writers add new versions. Postgres's xmin/xmax (the transaction ids that created and removed a row version), Oracle's undo segments and an 's natural multi-versioning are the same structure at different granularity.
  • Copy-on-write B-trees (for example LMDB) combine two escapes: single writer plus never-mutate. The result is readers and crash consistency without a (write-ahead log).
  • Iceberg and Delta Lake are persistent data structures at table scale. A new table snapshot shares most of its manifests (lists of data files) with the previous one. The root pointer is the current metadata file. Committing is a CAS on that pointer. Time travel is just holding an old root. The is snapshot expiration and orphan-file cleanup. This is the same mechanism as a Clojure vector, across twelve orders of magnitude of scale.
  • Git is the same object (commits share unchanged trees and files). Spark's RDD lineage is the same idea at the dataset level.

In data engineering, the main payoff is usually not concurrency at all. It is reproducibility. Deterministic reprocessing, auditability, and the ability to answer "what did this table say last Tuesday" all come from the property that makes readers . This is one of the few cases here where a structural choice pays in a currency outside the technical stack.