Persistent Data Structures

in reviewThis lesson is complete and being validated before release - details may still change.

Persistent tree

Loading interactive demo…

Each box is a node holding one key, labelled with the version that made it, smaller keys to its left and larger to its right. A dashed link is a pointer a copy reused, so the subtree below it is shared with an older version. The strip beneath lists the versions, each marked once committed; tap one to draw the tree it sees, at any step. The strip under that is every node ever allocated, the drawn version's marked.Take the tour, or press and explore. Legend:

The panel beside the stage is the real PersistentTree class from the published library executing in your browser, with the current line highlighted.

The node being read, and the ancestors the current insert has copied.
The leaf the current insert attached, and versions already committed.
Nodes the drawn version made, and the pointers between them.
Nodes made by the version just before the drawn one.
A pointer the drawn version's copies reused: the subtree below is shared.
Older nodes the drawn version shares, and versions not yet made.

versions counts the roots committed so far, the empty tree included; nodes allocated is every node ever made, the keys plus the copies; copied counts the ancestors duplicated along the paths and shared the pointers reused instead; height is the levels of the drawn version, the most any insert into it would copy.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The rule: a node, once made, never changes. An ordinary binary search tree inserts by walking down and writing one pointer in the parent of the new leaf. That single write is what destroys the old tree. A persistent tree forbids it: every node is final the moment it is allocated. The insert still walks down exactly as before, comparing once per level and reading nodes without touching them, and still makes a new leaf. But the leaf's parent cannot be made to point at it. So the parent is copied: a new node with the same key, one pointer aimed at the new leaf, and the other pointer the original's. The copy's parent cannot point at the copy either, so it is copied too, and so on up to the root. The last copy is the new version's root.

Path copying. The nodes duplicated are exactly the path from the root to the new leaf, one per level, so an insert into a tree of height $h$ allocates

1 + h \text{ nodes},

one leaf and $h$ copies. Everything off the path is untouched and shared: a copy's second pointer is the original's, so the whole subtree below it now belongs to both versions, stored once. The dashed links on the stage are those reused pointers. In a balanced tree $h = O(\log n)$ , so $n$ inserts cost $O(n \log n)$ nodes in all for $n + 1$ fully readable versions, against $O(n^2)$ for copying each tree whole.

Why every version survives. The old root was not changed, and no node it can reach was changed, because the only nodes made were new ones. Reading from the old root therefore gives the old tree, byte for byte, however many inserts have happened since. Tap any version in the strip, at any step, and the stage draws exactly what that version sees: the nodes made by it, the nodes made by the version before, and the older nodes it shares, outlined. This is partial persistence in the vocabulary of Driscoll, Sarnak, Sleator and Tarjan: every version can be read, only the newest is extended. Full persistence, where any version can be updated and the versions form a tree, needs more machinery; the path copying here is the simplest of the techniques their paper gives.

The cost follows the height. The sorted run scenario makes the point the balanced-trees lesson made, with a sharper edge: eight keys in increasing order build a chain, and inserting the $k$ -th key copies all $k - 1$ ancestors. Nothing is ever shared, and the eight versions cost

\sum_{k=1}^{8} k = 36 \text{ nodes}

for eight keys. The library tree here does not rebalance, so you can see the chain; a persistent AVL or red-black tree copies the same path and rotates among the copies, keeping every insert at $O(\log n)$ new nodes. Okasaki's book works through exactly that red-black tree in a page.

Beyond trees. The same move works on any linked structure: copy what you change, share the rest. A persistent hash map is a wide trie over the bits of the hash (Bagwell's hash array mapped trie), and with 32 children per node a map of a million keys is four levels deep, so an update copies four nodes. A persistent vector is the same trie indexed by position. Clojure made these its default collections, which is what lets a function hand out a map and never worry that the caller will change it underneath. Git's object store is the same picture at the scale of a repository: a commit's tree is immutable and content-addressed, and a new commit copies only the directories on the path to the changed file.

Where this goes next. Persistence keeps old versions; the next lessons in the unit turn to problems whose structure is a tree of subproblems, where the point is to reuse an answer rather than keep it.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

A pool of immutable records. Every node lives in a map by id with readonly fields and is never written after allocate. The ids are creation order, so a copy has a new id and the original keeps its own; the stage labels each box with the version that made it for the same reason.
One root per version. roots[v] is all a version is: an id, or null for version 0. Reading a version is a walk from its root; nothing is tagged with version ranges, nothing is checked at read time.
The path is remembered, then replayed upward. The descent pushes each node and the side taken; the loop after attach walks that list from the bottom, so the copy of each ancestor is made after the node it must point at exists. below carries the newest node up one level at a time.
share is the pointer not changed. A copy takes old.left or old.right on the side the insert did not use; the emit fires only when that child exists, so a copy at the bottom of a chain shares nothing, which the sorted run shows.
Insert only, by design. Delete copies the path the same way, with the usual successor dance below it, and is left out so the trace stays about one idea. PERSISTENT_MAX_KEYS keeps the leaning picture readable.

An ordinary data structure forgets: insert a key and the old tree is overwritten in place, and keeping it means a full copy. In 1986 Driscoll, Sarnak, Sleator and Tarjan asked what it costs to keep every version of a linked structure readable, and answered: almost nothing. A node that never changes can be shared by every version that reaches it, so an update only copies the path it touched. Chris Okasaki showed that functional languages had built their data this way all along, Phil Bagwell made it fast for hash maps, and Clojure shipped it as a language's default collections.

1986Neil Sarnak and Robert Tarjan - 'Planar point location using persistent search trees' in Communications of the ACM: a sweep line's search tree is kept at every event, so a query reads the version for its x in logarithmic time with linear space.source
1989Driscoll, Sarnak, Sleator and Tarjan - 'Making data structures persistent' in the Journal of Computer and System Sciences (first presented at STOC 1986) defines partial and full persistence and gives path copying and the fat node and node copying methods, with O(1) amortized space per update.source
1996Chris Okasaki - His Carnegie Mellon thesis 'Purely Functional Data Structures' shows how lazy evaluation and amortization give functional, and so persistent, queues, deques and heaps with the bounds of their imperative cousins; it became the 1998 Cambridge book of the same name.source
2001Phil Bagwell - 'Ideal Hash Trees', an EPFL report, describes the hash array mapped trie: a hash table as a wide trie over hash bits, the structure a persistent hash map copies by the path.source
2007Rich Hickey - Clojure makes persistent vectors, maps and sets its default collections, built as 32-way tries over Bagwell's design so that an update copies a path about log32 n nodes long.source

Used today

Functional languages - Clojure, Scala and Haskell collections are immutable: an update returns a new version that shares all but the path with the old, so no caller ever sees a change.
Undo histories - An editor that keeps each state as a version can undo and redo by switching roots, with the unchanged parts of the document stored once.
Git objects - A commit's tree is content-addressed and immutable; a new commit copies only the directories on the path to a changed file and shares every other subtree with its parent.
MVCC snapshots - Databases that let readers see a consistent snapshot while writers proceed keep old versions of index pages alive until no reader needs them.

Did you know

Clojure's persistent vector is a 32-way trie, so a vector of a million elements is four levels deep and an update copies four nodes; Rich Hickey described the lookup cost as effectively constant, since log32 of any practical size is a small number.source
Okasaki's banker's queue is two lists and a promise: the front list is lazily reversed onto the back before it runs out, and the credit accounting of amortized analysis survives even when old versions are reused, which a naive amortized queue cannot promise.source
The planar point location result that started the field needed a tree that could be queried in the past: the sweep line's search tree at every x is a version, and with path copying all of them fit in space linear in the segments.source
Driscoll, Sarnak, Sleator and Tarjan separated partial persistence, where only the newest version can be changed, from full persistence, where any version can be updated and the versions form a tree rather than a line.source

scenario

versions: 8 of 8
nodes allocated: 17
copied: 10
shared: 7
height: 3 levels in v7

persistent-tree.ts

import type { Tracer } from "../trace";export const PERSISTENT_MIN_KEY = 1;export const PERSISTENT_MAX_KEY = 99;/** Keys the tree takes at most, so every version's picture stays readable. */export const PERSISTENT_MAX_KEYS = 12;/** Which child of a node an insert passed through or replaced. */type PersistentSide = "left" | "right";export interface PersistentNode {  /** Numbered in creation order; a copy is a new node with a new id, the original keeps its own. */  readonly id: number;  readonly key: number;  readonly left: number | null;  readonly right: number | null;  /** The version whose insert created this node. */  readonly version: number;}export interface PersistentReport {  /** Ancestors copied over every insert. */  readonly copies: number;  /** Keys inserted. */  readonly keys: number;  /** Nodes allocated in all: the keys plus the copies. */  readonly nodes: number;  /** Untouched children pointed at by a copy, over every insert. */  readonly shared: number;  /** Versions readable, version 0 (the empty tree) included. */  readonly versions: number;}/** * A binary search tree that keeps every version it has ever been. * Nothing is overwritten: a node, once created, never changes. An * insert descends from the latest root as any search tree does, hangs a * new leaf, and then walks back up the path it took, copying each * ancestor with one child pointer changed to the node just made below * and the other pointer shared, untouched, with the old tree. The last * copy is the new root, and the old root still describes the old tree * exactly, so every version stays readable forever. The copies cost * one node per level, O(log n) in a balanced tree, and everything off * the path is shared between the versions rather than duplicated. * * Insert only: delete is a non-goal here (it copies the path the same * way, with the usual successor dance below it). Keys arrive in the * order given and the tree is not rebalanced, so a sorted run leans * and copies a longer path each time, which the lesson shows on purpose. * * Time: O(height) per insert, O(size) to read a version in order. * Space: O(height) new nodes per insert, O(n log n) over n inserts into * a balanced tree. */export class PersistentTree {  private readonly pool = new Map<number, PersistentNode>();  /** Root id per version; index 0 is the empty tree. */  private readonly roots: (number | null)[] = [null];  private readonly held = new Set<number>();  private readonly keysHeld = new Set<number>();  private copies = 0;  private shared = 0;  constructor(private readonly tracer?: Tracer) {}  /** How many versions exist, version 0 (empty) included. */  get versions(): number {    return this.roots.length;  }  /** The root id of a version, null for the empty tree. */  root(version: number): number | null {    this.checkVersion(version);    return this.roots[version] ?? null;  }  /** The nodes a version reaches, in key order; copies. */  nodes(version: number): PersistentNode[] {    const out: PersistentNode[] = [];    const walk = (id: number | null): void => {      if (id === null) return;      const node = this.node(id);      walk(node.left);      out.push({ ...node });      walk(node.right);    };    walk(this.root(version));    return out;  }  /** Every node ever allocated, by id; copies. */  allNodes(): PersistentNode[] {    return [...this.pool.values()].map((node) => ({ ...node }));  }  /** Nodes on the longest root-to-leaf path of a version; 0 for the empty tree. */  height(version: number): number {    const depth = (id: number | null): number => {      if (id === null) return 0;      const node = this.node(id);      return 1 + Math.max(depth(node.left), depth(node.right));    };    return depth(this.root(version));  }  /**   * Inserts into the latest version and returns the number of the version   * it makes: descend, attach a leaf, copy the path back up with the   * changed child swapped in and the other child shared.   */  insert(key: number): number {    this.checkKey(key);    if (this.held.has(key)) throw new RangeError(`the tree already holds ${key}`);    if (this.keysHeld.has(key)) throw new RangeError(`the tree already holds ${key}`);    if (this.held.size >= PERSISTENT_MAX_KEYS) throw new RangeError(`the tree takes at most ${PERSISTENT_MAX_KEYS} keys`);    if (this.keysHeld.size >= PERSISTENT_MAX_KEYS) throw new RangeError(`the tree takes at most ${PERSISTENT_MAX_KEYS} keys`);    const version = this.roots.length;    const path: { id: number; side: PersistentSide }[] = [];    let at = this.roots[version - 1] ?? null;    while (at !== null) {      const node = this.node(at);      const side: PersistentSide = key < node.key ? "left" : "right";      // ▸ walk down from the latest root as any search tree does: smaller goes left, larger goes right, and nothing on the way is changed      this.tracer?.emit("descend", { key, node: at, side, version });      path.push({ id: at, side });      at = side === "left" ? node.left : node.right;    }    let below = this.allocate(key, null, null, version);    this.held.add(key);    this.keysHeld.add(key);    // ▸ the side the key wanted is empty: a new leaf is made there, a node only the new version will reach    this.tracer?.emit("attach", { id: below, key, version });    for (let i = path.length - 1; i >= 0; i--) {      const { id, side } = path[i]!;      const old = this.node(id);      const original = this.node(id);      const left = side === "left" ? below : old.left;      const left = side === "left" ? below : original.left;      const right = side === "right" ? below : old.right;      const right = side === "right" ? below : original.right;      const copy = this.allocate(old.key, left, right, version);      const copy = this.allocate(original.key, left, right, version);      this.copies++;      // ▸ back up the path, each ancestor is copied with one pointer aimed at the node just made below; the original keeps its old children      this.tracer?.emit("copy", { from: id, key: old.key, side, to: copy, version });      this.tracer?.emit("copy", { from: id, key: original.key, side, to: copy, version });      const other = side === "left" ? old.right : old.left;      const other = side === "left" ? original.right : original.left;      if (other !== null) {        this.shared++;        // ▸ the copy's other pointer is the original's, untouched: that whole subtree is shared with the old tree, not duplicated        this.tracer?.emit("share", { node: other, parent: copy, side: side === "left" ? "right" : "left" });      }      below = copy;    }    this.roots.push(below);    // ▸ the last copy is the new version's root; the old root still describes the old tree exactly    this.tracer?.emit("version", { copied: path.length, root: below, version });    return version;  }  /** Inserts the keys in order, one version each, and reports. */  run(keys: readonly number[]): PersistentReport {    if (keys.length > PERSISTENT_MAX_KEYS) throw new RangeError(`${keys.length} keys exceeds ${PERSISTENT_MAX_KEYS}`);    for (const key of keys) this.insert(key);    return this.report();  }  report(): PersistentReport {    return { copies: this.copies, keys: this.held.size, nodes: this.pool.size, shared: this.shared, versions: this.roots.length };    return { copies: this.copies, keys: this.keysHeld.size, nodes: this.pool.size, shared: this.shared, versions: this.roots.length };  }  private allocate(key: number, left: number | null, right: number | null, version: number): number {    const id = this.pool.size;    this.pool.set(id, { id, key, left, right, version });    return id;  }  private node(id: number): PersistentNode {    const node = this.pool.get(id);    if (!node) throw new RangeError(`no node ${id}`);    return node;  }  private checkKey(key: number): void {    if (!Number.isInteger(key) || key < PERSISTENT_MIN_KEY || key > PERSISTENT_MAX_KEY) {      throw new RangeError(`key must be an integer in [${PERSISTENT_MIN_KEY}, ${PERSISTENT_MAX_KEY}]`);    }  }  private checkVersion(version: number): void {    if (!Number.isInteger(version) || version < 0 || version >= this.roots.length) {      throw new RangeError(`version must be an integer in [0, ${this.roots.length - 1}]`);    }  }}

versions =: 8
allocated =: 17
copied =: 10
shared =: 7

8 versions readable from 17 nodes: 10 copies along the paths and 7 subtrees shared rather than duplicated. Tap a version to draw the tree it sees.

import type { Tracer } from "../trace";export const PERSISTENT_MIN_KEY = 1;export const PERSISTENT_MAX_KEY = 99;/** Keys the tree takes at most, so every version's picture stays readable. */export const PERSISTENT_MAX_KEYS = 12;/** Which child of a node an insert passed through or replaced. */type PersistentSide = "left" | "right";export interface PersistentNode { /** Numbered in creation order; a copy is a new node with a new id, the original keeps its own. */ readonly id: number; readonly key: number; readonly left: number | null; readonly right: number | null; /** The version whose insert created this node. */ readonly version: number;}export interface PersistentReport { /** Ancestors copied over every insert. */ readonly copies: number; /** Keys inserted. */ readonly keys: number; /** Nodes allocated in all: the keys plus the copies. */ readonly nodes: number; /** Untouched children pointed at by a copy, over every insert. */ readonly shared: number; /** Versions readable, version 0 (the empty tree) included. */ readonly versions: number;}/** * A binary search tree that keeps every version it has ever been. * Nothing is overwritten: a node, once created, never changes. An * insert descends from the latest root as any search tree does, hangs a * new leaf, and then walks back up the path it took, copying each * ancestor with one child pointer changed to the node just made below * and the other pointer shared, untouched, with the old tree. The last * copy is the new root, and the old root still describes the old tree * exactly, so every version stays readable forever. The copies cost * one node per level, O(log n) in a balanced tree, and everything off * the path is shared between the versions rather than duplicated. * * Insert only: delete is a non-goal here (it copies the path the same * way, with the usual successor dance below it). Keys arrive in the * order given and the tree is not rebalanced, so a sorted run leans * and copies a longer path each time, which the lesson shows on purpose. * * Time: O(height) per insert, O(size) to read a version in order. * Space: O(height) new nodes per insert, O(n log n) over n inserts into * a balanced tree. */export class PersistentTree { private readonly pool = new Map<number, PersistentNode>(); /** Root id per version; index 0 is the empty tree. */ private readonly roots: (number | null)[] = [null]; private readonly held = new Set<number>(); private readonly keysHeld = new Set<number>(); private copies = 0; private shared = 0; constructor(private readonly tracer?: Tracer) {} /** How many versions exist, version 0 (empty) included. */ get versions(): number { return this.roots.length; } /** The root id of a version, null for the empty tree. */ root(version: number): number | null { this.checkVersion(version); return this.roots[version] ?? null; } /** The nodes a version reaches, in key order; copies. */ nodes(version: number): PersistentNode[] { const out: PersistentNode[] = []; const walk = (id: number | null): void => { if (id === null) return; const node = this.node(id); walk(node.left); out.push({ ...node }); walk(node.right); }; walk(this.root(version)); return out; } /** Every node ever allocated, by id; copies. */ allNodes(): PersistentNode[] { return [...this.pool.values()].map((node) => ({ ...node })); } /** Nodes on the longest root-to-leaf path of a version; 0 for the empty tree. */ height(version: number): number { const depth = (id: number | null): number => { if (id === null) return 0; const node = this.node(id); return 1 + Math.max(depth(node.left), depth(node.right)); }; return depth(this.root(version)); } /** * Inserts into the latest version and returns the number of the version * it makes: descend, attach a leaf, copy the path back up with the * changed child swapped in and the other child shared. */ insert(key: number): number { this.checkKey(key); if (this.held.has(key)) throw new RangeError(`the tree already holds ${key}`); if (this.keysHeld.has(key)) throw new RangeError(`the tree already holds ${key}`); if (this.held.size >= PERSISTENT_MAX_KEYS) throw new RangeError(`the tree takes at most ${PERSISTENT_MAX_KEYS} keys`); if (this.keysHeld.size >= PERSISTENT_MAX_KEYS) throw new RangeError(`the tree takes at most ${PERSISTENT_MAX_KEYS} keys`); const version = this.roots.length; const path: { id: number; side: PersistentSide }[] = []; let at = this.roots[version - 1] ?? null; while (at !== null) { const node = this.node(at); const side: PersistentSide = key < node.key ? "left" : "right"; // ▸ walk down from the latest root as any search tree does: smaller goes left, larger goes right, and nothing on the way is changed this.tracer?.emit("descend", { key, node: at, side, version }); path.push({ id: at, side }); at = side === "left" ? node.left : node.right; } let below = this.allocate(key, null, null, version); this.held.add(key); this.keysHeld.add(key); // ▸ the side the key wanted is empty: a new leaf is made there, a node only the new version will reach this.tracer?.emit("attach", { id: below, key, version }); for (let i = path.length - 1; i >= 0; i--) { const { id, side } = path[i]!; const old = this.node(id); const original = this.node(id); const left = side === "left" ? below : old.left; const left = side === "left" ? below : original.left; const right = side === "right" ? below : old.right; const right = side === "right" ? below : original.right; const copy = this.allocate(old.key, left, right, version); const copy = this.allocate(original.key, left, right, version); this.copies++; // ▸ back up the path, each ancestor is copied with one pointer aimed at the node just made below; the original keeps its old children this.tracer?.emit("copy", { from: id, key: old.key, side, to: copy, version }); this.tracer?.emit("copy", { from: id, key: original.key, side, to: copy, version }); const other = side === "left" ? old.right : old.left; const other = side === "left" ? original.right : original.left; if (other !== null) { this.shared++; // ▸ the copy's other pointer is the original's, untouched: that whole subtree is shared with the old tree, not duplicated this.tracer?.emit("share", { node: other, parent: copy, side: side === "left" ? "right" : "left" }); } below = copy; } this.roots.push(below); // ▸ the last copy is the new version's root; the old root still describes the old tree exactly this.tracer?.emit("version", { copied: path.length, root: below, version }); return version; } /** Inserts the keys in order, one version each, and reports. */ run(keys: readonly number[]): PersistentReport { if (keys.length > PERSISTENT_MAX_KEYS) throw new RangeError(`${keys.length} keys exceeds ${PERSISTENT_MAX_KEYS}`); for (const key of keys) this.insert(key); return this.report(); } report(): PersistentReport { return { copies: this.copies, keys: this.held.size, nodes: this.pool.size, shared: this.shared, versions: this.roots.length }; return { copies: this.copies, keys: this.keysHeld.size, nodes: this.pool.size, shared: this.shared, versions: this.roots.length }; } private allocate(key: number, left: number | null, right: number | null, version: number): number { const id = this.pool.size; this.pool.set(id, { id, key, left, right, version }); return id; } private node(id: number): PersistentNode { const node = this.pool.get(id); if (!node) throw new RangeError(`no node ${id}`); return node; } private checkKey(key: number): void { if (!Number.isInteger(key) || key < PERSISTENT_MIN_KEY || key > PERSISTENT_MAX_KEY) { throw new RangeError(`key must be an integer in [${PERSISTENT_MIN_KEY}, ${PERSISTENT_MAX_KEY}]`); } } private checkVersion(version: number): void { if (!Number.isInteger(version) || version < 0 || version >= this.roots.length) { throw new RangeError(`version must be an integer in [0, ${this.roots.length - 1}]`); } }}