高效的数据结构，可存储大量具有相同前缀的文件路径并能够执行汇总

Question

我正在处理大约 10-2000 万条记录的大量文件路径。对于大多数部分，这些文件路径具有相似的前缀，只有文件名不同，但这并不总是正确的。文件路径也可以有不同的深度。

例如考虑

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file1.txt
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file2.txt
...
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file10.txt

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir2/another_file1.txt
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir2/another_file2.txt
...
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir2/another_file10.txt

filesystem:root_dir1/some_dir2/top_file1.txt
filesystem:root_dir1/some_dir2/top_file2.txt
...
filesystem:root_dir1/some_dir2/top_file10.txt

我有以下需求：

1. 节省空间：这些文件路径是从

   n

   不同的机器获取并通过线路发送的，因此它必须具有空间效率才能成为有效负载的一部分。
2. 持久化：我需要持久化存储它们的数据结构，然后能够稍后将它们全部读回并带入内存。
3. 组合：由于我从主服务器上的

   n

   不同机器接收这些文件路径，因此我需要将它们全部合并/组合在一起。
4. Roll up：在某个级别有超过 n 个（比如 1000 个）唯一目录/文件后，想要滚动到父级并删除此后的所有路径，因为在 n 之后我对保留空间的粒度记录不感兴趣节省。
5. 我对存储此数据结构的主要操作将是

   add

   新路径。我不需要直接检查

   contains

   或

   remove

   。我确实需要迭代它，但不需要任何排序。

For example says n  = 10

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file1.txt
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file2.txt
...
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file11.txt
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file12.txt

在这种情况下，一旦我看到

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1/file11.txt

，我想将跟踪文件放在

much_more_dir1

下，并将路径保留为

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1

如果我有类似的东西，在一些汇总后类似

filesystem:root_dir1/some_dir1/more_dir1/much_more_dir1
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir2
...
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir10
filesystem:root_dir1/some_dir1/more_dir1/much_more_dir11

我想再次汇总以优化空间并仅跟踪

filesystem:root_dir1/some_dir1/more_dir1

等等...

我首先将每个文件路径存储为一个条目。但哈希集为此占用的空间非常大，以至于我无法通过网络发送它，因为它超过了 10 Mb。我的 RPC 调用的最大有效负载大小。

我已经开始研究

HashSet

和

Trie

来存储它，因为当字符串共享公共前缀时，它们似乎是节省空间的解决方案。还研究了

PatriciaTrie

树。但即使如此，我也可能无法实现 100 万个文件路径的 10 mb 大小限制。所以我想到了在我的用例中可以接受的汇总方法来优化空间。

我想知道什么是一个好的数据结构，它可以为我提供这种汇总功能并节省 trie 的空间。如果没有，那么我应该如何自己有效地构建一个？

Answer 1