What are Persistent Data Structures?
– Persistent data structures hold a great importance in the field of computing.
– These are the data structures which are capable of retaining their previous version even after being modified.
– These data structures are effective and highly immutable.
– Immutable is their capability to generate a new updated structure whenever some operation is carried out on the original structure.
– A persistent data structure is not to be considered a data structure that commits to the persistent storage like a disk.
– A data structure is said to be partially persistent if only the new version is modifiable and rest can only be accessed.
– Likewise, if every version of a data structure is both modifiable and accessible it is said to be fully persistent. – Con-fluent persistent data structures which are data structures that are capable of generating a new version from the existing twos through some merge or meld operation.
– On the other hand, ephemeral are the data structures that do not possess this persistent quality.
– Persistent data structures find their frequent use in the field of functional and logical programming.
– The pure functional programming involves only immutable data and therefore requires that all the data structures must be fully persistent.
Method to create Persistent Data Structure
– There is an alternate method for the creation of persistent data structures which is using in – place updating of data.
– This method makes sure that the data structures use less storage disk as well as time when compared to the data structures generated using pure functional programming.
– The persistence feature can be achieved through simple copy operation.
– However, this proves to be inefficient in the case of CPU and RAM usage.
– This is so because the changes made to a data structure by most of the operations are quite small.
– Here, a better alternative would be to make a comparison of similarity among the new and old versions of the data structures so that the common structure could be shared between them.
– For example, for a number of tree structures, a same sub tree can be used.
– But this method too has a disadvantage which is that it calls for an environment with garbage collection since sooner or later it gets in-feasible determining by how many versions a part of structure is shared.
Based on two types of persistent data structures we have two types of models namely partially persistence model and fully persistence model. In this model the previous version of the data structure might be questioned but it is the latest version that might be updated. This calls for a need of linear ordering for the versions.
Three methods have been defined for a balanced binary search tree:
1. Fat node
2. Path copying
3. A combination
Example of Persistent Data Structure
– Cons based list or the singly linked list is the simplest example of persistent data structure i.e., a list of objects which is formed by each object having reference to the next object.
– This data structure has been called persistent since a tail of the list can be taken which is not duplicated but would be shared among new and the old list.
– The sharing of tail will remain invisible to the program till the tail’s contents are immutable.
– There are certain data structures which are reference based and are usually adapted for the creation of a new persistent version:
2. Red black trees etc.
But, there are some data structures which require a little more effort such as the following:
2. Double – ended queues
3. Min – dequeue
4. Random access list
5. Random access queue
6. Random access stack