前言
学习上一章，我们对ElasticSearch有了清晰的理解，博客继续学习ES核心原理和具体实现更为重要。相对于MySQL索引机制主要是基于B 树，我们需要手动创建索引，但是ES无需手动创建索引，默认为自动创建索引。所以学习ES的倒排索引可以和MySQL比较索引，学习，思考为什么ES可实时实现倒排索引（NRT）的查询效率
知识点
- 知道ES具体实现倒排索引？
- 什么是FST和作用？
- 索引帧Frame Of Reference的实现原理
- Roaring Bitmaps 咆哮位图的作用
什么是倒排索引？
ES的宗旨就是“一切为了查询”，ES查询速度快的主要原因是index，也就是Inverted index，翻译是倒排索引。那么倒排索引是什么呢？例如，需要保存以下数据
| ID | Name | Sex | Job |
|---|---|---|---|
| 1 | Tom | Man | driver |
| 2 | Jack | Man | driver |
| 3 | Alice | Female | actor |
Name:
| Term | Posting List |
|---|---|
| Tom | 1 |
| Jack | 2 |
| Alice | 3 |
Sex:
| Term | Posting List |
|---|---|
| Man | [1,2] |
| Female | 3 |
Job:
| Term | Posting List |
|---|---|
| driver | [1,2] |
| actor | 3 |
-
Posting List（倒排表） ES会为每一个Field建立倒排索引。document数据分词，
tom、man、driver这些叫term(分类索引)，而[1,2]是Posting List(倒排表)，Posting List所有的存储都符合一个term的文档id。比如要查找job为driver人员信息可以立即获得ID为1和2提供人员信息。但是，如果有数千万的数据，并且必须通过name查找？ -
Term Dictionary（词典） 为了通过上述name查找的情况，ES会将所有term排序，然后通过二分法找到term，所以查找效率是log(N)，这种搜索就像通过字典搜索，这就是
Term Dictionary。不过熟悉B/B 树会知道，这似乎与传统有关B/B 树的方式是一样的，MySQL大多数索引也直接使用B 建立索引词典指向索引的数据 -
Term Index(词典索引) 相对于B/B 对于树木的搜索，ES查询性能进一步提高，ES当然，直接将字典数据转移到内存是不合理的。如果有大量的数据，内存估计是不够的。ES通过建立词典索引(Term Index)在这种方式中，只有占用空间相对较小的词典索引被放置在内存中，这个词典索引通常只保留词典的前缀或后缀和相应的关系，所以当前的关系可以用图表来表示：
- B通过减少磁盘的搜索次数，提高查询性能；
- B 尽量将随机读变为顺序读，提高查询性能；
- ES此外，在倒排表和二分搜索的基础上，将词典索引转移到内存搜索中，因此查询效率会更快
然后term index它是如何产生的？ES通过穷状态转换器，简称FST技术生成Term Index，放到内存
2、Finite State Transducers(FST)
Finite State Transducers，简称FST，中文通常翻译为有限状态转换器或有限状态传感器 FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output. FST一个字节序列映射block块的技术
假设有单词序列mop、moth、pop、star、stop和top，要映射到编号0…最简单的方法是定义一个Map<String,Integer>可以，但从内存占用较少的角度来看，有什么更好的方法，答案是FST。
排序好的单词mop、moth、pop、star、stop和top以及他们的顺序号0，…,5.可生成以下状态转换图：
遍历上面的每一个边，如输入pop会过去的p/2、o、p，相加得到的排名对于mop，排名结果为0。
这棵树只保存term磁盘对应的前缀可以通过这个前缀找到block，然后再通过block去找倒排表Posting List。例如，为了压缩词典空间，mop和moth两个term，在都是以mo开头的block，在相应的词典中只保存p和th，这样，空间利用率大大提高。FST可怜的状态转换器可以节省大量的内存空间，但它需要更多的查询CPU资源。
使用维基百科的索引FST，只使用了69MB只需要8秒左右的时间，就可以为近1000万个单词设置索引，使用的堆空间不到256MB
通过FST，词典索引可以放在内存中，占用很小的空间，通过词典索引可以找到倒排表Posting List。但另一个问题是，这些文档ID会放在倒排表上Posting List在里面，如果有1亿个文档，每个文档有10个字段，Posting List要花10亿integer磁盘占用的空间也比较大，所以ES采用另一种巧妙的处理方法，该技术是Frame of Reference
3、Frame of Reference
针对上述文档ID磁盘空间占用过多，ES采用压缩算法：Frame of Reference，可翻译成索引帧
ES根据这个算法，倒排表将被执行
Posting List的文档进行delta-encoding(可翻译成增量编码)block，每个block只需包含256个文档，然后计算每个文档block保存这个文档最多需要占用多少数据？ID，并将此位数作为头部信息放在每个位置block这种技术叫索引帧（Frame of Reference）
图来自https://www.elastic.co/cn/blog/frame-of-referece-and-roaring-bitmaps，这里进行中文翻译，注意，图例，假设每个block只有3个文件而不是256，实际情况应该是256的，这里还会进行增量编码，比如73+227=300 ,300+2=302，所以增量编码只会存储增量的值
这种压缩算法的原理是通过增量算法(delta-encoding)，将原来的大数变成小数，仅存储增量值，再分为多个block，计算最多需要多少位（比如前面的图例327需要二进制的11111111，也是十进制的256，要8位才能存储），将计算总的，需要多少字节，加上header存的1位，转为字节存储，而不是用int(4个字节)存储，仅仅6个值就用了24字节
在返回结果的时候，其实也并不需要把所有的数据直接解压然后全部返回，可以直接返回一个迭代器iterator，直接通过迭代器的next方法逐一取出压缩的文档ID，通过这种方法极大的节省计算和内存开销
ES使用索引帧可以极大地节省posting list占用的磁盘空间和内存开销，同时ES为了提高filter过滤器查询的性能，也使用了缓存的方法，比如Roaring Bitmaps，可以翻译为咆哮位图
4、Roaring Bitmaps
ES使用Roaring Bitmaps缓存使用频率比较高的Filter查询， 原理是生成(fitler, segment数据空间)和ID列表的映射。
Roaring Bitmaps是由int数组和bitmap这两个数据结构改良过的成果，因为int数组速度虽然快，但是空间占用比较多；bitmap相对来说占用空间比较小，但是不管多少文档都需要12.5Mb的空间，即使只有一个文件也要
- Roaring Bitmaps根据每个id的高16位分配id到对应的block里面，比如第一个block里面id应 该都是在0到65535之间，第二个block的id在65536和131071之间，以此类推
- 然后对每一个block里面的数据，根据id数据选择short数组或者bitmap存储
- 如果数量小于4096，就用short数组存储
- 如果数量大于等于4096，就用bitmap保存
图来自https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps，这里进行中文翻译
5、倒排索引怎么做联合索引？
前面介绍的都是单个field的索引，如果是多个field索引的联合查询，倒排索引如何快速查询？
- 利用跳表(Skip List)的数据结构快速做“与”运算
- 利用bitset这种数据结构按位“与”运算
如图，跳表的数据结构：有一个有序链表Level0，挑出其中几个元素到level1和level2，每一个level越往上，选出来的指针元素就越少，查找时候从高level往低查找。比如查找45，先找到level2的25，然后往下查找到45，查找效率和level2相当，但是也是利用了一定的空间冗余来实现的
假如有下面的Posting List需要联合索引，如果使用跳表，对最短的Posting List中的每一个id，逐个在另外两个Posting list中查找看是否存在，最后得到交集的结果； 如果使用bitset，bitset是基于bitmap的，直接按位与，得到的结果就是最后的交集
6、ES索引使用注意事项
- ES默认是自动建索引的，不需要索引的字段，要明确定义出来
- 同样，对于string类型默认是会进行analysis（分词）的，不需要analysis的需要定义出来
- 文档的ID需要选择有规律的ID，随机性太大，比如UUID不利于查询
7、总结和思考
- ES之所以查询很快，主要是依赖于倒排索引的设计，尽量将数据放在内存，加上各种压缩算法和缓存算法。
- 由于索引数据量很大，不能直接将数据丢在内存，所以通过构建有序状态转换器FST放在内存中。
- 为了避免Posting List大量的文档ID占用太多磁盘空间，ES使用了索引帧（Frame of Reference）技术压缩posting list。
- ES还采用了Roaring Bitmap技术来缓存使用频率比较高的Filter搜索结果
8、参考资料
- https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps
- https://zhuanlan.zhihu.com/p/137574234