算法高级（34）搜索引擎速度快的秘诀倒排索引介绍

对于数据库查询来说&＃xff0c;大家都知道&＃xff0c;模糊查询比较耗时&＃xff0c;即使建立索引&＃xff0c;查起来也不快&＃xff0c;而像百度、谷歌这样的搜索引擎&＃xff0c;基本上也是模糊查询&＃xff0c;而且响应速度特别快&＃xff0c;这是为什么呢&＃xff1f;其实里面有个很重要的因素&＃xff0c;就是使用了倒排索引&＃xff0c;这极大地提高了查询效率。而一切的设计都是为了提高搜索的速度。

一、倒排索引和正排索引

倒排索引&＃xff08;Inverted Index&＃xff09;也叫反向索引&＃xff0c;有反向索引必有正向索引。通俗地来讲&＃xff0c;正向索引是通过key找value&＃xff0c;反向索引则是通过value找key。

【百度百科】倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值&＃xff0c;而是由属性值来确定记录的位置&＃xff0c;因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件&＃xff0c;简称倒排文件(inverted file)。

很典型的&＃xff0c;数据库的查询是根据key查询value的过程&＃xff0c;索引可以把数据库索引理解为正排索引。

二、数据库索引和倒排索引的区别联系

数据库中的MyISAM存储引擎就是一颗多路树&＃xff0c;也是一颗B&＃43;树&＃xff0c;结构如下&＃xff1a;

这种结构我们前面讲过&＃xff0c;根节点存储了我们需要查询的数据&＃xff0c;可以根据查询条件遍历这颗树&＃xff0c;找到我们要的内容&＃xff0c;但从查询效率上来说&＃xff0c;即使建立索引&＃xff0c;我们也需要从上往下依次遍历。最好的就是二分查找。

那么有没有可能我们通过输入的关键字直接找到我们要的结果呢&＃xff1f;这就需要倒排索引了&＃xff0c;我们给上图中所有的P节点再建立索引&＃xff0c;查询的时候&＃xff0c;我们根据索引能快速找到P节点对应的具体内容直接返回&＃xff0c;这其实就是倒排索引。

一句话概括&＃xff0c;对数据库的索引再次建立索引就是倒排索引。而倒排索引因此会占用比较多的磁盘空间&＃xff0c;典型的以空间换时间的范例。为了更进一步理解&＃xff0c;下面从网上摘了两张图来具现化这一过程&＃xff1a;

三、Lucene中的倒排索引

而像Lucene这样的搜索API实现&＃xff0c;底层的数据结构使用的就是倒排索引&＃xff0c;接下来我们具体研究一下。

Lucene中没有使用B树这种数据结构&＃xff0c;而是将关键字按字符顺序排列、顺序存储在磁盘上&＃xff0c;因此lucene可以使用二分查找来快速定位记录。

Lucene中使用字典文件记录所有的关键字&＃xff0c;所以一开始需要一个字典文件&＃xff0c;对于英文&＃xff0c;可以使用词典中的单词&＃xff0c;而对于汉字&＃xff0c;因为单个的汉字通常不能表达太多意义&＃xff0c;所以中文我们一般会提供中文词典。

接下来要对我们的数据集进行分析处理&＃xff0c;分析的过程&＃xff0c;就是把记录的内容按照字典中的词汇进行分解&＃xff0c;分解成一个个的短语&＃xff0c;并且记录这些短语给这些短语建立索引&＃xff0c;记录下每个短语对应的记录的位置。

第三步&＃xff0c;要对用户输入的关键字进行拆分&＃xff0c;拆分为一个个的词条&＃xff0c;拆分完去跟第二步建立的索引进行比对&＃xff0c;找到我们要的结果。

可以发现&＃xff0c;在整个过程中&＃xff0c;比较耗时的操作是数据的预处理阶段&＃xff0c;我们需要对原始数据进行分解并建立索引。而索引建立完毕的查询操作&＃xff0c;就是二分查找&＃xff0c;那是非常的快速了。

四、Lucene对倒排索引的优化之压缩算法

为了减小索引文件的大小&＃xff0c;Lucene对索引还使用了压缩技术。

1.首先&＃xff0c;对词典文件中的关键词进行了压缩&＃xff0c;关键词压缩为<前缀长度&＃xff0c;后缀>。

例如&＃xff1a;当前词为“阿拉伯语”&＃xff0c;上一个词为“阿拉伯”&＃xff0c;那么“阿拉伯语”压缩为<3&＃xff0c;语>。

2.其次大量用到的是对数字的压缩&＃xff0c;数字只保存与上一个值的差值

&＃xff08;这样可以减小数字的长度&＃xff0c;进而减少保存该数字需要的字节数&＃xff09;。
例如当前文章号是16389&＃xff08;不压缩要用3个字节保存&＃xff09;&＃xff0c;上一文章号是16382&＃xff0c;压缩后保存7&＃xff08;只用一个字节&＃xff09;。

五、总结

关于倒排索引就介绍到这里&＃xff0c;最后给大家举一个非常形象的例子&＃xff0c;我相信大家瞬间就可以明白倒排索引这种结构了。

各位同学作为九年义务教育的好学生&＃xff0c;相信大家一定都学过英语&＃xff0c;也用过英语字典&＃xff0c;在使用英语字典的时候&＃xff0c;同学们肯定深有体会&＃xff0c;查个单词怎么那么慢呢&＃xff1f;要一页一页地翻。这种查询跟数据库的查询类似&＃xff0c;就是遍历结果集&＃xff0c;所以效率不高。

而作为都读过小学的各位读者老爷们&＃xff0c;也一定使用过新华字典&＃xff0c;你是不是发现查新华字典是一种享受啊&＃xff0c;为啥呢&＃xff0c;因为新华字典有拼音检字法和部首检字法&＃xff0c;通过检字法我们能速度定位我们要查的汉字在字典中的位置&＃xff0c;到了这里&＃xff0c;你应该就明白了&＃xff0c;原来新华字典中的检字法用的就是倒排索引的原理呀。神不神奇&＃xff1f;意不意外&＃xff1f;

哈哈&＃xff0c;完工&＃xff01;

我的微信公众号&＃xff1a;架构真经&＃xff08;关注领取免费资源&＃xff09;

参考文章

1. https://www.cnblogs.com/cjsblog/p/10327673.html
2. https://blog.csdn.net/u010558660/article/details/53407455