I think you can adapt the concept of immutable data structures to any situation. For key-value store an immutable hash array mapped trie is a good place to sta

I think you can adapt the concept of immutable data structures to any situation. For key-value store an immutable hash array mapped trie is a good place to start. I.e. each update creates a new "head" node and duplicates only those parts which are required to maintain unique versions of the tree. The hash array mapped trie is excellent for this purpose since each node has many children, and thus a unique version does not need to duplicate too many nodes. Then, just store all the head nodes in a linear order in e.g. a list, and you can travel back in time by navigating the head nodes backwards. https://en.wikipedia.org/wiki/Hash_array_mapped_trie https://en.wikipedia.org/wiki/Hash_array_mapped_trie https://infoscience.epfl.ch//record/64398/files/idealhashtrees.pdf https://infoscience.epfl.ch//record/64398/files/idealhashtre... https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java https://github.com/clojure/clojure/blob/master/src/jvm/cloju...