[toc]

为什么需要倒排索引

倒排索引也是索引。索引初衷都是为了快速检索到你要的数据。

每种数据库有自己需要解决的问题(或者说擅长的领域)，对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。

对MySQL来说，是B+树，对于ES/Lucene来说是倒排索引。

• ES是建立在全文搜索引擎库Lucene基础上的搜索引擎，他隐藏了Lucene的复杂性，取而代之的提供一套简单一致的RESTful API，不过掩盖不了他底层也是Lucene的事实，Es的倒排索引，其实就是Lucene的倒排索引。

为什么叫倒排索引

在没有搜索引擎时，我们是直接输入网址，然后获取网站内容，这时我们的行文是：document->to->words，通过文章，获取里面的单词，此为倒排索引，forward index。

后来，我们希望能够输入一个单词，找到含有这个单词，或者和单词有关系的文章：word->to->documennts

于是我们把这种索引，称为inverted index，直译过来，应该叫反向索引，国内翻译成倒排索引。

倒排索引的内部结构

首先，在数据生成的时候，比如爬虫爬到一篇文章，这里我们需要对这篇文章进行分析，将文本拆解成一个个单词。

这个过程很复杂，比如“生成还是死亡”，要如何让分词器自动将他分解为“生存”，“还是”，“死亡”三个词语，然后把“还是”，这个无意义的词语干掉。接着，把这两个词语已经它对应的文档id存下来：

word	document Id
生存	1
死亡	1

接着爬虫继续，又爬到一个含有“生存”的文档，于是索引变成：

word	document Id
生存	1，2
死亡	1

下次搜索“生存”，就会返回文档ID是1、2的两份文档。

上面这套索引的实现，只是最简单，想想看，这个世界上那么多单词，，每次搜索一个单词，都要全局遍历一遍，很明显不行。于是有了排序，我们需要对单词进行排序，像B+树一样，可以在页面实现二分查找。光排序还不行，单词都放在磁盘呢，磁盘IO非常慢，所以MySQL特意把索引缓存到了内存，但是ES不行，因为单词太多，所以是下面的结构：

image

ES的倒排索引，增加了最左边的一层字典树term index，他不存存储所有单词，只存储单词的前缀，通过字典树找到单词所在的块，也就是单词大概的位置，再在块里进行二分查找，找到对应的单词，在找到对应的文档列表。

当然内存，能省则省，所以ES还用了FST(Finite State Transducers)对他进一步压缩。

这里重点说一下最右边的Postinng List，别看只是存一个文档ID数组，但是他的设计，遇到的问题可不少。

Frame Of Reference

原生的Posting List有两个痛点：

• 如何压缩以节省磁盘你内存
• 如何快速求交并集(intersections and unionns)

压缩数据

我们简化一个ES要面对的问题，假设有这样的一个数组：[73, 300, 302, 332, 343, 372]，如何把他进行压缩？

Es里，数据是按Segment存储的，每个Segment最多存65536个文档ID，所以文档ID的范围，从0到2^32 - 1，所以如果不进行任何处理，那么每个元素都会占用2 bytes，对应上面的数组就是6*2=12 bytes。

怎么压缩？

压缩，就是尽可能降低每个数据占用的空间，同时又能让信息不失真，能够还原回来

Step 1：Delta-encode 增量编码

我们只需要记录元素与元素之间的增量，于是数组变成了[73,227,2,30,11,29]

Step 2：Split into blockes 分隔成块

ES里面每个块是256个文档ID，这样可以保证每个块，增量编码后，每个元素都不会超过256(1 byte)。

为了方便演示，我们假设每个块是3个文档ID：
[73,227,2]，[30,11,29]

Step 3：Bit packing 按需分配空间

对于第一个块，[73,227,2]，最大元素是227，需要8 bits，那么给这个块每个元素，都分配8 bits的空间。
但是对于第二个块，[30,11,29]，最大的元素才30，只需要5 bits，那么给每个元素只分配5 bits的空间足够。

这一步，可以说是把吝啬发挥到极致。

以上三个步骤，共同组成了一项编码技术，Frame Of Reference(FOR)：

image

Roaring bitmaps

现在来说Posting List的第二个痛点，如何快速求交并集(inteersections and unions)

在ES中查询，通常不只有一个查询条件，比如想搜索：

• 含有“生存”相关词语的文档
• 文档发布时间在最近一个月
• 文档发布者是平台的特约作者
  这样就需要根据三个字段，去三个倒排索引里去查，当然磁盘里的数据，上一节提到了，用了FOR进行压缩，所以我们要吧数据进行反向处理，即解压，才能还原成原始文档ID，然后把这三个文档ID数组在内存中做一个交集。

注：即使没有多条件查询，ES也需要频繁求并集，因为ES是分片存储的。

我么把ES遇到的问题，简化成一道算法题。

加入有下面三个数组：
[64,300,303,343]

[73,300,302,303,343,372]

[303,311,333,343]
求他们的交集

Integer 数组

直接用原始文档ID，可能会说，那就逐个遍历，遍历完就知道交集是什么了。

其实对于有序数组，用跳表(skip table)可以更搞笑，这里不展开了，因为不管是从性能，还是空间上考虑，Integer数组都不靠谱，假设有100M个文档ID，每个文档ID占2 bytes，那已经是200MB，而这些数据要放到内存中进行处理的，把这么大量的数据，从磁盘解压后丢到内存，内存肯定撑不住。

Bitmap

假设有这样的一个数组：

[3,6,7,10]

我们可以这样来表示：
[0,0,0,1,0,0,1,1,0,0,1]

我们用0表示角标对应的数组不存在，1表示存在
这样两个好处：

• 节省空间：我们只需要0和1，那每个文档ID就只需要1 bit，还是假设有100M个文档，那只需要100M bits=100M * 1/8 bytes=12.5M，比之前用Integer数组的200MB，优秀太多
• 运算更快：0和1，天然就适合进行为运算，求交集，&一下，求并集，|一下，一切都回归到计算机的起点。

Roaring Bitmaps

Bitmap有个硬伤，就是不管有多少个文档，占用的空间都是一样的，之前说过，Posting List的每个Segement最多放65536个文档ID，举一个极端的例子，有一个数组，里面只有两个文档ID：[0,65535]，用Bitmap，要怎么表示[1,0,0,0...(超多个0)...,0,0,1]，你需要65536个bit，也就是65536/8=8192 bytes，而用Integer数组，只需要2*2 bytes=4 bytes，可见文档数量不多的时候，使用Integer数组更加节省内存。

算一下临界值，很简单文档数量多少，bitmap都需要8192 bytes，而Integer数组则和文档数量成线性相关，每个文档ID占2 bytes，所以：8192/2=4096，当文档数量少于4096时，用Integer数组，否则，用bitmap

image

注：补充一下Roaring bitmaps和之前讲的Frame Of Referrence的关系。Frame Of Referrence是压缩数据，减少磁盘占用空间，所以我们从磁盘取数据时，也需要一个反向过程，即解压，解压后才有我们上面看到的这样子的文档ID数组：[73,300,302,303,343,372]，接着我们需要对数据进行处理，求交集或者并集，这时候数据是需要放到内存进行处理的，我们三个这样的数组，这些数组可能很大，而内存空间比磁盘还宝贵，于是需要更强有力的压缩算法，同时还要有利于快速的求交并集，于是有了Roaring bitmaps处理后，缓存到内存中ES称之为filter cache。

总结

每一种数据库都有自己要解决的问题(或者说擅长的领域)，对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询目的。