搜查引擎之倒排索引浅析

倒排索引

倒排索引(Inverted Index) 也常被称为反向索引，是搜查引擎中十分关键的数据结构，为什么说它关键呢，咱们首先拿一本书《重构改善既有代码的设计》举个例子：

假设一本书没有目录的话，通常上也是可以读的，只是合上书下次再次阅读的时刻，就有些消耗期间了。

经过给一本书加目录页，可以极速了解这本书的大抵内容散布以及每个章节的页码数，这样在查问内容的时刻效率就会十分高了，所以书的目录就是书本内容的便捷索引。

目录页

构想一下你要搜查 case语句 这个关键词在这本书的页码，你应该怎样办呢?有些技术类的书籍会在最后提供索引页，这本书的索引页如下：

索引页

只有要从索引页中查找 case语句，就可以查找到关键词在书本中的页码位置了。

看完这个例子，让咱们来把图书和搜查引擎做个便捷的类比：

图书当中的目录页就相当正向索引(Forward Index)，索引页就相当于倒排索引的便捷成功，在搜查引擎中，正向索引指的是文档 ID到文档内容和单词的关联，倒排索引就是单词到文档 ID 的相关。

上方来看一个很便捷的例子：

如上有三篇文档，每篇文档的内容都是关于 ElasticSearch 的三本书，那咱们思索下怎样样变为一个倒排索引呢?

把书中内容出现所以的词都分红不同的关键词(Term)，陈列在第一栏，区分是 ElasticSearch，Mastering，Server 和Essentials;第二栏是统计了关键词在一切内容中出现的次数，比如 ElasticSearch 在内容中出现了三次，就记为 3;第三栏标注的是文档 ID和文档出现的位置，比如 ElasticSearch 在第 1,2,3 文档中都出现了，在第一个文档所处的位置是第二个，所以标注的为 1。

以上就是便捷的正排索引和倒排索引的结构，上方让咱们来看下倒排索引的数据结构：

倒排索引数据结构

倒排索引的外围分为两局部，第一局部为单词词典(TermDictionary)，记载一切文档的单词以及单词到倒陈列表的关联相关。在前面的例子中，单词的量并不是很多，然而在实践消费中，单词量会十分大，所以实践会驳回B+ 树和哈希拉链法去存储单词的词典，以满足高功能的拔出与查问。

第二局部是倒陈列表(Posting List)，它记载了单词对应文档的联合，倒陈列表是由倒排索引项(Posting) 组成，倒排索引项蕴含：

上方咱们来用一张图来全体看下倒排索引：

一个倒排索引是由单词词典(Term Dictionary)和倒陈列表(PostingList)组成的，单词词典会记载倒陈列表中每个单词的偏移位置。比如当搜查 Allen 的时刻，首先会经过单词词典极速定位到 Allen，而后从 Allen这里拿到在倒陈列表中的偏移，极速定位到在倒陈列表中的位置，从而真正拿到倒排索引项 [12,15](这里只是列了下 Document ID，其实是像上方讲的蕴含4 项信息的项)，拿到这个项可以去索引上拿到原始信息，可以去计算打分排序前往给用户。

再了解了倒排索引的数据结构后，让咱们来看下 ES 中的倒排索引吧!

ElasticSearch 倒排索引

那么在 ElasticSearch 中的文档是基于 Json格局的，其中一个文档蕴含多个字段，每个字段都会有自己的倒排索引。在 Mapping中可以去设置对某些字段不做索引，这样做可以节俭存储空间，但同时也会造成这个字段无法搜查了。

比如一个文档，其中蕴含两个字段 username 和 job：

在构建索引的时刻是依据字段构建的，那么 ES 中 username 会有一个倒排索引，job 也会有一个倒排索引。

总结

参考文献

Elasticsearch外围技术与实战