Persistent data structure: Difference between revisions

Revision as of 10:19, 11 March 2022

Revision as of 22:58, 16 March 2022

Line 1:

{{Short description|Data structure that always preserves the previous version of itself when it is modified}}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 Tarjans' 1986 article.

{{Distinguish|Persistent storage}}

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''.

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 object|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 Tarjans' 1986 article.<ref name="Driscoll">{{Cite book |vauthors=Driscoll JR, Sarnak N, Sleator DD, Tarjan RE |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |year=1986 |chapter=Making data structures persistent |isbn=978-0-89791-193-1 |doi=10.1145/12130.12142 |journal=Proceeding STOC '86. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing |pages=109–121|citeseerx=10.1.1.133.4630 |s2cid=364871 }}</ref>

AThese datatypes structure is '''partially persistent''' if all versions can be accessed but only the newest version can be modified. Theof data structurestructures isare '''fullyparticularly persistent'''common ifin every version can be both accessedlogical and modified.functional If there is also a meld or merge operation that can create a new version from two previous versionsprogramming, the data structure is called '''confluently persistent'''. Structures that are not persistent are called ''ephemeral''.<ref name="kaplan2">{{Cite journal |author=Kaplan, Haim |year=2001 |title=Persistent data structures |url=http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps |journal=Handbook on Data Structures and Applications}}</ref> as languages in those paradigms discourage (or fully forbid) the use of mutable data.

These types of data structures are particularly common in [[Logic programming|logical]] and [[functional programming]],<ref name="kaplan2" /> as languages in those paradigms discourage (or fully forbid) the use of mutable data.

==Partial versus full persistence==

Line 29 ⟶ 26:

===A combination===

Driscoll, Sarnak, [[Daniel Sleator|Sleator]], [[Robert Tarjan|Tarjan]] came up<ref name="Driscoll">{{Cite book |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |vauthors=Driscoll JR, Sarnak N, Sleator DD, Tarjan RE |journal=Proceeding STOC '86. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing |year=1986 |isbn=978-0-89791-193-1 |pages=109–121 |chapter=Making data structures persistent |citeseerx=10.1.1.133.4630 |doi=10.1145/12130.12142 |s2cid=364871}}</ref> with a way to combine the techniques of fat nodes and path copying, achieving O(1) access slowdown and O(1) modification space and time complexity.

In each node, one modification box is stored. This box can hold one modification to the node—either a modification to one of the pointers, or to the node's key, or to some other piece of node-specific data—and a timestamp for when that modification was applied. Initially, every node's modification box is empty.