algorithm - 自动完成的后端

Question

这是一道面试题:为自动完成设计一个分布式后端。

我会这样回答:

自动完成是通过给定的后缀在字典中进行搜索。字典可能应该组织成一个 trie。该词典是根据最频繁的查询构建的，但这是另一回事。

现在我假设字典不会经常更改(例如每天一次而不是每毫秒一次)。因此，我们可以跨多个处理自动完成查询的服务器复制字典(例如，使用负载均衡器和循环策略)。

我们还应该考虑字典，但这又是另外一回事了。

有意义吗？我错过了什么吗？

Answer 1

这看起来是个正确的问题。 trie 的想法非常好，可以帮助您在 log(n) 中进行搜索。更改频率取决于信息，所以我不会说确切的时间，但我会动态调整它。假设您每天更改一次，树的更改量会很好。你可以给出一个界限(例如 10%)。如果超出边界，您可以更频繁地更新 trie。这也取决于保持最新的重要性，因为在大多数情况下并非如此。负载均衡器的想法也不错。