1

我有一个树数据结构，在特定级别上最多有 1000 个节点（最大深度为 8-9 级）。

我需要维护整个树的版本。在一些处理发生后创建一个版本。在这些版本之间，节点中的数据可能会发生变化（不超过 100 个左右）。

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

将这些版本存储在数据库中的最佳方式是什么？（如果不是分贝，任何替代方式）。

4

5 回答 5

3

这不是一个非常简单的问题，但它是一个已解决的问题。通常，记住其历史的数据结构称为持久数据结构。

链接的 Wikipedia 页面有一个您应该查看的持久树示例。

路径复制方法实现起来相当简单，但没有尽可能好的性能。

于 2013-11-12T07:00:41.717 回答
1

一个可能的实际解决方案可能是：

如果您需要恢复旧版本：

  1. 将新树和前一个树序列化为 XML。
  2. 将新 XML 与以前的 XML 进行比较，序列化并将差异存储在数据库中（对于 Java 解决方案，我找到了http://diffxml.sourceforge.net和 XMLUnit，但必须检查它们是否能够计算差异在新 XML 和以前的 XML 之间以允许从新 XML 轻松恢复以前的 XML 的方式。
  3. 每次需要旧版本时，依次从数据库中取出差异，从最近到最远，依次应用到（序列化成XML）当前树上，得到XML形式的树的旧版本。

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

于 2013-11-12T09:35:34.830 回答
0

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

于 2013-11-12T06:36:16.773 回答
0

由于您关心树的先前版本，并且空间是您主要关心的问题，假设从一个版本到另一个版本，treas 并不完全不同，您可以只存储 tres 之间的差异。如何做到这一点完全取决于您：-您可以对树进行内/前/后顺序解析（假设它是二进制的）并提出一个逻辑来从差异位置到另一个位置 - 或使用一个只存储差异的链表+一些重建珍宝的逻辑

于 2013-11-12T11:41:18.963 回答
0

将每个“版本”存储为已更改节点与旧/新值之间的映射。

您可以通过反转操作序列来重建任何以前的版本。

于 2013-11-12T06:38:12.333 回答