java - 使用有限的内存构建和导出非常大的树结构

Question

总而言之，我有一个应用程序，它接受一组输入文件，从数据中生成一棵树，然后将其作为 XML 写入文本文件。

目前，整个树在写出之前都存储在内存中，因为在解析期间我们需要引用树上的任意节点以获取或更新其值。

当树变得太大而无法将其全部存储在内存中时，就会出现我们面临的问题。树本身非常平坦，只有 4-6 层深度。看起来像这样

Root
   Group
      Record
         Data
         Data
      Record
         Data
         Data
         Data
         ...
      ...
   Group
      Record
      ...

总会有一个Root节点，每个节点只有一种子节点。但是，节点添加到其他节点的方式也没有顺序:根据数据的格式化方式，您可以将记录添加到不同的组，也可以将数据添加到不同的记录(而不是为一个记录构建一个记录)组，然后移动到另一个)

我的第一个建议是为我们的机器增加更多内存。我们在 64 位 Windows 机器上运行该工具，因此如果内存不足，那么我们只需要获取更多内存即可。但是这个建议没有被采纳。

我的下一个想法是每当树在内存中占用太多空间时写出节点，但是因为数据可以随时添加到特定记录，所以很难确定我们何时真正完成记录与否。尤其是当我们需要回顾一条记录时，它已经被写出来了。

还有其他几个选项，例如优化树的设计方式(因为每个节点占用相当大的内存)，但对于这个问题，我想知道构建和导出大树的技术。

Answer 1

在我看来，有两种方法可以解决这个问题。

• 详细了解如何使用数据来确定特定模式，并针对您的用例提出最有效的方法。

• 假设访问或更改数据的任何场景都可能以相同的频率和概率发生，将数据视为黑盒。

您没有为第一种方法提供任何食物，所以我们必须假设是后者。缓存的概念作为一种解决方案浮现在脑海中。有不同类型的缓存，但基本概念是尽可能多地保留在内存中，一旦超过一定限制，您就会保留并从内存中删除使用次数最少或使用时间最长的部分。

当您这样做时，您可以选择将实际的树结构保留在内存中，仅清除节点内容或同时清除节点内容和树结构本身。如果您有大量但数量有限的节点，那么最好保持树结构，使“清除”的节点尽可能轻量级。但是，如果树中的节点数几乎没有限制，那么您可能会考虑清除整个子树。

对于通常通过访问子树而不是完全随机访问树来访问树的用例，最后一种方法可能非常有效。

如果您提供有关数据和使用模式的更多信息，我们可能会提出更详细的建议。