Elasticsearch黑鸟教程18：Elasticsearch的压缩技术系列介绍
Elasticsearch的核心数据结构是倒排索引，其分为三个部分，如下所示：
更多介绍，请移步：《Elasticsearch入门教程13：倒排索引原理介绍》
为了查询的高效，Elasticsearch对于Term Index和Posting List两部分，分别采用了不同的压缩技巧。
1、Term Index的压缩
Elasticsearch用FST（Finite State Transducer）压缩Term Index。
FST有两个优点：（1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；（2）查询速度快。O(len(str))的查询时间复杂度。
下面简单描述下FST的构造过程。我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（注：必须已排序）
（1）插入“cat”
插入cat，每个字母形成一条边，其中t边指向终点。
（2）插入“deep”
与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。
（3）插入“do”
与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。
（4）插入“dog”
与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。
（5）插入“dogs”
与前一个单词“dog”进行最大前缀匹配，发现是dog，则在g后增加新边s，s边指向终点。
最终，我们得到了如上一个有向无环图。利用该结构可以很方便的进行查询，如给定一个term “dog”，我们可以通过上述结构很方便的查询存不存在，甚至我们在构建过程中可以将单词与某一数字、单词进行关联，从而实现key-value的映射。
2、Posting List压缩技巧和存储技巧
很多情况下，每个posting list都会有至少百万个文档id，Elasticsearch是如何有效的对这些文档id压缩的呢？
其主要的思想是：增量编码压缩，将大数变小数，按字节存储
首先，Elasticsearch要求posting list是有序的，这样做的一个好处是方便压缩，看下面这个图：
备注：
227的二进制是1110 0011，30的二进制是0001 1110。为了保证数据不丢失，则位数至少要能存储最大的数字，自然前者用8位，后者用5位
上面说完了posting list压缩技巧，下面再说一下它的存储技巧吧。
存储posting list的数据结构是Roaring bitmaps。说到Roaring bitmaps，就必须先从bitmap说起。Bitmap是一种数据结构，假设有某个posting list：
[1,3,4,7,10]对应的bitmap就是：
[1,0,1,1,0,0,1,0,0,1]非常直观，用0/1表示某个值是否存在，比如10这个值就对应第10位，对应的bit值是1，这样用一个字节就可以代表8个文档id，旧版本(5.0之前)的Lucene就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有1亿个文档，那么需要12.5MB的存储空间，这仅仅是对应一个索引字段，实际上我们往往会有很多个索引字段，会造成存储空间的极大负担。于是有人想出了Roaring bitmaps这样更高效的数据结构。
Bitmap的缺点是存储空间随着文档个数线性增长，Roaring bitmaps需要打破这个魔咒，它将posting list按照65535为界限分块，比如第一块所包含的文档id范围在0~65535之间，第二块的id范围是65536~131071，以此类推。Roaring bitmaps用<商，余数>的组合表示每一组id，这样每组里的id范围都在0~65535内了，既然每组id不会变得无限大，那么我们就可以通过最有效的方式对这里的id存储。
如上所述，定会有人问：为什么是以65535为界限? 因为 65535 是一个经典值，因为它是2^16-1，正好是用2个字节能表示的最大数，一个short的存储单位。
另外，要注意到上图里的最后一行：If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value。其含义是指，如果是大块数据，用bitset存储，小块数据，2个字节即可。
那为什么用 4096 来区分大块还是小块呢？因为固定每块需要内存 65535 位，这种情况下，short 最多存 4096 个数，大于4096 只能用 bitmap，小于 4096 没必要做转换，直接 short 就可以了。