Persistent data structure: Difference between revisions

Revision as of 14:52, 13 November 2023

Revision as of 12:47, 30 November 2023

Line 9:

==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 [[Total order|linear ordering]] among each version of the data structure.<ref>{{Citation|last1=Conchon|first1=Sylvain|chapter=Semi-persistent Data Structures|pages=322–336|publisher=Springer Berlin Heidelberg|isbn=9783540787389|last2=Filliâtre|first2=Jean-Christophe|doi=10.1007/978-3-540-78739-6_25|title=Programming Languages and Systems|volume=4960|series=Lecture Notes in Computer Science|year=2008|doi-access=free}}</ref> In the fully persistent model, both updates and queries are allowed on any version of the data structure. In some cases the [[Computer performance|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)|rope data structure]].<ref>{{Cite book|title=RRB-Trees: Efficient Immutable Vectors|last=Tiark|first=Bagwell, Philip Rompf|date=2011|oclc=820379112}}</ref> 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.<ref>{{Citation|last1=Brodal|first1=Gerth Stølting|title=PurelyAlgorithms Functional– WorstESA Case Constant Time Catenable Sorted Lists2006|date=2006|series=Lecture Notes in Computer Science|pages=172–183|publisher=Springer Berlin Heidelberg|isbn=9783540388753|last2=Makris|first2=Christos|last3=Tsichlas|first3=Kostas|chapter=Purely Functional Worst Case Constant Time Catenable Sorted Lists |volume=4168 |doi=10.1007/11841036_18|citeseerx=10.1.1.70.1493}}</ref>

==Techniques for preserving previous versions==