> Google for ‘David’ – 在0.28秒内达到591百万次点击
> Google for ‘John’ – 在0.18秒内达到785百万次点击
好.页面被索引,它只需要查找索引表中的计数和前几个项目,因此速度是可以理解的.
现在考虑使用AND操作进行以下搜索：
> Google for ‘David John’(‘David’AND’John’) – 在0.25秒内达到17300万次点击
这让我勾选;)搜索引擎如何能够如此快速地在巨型数据集上获得AND操作的结果？我看到以下两种方式来执行任务,两者都很糟糕：
>你进行’大卫’的搜索.拿着巨大的临时表,在上面搜索“John”.但是,临时表未被“John”索引,因此需要进行强力搜索.无论你有什么硬件,这都不会在0.25秒内计算出来.
>按所有可能的词索引
像’大卫约翰’这样的组合.然后
我们面临关键数量的组合爆炸
谷歌甚至没有存储空间
处理这个问题的能力.
你可以和as many search phrases as you want在一起,你仍然可以在0.5秒内获得答案！怎么样？
Markus写的关于Google在许多机器上并行处理查询的内容是正确的.此外,还有information retrieval种算法可以使这项工作更容易一些.这样做的经典方法是构建一个inverted index,其中包含发布列表 – 按顺序包含该术语的所有文档的每个术语的列表.
搜索具有两个术语的查询时,从概念上讲,您将为两个术语(“david”和“john”)中的每一个都采用发布列表,然后沿着它们查找两个列表中的文档.如果两个列表以相同的方式排序,则可以在O(N)中完成.当然,N仍然是巨大的,这就是为什么这将在数百台并行机器上完成的原因.
此外,可能还有其他技巧.例如,如果排名最高的文档在列表中放置得更高,那么算法可能会确定它在没有遍历整个列表的情况下找到了10个最佳结果.然后它将猜测剩余的结果数(基于两个列表的大小).