search - 搜索引擎如何进行 'AND'操作？

Question

考虑以下搜索结果:

Google for 'David' - 5.91亿在 0.28 秒内点击

Google for 'John' - 7.85亿在 0.18 秒内点击

好的。页面是有索引的，只需要在索引表中查找count和前几项，速度可以理解。

现在考虑使用 AND 运算进行以下搜索:

Google for 'David John' ('David' AND 'John') - 1.73 亿次点击 在 0.25 秒内

这让我很感动 ;) 搜索引擎怎么能如此快速地获得对巨大数据集进行 AND 运算的结果？我看到以下两种执行任务的方法，两者都很糟糕:

您搜索“大卫”。拿起巨大的临时表并在其上搜索“John”。但是，临时表不是由“约翰”索引的，因此需要进行强力搜索。无论您拥有什么硬件，这都不会在 0.25 秒内计算出来。

按所有可能的词索引
像“大卫约翰”这样的组合。然后
我们面临着 key 数量的组合爆炸
甚至谷歌都没有存储空间
处理那个的能力。

你可以和一起 as many search phrases as you want你仍然可以在 0.5 秒内得到答案!如何？

Answer 1

Markus 写的关于 Google 在多台机器上并行处理查询的内容是正确的。

另外还有information retrieval使这项工作更容易一些的算法。经典的做法是构建一个 inverted index其中包含 帖子列表 - 包含该术语的所有文档的每个术语的列表，按顺序排列。

当搜索包含两个词的查询时，从概念上讲，您将获取两个词('david' 和 'john')中每一个的发布列表，并沿着它们走，查找两个列表中的文档。如果两个列表的排序方式相同，则可以在 O(N) 中完成。当然，N 仍然很大，这就是为什么这将在数百台机器上并行完成。

此外，可能还有其他技巧。例如，如果排名最高的文档在列表中的位置更高，那么算法可能会决定它找到 10 个最佳结果，而无需遍历整个列表。然后它会猜测剩余的结果数(基于两个列表的大小)。