Ordinary data structures are ephemeral implying that any update made to it destroys the old version and all we are left with is the updated latest one.
Persistent Data Structures change this notion and allow us to hold multiple versions of a data structure at any given instant of time. This enables us to go back in “time” and access any version that we want.
Depending on the operations allowed on the previous versions, persistence is classified into three categories:
Persistent Data Structures find their applications spanning the entire spectrum of Computer Science, including but not limited to - Functional Programming Languages, Computational Geometry, Text Editors, and many more.
Since persistent data structures thrive on high memory usage, they require some garbage collection system to prevent memory leaks.
A naïve way to implement Partial Persistence is by utilizing the Copy-on-Write semantics and naively creating a deep copy upon every update. This technique is inefficient because upon every writes the entire data structure is deep copied.