A persistent data structure is one that preserves its previous versions when it is updated. Rather than mutating the data in place, an update returns a new version while leaving the old one intact and still usable. To make this affordable, the new version shares as much of its internal structure as possible with the old one, a technique called structural sharing, so an update copies only the parts that actually change.
The definitive treatment is Chris Okasaki’s 1996 Carnegie Mellon thesis “Purely Functional Data Structures” (CMU-CS-96-177). It shows how to design efficient data structures for purely functional languages, where data is immutable, using techniques such as lazy evaluation and amortized analysis. It presents both classical structures, like red-black trees and binomial queues, and new ones built specifically for functional settings, with code in Standard ML and Haskell.
Persistence is central to languages built around immutability. Clojure’s reference documentation states that “All of the Clojure collections are immutable and persistent. In particular, the Clojure collections support efficient creation of ‘modified’ versions, by utilizing structural sharing.” The result behaves like a value while keeping operations cheap.
This combination matters for correctness as well as performance. Because old versions are never disturbed, persistent structures are inherently thread-safe and easy to reason about: a reference to a collection always sees the same contents, even as other code derives new versions from it. That property is a large part of why immutable, persistent collections are a foundation of functional programming.