In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjan's 1986 article. A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral. These types of data structures are particularly common in logical and functional programming, as languages in those paradigms discourage (or fully forbid) the use of mutable data.
Partial versus full persistence In the partial persistence model, a programmer may query any previous version of a data structure, but may only update the latest version. This implies a linear ordering among each version of the data structure. In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the performance characteristics of querying or updating older versions of a data structure may be allowed to degrade, as is true with the rope data structure. In addition, a data structure can be referred to as confluently persistent if, in addition to being fully persistent, two versions of the same data structure can be combined to form a new version which is still fully persistent.
Techniques for preserving previous versions
Copy-on-write One method for creating a persistent data structure is to use a platform provided ephemeral data structure such as an array to store the data in the data structure and copy the entirety of that data structure. This is an inefficient technique because the entire backing data structure must be copied for each write, leading to worst case O ( n ⋅ m ) {\displaystyle O(n\cdot m)} performance characteristics for m modifications of an array of size n. Copy-on-write memory management can reduce the price for an update from Θ ( n ) {\displaystyle \Theta (n)} to O ( B u ) {\displaystyle O(Bu)} , where B is the memory block size and u the number of pages updated in an operation.
Fat node The fat node method is to record all changes made to node fields in the nodes themselves, without erasing old values of the fields. This requires that nodes be allowed to become arbitrarily "fat". In other words, each fat node contains the same information and pointer fields as an ephemeral node, along with space for an arbitrary number of extra field values. Each extra field value has an associated field name and a version stamp which indicates the version in which the named field was changed to have the specified value. Besides, each fat node has its own version stamp, indicating the version in which the node was created. The only purpose of nodes having version stamps is to make sure that each node only contains one value per field name per version. In order to navigate through the structure, each original field value in a node has a version stamp of zero.
Complexity of fat node With using fat node method, it requires O(1) space for every modification: just store the new data. Each modification takes O(1) additional time to store the modification at the end of the modification history. This is an amortized time bound, assuming modification history is stored in a growable array. At access time, the right version at each node must be found as the structure is traversed. If m modifications were to be made, then each access operation would have O ( log m ) {\displaystyle O(\log m)} slowdown resulting from the cost of finding the nearest modification in the array. Alternatively, one can employ the van Emde Boas tree at each node (possibly the space-efficient version using hashing) to reduce the time for an access to O ( log log m ) {\displaystyle O(\log \log m)} at the cost of increasing update time to O ( log log m ) {\displaystyle O(\log \log m)} . If only partial persistence is required, the time for an update can be kept at its original order of magnitude, modulo randomization and amortization (since the time for a single update to the fat node can be amortized expected O ( 1 ) {\displaystyle O(1)} ).
Path copying This method assumes that the data structure is a linked graph of nodes. On update, a copy is made of all nodes on the path to any node which is about to be modified. These changes must then be cascaded back through the data structure: all nodes that pointed to the old node must be modified to point to the new node instead. These modifications cause more cascading changes, and so on, until the root node is reached.
Complexity of path copying With m modifications, this costs O(log m) additive lookup time. Modification time and space are bounded by the maximal number of ancestors for any node in the data structure times the cost of the update in the ephemeral data structure. In a Balanced Binary Search Tree without parent pointers the worst case modification time complexity is O(log n + update cost). However, in a linked list the worst case modification time complexity is O(n + update cost).
… excerpt ends here. Continue reading the full article.
