搜索引擎的基石－倒排索引

Google和百度这两家公司都挺能挣钱的，而给它们印钞票的机器就是搜索引擎，果果虽然没写过印钞机程序，但还是了解一些搜索引擎的原理，今天就聊聊它的基础，倒排索引。

先来回想一下我们使用搜索引擎的过程，输入一个或多个关键词，然后搜索引擎就返回了一个结果列表，这些搜索结果都是链接到不同的网页文档。这个过程其实很简单，对于搜索引擎，它要做的事情，就是从一大堆文档中，找出关键词的相关的文档，展示出来。

简单的做法就是，搜索引擎将会遍历它抓取到的所有文档，从中挑选出与关键词相关的文档，这种叫做正向索引。可是要知道，Google现在收录的网页数目是万亿级别的，要是真像这样遍历全部文档，那估计你搜索一个关键词，要等个一年才能看到搜索结果。

那么为了加快搜索速度，需要建立相反的一个索引的列表，在爬虫抓取回一个网页后，先对它进行分词处理，然后把这些提取出来的关键词与这个网页的ID做一个映射，这就是倒排索引（Inverted index）。

比如我们有编号T0-T2的三篇文档，它们的内容分别是：T0="it is what it is"，T1="what is it"，T2="it is a banana"，可以对每篇文章都先分词处理，然后统计每个词对应的文档，得到这样一个倒排索引：

当我们要搜索"what is it"时，可以直接找出这三个词索引的文档编号的并集，即T0和T1，这就是用倒排索引搜索关键词的基本流程。所以平时我们使用搜索引擎时，它的搜索结果并不是实时查找出来的，而是使用了提前做好的倒排索引，将关键词的索引结果合并展示出来的。

当然了，倒排索引只是搜索引擎的一个基础架构，一个单词的索引结果也会有成百上千万个，如何对这些结果进行有效的排序，让用户真正想要的搜索结果排名靠前，才是关键技术。

搜索引擎都是倒排索引，即关键词对应文件（文档）的形式。