我正在开发一个实现重复数据删除的开源项目。（有关该项目的链接，请参阅下面的两个超链接）该项目的性能目前还不错，但随着更多块写入磁盘而降级。这是由于 HashManager。对于每个写入的块，hashmanager 存储一个 Hash-BlockId 对。对于重复数据删除过程，需要具有给定哈希的块标识符列表。（使用的hash为Crc32）HashManager的接口见源码。
该接口的当前实现将列表存储在 256 个文件（crc & 0xFF）中，并将完整的列表加载到内存中。当需要另一个列表时，保存前一个列表并加载下一个列表。除了这可能导致内存耗尽这一事实之外，这还意味着性能下降。
有什么好的选择来克服这个问题？
（只是为了澄清：在去重之前完全检查块以查看它们是否匹配）
我不是磁盘结构方面的专家，但我听说 B-Tree 通常用于实现存储在磁盘上的键值映射。所以我想你可以有一个 CRC 的 B-Tree 索引，然后将某种链接存储到块 ID 列表中。您还可以将列表组合到 B-Tree 结构中，方法是有效地拥有一个键，即 CRC 和块 ID 的串联，然后在 B-Tree 上执行有效的前缀/范围查询.
Wikipedia Page on B-Trees：“在计算机科学中，B-tree 是一种树数据结构，它保持数据排序并允许在对数时间内进行搜索、顺序访问、插入和删除。B-tree 是二进制的概括搜索树，因为一个节点可以有两个以上的子节点。（Comer 1979, p. 123）与自平衡二叉搜索树不同，B 树针对读取和写入大块数据的系统进行了优化。它常用在数据库和文件系统中。”
如果您使用 256 个列表文件来存储 crcs，那么显而易见的第一步是将所有以字节 0 开头的 crcs 放入列表 0 中，将所有字节为 1 的 crcs 放入列表文件 1 中，等等。然后只存储每个文件中 crc 的最后三个字节。这将节省 25% 的密钥存储空间，或许还能加快处理速度。
第二件事是创建一个 4 gigaBIT 内存标志数组，以显示列表中是否已注册 4 字节 crc。这将大大加快向数组中添加新项目的速度，因为您将知道是否需要先查找现有条目 - 如果该位为零，则该 crc 尚未使用。
根据数据域开发人员的一篇论文，这种不必要的查找是最减慢摄取过程的原因（他们有不同的方法来避免它）。
我假设您正在保存列表，因为您正在修改它们。我建议不要重写整个列表，而是将所有更改放在文件末尾，这样您就可以追加到文件末尾而不是重写整个列表。使用了一个链表结构，该结构以文件尾端的指针开始，每次追加时将一个新标题写入文件末尾的列表。您可以通过在列表更高的位置写入一个带有删除标志的新条目来标记要删除的条目。然后，您可以定期对每个列表进行垃圾收集以减小列表大小（例如，每周或每月一次批处理）。您可以对列表修改执行相同的操作。只需编写一个新条目来替换旧条目，也许用一个标志。然后定期收集垃圾以删除旧条目。
您可以做的任何事情来构建列表，这样您就不需要每次都将整个内容加载到内存中，这会加快速度。尽可能少地移动数据。
这是我在 Stack Overflow 上写的第一件事，所以如果我的帖子不符合首选规范，请原谅。
我注意到我的回复编辑区域上方的说明，我不应该要求澄清，我想这是为了让我可以更有趣地猜测确切的问题是什么。我希望我的猜测很接近，并且我的答案包含有用的元素。