c# - 用于将数据与文件系统路径相关联的高效数据结构？

Question

我需要在内存中保留一些关于可能大量文件和目录(通常高达几十万)的数据。显而易见的方法是使用 Dictionary<string, Something>以路径为键，但这有两个问题:

• 许多文件的大部分路径都是相同的，因此存储每个文件的完整路径可能会浪费内存
• 我需要能够快速访问有关目录的所有后代的数据；使用字典，唯一的方法是测试每个键并检查它是否以指定路径开头，这是非常低效的

这个问题似乎很适合使用前缀树(或 trie )，其中路径段作为“字符”。我尝试实现它，并且对于通过前缀查找来说性能还算不错(比字典快 4 倍左右)，但是它有两个问题:

• 内存消耗没有减少，可能是因为每个节点的 child 列表的开销
• 构建时间比字典差很多(填充集合的时间慢了大约 4 倍)

我确定这一定是一个非常普遍的问题，所以也许有我不知道的众所周知的解决方案？

Answer 1

只是一些通用的想法:

首先，一个 Patricia trie可能是改善尝试内存消耗的最著名方法 - 它将所有节点都有一个子节点的路径压缩到一个节点中，并沿着路径连接字符。还有一种版本，您将数据视为二进制数字序列，其优点是您始终最多有 2 个子节点，并且也更易于实现。

其次，内存消耗实际上取决于您如何存储给定节点的子节点 - 您是否维护一个包含 256 个节点的数组？这通常是直接查找的最有效方法，但也会消耗最多的内存，如果您需要遍历所有子项，则速度很慢。其他选项是:

• 存储成对的数组(字母，子节点) - 这可能是内存效率最高的，因为它只存储你真正关心的对象，而且它还有一个很好的遍历所有 child 的表现。但是，您必须检查所有对以进行直接查找 - 这通常离根越远越好，但在根附近可能会出现问题。

• 在每个节点内存储某种字典，将字母映射到子节点。这是性能方面最平衡的 - 它为您提供了相当不错的所有操作速度，并且在一定程度上节省了内存。

此外，如果您预先构建整个集合然后仅查询它，则有一种方法可以基于 Tarjan tables 存储子链接。这可能会增加构建时间，但会节省内存和以后的查询时间。