immutable persistent data structures

1 Background and motivation

Immutable persistent data structures arise from two related but distinct goals: immutability (preventing in‑place mutation) and persistence (preserving all historical versions). Their development has been driven by the needs of functional programming, concurrent systems, and versioned data management.

1.1 Immutability in programming

In most imperative languages, variables and data structures are mutable: an update changes the value in place. Immutability, by contrast, guarantees that once a data structure is created, its state never changes. Any operation that would modify it instead produces a new structure while leaving the original intact. This property simplifies reasoning about code, eliminates a broad class of bugs caused by unintended sharing, and makes it safe to share data across threads without locking. Functional programming languages such as Clojure, Haskell, and Scala embrace immutability as a core tenet.

1.2 Persistence vs. ephemeral data structures

An *ephemeral* data structure supports only a single, current version; modifications destroy the prior state. A *persistent* data structure, by contrast, allows access to older versions after updates. Persistence is further classified as *partial* (only the most recent version can be modified) or *full* (any version can be modified, creating a branching history). Immutable persistent data structures provide full persistence by construction, since every “modification” creates a new version without invalidating any previous one.

2 Fundamental concepts

The design of immutable persistent data structures relies on two key ideas: sharing structure among versions and efficiently copying only the parts that change.

2.1 Structural sharing

Instead of copying an entire data structure for each update, implementations reuse large portions of the old structure. For example, when updating a single element in a tree, only the nodes along the path from root to the changed leaf need to be duplicated; all other subtrees are shared between the old and new versions. This technique dramatically reduces memory and time overhead.

2.1.1 Path copying

Path copying is the simplest form of structural sharing. In a tree, to set a value at a leaf, a new root and every node on the path to that leaf are created; the unchanged subtrees are referenced directly. The old root remains accessible and unchanged. The cost is proportional to the depth of the tree (usually logarithmic in the number of elements).

2.1.2 Fat nodes

Fat nodes store multiple values in a single node, each associated with a version timestamp. When an update occurs, the affected node simply adds a new value tag. Queries must examine all versions to find the correct one for a given time. While this approach can save memory by avoiding node duplication, it complicates garbage collection and is less common than path copying in modern implementations.

2.2 Version control analogy

The relationship between versions of a persistent data structure resembles a version‑control system (e.g., Git). Each update creates a new commit, and unchanged parts are shared via pointers—analogous to Git’s reuse of unchanged blobs and trees. The data structure itself forms a DAG (directed acyclic graph) of versions, enabling branching and merging.

3 Classic implementations

Many common data structures have been adapted to be both immutable and persistent, with the trade‑off between performance and implementation complexity.

3.1 Persistent linked lists

A singly linked list becomes persistent by simply allowing sharing of tails. Prepending an element creates a new “cons” cell whose tail points to the old list; the old list remains intact. Random access requires linear time. This structure is ubiquitous in functional languages such as Lisp, Scheme, and Haskell (where it appears as the default list type).

3.2 Persistent binary trees

Binary search trees can be made persistent by applying path copying on each insertion or deletion. The most common variants use self‑balancing schemes to keep depths logarithmic.

3.2.1 Red‑black trees

The persistent red‑black tree (P‑RBT) maintains the red‑black balance invariants while copying nodes along the update path. Insertion and deletion follow the usual rotations and color flips, but each modified node is freshly allocated. The resulting structure guarantees O(log n) operations and is used, for example, in Clojure’s sorted maps and in Haskell’s Data.Map.

3.2.2 Treaps

A treap (tree + heap) combines a binary search tree with a heap property based on random priorities. Persistent treaps support split, merge, and other operations with high probability in O(log n). Their simplicity and good performance make them popular in competitive programming and in libraries such as Immutable.js.

3.3 Persistent arrays

Regular arrays are inherently ephemeral, but persistent array abstractions can be built using trees or linked structures.

3.3.1 VList

A VList is a persistent array that stores elements in contiguous blocks (chunks). Updates copy only the block containing the modified index and all blocks along a spine. It supports O(log n) access and update, with good cache locality. VLists were notably used in the early versions of Clojure’s vectors.

3.3.2 Relaxed Radix Balanced Trees (RRB‑trees)

RRB‑trees extend the radix‑balanced tree (used in Clojure’s persistent vector) to support efficient concatenation and slicing. They store elements in fixed‑size leaf blocks and use a flexible branching factor. Operations such as index access, update, append, and concatenation run in O(log n) time, making them ideal for sequence operations in functional languages.

4 Practical usage

Immutable persistent data structures have found application across many domains, from language runtimes to web applications and databases.

4.1 Functional programming languages

Several modern languages provide families of persistent data structures as part of their standard or widely adopted libraries.

4.1.1 Clojure's persistent vector and hash map

Clojure’s most iconic persistent structures are its vector (based on a 32‑way trie) and its hash map (using a hash‑array mapped trie). Both achieve near‑O(1) operations in practice due to the fixed branching factor, making them perform comparably to mutable structures for everyday workloads. Clojure also provides persistent sorted maps and sets built on red‑black trees.

4.1.2 Haskell's Data.Map and Data.Sequence

Haskell’s Data.Map is a persistent ordered map implemented as a size‑balanced tree (based on Adams’ trees). Data.Sequence uses finger trees to provide amortized O(1) access at both ends and O(log n) concatenation. The language’s purity ensures that all standard data structures are immutable by default.

4.2 Immutable.js in JavaScript

Immutable.js is a library that brings persistent data structures (lists, maps, sets, stacks) to JavaScript, a primarily mutable language. It uses structural sharing (e.g., hash‑array mapped tries) to enable efficient cloning and comparison. The library is widely used in React applications for state management, where immutable updates simplify change detection.

4.3 Database versioning and snapshot isolation

Persistent data structures are a natural fit for database systems that support multiversion concurrency control (MVCC). In MVCC, each transaction sees a snapshot of the database at its start time; updates create new versions of records. This is conceptually identical to persistent data structures at the page or tuple level. Systems such as PostgreSQL and Datomic (which uses persistent data structures internally) rely on this approach for snapshot isolation and time‑travel queries.

5 Performance and trade‑offs

While immutable persistent structures offer correctness and concurrency benefits, they introduce performance characteristics that differ from their mutable counterparts.

5.1 Time complexity characteristics

Most persistent structures have the same asymptotic complexity as their ephemeral versions for lookups, insertions, and deletions (often O(log n)). However, the constant factors are typically larger due to extra allocations and pointer chasing. In practice, careful engineering (e.g., using wide trees) can bring constant factors close to unity.

5.2 Space overhead and garbage collection

Structural sharing reduces duplication, but every update still allocates O(log n) new nodes. Over many updates, the total memory used can be significantly larger than an in‑place version, especially if old versions are retained. Garbage‑collected environments must reclaim unused versions; reference counting or tracing collectors can become a bottleneck if many old nodes are kept alive.

5.3 Amortized vs. worst‑case guarantees

Some persistent structures (e.g., finger trees) offer amortized guarantees that depend on occasional large operations. Others, such as red‑black trees, provide strict worst‑case bounds. Designers must choose between predictable latency and better average performance.

6 Advanced topics

6.1 Concurrency and lock‑free persistence

Because immutable structures are read‑only after creation, they can be shared freely without locks. This property makes them attractive for concurrent programming. However, the act of “updating” still requires some coordination to ensure that the new version is correctly published.

6.1.1 Software transactional memory

Software transactional memory (STM) systems often build on persistent data structures. For example, Clojure’s STM uses persistent maps as the backing store for refs; a transaction reads a snapshot and, on commit, atomically replaces the root pointer with a new version. This eliminates locking while ensuring consistency.

6.2 Persistent data structures in distributed systems

In distributed environments, the ability to maintain independent copies and later merge changes is valuable.

6.2.1 Conflict‑free replicated data types (CRDTs)

CRDTs are data structures that can be replicated across nodes and merged without conflict, using algebraic properties like commutativity or idempotence. Many CRDTs are built on persistent structures, because persistent versions can be combined by taking the union of operations or by merging the underlying trees. Examples include grow‑only sets, last‑writer‑wins registers, and replicated growable arrays (RGAs).

7 See also

• Functional programming
• Immutable object
• Persistence (computer science)
• Hash array mapped trie
• Finger tree
• Data versioning