The recent trend in designing mass-scale electronic devices is to emphasize as much as possible software role in the devices. It means that the modules responsible for delivering particular functionalities are planned in such way that software part of the device realizes most of the work and hardware is meant to be as cheap as possible while preserving basic quality assurance. In simple words, it is beneficial to spend big amount of funds to prepare sophisticated software recompensating for even small drop of hardware production cost. One of the common example of such approach is to resign from using modules to maintain power supply in case of power failure. In such case a question occurs: How to maintain data integrity when the power failure may happen at any time? Software answer for this question is to use a method for storing data that assures resistance against data corruption. Using persistence data structures is one of those methods.

So what is persistent data structure?

It is a data structure that preserves older version of itself during its modification. In that case, if the currently being modified structure get corrupted, there is always an older version from just before the modification that is safe and can be used. In case of power failure during modification process of such structure, all the modifications are lost, obviously. However using some transactional system along with the assurance of having the previous version of the data structure should be enough to meet most functionality criteria for maintaining data integrity.

How does persistent data structure work?

Let’s assume that we store data in tree-like structure. On the picture below, the tree includes 6 nodes named A-F. Now, let’s assume that we want to modify one of the nodes of the tree – let it be E indicated by red color. To do so in a safe way, we cannot directly modify this node – thus we create a copy of this node (E’ on the diagram). Creating a copy of the modified node is not enough – the new version of the node has to be included in the tree. It requires modifying of the parent node of the modified one (C on a diagram). Thus, new version of the C node has to be created. Then, also parent of the C node has to be modified, and so on until the root node. Finally, we had to modify three nodes of the tree – three new versions of the previous nodes were created – they are indicated as green. Also, one of those new nodes is a new root of the tree (A’). If the entire process of the modification will process uninterrupted, the new version of the tree will be used as a current version, otherwise (for example, in case of power failure), the untouched old version of the tree will be still available.

Some technical details:

– persistent data structure schema is best suited for structures that uses pointers to its elements (lists, tries, graphs, and so on),
– the modifications always go to the “entry nodes” of the structure (head for list, root for tree),
– versions of these entry nodes indicate versions of the data structure and should be kept separately in a sorted way to allow for fast access to particular version of the data structure,
– it is a good method to assign timestamp for each version of the structure,
– time and memory complexity directly depends on the average distance through the structure to the modified node,
– there are different levels of structure persistence depending on their implementation; two main levels are partial and full,
– in partial persistent structure one can access all versions, but update only the latest one,
– in fully persistent data structures one can access and modify all versions (branching) and an update operation only operates on a single version at time,
– in a case where the full history should be kept, there is an implementation of the structure that guarantees that a structure storing m modifications has O(log(m)) access time and O(1) modification space and time complexity; the implementation utilizes the idea of modification boxes related to each node and containing information about single modifications; for more details check [1],
– persistent data structures may be also applied for other algorithmic problem, for example for solving planar point location problem; for more details check [2].

If you more need or you want to grow with us, contact us:

References
[1] Driscoll et al., Making data structures persistent, Journal of Computer and System Science, 1989.
[2] Sarnak and Tarjan, Planar Point Location Using Persistent Search Tree, Programming Techniques and Data Structures edited by Ian Munro, 1986.