作者：京东物流 李洪吉
作为搜索引擎的一部分，ES自然具有速度快、结果准确、结果丰富等特点，那么ES是如何达到“搜索引擎”级别的查询效率呢？首先是索引，其次是压缩算法，接下来我们就一起了解下ES的索引结构和压缩算法
1 结构
1.1 Mysql
其中表columns_priv对应了3个文件：columns_priv.frm、columns_priv.MYD、columns_priv.MYI。
1.2 Elasticsearch
cfs、cfe 在segment还很小的时候，将segment的所有文件都存在在cfs中，在cfs逐渐变大时，大小超过shard的10%，则会拆分为其他文件，如tim、dvd、fdt等文件
1.3 存储结构
词项字典包含了index field的所有经过处理之后的词项数据，最终存储在.tim文件中
1.4 结构对比
id是int类型的有序主键，分词“小米”在数组Posting List中100万int类型数字总长度=100万✖每个int占4字节=400万Byte≈4MB。1个分词占4MB空间,假如10亿条数据有500万个分词，总空间=4MB✖500万=2千万MB，磁盘空间直接爆炸
2 算法
ES中倒排索引的压缩算法主要有FOR算法(Frame Of Reference和RBM算法(RoaringBitMap
2.1 FOR
数组[73,227]占据总空间为8bit✖2个=16bit=2Byte
为什么20bit=3Byte呢？因为8bit=1Byte，小于8bit也会占据1个字节空间，所以17bit到24bit均为3Byte
答：如果继续拆分数组，空间确实会使用更少，但是，之前我们提到搜索引擎速度快的方式有两种：高效的压缩算法和快速的编码解码速度，单个数字存储确实压缩了空间，但是我们无法再通过解码的方式将源数据还原
答：数据量小的情况下确实会出现该情况，因为我们需要拆分数组并记录拆分数组的长度（如上面示例中的8bit和5bit），在原数据存储空间基础上还要存储拆分长度，所以数据量小的情况下会出现比直接存储占据空间大的情况。但是不管是搜索引擎还是Elasticsearch更多处理的是海量数据，数据量越多，差值数组拆分的方式节省空间越明显
2.2 RBM
源数据PostingList是由int类型组成的数组，int类型=4Byte=32bit，最大值=2的32次方-1=4294967295≈43亿。当数据较大且稀疏时，我们将32bit拆分为16bit和16bit，16bit最大值=65535，前16bit存放商，后16bit存放余数，所以商和余数都不会超过65535.我们将源数组的值除以65536，得到的商和余数分别存放在前16bit和后16bit。
由于源数组为有序数组，所以按照高低16位转化后，商和余数都是从小到大排列
- ArrayContainer本质为集合，所以随着数组中数量越多，占用空间越多，呈正向增长。
当数组种数量为65536时，占据总空间=65536个✖16bit(即2Byte➗1024=128KB
- BitmapContainer位图，核心就是将原有存储数值转化成该数值在哪个位置上存在
- 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的原理，能够帮我们开阔下视野，了解数字之美，算法之美。