memory - 如何创建、更新和读取不适合内存的基数树？

Question

我有兴趣使用基数树（或 Patricia trie）来存储strings -> values. 但是，我发现我有太多的字符串无法放入内存。

我发现Algolia 的一篇文章，介绍了他们如何通过搜索索引解决这个问题，他们谈到了我正在尝试做的事情：在构建每个分支时将基数树刷新到磁盘，并且只读回您需要的分支。

但是，他们没有提到他们是如何做到这一点的。我能想到的存储基数树的唯一方法是作为完整（序列化）对象或作为简单的键/值存储的哈希/数组。

例如，使用键/值存储

SET smile:  [...values...]
SET smiled: [...values...]
SET smiles:  [...values...]
SET smiling: [...values...]

然后进行前缀扫描以提取MATCH smil*. 然而，这种方式失去了基数树节省空间的优势，而且它需要在负载时重建至少部分基数树。

标签： memorytrieradix-treepatricia-trie

Answer 1

为什么不在预处理步骤中对字符串进行散列，将映射存储在核外并在散列上构建 trie？这应该会显着减少内存负载，因为只剩下哈希值需要考虑。