Maintain versions of a tree

Question

I have a tree datastructure having upto 1000 nodes at a particular level ( max depth of 8-9 levels).

I need to maintain versions of this entire tree. A version is created after some processing happens. Between these versions, the data in the nodes may change ( not more than a 100 or so).

As of now, I was cloning the entire tree for each new version, but the space consumption is huge after a few versions. I cannot entirely delete the previous version records since I need to keep a track of the changes.

Whats the optimal way to store these versions in the database? (If not the db, any alternative way).

Answer 1

This is not a very straightforward problem, but it is a solved problem. In general, data structures that remember their history are called persistent data structures.

The linked Wikipedia page has an example of a persistent tree that you should look at.

The path copying approach is fairly simple to implement but doesn't have performance as good as is possible.