倒序索引的原理和在全文搜索中的应用

（Ceeji 原创，转载请注明作者和出处网址）

我们都知道搜索引擎搜索一个词是非常快的，但你有没有想过为什么搜索引擎能够以这么快的速度从数以亿计的网页中找到你想要的内容？一个很重要的原因是，现代的搜索引擎基本上都使用了倒序索引技术。

如果不使用倒序索引技术，在每次进行检索时，搜索引擎必须遍历每一个网页，查找网页中是否包含你指定的关键词。这个工作量是十分巨大的，主要原因有二：

• 互联网的网页基数非常大；
• 在每一个网页中检索是否含有指定的关键词不是一件简单的事情，它需要遍历网页的每个字符。

为了更好的建立被搜索的关键字和含有这些关键字的页面之间的映射关系，倒序索引产生了。简单的说，倒序索引的倒序，指的是这个索引是从关键词中查找对应的源的，而不是从源中检索对应的关键词。

举例如下：为了检索关键词 A，首先从倒序索引的索引表中，找到关键词 A，然后查找 A 所在的页。由于倒序索引表排序后，在其中查找一个关键词可以使用二分查找，特别是在采用分布式数据、服务器集群、多线程技术等条件下，效率极高，所以，查找含有某个关键词的页变得非常简单。

假设数据库中含有1000000条记录，其中有 10 条记录符合搜寻条件，如果使用倒序索引，可以很快找到这些关键词，并且定位到含有这些关键词的十条记录；否则，需要遍历1000000条记录，效率的差异可想而知。

所以，倒序索引相当于一本出处大字典，查阅其中的每个词汇，都可以告诉你它的所有出处。

倒序索引中的关键词，一般是蜘蛛（Spider）在网页爬行时对网页进行分词的结果。中文分词也是一件比较麻烦的事情。关于分词技术，请查阅其他相关文章。

（我开发的题典（Tidian）搜索引擎采用了倒序索引技术和智能中文分词技术。）