在分布式系统中存储预先输入建议的字典树的最佳方法是什么？

Question

我一直在阅读一些有关尝试的内容，以及它们如何成为提前设计的良好结构。除了 trie 之外，您通常还有节点的键/值对和预先计算的 top-n 建议，以缩短响应时间。

通常，根据我收集的信息，最好将它们保留在内存中以便快速搜索，例如这个问题中建议的内容：拼字游戏单词查找器：构建特里树，存储特里树，使用特里树？。但是，如果您的 Trie 太大而您必须以某种方式对其进行分片怎么办？（例如，也许是一个大型电子商务网站）。

预先计算建议的键/值对显然可以在键/值存储中实现（保存在内存中，如 memcached/redis 或数据库中，并根据需要水平调用），但是存储的最佳方式是什么如果内存无法容纳的话，会使用 trie 吗？是否应该这样做，或者每个分布式系统都应该在内存中保存部分 trie，同时复制它以使其不会丢失？

或者，可以使用搜索服务（例如 Solr 或 Elasticsearch）来生成搜索建议/自动完成，但我不确定性能是否达到此特定用例的标准。Trie 的优点是您可以根据其结构预先计算前 N 个建议，让搜索服务处理网站上的实际搜索。

我知道有现成的解决方案，但我最感兴趣的是学习如何重新发明轮子，或者如果有人想讨论这个主题，至少可以了解一下最佳实践。

你怎么看？

编辑：我还看到了这篇文章： https: //medium.com/@prefixyteam/how-we-built-prefixy-a-scalable-prefix-search-service-for-powering-autocomplete-c20f98e2eff1，它基本上涵盖了使用使用 Redis 作为跳跃列表的主要数据存储，并使用 mongodb 作为 LRU 前缀。似乎是一个不错的方法，但我仍然想了解是否有其他可行/更好的方法。

Answer 1

我正在阅读 Alex Yu 撰写的《系统设计访谈：内部人士指南》，他简要介绍了这个主题。

\n

\n

特里数据库。Trie DB 是持久性存储。有两个选项可用于存储数据：

\n

\n
1. 文档存储：由于每周都会构建一个新的 trie，因此我们可以定期对其进行快照，序列化，并将序列化的数据存储在数据库中。像 MongoDB [4] 这样的文档存储非常适合序列化数据。
\n
2. 键值存储：特里树可以通过应用以下逻辑以哈希表形式[4]表示：
   \n\xe2\x80\xa2 特里树中的每个前缀都映射到哈希表中的键。
   \n\xe2\x80\xa2 每个 trie 节点上的数据都映射到哈希表中的值。
   \n图13-10显示了trie和哈希表之间的映射。
\n

\n

\n

\n

每个前缀节点上的数字表示搜索该特定前缀/单词的频率。

\n

然后，他建议可能通过按每个字母表（或字母表组，如 am、nz）对数据进行分片来扩展存储。但这会使数据分布不均匀，因为以“a”开头的单词比以“z”开头的单词多。

\n

因此，他建议使用某种类型的分片管理器，它可以跟踪查询频率并根据该频率分配分片。因此，如果对“s”的查询量是“z”和“x”组合的两倍，则可以使用两个分片，一个用于“s”，另一个用于“” z\' 和 \'x\'。

\n