Elasticsearch检索为什么这么快，倒排索引，inverted-index

相比传统的关系型数据库Mysql，ES在大数据量(几千万，亿级)搜索方面的性能要好很多，ES的设计核心就是一切为了搜索，这样的出发点也会导致ES的偏科，比如，ES在写入/更新方面的性能就一般。

所以ES一般用来做搜索库，主库Mysql提供主要服务，并将需要检索的数据同步到ES，由ES来提供检索服务。

特性：
1、ES是一个面向文档型的数据库，每一条记录是一个文档，用JSON作为文档序列化的格式
2、ES是一个分布式，可扩展，实时搜索和分析，全文检索的服务
3、建立在全文搜索引擎Apache Lucene基础之上
4、默认为每一个字段创建索引
5、可以扩展到上百台服务器，处理PB级别的结构化或非结构化数据

文档结果：

{
    "name" :     "John",
    "sex" :      "Male",
    "age" :      25,
    "birthDate": "1990/05/01",
    "about" :    "I love to go rock climbing",
    "interests": [ "sports", "music" ]
}
1
2
3
4
5
6
7
8

ES的存储：索引(index) -> 分类(type) -> 文档(document) -> 字段(field)
从ES7.0.0开始，废弃了分类type这个层级。

ES提供了restful api供外部调用。

ES高效的检索能力最关键的点就是其对于索引的处理，这里的索引和MySQL的索引是一样的意思，不同之处在于Mysql索引基于B+Tree，而ES索引却是自创的；而且Mysql的索引是以文件形式存在磁盘上，而ES是存在内存中。

以下来讲解ES的索引的创建和查找

记录如下：

| Name | Age  |  Sex
|--------|------| -----
| Carla  | 24   | Female
| Sara   | 24   | Male
| Elin   | 29   | Male
| Ada    | 24   | Female
| Patty  | 24   | Male
| Kate   | 29   | Male
| Selena | 29   | Male
1
2
3
4
5
6
7
8
9

因为ES是文档型的数据库，所以会自动为每个文档创建文档id，便于管理

ID | Name | Age  |  Sex
---|------| -----| -----
1  | Carla  | 24   | Female
2  | Sara   | 24   | Male
3  | Elin   | 29   | Male
4  | Ada    | 24   | Female
5  | Patty  | 24   | Male
6  | Kate   | 29   | Male
7  | Selena | 29   | Male
1
2
3
4
5
6
7
8
9

1、索引创建

倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。

ES默认为每一个字段都建立索引，可以单独发挥作用，也可以联合发挥作用，我们先讨论单个索引的创建，比如 Name字段。
把字段的值 Carla,Sara,Elin,Ada,Patty,Kate,Selena 称为term。于是可以这么表示

term 	Posting List

Carla	[1]
Sara	[2]
Elin	[3]
Ada		[4]
Patty	[5]
Kate	[6]
Selena	[7]
1
2
3
4
5
6
7
8
9

term 是单词，也就是分词之后的最小单元。
Posting List 是倒排列表，为文档的id，是一个int的数组，存储了所有符合某个term的文档id（实际的Posting List中还存储了此单词在此文档中出现的位置，出现的频次）。这一点和MySQL很像，也就是将其他字段关联到主键上。

同理 Age 字段

term 	Posting List
24		[1,2,4,5]
29		[3,6,7]
1
2
3

以上结构就是 term -> Posting List 结构，只要找到 term，就能找到文档id。
而term就是索引，现在需要对term做优化。

首先，对term排序，得到 Ada,Carla,Elin,Kate,Patty,Sara,Selena 排序后的结果称为 term Dictionary,有了排序就可以通过二分查找法来提高效率了，但是如果仅仅是这样，那么其检索效率还不如mysql呢，毕竟B+Tree比二分查找层级浅，结构更合理。于是，在term dictionary上面再抽象出了一层 term index，可以理解为字典中的目录页，可以快速定位 term dictionary 中的 offset。

如果所有的term都是英文字符的话，可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是，term未必都是英文字符，term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term，比如x字符开头的term可能一个都没有，而s开头的term又特别多。实际上 term index 是一棵trie树。

例子是一个包含 “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, 和 “inn” 的 trie 树。
其中有数字的代表此处有值，而数字就是 term dictionary 中的 offset，然后从这个位置再往后顺序查找，找到对应的 term 之后就能知道文档ID了。隐射关系如下：

现在我们可以回答“为什么Elasticsearch/Lucene检索可以比mysql快了。Mysql只有term dictionary这一层，是以b+tree排序的方式存储在磁盘上的。检索一个term需要若干次的random access的磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的random access次数。

为了减小内存占用，term index 取的是 term 的一些前缀，并不是完整的 term 值。额外值得一提的两点是：term index在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b+tree更节约磁盘空间。

另外，Term dictionary 在磁盘上是以分 block 的方式保存的，一个 block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。

elasticsearch 会先进行分词，再来建立索引，这会导致在搜索的时候，输入的关键词不同，结果不同。比如有本书《刘心武妙品红楼梦》，输入关键词：
刘心武：无结果
红楼梦：有结果
妙品红楼梦：有结果
刘心武妙品：无结果
妙品：有结果
刘心武妙品红楼梦：无结果

所以，需要选择好的分词器，尤其是面对中文分词场景，比如 elasticsearch-analysis-ik，同时，对于一些专有名词，自定义名称，我们还需要设置词库词典，这样它就会优先按照词典来分词，更加准确。可以参考 中文分词优化

2、索引查找

倒排索引：(索引块)Term Index -> (索引词典)Term Dictionary -> Posting List

3、联合索引查询

age=18 AND gender= 女
可以理解为 将 age=18的Posting List 和 gender=女 的 Posting List 合并，取交集。
这个理论上的“与”合并的操作可不容易。对于 mysql 来说，如果你给 age 和 gender 两个字段都建立了索引，查询的时候只会选择其中最 selective 的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：

使用 skip list 数据结构。同时遍历 gender 和 age 的 posting list，互相 skip；
使用 bitset 数据结构，对 gender 和 age 两个 filter 分别求出 bitset，对两个 bitset 做 AND 操作。
1
2

PostgreSQL 从 8.4 版本开始支持通过 bitmap 联合使用两个索引，就是利用了 bitset 数据结构来做到的。当然一些商业的关系型数据库也支持类似的联合索引的功能。Elasticsearch 支持以上两种的联合索引方式，如果查询的 filter 缓存到了内存中（以 bitset 的形式），那么合并就是两个 bitset 的 AND。如果查询的 filter 没有缓存，那么就用 skip list 的方式去遍历两个 on disk 的 posting list。

利用 Skip 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!!!
1
2
3
4
5
6
7
8
9
10

最后得出的交集是 [13,98]，所需的时间比完整遍历三个 posting list 要快得多。但是前提是每个 list 需要指出 Advance 这个操作，快速移动指向的位置。什么样的 list 可以这样 Advance 往前做蛙跳？skip list：

从概念上来说，对于一个很长的posting list，比如：
[1,3,13,101,105,108,255,256,257]

我们可以把这个list分成三个block：

[1,3,13] [101,105,108] [255,256,257]

然后可以构建出skip list的第二层：

[1,101,255]

1,101,255分别指向自己对应的block。这样就可以很快地跨block的移动指向位置了。

Lucene自然会对这个block再次进行压缩。其压缩方式叫做Frame Of Reference编码。示例如下：

考虑到频繁出现的term（所谓low cardinality的值），比如gender里的男或者女。如果有1百万个文档，那么性别为男的posting list里就会有50万个int值。用Frame of Reference编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然mysql b+tree里也有一个类似的posting list的东西，是未经过这样压缩的。

因为这个Frame of Reference的编码是有解压缩成本的。利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu。

利用bitset合并

Bitset是一种很直观的数据结构，对应posting list如：

[1,3,4,7,10]

对应的bitset就是（从左到右看）：

[1,0,1,1,0,0,1,0,0,1]

每个文档按照文档id排序对应其中的一个bit。Bitset自身就有压缩的特点，其用一个byte就可以代表8个文档。所以100万个文档只需要12.5万个byte。但是考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情。而且对于个每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset，18<=age<25是另外一个filter缓存起来也要一个bitset。

所以秘诀就在于需要有一个数据结构：

可以很压缩地保存上亿个bit代表对应的文档是否匹配filter；
这个压缩的bitset仍然可以很快地进行AND和 OR的逻辑操作。
Lucene使用的这个数据结构叫做 Roaring Bitmap。

其压缩的思路其实很简单。与其保存100个0，占用100个bit。还不如保存0一次，然后声明这个0重复了100遍。

这两种合并使用索引的方式都有其用途。Elasticsearch对其性能有详细的对比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为Frame of Reference编码是如此 高效，对于简单的相等条件的过滤缓存成纯内存的bitset还不如需要访问磁盘的skip list的方式要快。

如何减少文档数？

一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用mysql存储的时候，也把一分钟的很多数据点合并存储到mysql的一行里以减少行数。

这个过程可以示例如下：

可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。

Elasticsearch有一个功能可以实现类似的优化效果，那就是Nested Document。我们可以把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。示例如下：

{timestamp:12:05:01, idc:sz, value1:10,value2:11}
{timestamp:12:05:02, idc:sz, value1:9,value2:9}
{timestamp:12:05:02, idc:sz, value1:18,value:17}
1
2
3

可以打包成：

{
max_timestamp:12:05:02, min_timestamp: 1205:01, idc:sz,
records: [
		{timestamp:12:05:01, value1:10,value2:11}
{timestamp:12:05:02, value1:9,value2:9}
{timestamp:12:05:02, value1:18,value:17}
]
}
1
2
3
4
5
6
7
8

这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。

在存储的时候，无论父文档还是子文档，对于Lucene来说都是文档，都会有文档Id。但是对于嵌套文档来说，可以保存起子文档和父文档的文档id是连续的，而且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的posting list就可以跟踪所有的父子关系。也可以很容易地在父子文档id之间做转换。把父子关系也理解为一个filter，那么查询时检索的时候不过是又AND了另外一个filter而已。前面我们已经看到了Elasticsearch可以非常高效地处理多filter的情况，充分利用底层的索引。

使用了嵌套文档之后，对于term的posting list只需要保存父文档的doc id就可以了，可以比保存所有的数据点的doc id要少很多。如果我们可以在一个父文档里塞入50个嵌套文档，那么posting list可以变成之前的1/50。

最后，值得注意的点
不需要索引的字段，一定要明确定义出来，因为默认是自动建索引的
同样的道理，对于String类型的字段，不需要analysis的也需要明确定义出来，因为默认也是会analysis的
选择有规律的ID很重要，随机性太大的ID(比如java的UUID)不利于查询

参考
https://zhuanlan.zhihu.com/p/33671444