Elasticsearch 倒排索引原理
倒排索引也是索引的一种。索引，本质上就是为了快速检索我们存储的数据。
每种数据库都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。
对于 MySQL 来说，使用 B+ tree 索引是为了优化已有数据的存储结构，对于不需要快速更新的时候，采用预先排序等方式换取更小的存储空间，更快的检索速度，但同时，由于每次更新都需要对 B+ 树进行调整，导致更新比较慢。Elasticsearch 是通过 Lucene 的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好。
Elasticsearch 是建立在全文搜索引擎库 Lucene 基础上的搜索引擎，它隐藏了 Lucene 的复杂性，取而代之的提供一套简单一致的 RESTful API，不过掩盖不了它底层也是 Lucene 的事实。
Elasticsearch 的倒排索引，其实就是 Lucene 的倒排索引。
倒排索引名字的由来
在没有搜索引擎时，我们是直接输入一个网址，然后获取网站内容，这时我们的行为是：
document -> to -> words
通过文章，获取里面的单词，这种就是所谓的”正向索引”（forward index）。
后来，我们希望能够输入一个单词，找到含有这个单词，或者和这个单词有关系的文章：
word -> to -> documents
于是就把这种索引，称为 inverted index，直译过来，应该叫”反向索引”，国内翻译成”倒排索引”。
倒排索引的内部结构
首先，在数据生成的时候，比如插入一份文档，内容是“生存还是死亡”，这个时候通过使用分词器，会将它分解为“生存”、“还是”、“死亡”三个词语，然后可能还会把“还是”这个无意义的词语干掉。
接着，就会将这两个词语以及对应的文档 id 存下来：
| word | documentId |
|---|---|
| 生存 | 1 |
| 死亡 | 1 |
然后我们再插入一个文档，这个内容是“生存”，于是索引就变成了：
| word | documentId |
|---|---|
| 生存 | 1，2 |
| 死亡 | 1 |
下回在搜索“生存”的时候，就会返回1，2两份文档。
但是只是这样是远远不够的，世界上的语言种类特别多，没搜索一个单词，就都要全局遍历，效率特别低。这时候就需要用到了排序，以便采用二分查找等方式提高遍历效率，在这里 lucene 采用了跳表的数据结构，这就是Term Dictionary,另一方面，光使用排序还会导致磁盘IO速度过慢（因为数据都放在磁盘中），如果将数据放入内存，又会导致内存爆满。
所以，Lucene 的倒排索引，在上面的表格的基础上，在左边增加了一层字典树 term index，它不存储所有的单词，只存储单词前缀，通过字典书找到单词所在的块，也就是单词的大概位置，再在块里二分查找，找到对应的单词，再找到单词对应的文档列表。
另外，为了进一步节省内存，Lucene 还用了 FST（Finite State Transducers）对 Term Index 做进一步压缩，term index 在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary 在磁盘上是以分 block 的方式保存的，一个block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。
对 Posting List 的改进
原生的 Posting List 有两个可以改进的地方：
- 如何压缩以节省磁盘空间
- 如何快速求并交集
压缩
假设有这样一个数组：
[73, 300, 302, 332, 343, 372]
如何进行压缩呢？
在Lucene里，数据是按照 Segment 存储的，每个 Segment 最多存 65536 个文档 ID， 所以文档 ID 的范围，从 0 到 2^16-1，所以如果不进行任何处理，那么每个元素都会占用 2 bytes ，对应上面的数组，就是 6 * 2 = 12 bytes。
压缩，就是尽可能降低每个数据占用的空间，同时又能让信息不失真，能够还原回来。
增量编码
数据只记录元素与元素之间的增量，于是数组变成了：
[73, 227, 2, 30, 11, 29]
分割成块
Lucene 里每个块是 256 个文档 ID，这样可以保证每个块，增量编码后，每个元素都不会超过 256（1 byte），另外还方便进行后面求交并集的跳表运算。
为了方便演示，我们假设每个块是 3 个文档 ID：
[73, 227, 2], [30, 11, 29]
按需分配空间
对于第一个块，[73, 227, 2]，最大元素是227，需要 8 bits，所以就给每个元素都分配 8 bits的空间。
但是对于第二个块，[30, 11, 29]，最大的元素才30，只需要 5 bits，所有给每个元素只分配 5 bits 的空间足矣。
以上三个步骤，共同组成了一项编码技术，Frame Of Reference（FOR）：
快速求交并集
在 Lucene 中查询，通常不只有一个查询条件，比如想搜索：
- 含有“生存”相关词语的文档
- 文档发布时间在最近一个月
- 文档发布者是平台的特约作者
这样就需要根据三个字段，去三棵倒排索引里去查，当然，磁盘里的数据，上一节提到过，用了 FOR 进行压缩，所以我们要把数据进行反向处理，即解压，才能还原成原始的文档 ID，然后把这三个文档 ID 数组在内存中做一个交集。
即使没有多条件查询， Lucene 也需要频繁求并集，因为 Lucene 是分片存储的。
可以把 Lucene 遇到的问题，简化成一道算法题。
假设有下面三个数组：
[64, 300, 303, 343]
[73, 300, 302, 303, 343, 372]
[303, 311, 333, 343]
求它们的交集。
Integer 数组
直接用原始的文档 ID ，如果逐个数组遍历一遍，这样就可以求了，这样不管是空间还是性能都不够理想。
其实对于有序的数组，用跳表（skip table）可以更高效，但是不管是从性能，还是空间上考虑，Integer 数组都不靠谱，假设有100M 个文档 ID，每个文档 ID 占 2 bytes，那已经是 200 MB，而这些数据是要放到内存中进行处理的，把这么大量的数据，从磁盘解压后丢到内存，内存肯定撑不住。
Bitmap
假设有这样一个数组：
[3,6,7,10]
那么可以这样通过使用 bitmap （位图）来表示：
[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.5 MB，比之前用 Integer 数组的 200 MB 节省了大量的内存。
- 运算更快：0 和 1，天然就适合进行位运算，求交集，「与」一下，求并集，「或」一下，一切都回归到计算机的起点
Roaring Bitmaps
bitmap 有个硬伤，就是不管你有多少个文档，你占用的空间都是一样的，之前说过，Lucene 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。
对于 Integer，使用 Skip List（跳表）做合并计算
对于需要查找的每一个 int 数组建立跳表，然后由最短的 posting list 开始遍历，遍历的过程中各自可以跳过不少元素，比如下面的例子：
以上是三个posting list。现在需要把它们用AND的关系合并，得出posting list的交集。首先选择最短的posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。
整个过程如下：
Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!
Roaring bitmaps 和 Frame Of Reference 的关系
Frame Of Reference 是压缩数据，减少磁盘占用空间，所以当我们从磁盘取数据时，也需要一个反向的过程，即解压，解压后才有我们上面看到的这样子的文档ID数组：[73, 300, 302, 303, 343, 372] ，接着我们需要对数据进行处理，求交集或者并集，这时候数据是需要放到内存进行处理的，我们有三个这样的数组，这些数组可能很大，而内存空间比磁盘还宝贵，于是需要更强有力的压缩算法，同时还要有利于快速的求交并集，于是有了Roaring Bitmaps 算法。
另外，Lucene 还会把从磁盘取出来的数据，通过 Roaring bitmaps 处理后，缓存到内存中，Lucene 称之为 filter cache.
为什么 Elasticsearch/Lucene 检索可以比 mysql 快
Mysql 只有 term dictionary 这一层，是以 b-tree 排序的方式存储在磁盘上的。检索一个 term 需要若干次随机 IO 的磁盘操作。而 Lucene 在 term dictionary 的基础上添加了term index来加速检索，term index 以树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access （随机IO）次数。
参考文档