Introduction
A persistent data structure always retains every historical version and supports the immutable nature of operations.
Categories of Persistence
Partially Persistent
All versions can be accessed, but only the latest version can be modified.
Fully Persistent
All versions can both be accessed and modified.
If merging two historical versions is supported, the structure is also called confluently persistent.
Practical Applications
Geometric Computation
Many offline algorithms in computational geometry, such as the sweep-line algorithm, sweep through once and answer all queries, which is excellent in terms of time complexity. Under an online requirement, however, scanning once for every query raises the query complexity from logarithmic to linear. Persistence offers another way to think about this situation: we use the sweep line's time axis as a changing reference, and persist the related structure. As long as we can move through this time axis while answering a query in logarithmic time, we can solve the original problem dynamically.
String Processing
Persistence can enable highly efficient merging operations and prevent performance degradation caused by generating large numbers of duplicate strings, allowing operations in many aspects to remain well below linear time. For example, C++ rope is a persistent data structure. The idea is useful not only for string operations: whenever the data being processed contains many repeated parts, persistence may help.
Version Rollback
This corresponds to redo/undo in most application software. If a database or operation history uses a complex structure for efficient updates (unlike the inverse operation of a hash or set, which takes only constant or logarithmic time), a persistent structure reduces the cost of quickly rolling back changes.
A database itself may be rolled back in constant time by recording only the changed parts. At the application layer, however, most implementations discard the cache and recompute a new structure. Sometimes the size of a rollback is m, but recomputing the structure costs n+m. If n and m differ greatly, repeated rollbacks feel very slow.
Functional Programming
Functional programming needs special data structures to match the language's characteristics, among which immutability is especially important for parallel environments and debugging. For example, Java introduced the stream class after Java 8 as an object-oriented feature supporting functional syntax and special capabilities such as lazy evaluation and an infinite value domain.