> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/persistent_data_structures.md).

# Persistent data structures

## Basic idea

A persistent data structure preserves previous versions after an update. Rather than copying the entire structure, functional implementations use immutability and structural sharing: copy the path to changed nodes and reuse unaffected subtrees.

## Key facts

* Partial persistence permits queries of all versions but updates only the newest version.
* Full persistence permits updates to any version, producing a version tree.
* Confluent persistence additionally permits merging versions.
* Path copying in a balanced tree costs $O(\log n)$ new nodes per update.
* HAMTs provide persistent maps; radix-balanced and RRB trees provide persistent vectors.
* Persistence simplifies snapshots, undo, speculative computation, and concurrent reads but can complicate reclamation and cache locality.

## Resources

<https://en.wikipedia.org/wiki/Persistent_data_structure>