Persistent, Immutable, Succinct and Compressed Structures

Introduction

Advanced data structures are increasingly required to support not only efficient queries and updates, but also reproducibility, concurrency, historical inspection, and memory-conscious storage. These requirements arise in version-control systems, databases, compilers, geographic information systems, scientific workflows, and machine-learning pipelines. A conventional mutable structure represents one current state. A persistent structure represents multiple states simultaneously, allowing earlier versions to remain accessible after updates. An immutable structure prevents in-place modification, while structural sharing allows new versions to reuse unchanged components of old versions.

Succinct and compressed structures address a related but distinct problem: representing data close to the information-theoretic lower bound while retaining useful query performance. Bit vectors, rank/select dictionaries, compressed trees, and compact indexes are central examples. Persistence emphasizes time and version history; succinctness emphasizes space; compression exploits statistical regularities. In advanced systems, these properties are often combined.

This chapter develops the principles, implementation techniques, complexity trade-offs, and governance implications of these structures. Particular attention is given to functional data structures, persistent trees, copy-on-write, bit-vector operations, and applications in trustworthy AI and reproducible computation.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Distinguish mutable, immutable, partially persistent, fully persistent, and confluent structures.
2. Explain structural sharing and copy-on-write, including their time and space costs.
3. Design and analyze persistent linked structures, trees, maps, and vectors.
4. Use rank, select, and related operations on bit vectors.
5. Compare succinct representations with ordinary pointer-based structures.
6. Evaluate persistence and compression for reproducibility, auditability, concurrency, and AI data pipelines.
7. Identify implementation hazards involving memory reclamation, hashing, security, and update amplification.

1. Conceptual Foundations

1.1 Mutability, immutability, and persistence

A mutable data structure permits an operation to change the representation in place. If a reference points to a mutable map, inserting a key may alter what every holder of that reference observes. This is efficient in a single-threaded setting, but aliasing makes reasoning difficult: the effect of an operation depends on which other components share references.

An immutable object cannot change after construction. An apparent update creates a new object. Immutability simplifies reasoning because an object’s value remains stable, supports safe sharing between threads, and makes cached results easier to validate.

Persistence is a property of the data-structure interface: an update produces a new version while preserving access to one or more earlier versions. Thus, persistence is stronger than merely using immutable fields. A structure may be immutable but expose only its latest version; such a structure is not necessarily persistent.

The principal persistence models are:

If an update operation is written as U(V_i, x) → V_i+1, the old version V_i remains valid. In a fully persistent system, an update may instead use any V_j. In a confluent system, a merge operation can derive a version from two preceding versions, although conflict semantics must be explicitly defined.

1.2 Structural sharing

Structural sharing means that two versions contain references to the same unchanged substructures. Consider an immutable binary search tree. Inserting a key changes only nodes on the search path. The new tree copies those nodes and points to the old subtrees elsewhere. If the tree height is h, the update generally allocates O(h) new nodes rather than copying all n nodes.

Sharing is safe only when shared components are immutable. If a shared node can later be modified, an update in one version may silently corrupt another version. This is the central reason immutable representation and persistence are closely associated.

The space used by a sequence of updates is approximately:

where S_initial is the initial representation size, m is the number of updates, and a_i is the number of newly allocated words or nodes for update i. The equation assumes that reclaimed objects are not counted and that shared objects are counted only once. For a balanced tree with bounded path copying, a_i = O(log n); for a persistent linked list with insertion at the front, a_i = O(1).

1.3 Copy-on-write

Copy-on-write (COW) delays copying until a shared object is about to be modified. Multiple processes or versions may initially reference one physical page or node. A write checks whether the object is shared. If it is, the writer copies it and modifies the private copy; otherwise, it modifies the object directly.

COW is common in operating-system process creation, database snapshots, memory-mapped files, and persistent storage engines. It differs from purely functional path copying because COW may retain mutable objects and use reference counts, page tables, or ownership metadata to detect sharing. Its granularity may be a machine word, object, page, or large storage block.

COW reduces unnecessary copying, but its cost can be unpredictable. A small logical update may cause a full page or block to be copied. Consequently, the relevant metric is not merely logical complexity but physical write amplification:

Here A_w is dimensionless. A value substantially greater than 1 indicates that representation-level copying exceeds the logical change. The ratio depends on allocation granularity, workload, and locality.

2. Functional Data Structures

Functional data structures express updates as functions that return new values rather than modifying old values. Their key design principles are referential transparency, persistent values, and local reconstruction.

2.1 Persistent lists, stacks, and queues

A persistent singly linked list supports constant-time insertion at the front:

cons(x, L) = Node(x, L)

The old list L remains valid, and the new list shares its tail. Removing the first item is also constant time. However, appending to the end requires traversal and is generally linear in the list length.

A persistent queue can be implemented using two immutable lists: a front list and a rear list. When the front becomes empty, the rear list is reversed to form a new front. Amortized analysis distributes the reversal cost across operations. If a sequence of q queue operations performs total work proportional to q, the amortized cost per operation is O(1), although an individual operation may cost O(q). This guarantee assumes a standard potential argument and a workload in which elements are not repeatedly moved without being consumed.

2.2 Path copying in trees

For an immutable search tree, insertion copies every node from the root to the modified leaf and reuses all untouched subtrees. In an unbalanced tree, the worst-case height is O(n). In a balanced tree, the height is O(log n), so lookup and update are typically logarithmic.

A persistent tree must preserve its ordering and balancing invariants in every version. Red-black trees, AVL trees, weight-balanced trees, and B-trees can all be adapted, but balancing may require copying additional nodes or reconstructing local neighborhoods. In a persistent B-tree, path copying can copy several pages per update; higher branching reduces height but increases the amount of metadata or page-local work.

2.3 Hash-array mapped tries

Persistent maps often use hash-array mapped tries (HAMTs). A key’s hash is divided into fixed-width segments. Each segment selects a branch at one trie level. Bitmap indexing stores only occupied branches rather than a full array of child pointers. An update copies the nodes along the hash path and shares the rest.

If each level consumes b hash bits, the nominal branching factor is 2^b. The expected path length is approximately:

where w is the number of hash bits used and the ceiling function rounds upward. This estimate assumes a sufficiently distributed hash function and ignores collision nodes and implementation-specific compression. Hash collisions must still be handled correctly, usually through collision buckets or secondary structures.

3. Persistent Vectors and Trees in Practice

A persistent vector is commonly implemented as a shallow trie with a high branching factor and a tail array. Random access and updates are typically logarithmic in the number of elements, but the logarithm is small because the branching factor is large. Updating one element copies the path from the root to a leaf block, while the remaining blocks are shared.

Persistent range structures are especially important for analytics. A persistent segment tree stores aggregate information over intervals. Each update changes one position and copies the nodes on the corresponding root-to-leaf path. For a domain of size [[MATH,N]] and a balanced binary segmentation, the number of copied nodes is [[MATH,O(log N)]]. A query on an interval also takes O(log N) for a standard segment tree, assuming the interval operation is compatible with the stored aggregate, such as sum, minimum, or maximum.

A useful application is historical threshold analysis. Suppose each version records the distribution of model scores after one data-ingestion batch. A persistent frequency tree can answer questions such as “How many scores in version [[MATH,V_j]] lie within interval [[MATH,[a,b]]]]?” without reconstructing the entire historical dataset.

Complexity comparison

Big-O values describe asymptotic behavior, not constant factors. Cache locality, allocator overhead, garbage collection, and pointer width can dominate performance for realistic datasets.

4. Succinct Structures and Bit Vectors

A structure is succinct when its representation uses space close to the information-theoretic minimum while supporting useful operations. If a bit vector contains n bits, its raw content already requires n bits. A pointer-based representation of individual bits would usually consume far more because of object headers and addresses.

4.1 Bit-vector operations

Let B[0…n−1] be a bit vector. Important operations include:

• access(i): return B[i].
• rank₁(i): count 1-bits in positions 0 through i−1.
• rank₀(i): count 0-bits in the same prefix.
• select₁(k): return the position of the kth 1-bit.
• select₀(k): return the position of the kth 0-bit.

Under the stated zero-based rank convention, the following identity holds when the requested select operation exists:

for one-based k. If rank is instead defined inclusively, the identity changes. Definitions must therefore be documented precisely.

A practical rank directory divides the vector into superblocks and blocks. It stores cumulative counts at superblock boundaries and smaller relative counts inside each superblock. A query combines a directory value with a machine-word population count. With suitable tables or broadword operations, rank can be supported in constant time on a word-RAM model while using near-linear space. Select can be implemented using sampling plus local search, often in constant or near-constant time depending on the representation.

The count of zeros in a prefix follows directly from the prefix length:

This assumes rank counts positions before i and that 0 ≤ i ≤ n.

4.2 Balanced parentheses and tree encoding

Ordered rooted trees can be encoded using balanced-parentheses sequences. An opening parenthesis represents entering a node and a closing parenthesis represents leaving it. A tree with n nodes requires 2n parentheses, or 2n bits when represented as a bit vector.

With rank, select, and excess operations, one can support navigation such as parent, child, subtree size, and depth. The representation is often much smaller than storing explicit pointers, particularly when the tree is static. However, dynamic updates to succinct encodings are substantially more difficult than queries, and supporting persistence adds further metadata and copying costs.

5. Compression and Compressed Representations

Compression reduces storage by exploiting redundancy. Lossless compression is required when exact reconstruction matters, as in source data, model features, audit logs, and database indexes. A compressed structure may use variable-length codes, run-length encoding, delta encoding, grammar compression, or entropy-coded blocks.

For a symbol distribution with probabilities p₁, p₂, …, p_σ, the zeroth-order empirical entropy is:

Here σ is the alphabet size, p_i ≥ 0, and ∑p_i = 1. The result is measured in bits per symbol. It is a theoretical benchmark for memoryless coding; practical compressed representations include headers, dictionaries, alignment, and query-support overhead.

Delta encoding stores differences between successive sorted values. It is effective when gaps are small. Run-length encoding stores a symbol and the length of its run, making it effective for long repeated regions. These techniques can be combined with bit vectors and succinct indexes.

Compression and persistence interact in complex ways. Updating a compressed block may require decoding and recompressing the block, producing high write amplification. Conversely, immutable compressed blocks can be shared efficiently across many versions when updates are sparse. A block size that is too large increases update cost; a block size that is too small reduces compression effectiveness and increases metadata.

6. Versioning, Reproducibility, and Auditability

Persistent structures provide an explicit basis for reproducible computation. A pipeline can retain the exact data, configuration, feature definition, and model artifact used for each result. Rather than overwriting a table, a system creates a new root or snapshot. A version identifier may be a cryptographic digest of the root and relevant metadata.

A robust audit record should identify:

• the parent version or versions;
• the operation and its parameters;
• the responsible principal or service;
• the software and schema versions;
• timestamps and provenance metadata;
• integrity digests for roots or immutable blocks;
• authorization and retention information.

A digest does not prove that the underlying computation was correct; it provides evidence that the referenced content has not changed under the assumed cryptographic model. Auditability therefore requires both integrity mechanisms and meaningful operational semantics.

Persistence also enables differential inspection. If two versions share most subtrees, the differing roots identify a small set of changed regions. This can support efficient review, rollback, and compliance reporting. However, persistence is not automatically privacy-preserving. Historical versions may retain deleted personal data, and shared blocks may complicate erasure obligations. Retention and secure deletion policies must be designed at the storage layer.

7. Case Study: Reproducible Feature Store for Model Monitoring

The following is an illustrative case study.

Background

A financial-risk laboratory trains models from monthly customer features. Earlier practice mutated feature tables in place, making it difficult to reproduce a model’s training set after corrections or late-arriving records. Investigators also needed to compare predictions before and after a feature-engineering change.

Problem

The laboratory required historical snapshots, efficient comparison, controlled access, and lower storage consumption. A full copy of every monthly table would be expensive, while ordinary mutable tables provided weak historical guarantees.

Approach

The team represented each logical table as an immutable persistent map whose root identified a version. Large column blocks were compressed using delta encoding and bit-packed validity vectors. Unchanged blocks were structurally shared. A manifest recorded the root digest, schema identifier, transformation code version, and authorization event.

For a corrected record, the system copied only the map path and the affected compressed block. Since the block had to be rewritten, the implementation measured write amplification using A_w. Small blocks reduced rewrite cost but weakened compression; larger blocks improved compression but increased update cost. Benchmarking under the expected correction workload selected an intermediate block size.

Outcome

Analysts could reconstruct the exact feature snapshot used by a historical model and compare two versions by traversing their roots. Storage grew approximately with changed paths and blocks rather than with complete table copies. Access controls prevented ordinary users from reading obsolete sensitive versions, while regulated retention policies preserved designated snapshots.

Learning points

1. Persistence supports reproducibility only when metadata and computation versions are also retained.
2. Structural sharing reduces logical storage but does not eliminate allocator, index, or metadata costs.
3. Compression must be evaluated together with update frequency and block granularity.
4. Historical retention can conflict with privacy requirements; deletion semantics must be explicit.
5. Integrity hashes improve audit evidence but do not replace access control, validation, or human review.

8. Implementation and Design Guidance

A sound implementation begins by defining the version model and mutation semantics. Important design choices include:

• Granularity: object, node, page, block, or file.
• Update pattern: random, append-only, batched, or range-based.
• Sharing policy: automatic reference sharing, ownership tracking, or explicit snapshots.
• Memory management: tracing garbage collection, reference counting, epochs, or arena reclamation.
• Concurrency: immutable roots, atomic root publication, transactions, or multi-version concurrency control.
• Integrity: content-addressed identifiers, checksums, signatures, and manifests.
• Compression: static or dynamic coding, block size, and query support.

Reference counting is simple for acyclic structures but cannot reclaim cycles without additional mechanisms. Tracing collectors can reclaim unreachable historical versions after a retention policy permits deletion. In concurrent systems, reclamation must account for readers that still hold old roots. Epoch-based reclamation and hazard pointers are common techniques for safe memory reuse.

Hash-consing can canonicalize equal immutable substructures so that structurally identical objects are stored once. It can improve sharing but introduces hash-table overhead and potential denial-of-service concerns if adversarial inputs cause excessive collisions. Cryptographic content addressing provides stronger identity properties than ordinary hash-consing, but digest computation and collision assumptions must be documented.

9. Limitations, Security, and Ethical Considerations

Persistence can increase storage use when updates touch large portions of a structure. It can also create retention risks because “deleted” content may remain reachable from an old root or backup. Systems handling personal or confidential data should define legal retention, deletion, redaction, and access policies before adopting immutable histories.

Compressed indexes can leak information through size, timing, or access patterns. For example, a compressed representation may reveal the frequency of a category even when content is encrypted. Side-channel analysis is relevant in multi-tenant services.

Immutability does not guarantee truth. A persistent record may faithfully preserve an erroneous feature or biased label. AI governance still requires data-quality controls, provenance, bias assessment, model validation, and accountability. Reproducibility should include the ability to explain transformations and assumptions, not merely the ability to retrieve bytes.

10. Contemporary Developments

Modern storage engines combine persistent trees, log-structured storage, snapshots, and content-addressed blocks. Distributed systems use immutable manifests and Merkle structures to synchronize versions and verify integrity. Succinct indexes are important in large-scale text search, genome analysis, graph processing, and compressed column stores.

Research continues on dynamic succinct structures, learned indexes, cache-aware persistent layouts, GPU-compatible compact representations, and authenticated data structures. Learned indexes may predict positions in sorted data, but they do not remove the need for exact correction and worst-case safeguards. Persistent structures are also being explored for machine-learning datasets, experiment tracking, vector databases, and verifiable data pipelines.

Best Practices

1. Specify whether persistence is partial, full, or confluent.
2. Make shared nodes immutable or enforce ownership before mutation.
3. Measure physical allocation and write amplification, not only asymptotic complexity.
4. Define rank and select indexing conventions unambiguously.
5. Benchmark cache behavior, allocation, garbage collection, and compression together.
6. Store schemas, code versions, configuration, and provenance with data roots.
7. Use authenticated identifiers where integrity and synchronization matter.
8. Design retention and deletion semantics before enabling historical snapshots.
9. Test collision handling, malformed inputs, and adversarial workloads.
10. Treat compactness as a systems property: query speed, update cost, memory, and operational risk must be evaluated jointly.

Chapter Summary

Persistent structures preserve historical versions while allowing updates to create new states. Immutability makes structural sharing safe, and path copying enables efficient persistent lists, trees, vectors, maps, and range structures. Copy-on-write provides a related mechanism that postpones copying until a shared object is modified, although physical write amplification may be substantial.

Succinct structures reduce representation overhead by using bit vectors, rank/select dictionaries, balanced-parentheses encodings, and compact indexes. Compression exploits redundancy through entropy-aware coding, runs, deltas, and blocks, but compression can increase update complexity. Persistence, succinctness, and compression therefore require workload-sensitive design.

For AI and data-intensive systems, these structures support reproducibility, version comparison, rollback, provenance, and auditability. They do not by themselves guarantee correctness, fairness, privacy, or regulatory compliance. Effective designs combine structural techniques with integrity protection, access control, retention policy, validation, and transparent metadata.

Key Terms

Persistence: The ability to retain and access one or more earlier versions after updates.

Immutability: The property that an object cannot be changed after construction.

Structural sharing: Reuse of unchanged substructures by multiple versions.

Copy-on-write: A technique that copies a shared object only when modification is attempted.

Partial persistence: A model in which all versions are readable but only the newest is updated.

Full persistence: A model in which any version can be read and updated.

Confluent persistence: Persistence allowing versions to be combined through merge operations.

Path copying: Creating new nodes along an update path while sharing unaffected subtrees.

Functional data structure: A structure whose updates return new values rather than mutating existing values.

Persistent vector: An immutable sequence commonly implemented using a shallow trie and shared blocks.

HAMT: Hash-array mapped trie used for efficient persistent maps and sets.

Succinct structure: A representation using space close to an information-theoretic minimum while supporting queries.

Bit vector: An indexed sequence of zeros and ones.

Rank: An operation counting occurrences of a bit in a prefix.

Select: An operation returning the position of the kth occurrence of a bit.

Compression: Reduction of representation size by exploiting redundancy.

Write amplification: The ratio of physical bytes written to logically changed bytes.

Structural hash: A digest identifying content or a root of an immutable structure.

Provenance: Metadata describing the origin, transformations, and lineage of data.

Auditability: The ability to inspect and verify relevant historical actions and states.

Review Questions

Short Answer Questions

1. What is the difference between immutability and persistence?
2. Why is structural sharing safe only when shared components cannot be mutated?
3. Define rank and select for a bit vector.
4. What is write amplification in a copy-on-write system?
5. Name two advantages and one limitation of persistent data structures.

Long Answer Questions

1. Explain path copying in a persistent balanced search tree and analyze its time and space costs.
2. Compare partial, full, and confluent persistence with suitable applications.
3. Describe how rank directories support efficient bit-vector queries.
4. Discuss the interaction between compression, block size, and persistent updates.
5. Evaluate how persistent structures contribute to reproducibility and auditability in AI pipelines.

Analytical / Application Questions

1. Design a persistent data structure for historical range-sum queries over successive data-ingestion batches. State the update, query, sharing, and retention strategies.
2. A system stores compressed blocks of 64 KiB but logically changes only 4 KiB per update. Calculate A_w and discuss two ways to reduce its practical impact.
3. An organization wants immutable model-training snapshots but must honor deletion requests for personal data. Propose a design that addresses historical reproducibility, access control, cryptographic integrity, and deletion semantics.

Multiple Choice Questions with Answers

Question 1

Which persistence model allows every version to be read but permits updates only to the newest version?

A. Ephemeral persistence

B. Partial persistence

C. Full persistence

D. Confluent persistence

Correct Answer: B. Partial persistence

Question 2

In path copying for a balanced persistent search tree, a typical update creates how many new nodes?

A. O(1) regardless of tree height

B. O(n) in every case

C. O(log n)

D. O(n log n)

Correct Answer: C. O(log n)

Question 3

What is the principal safety condition for structural sharing?

A. All nodes must be stored on disk

B. Shared components must be immutable

C. Every version must use a different hash function

D. Updates must always be performed in place

Correct Answer: B. Shared components must be immutable

Question 4

Under the convention that rank₁(i) counts 1-bits before position i, what is rank₀(i)?

A. rank₁(i) − i

B. i + rank₁(i)

C. i − rank₁(i)

D. n − rank₁(i)

Correct Answer: C. i − rank₁(i)

Question 5

A copy-on-write system writes 64 KiB physically when only 4 KiB changes logically. What is the write amplification?

A. 0.0625

B. 4

C. 16

D. 256

Correct Answer: C. 16

Question 6

Which operation returns the position of the kth occurrence of a specified bit?

A. Access

B. Rank

C. Select

D. Compress

Correct Answer: C. Select

Question 7

Which structure is especially suitable for persistent range-aggregate queries after point updates?

A. Persistent segment tree

B. Unordered mutable array only

C. Plain stack

D. Run-length decoder only

Correct Answer: A. Persistent segment tree

Question 8

What does a content digest of an immutable root primarily provide?

A. Proof that the computation was unbiased

B. Evidence of content integrity under cryptographic assumptions

C. Automatic deletion of personal data

D. A guarantee of constant-time updates

Correct Answer: B. Evidence of content integrity under cryptographic assumptions

Question 9

For a persistent singly linked list, inserting an item at the front generally requires what new space?

A. O(1)

B. O(log n)

C. O(n)

D. O(n²)

Correct Answer: A. O(1)

Question 10

Which statement best describes succinct structures?

A. They always compress data lossily

B. They use space close to a lower bound while retaining useful query operations

C. They require every element to have a pointer

D. They cannot support rank or select

Correct Answer: B. They use space close to a lower bound while retaining useful query operations