作者：京东物流 李洪吉

提到 ES，大多数爱好者想到的都是搜索引擎，但是明确一点，ES 不等同于搜索引擎。不管是谷歌、百度、必应、搜狗为代表的自然语言处理(NLP)、爬虫、网页处理、大数据处理的全文搜索引擎，还是有明确搜索目的的搜索行为，如各大电商网站、OA、站内搜索、视频网站的垂直搜索引擎，他们或多或少都使用到了 ES。

​作为搜索引擎的一部分，ES 自然具有速度快、结果准确、结果丰富等特点，那么 ES 是如何达到“搜索引擎”级别的查询效率呢？首先是索引，其次是压缩算法，接下来我们就一起了解下 ES 的索引结构和压缩算法

1 结构

1.1 Mysql

Mysql 下的 data 目录存放的文件就是 mysql 相关数据，mysql 文件夹对应的就是数据库 mysql。

其中表 columns_priv 对应了 3 个文件：columns_priv.frm、columns_priv.MYD、columns_priv.MYI。

.frm：表结构；.MYD：myisam 存储引擎原数据；.MYI：myisam 存储引擎索引；.ibd：innodb 存储引擎数据

1.2 Elasticsearch

cfe 为索引文，cfs 为数据文件，cfe 文件保存 Lucene 各文件在.cfs 文件的位置信息

cfs、cfe 在 segment 还很小的时候，将 segment 的所有文件都存在在 cfs 中，在 cfs 逐渐变大时，大小超过 shard 的 10%，则会拆分为其他文件，如 tim、dvd、fdt 等文件

1.3 存储结构

倒排索引结构分为倒排表、词项字典、词项索引

倒排表包含某个词项的所有 id 的数据存储了在.doc 文件中

词项字典包含了 index field 的所有经过处理之后的词项数据，最终存储在.tim 文件中

1.4 结构对比

我们以某商城的手机为例，左侧为 es 倒排索引结构，右侧为原始数据。左侧图示只是为了展示倒排索引结构，并不是说 es 中倒排表就是简单的数组

以上面结构对比示例图为例，假如共有 10 亿条数据需要存储在 ES 中(上图右)，分词后存储的倒排表(上图左)大概包含分词 term 以及对应的 id 数组等，在 10 亿条数据中，分词“小米”相关的数据有 100 万条，也就是说分词“小米”对应的数组 Posting List 长度是 100 万

id 是 int 类型的有序主键，分词“小米”在数组 Posting List 中 100 万 int 类型数字总长度=100 万✖每个 int 占 4 字节=400 万 Byte≈4MB。1 个分词占 4MB 空间,假如 10 亿条数据有 500 万个分词，总空间=4MB✖500 万=2 千万 MB，磁盘空间直接爆炸

2 算法

分词对应的数组 Posting List 实际就是一个个有序数组，而有序数值数组是比较容易进行压缩处理的，而且一般来说压缩效益也不错，如果能对其进行压缩是能够大大节约空间资源的

ES 中倒排索引的压缩算法主要有 FOR 算法(Frame Of Reference)和 RBM 算法(RoaringBitMap)

2.1 FOR

FOR 算法的核心思想是用减法来削减数值大小，从而达到降低空间存储。 假设 V(n)表示数组中第 n 个字段的值，那么经过 FOR 算法压缩的数值 V(n)=V(n)-V(n-1)。也就是说存储的是后一位减去前一位的差值。存储是也不再按照 int 来计算了，而是看这个数组的最大值需要占用多少 bit 来计算

我们按照差值计算的方式来保存数据，初始值为 1，2 与 1 的差值为 1，3 与 2 的差值为 1……最终我们就将原始 Posting List 数据转化为 100 万个 1，每个 1 我们可以用 1bit 来记录，总空间=1bit✖100 万=100 万 bit，相比原有 400 万 Byte=3200bit，空间压缩了 32 倍

在实际生产中，不可能出现一个 term 的 Posting List 是这种差值均为 1 的情况，所以我们以通用示例举例。假如原数据为[73，300，302，332，343，372],数组中 6 个数字占据总空间为 24 字节。按照差值方式记录，数组转化为[73,227,2,30,11,29],最大数字为 227，大于 2 的 7 次方 128，小于 2 的 8 次方 256，所以每个数字可以使用 8bit 即 1Byte 来保存，占据总空间为 1Byte*6 + 1Byte=7Byte

在此基础上，我们将差值数组按照密集度划分为[73,227]和[2,30,11,29]，其中[73,227]中最大值 227 介于 2 的 7 次方和 2 的 8 次方之间，所以用 8bit=1Byte 作为切割分段，[2,30,11,29]中最大数 30 介于 2 的 4 次方和 2 的 5 次方之间，所以用 5bit 作为切割分段。

数组[73,227]占据总空间为 8bit✖2 个=16bit=2Byte

数组[2,30,11,29]占据总空间为 5bit✖4 个=20bit=3Byte

为什么 20bit=3Byte 呢？因为 8bit=1Byte，小于 8bit 也会占据 1 个字节空间，所以 17bit 到 24bit 均为 3Byte

所以，最终占据总空间=1+2+1+3=7Byte

疑问一：既然原数组[73，300，302，332，343，372]要按照密集度拆分为[73,227]和[2,30,11,29]两个数组，那为什么不继续往下拆分，直接拆分到每个数字是一个数组，这样使用 bit 记录时占据总空间会更少？

答：如果继续拆分数组，空间确实会使用更少，但是，之前我们提到搜索引擎速度快的方式有两种：高效的压缩算法和快速的编码解码速度，单个数字存储确实压缩了空间，但是我们无法再通过解码的方式将源数据还原

疑问二：为什么源数据使用差值记录占据 6Byte，拆分数组后占据 7Byte，拆分后占据空间不变，有时候甚至会变大，为什么？

答：数据量小的情况下确实会出现该情况，因为我们需要拆分数组并记录拆分数组的长度（如上面示例中的 8bit 和 5bit），在原数据存储空间基础上还要存储拆分长度，所以数据量小的情况下会出现比直接存储占据空间大的情况。但是不管是搜索引擎还是 Elasticsearch 更多处理的是海量数据，数据量越多，差值数组拆分的方式节省空间越明显

2.2 RBM

我们已经了解了 FOR 压缩算法，算法核心是将 PostingList 按照差值密集度转化成两个差值数组。在这里我们要考虑一种情况就是：在大数据中，10 亿条数据分词 500 万个，如果分词“小米”所在 PostList 比较分散且差值很大，此时使用 FOR 算法效果就会大打折扣。所以稀疏的数组，不适合使用 FOR 算法

在这里我们以[1000，62101，131385，132052，191173，196658]为例，如果按照 FOR 算法，转化成的差值数组为[1000，61101，69284，667，59121，5485]密集度很低。我们采用 RBM 算法

源数据 PostingList 是由 int 类型组成的数组，int 类型=4Byte=32bit，最大值=2 的 32 次方-1=4294967295≈43 亿。当数据较大且稀疏时，我们将 32bit 拆分为 16bit 和 16bit，16bit 最大值=65535，前 16bit 存放商，后 16bit 存放余数，所以商和余数都不会超过 65535.我们将源数组的值除以 65536，得到的商和余数分别存放在前 16bit 和后 16bit。

以数字 196658 为例，转化为 2 进制，前 16 位=3，后 16 位=50

得到的结果以 K-V 存放。Key 最大值为 16bit，所以以 short[]数组存放，Value 以 Container 存放。

由于源数组为有序数组，所以按照高低 16 位转化后，商和余数都是从小到大排列

通过看 Container 源码，我们可以看到 Container 有 3 种：ArrayContainer、BitmapContainer、RunContainer。

1. ArrayContainer 本质为集合，所以随着数组中数量越多，占用空间越多，呈正向增长。

当数组种数量为 4096 时，占据总空间=4096 个✖16bit(即 2Byte)➗1024=8KB

当数组种数量为 65536 时，占据总空间=65536 个✖16bit(即 2Byte)➗1024=128KB

1. BitmapContainer 位图，核心就是将原有存储数值转化成该数值在哪个位置上存在

由于余数最大值为 65535，所以我们需要 65536 位位图，数值是多少，在位图上对应的位置就是多少。数值等于 4096，则位图上 4096 位值为 1；数值等于 65535，则位图上 65535 位值为 1。每个位置上的数都占用 8KB 空间（8KB=65536bit）

• RunContainer 用法相对狭隘，这种类型是 Lucene 5 之后新增的类型，主要应用在连续数字的存储商，比如倒排表中存储的数组为 [1,2,3…100W] 这样的连续数组，如果使用 RunContainer，只需存储开头和结尾两个数字：1 和 100W，即占用 8 个字节。这种存储方式的优缺点都很明显，它严重收到数字连续性的影响，连续的数字越多，它存储的效率就越高

• 如果数组是如下形式 [1,2,3,4,5,100,101,102,999,1000,1001] 就会被拆分为三段：[1,5],[100,102],[999,1001]

至于每次存储采用什么容器，需要进行一下判定，比如 ArrayContainer，当存储的元素少于 4096 个时，他会比 BitmapContainer 占用更少空间，而当大于 4096 个元素时，采用 ArrayContainer 所需要的空间就会大于 8kb，那么采用 BitmapContainer 就会占用更少空间

3 总结

ES 在处理海量数据时通过其独到的结构和压缩算法，将索引效率尽可能的提升。虽然在实际业务处理中我们极少遇到海量数据处理的情况，但是通过了解 ES 的原理，能够帮我们开阔下视野，了解数字之美，算法之美。