倒排索引和正排索引

倒排索引和正排索引
一 以有限对无限
这个世界很多东西是无限的,比如可以创造无限的小说,可以创造无限个程序。但是小说虽然无限，小说中的字数却是有限，拿汉字来说，我查到的最高记录也就9万多个，常用的就五六千个。程序虽然有限，但是CPU的指令条数却是有限。

从有限到无限给了我们极大的灵活性，像乐高积木，积木种类不多，却可以有N多种组合，而且越简单的单体的虽然组合看起来不多，却因为简单有了更多的可能性，比如围棋，比如计算机的0和1组合。

反过来，我们如何处理无限的东西，比如我们如何搜索小说，小说的数量可以说是无限的，因为可以不断的增加，如果有N个小说，我们在小说里面搜索“真气” ，如果没有特定索引，我们要把N个小说遍历一遍，且把小说的每个词都要遍历一遍，工作量实在是太大了。如果给小说的名字，用名字去搜小说却简单的多。因为一般小说网站都会对小说名字建立索引，比如采用上次聊的哈希表索引，可以简单的通过名字找到内容； 这也类似于我们背诵唐诗，给你个题目，可以很容易背诵出来一首诗，但是如果给你个词语，比如明月，让你给出哪些诗里面包含这个词语，却很难想。

二 倒排索引和正排索引
第一次看到倒排索引，还是16年的时候，一脸懵逼，为什么叫倒排索引，这么奇怪的名字，何为倒何为正，那正排索引是什么,倒排索引又是什么?

可以简单理解从文章到词语叫正排,从词语到文章叫倒排。以这些方式建的索引分别叫正排索引和倒排索引。

2.1 正排索引
这里面文档可以是一篇文章,也可以是一个网页,还可以是一章小说或者一本小说 。文档ID映射到词语列表的索引叫正排索引,也就是说我们首先对文档进行编号,然后对文档进行分词,建立一个文档ID和文档词语对应的哈希表, 同时保存的还有词出现的次数,位置等信息,如下图:

正排索引

这就是一个哈希表，key就是文档的ID，value就是一个组合结构，里面包含词语，词语频次，出现位置。只所以有出现位置，搜索时候可以高亮显示。

那么你可能会问了，我们搜文章的时候不可能知道ID，那怎么办。简单，如果文档少，可以建个大数组啊，数组位置就作为ID，数组是有序的，这样用二分查找，找到文档名称了，从而找到文档ID，再去搜索就可以了。

如果文档比较多，可以用跳表，红黑树等结构保存文档名称和ID，也可以方便地进行搜索的。也可以用哈希表保存，以文章名作为key，以文档ID作为value，可以快速搜到索引。

正排索引用处： 在ES，solr等开源搜索引擎中仍然是存在的，在ES中为doc values，我们在搜索的时候使用倒排索引，但是聚合的时候，需要查这个文档中有多少词语，所以倒排索引并不高效。在ES中，doc values 伴随倒排索引创建，是可以被序列化到磁盘的数据结构，在内存中用os的文件缓存来存储。
如果不需要对字段进行聚合，排序以及脚本操作，而且不是需要再次分词的字段可以关闭doc values，因为默认是开着的。

PUT my_index
{
"mappings": {
"my_type": {
  "properties": {
    "mystring": { 
      "type":       "keyword",
      "doc_values": false
    }
  }
}
}
}

更改my_type字段不保存doc_values，这样设置可以节省内存和磁盘空间。

正排索引缺点： 如果只有正排索引，如果搜索特定词语，比如搜索词语22，我们必须遍历整个哈希结构，获取每个文档对应的词语列表，一个一个比较，显然效率很低，N个文章，每个文章有M个词语，那查找的复杂度至少是O(N*M)。

2.2 倒排索引
如果按照前面说的，如果我们搜索包含特定词语的诗词，用正排索引，显然不合适，因为涉及到大量的遍历。直观地想，搜索什么，我们就对什么建索引，对于诗词，我们对每篇诗词分词后，建立一个以词语作为key，诗词的ID列表以及位置，词频等作为value的哈希表，这样我们在搜索词语的时候，可以在O(1)时间复杂度找到包含这个词语的诗词列表，如下：

倒排索引

三 倒排索引创建和查询
3.1 倒排索引创建
倒排索引的创建过程，整体来说比较简单，主要有以下几步：

首先对文档进行编号，且排序，这里面我觉得可以按照文档的编号遍历，编号顺序就是文档的顺序，
不然就需要对文档进行排序。

遍历排序后的文档，对每个文档进行分词，生成《词语，文档ID，位置》的一组组数据，只所以保存位置是为了高亮查询的关键词，有些多个词语查询，如果两个词语靠的更近，得分会更高些。

将《词语，文档ID，位置》插入到以词语作为key，《文档ID，位置》作为value的哈希表中。
value中也可以多存点信息，比如此在这个文档中出现的次数，这对于我们搜索后排序很有用。
最后形成如上图的倒排索引，注意下，上面的倒排索引的value是个链表，而且是排序的链表（id小的在前面）。

内存中的倒排索引可以这样创建，实际中倒排索引创建还需要考虑很多因素，比如文档数量很大，且每个文档也很大，导致索引在内存中无法保存怎么处理，需要将中间结果持久化到磁盘中； 一般还需要一个词典保存所有词语，这样，词语就可以用编号来表示，减少内存的使用；同样我们还要考虑压缩倒排所以的大小，比如对文档ID，因为是顺序存储，我们可以只保存差值，减少数据保存的位数。

3.2 利用倒排索引的查找
如果只是简单的一个词语进行查找，利用倒排索引轻易查出posting list获取到文档ID，在通过文档ID把一个个查询出来的文档提取出来就可以了。

但是实际中，我们查询的关键词经常是多个，如果查询即包含中国又包含真气词语的小说，我们会得到两个posting list如下：

Posting list 归并

如上图，查询两个关键词，我们得到两个posting list 然后进行归并，由于文档是有序的，所以归并的过程性能还不错，我们通过两个指针来指向posting list的开头，然后根据比较结果移动指针，如果相同，把docID取出来放在结果集合中，如果不相等，小的那个指针对后移动，继续进行比较，直到一个posting list结束。

这是查询同时包含两个词的情况，还有的情况需要查询包含多个词其中之一的，或者包含A词语，却不含有B词语的无非是两个集合的并集，交集，差集。

虽然上面这种归并的方法，性能还不错，但是实际工程中，需要用多种手段来优化归并的性能，因为posting list很长，如果上述的归并算法是O(m+n),仍然难以性能要求，可以通过调表，哈希表，位图等多种手段优化归并性能。

四 倒排索引延申
倒排索引更重要是一种思想，是一种从有限到无限，从属性到整体的建索引的思路。比如如何对pcap文件建索引，如果你查询需要根据IP，端口，四层协议去查询的话，很简单可以以这些查询关键字作为key，pcapid作为value，或者pcap的包的offset作为value。

通过这种方法，可以快速查询到pcap，最近工作中的pcap的查询就是大概采用这种方法，当然其中有不少细节和优化手段，下次再写篇文章和大家分享。

五 诗词欣赏

《水调歌头》·无名氏

无名氏

平生太湖上，短棹几经过。如今重到，何事愁与水云多。
拟把匣中长剑，换取扁舟一叶，归去老渔蓑。

银艾非吾事，丘壑已蹉跎。
脍新鲈，斟美酒，起悲歌。

太平生长，岂谓今日识兵戈。
欲泻三江雪浪，净洗胡尘千里，不用挽天河。
回首望霄汉，双泪堕清波。

根据曾敏行《独醒杂志》记载，宋高宗绍兴年间有人在吴江长桥头上题词一首(即本词)，不写姓名。以后这首词传入宫内，高宗派人大力查访。秦桧请高宗降黄榜招请，可作者竟然不到。人们议论说，作者是隐士，不屑做官。秦桧请降黄榜，并非真心寻求，而是居心叵测。

作者：明翼
链接：https://www.jianshu.com/p/3e9d0c039e13
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。