每当您开始在google上输入搜索内容时，您都会获得推荐列表，并且键入的字母越多，推荐的准确性就越高 。如果您像我一样，您总是想知道这是如何工作的-是存储倒排索引还是其他内容？
【如何构建Google搜索自动完成功能】这里适合的数据结构是Trie 。
系统要求
考虑到Google的规模，我们需要牢记的因素是延迟，一致性和可用性 。一个理想的延迟应该是非常低的，给人/每个信你可以键入改变的建议 。接下来，系统需要一直可用 。但是，这里可以包含一致性 。每次键入内容时，它都会更改以前存储的查询的频率，这会影响建议 。此处稍有延迟是可以的，最终的一致性也将起作用 。
文章插图
方法1
特里表示一个单词为树，每个字母为节点，下一个字母为子节点，依此类推 。Google还会以Trie的形式存储每个单词/句子 。在这里考虑，父节点是“ h”，其子节点是“ a”，然后是“ r”，依此类推 。每个节点可以有26个子节点 。现在，每个节点还可以存储搜索到的每个字母的频率 。
例如，节点“ h”存储搜索频率“ h”，其子节点“ a”存储搜索频率“ ha”，依此类推，现在，如果我们要显示前N条建议，请说键入“ h”，建议应该显示“ harry potter”或“ harry styles” 。然后，我们需要将父节点中的所有建议排序到频率的每个级别并进行显示，这意味着扫描数TB的数据，并且因为延迟是我们的目标，所以这种扫描方法将行不通 。
方法＃2
为了使这种方法更有效，我们可以在每个节点上存储更多数据以及搜索频率 。让我们在它下面的子树中的每个节点上存储前N个查询 。这意味着节点“ h”将存储“哈里·波特”，“哈雷·戴维森”等查询 。如果将树遍历到“ harl”（即键入“ harl”），则节点“ l”将具有诸如“ harley davidson”，“ harley quinn”之类的查询 。
与前一种方法相比，这种方法更好，因为读取效率很高 。每当节点的频率更新时，我们都会从该节点回溯到其父节点，直到到达根节点为止 。对于每个父级，我们检查当前查询是否是前N个查询的一部分 。如果是，则将相应的频率替换为更新的频率 。如果不是，则检查当前查询的频率是否足够高以成为前N个查询的一部分 。
如果是这样，我们用频率更新前N个 。尽管这种方法有效，但确实会影响我们的读取效率-每次执行写入/更新操作时，我们都需要在节点上加一个锁，这样用户就不会得到过时的值，但是如果我们考虑最终的一致性，则可能没什么大问题 。用户可能会暂时获取过时的值，但是最终它将保持一致 。尽管如此，我们将研究这种方法的扩展 。
方法3
作为先前方法的扩展，我们可以离线存储数据 。我们可以将查询的哈希图存储到其频率，一旦频率达到设置的阈值，便可以将其映射到服务器 。
缩放比例
现在，将不会只有一台大型服务器来存储所有PB级数据 。我们会垂直扩展生活–有更好的方法 。我们可以通过前缀在各种服务器上分发数据（分片） 。例如，前缀“ a”，“ aa”，“ aab”等将在服务器＃1上等等 。我们可以使用负载均衡器来保留带有服务器编号的前缀映射 。
但是考虑到这一点，与字母“ a”相比，某些具有“ x”，“ xa”，“ yy”等数据的服务器将具有较少的流量，因此，可以对每个服务器进行阈值检查；如果负载如果流量超过该流量，则可以在其他分片之间分发数据 。
如果您担心单点故障，则可能有许多服务器充当负载平衡器，因此，如果任何负载平衡器发生故障，则将其替换为另一个 。您可以使用ZooKeepers持续运行状况检查负载平衡器并采取相应的措施 。
推荐阅读
- 如何开淘宝网店的步骤手机 怎么用手机淘宝开店铺
- 双开门冰箱如何选购
- EC6价格能打，筹备电池资产公司，满血复活的蔚来如何加电？
- 如何穿得清凉又有型？10个搭配风格，时尚达人般的衣风你也能拥有
- 给花换盆拿不出来怎么办,花盆不砸如何换盆
- 养生之道 跟庄子学习如何养生保健
- 武夷山正山小种红茶功效如何
- 淘宝商家退店流程 淘宝网店如何退店
- 如何选择适合自己的婚礼主持人
- 如何才能泡好黑茶,那里的黑茶最好黑茶产地分布