维护树的版本

Question

我有一个树数据结构，在一个特定的层次上有多达1000个节点(最大深度为8-9个层次)。

我需要维护整个树的版本。一个版本是在一些处理发生后创建的。在这些版本之间，节点中的数据可能会更改(不超过100 )。

到目前为止，我正在为每个新版本克隆整个树，但是在几个版本之后，空间消耗是巨大的。我不能完全删除以前的版本记录，因为我需要跟踪更改。

在数据库中存储这些版本的最佳方法是什么？(如果不是db，则有任何替代方式)。

Answer 1

这不是一个非常直截了当的问题，但它是一个解决问题。通常，记忆其历史的数据结构称为持久数据结构。

链接到的维基百科页面上有你应该看的持久化树的示例。

路径复制法的实现相当简单，但性能却不尽如人意。

Answer 2

一个可行的解决办法可能是：

如果您需要还原旧版本：

1. 将新树和前一棵树序列化为XML。
2. 将新XML与前面的XML区分开来，序列化并将差异存储在数据库中(对于我找到的http://diffxml.sourceforge.net和XMLUnit解决方案，必须检查它们是否能够以允许从新XML轻松还原之前的XML的方式计算新XML和前XML之间的差异)。
3. 每次需要旧版本时，都会连续地从数据库获取差异，从最近的版本到最远程的版本，然后按照这个顺序将它们应用到(序列化为XML)当前树中，以获得旧版本的树的XML格式。

如果不需要重构旧版本，那么只需使用XMLUnit计算差异并将它们的序列化存储在数据库中。

Answer 3

将每个唯一节点永久冻结在一个表中(一旦您在其中插入一个节点，就不要编辑或删除它)。如果需要稍微更改节点，请将此修改后的节点插入表中。然后，使用节点表的外键跟踪树版本。这应该需要每棵树少量的空间。