用有限的内存构建和导出一个非常大的树形结构

Question

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

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

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

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

始终存在一个Root节点，并且每个节点只有一种子节点类型。但是，将节点添加到其他节点的方式也没有顺序:根据数据的格式，您可以将记录添加到不同的组中，也可以将数据添加到不同的记录中(而不是为一个组构建一条记录，然后移动到另一组)。

我的第一个建议是在我们的机器上投入更多的内存。我们在64位的windows机器上运行该工具，所以如果内存不足，我们只需要获得更多的内存。但这一建议并未被采纳。

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

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

Answer 1

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

• 了解有关数据用法的更多信息，以确定特定模式，并针对您的用例提出最有效的方法。
• 将数据视为黑盒，假设访问或更改数据的任何情况都可能以相同的频率和概率进行。

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

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

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

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

Answer 2

1)我想到的第一个选择是将所有(父-子)对存储在一个数据库中，然后递归地探索它以从它构建XML。

2)另一种选择是自下而上，通过扫描完整的输入三次(每层一次，从作为父级的记录开始，以根结束)。每一层都作为一组XML文件存储在磁盘中，每个节点对应一个文件。然后，当在树中构建更高级别时，子文件可以简单地附加到其相应的父文件中(因为它们被保证完全填充)。这需要维护2个内存中的索引；一个用于当前级别，另一个用于其下的级别。这些索引指向文件。

Answer 3

1. 在磁盘上创建一个工作目录。
2. 读取数据。当您遇到一个您以前没有见过的组时，在工作目录中为它创建一个子目录。当您看到以前未见过的记录时，请在相应的group目录中为其创建一个文件。当您看到一些数据时，将其附加到相应的文件中。继续操作，直到读完数据为止。
3. 遍历文件树，并将记录文件的内容连接到输出文件，并为根目录和组添加适当的标记。
4. 删除工作目录以及其中的所有内容

如果您保留内存中的文件句柄，并在写入和读取阶段之间重用它们(这意味着使用RandomAccessFile或MappedByteBuffer，两者都可以写入、读取和倒带)，并且在任何时候都不刷新它们，那么您将把磁盘IO和缓存的问题完全留给操作系统(以及运行库等等)。如果操作系统认为对程序的这一特定执行最好的做法是将一些数据写入磁盘，它将这样做。如果它们都可以放在内存中，它就会将它们都保存在内存中。它将能够批量写入，因此它们很好，很大，因此效率很高。它将能够预取读取，这是一组文件的顺序遍历，因此是可预测的。如果你的操作系统很好，这将是一个和这个问题一样有效的解决方案。如果它是Windows，它可能不是。

一个额外的技巧是将数据写入文件，而不是以XML格式，而是以某种更紧凑的中间格式，仅将其转换为XML以用于最终输出。这将更有效地利用缓存和带宽。