performance - 使用不适合内存的 Set

Question

假设我有一个固定长度字符串的巨大列表，我希望能够快速确定一个新的给定字符串是否是这个巨大列表的一部分。

如果列表仍然足够小以适合内存，我通常会使用一个set：我会首先使用字符串列表来提供它，并且根据设计，数据结构将允许我快速检查给定字符串是否是一部分的集合。

但据我所知，这个数据结构的各种标准实现将数据存储在内存中，而且我已经知道巨大的字符串列表不适合内存，我需要以某种方式将这个列表存储在磁盘。

我可以依靠 SQLite 之类的东西将字符串存储在索引表中，然后查询表以了解字符串是否是初始集合的一部分。但是，为此使用 SQLite 对我来说似乎是不必要的繁重，因为我绝对不需要它支持的所有查询功能。

小伙伴们以前遇到过这样的问题吗？你知道任何可能有用的图书馆吗？（我与语言无关，随意扔掉你有的东西）

标签： performancefileindexingdata-structures

Answer 1

有多种解决方案可以有效地查找字符串是否是大量字符串的一部分。

第一个解决方案是使用trie使集合更加紧凑。实际上，许多字符串可能会以相同的标题开头，并且在内存中一遍又一遍地重写它是不节省空间的。将整个集合保存在内存中可能就足够了。如果没有，则树的根部分可以存储在内存中，引用存储在磁盘上的叶状节点。这使应用程序能够以相对较小的成本快速找到需要加载的部分叶状节点。如果字符串的数量不是那么大，则与根部分的给定叶子相关的大多数叶子部分可以从存储设备中加载到一个大的顺序块中。

另一种解决方案是使用哈希表快速查找给定字符串是否存在于集合中且延迟较低（例如，只有 2 次提取）。这个想法只是散列搜索到的字符串并在存储设备上存储的大数组的特定项目上执行查找。开放寻址可用于使结构更紧凑，但代价可能是更高的延迟，而封闭寻址只需要 2 次获取（第一次获取与给定哈希关联的项目列表的位置，第二次获取所有实际项目）。

轻松实现此类数据结构以便它们可以在存储设备上工作的一种简单方法是使用映射内存。映射内存使您能够透明地访问存储设备上的数据，就像它在内存中一样（无论使用什么语言）。但是，访问数据的成本是存储设备的成本，而不是内存的成本。因此，数据结构实现应该适应映射内存的使用以获得更好的性能。

最后，您可以缓存数据，以便某些获取可以更快。一种方法是使用Bloom 过滤器。布隆过滤器是一种非常紧凑的基于概率散列的数据结构。它可用于在内存中缓存数据，而无需实际存储任何字符串项。假阳性匹配是可能的，但假阴性是不可能的。因此，它们可以很好地丢弃通常不在集合中的搜索字符串，而无需在存储设备上进行任何（缓慢）获取。一个大的布隆过滤器可以提供非常好的准确性。如果需要确定性结果，则需要将此数据结构与上述数据结构混合。LRU/LFU 缓存也可能有助于搜索项目的分布。