Elasticsearch利用Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件过滤的支持非常好，比如年龄在18-30之间，性别为女性等组合查询。倒排索引很多地方都介绍过，但是为什么比关系型数据库的b-tree索引快呢？为什么更快？一般来说，b-tree索引是一种为写入而优化的索引结构。当我们不需要支持快速更新时，我们可以使用预排序等方式来换取更小的存储空间、更快的检索速度等好处，代价是更新速度慢。更进一步，我们还需要看看Lucene的倒排索引是如何构成的。这里有几个概念。我们来看一个实际的例子，假设有以下数据：docidagegender118female220female318male这里每一行都是一个文档。每个文档都有一个docid。那么为这些文档创建的倒排索引就是：可以看到年龄和性别，倒排索引是perfield的，一个field有自己的倒排索引。18,20这些称为术语，[1,3]是发布列表。postinglist是一个int数组，里面存放了所有匹配某个term的文档id。那么术语词典和术语索引是什么？假设我们有很多术语，例如：Carla、Sara、Elin、Ada、Patty、Kate、Selena。如果按照这个顺序排列，找到具体的term肯定很慢，因为term没有排序，需要全部过滤才能找到具体的term。排序后变为：Ada、Carla、Elin、Kate、Patty、Sara、Selena。这样，我们可以使用二分查找比完全遍历更快地找到目标词。这是术语词典。使用术语字典，可以通过logN磁盘查找找到目标。但是随机磁盘读取操作仍然非常昂贵（随机访问大约需要10ms）。所以需要尽量少在内存中缓存一些数据来读取磁盘。但是整个术语词典本身太大，无法完全存储在内存中。所以有一个术语索引。术语索引有点像字典的大章节表。例如：以A…………开头的术语。第Xxx页以C开头的术语…………。第Xxx页以E开头的术语…………。如果xxx页的所有词条都是英文字符，这可能是词条索引真的由26个英文字符组成。但实际情况是term不一定全是英文字符，term可以是任意字节数组。而且，26个英文字符并不一定意味着每个字符都有相同的术语。例如，可能没有以字符x开头的术语，而以s开头的术语有很多。实际的术语索引是一个特里树：一个例子是一个包含“A”、“to”、“tea”、“ted”、“ten”、“i”、“in”和“inn”的特里树。这棵树不包含所有术语，它包含一些术语前缀。术语索引可以用来快速定位到术语词典中的某个偏移量，然后从这个位置开始依次查找。再加上一些压缩技术（搜索LuceneFiniteStateTransducers），termindex的大小可以只有所有term大小的十分之几，从而可以将整个termindex缓存在内存中。总的来说，就是这个效果。现在我们可以回答“为什么Elasticsearch/Lucene检索可以比mysql快。mysql只有term字典层，以b-tree排序的形式存储在磁盘上。检索一个term需要多次随机访问磁盘操作。并且Lucene在termdictionary的基础上增加了termindex来加快查找速度，termindex以树的形式缓存在内存中，从termindex找到对应termdictionary的block位置后，转到磁盘查找term，大大减少了对磁盘的随机访问次数，另外两点值得一提的是：termindex在内存中以FST（finitestatetransducer）的形式存储，其特点是节省内存.Term字典分为以块的形式存储，一个块用一个共同的前缀压缩，比如所有的单词都是以Ab开头的，Ab可以省略。这样Term字典就可以省去磁盘空间大于b-tree。如何结合索引查询？所以给定查询过滤条件age=18，过程就是从termindex中找到18在termdictionary中的大概位置，然后从termdictionary中精确找到term18，然后得到一个postinglist或者一个A指向发布列表位置的指针。那么查询gender=female的过程类似。最后，age=18ANDgender=female就是将两个发帖列表用一个“AND”合并。这种理论上的AND操作并不容易。对于mysql来说，如果对age和gender字段都建立索引，那么查询的时候只会选择其中最有选择性的使用，还有一个条件就是在遍历行的过程中在内存中计算后过滤掉。那么如何联合使用这两个指标呢？有两种方式：使用跳表数据结构。同时遍历性别和年龄的发帖列表，相互跳过；使用bitset数据结构计算性别和年龄这两个filter的bitset，对这两个bitset进行AN运算。PostgreSQL从8.4版本开始支持通过bitmap来联合使用两个索引，这是通过使用bitset数据结构来实现的。当然，一些商业关系型数据库也支持类似的联合索引功能。Elasticsearch支持以上两种组合索引方式。如果查询过滤器缓存在内存中（以bitset的形式），那么合并就是两个bitset的AND。如果queryfilter没有被缓存，使用skiplist的方式遍历这两个on-diskpostinglists。使用SkipList合并以上三个发布列表。我们现在需要将它们与AND的关系结合起来，以获得发布列表的交集。先选择最短的postinglist，然后从小到大遍历。在遍历过程中可以跳过一些元素。比如我们遍历到绿色13的时候，可以跳过蓝色3，因为3比13小。整个过程如下Next->2Advance(2)->13Advance(13)->13Alreadyon13Advance(13)->13MATCH!!!Next->17Advance(17)->22Advance(22)->98Advance(98)->98Advance(98)->98MATCH!!!最后的交集是[13,98]，所需时间比遍历三个postinglist要快很多。但前提是每个列表都需要指明Advance操作，快速移动指向的位置。什么样的榜单可以这样越级前进？Skiplist：概念上，对于一个很长的postinglist，比如：[1,3,13,101,105,108,255,256,257]，我们可以把这个list分成三块：[1,3,13][101,105,108][255,256,257]那么第二层的跳表可以构造为：[1,101,255]1,101,255分别指向它们对应的块。这样，跨块的移动可以快速指向位置。Lucene自然会再次压缩这个块。这种压缩方法称为参考帧编码。示例如下：考虑频繁出现的术语（所谓的低基数值），例如性别中的男性或女性。如果有100万份文件，发帖列表中就有50万个int值，性别是男。使用参考帧编码进行压缩可以大大减少磁盘使用量。此优化对于减小索引大小非常重要。当然mysql的b-tree中也有类似的postinglist，并没有采用这种方式进行压缩。因为这个FrameofReference的编码是有解压成本的。使用skiplist，除了跳过遍历的开销之外，还跳过了解压这些压缩块的过程，从而节省了cpu。使用bitset合并Bitset是一个很直观的数据结构，对应postinglist如：[1,3,4,7,10]对应bitset为：[1,0,1,1,0,0,1,0,0,1]每个文档根据其中一位对应的文档id进行排序。Bitset本身具有压缩的特性，一个字节可以表示8个文档。所以100万份文档只需要125,000字节。但考虑到可能有数十亿的文档，将bitsets保存在内存中仍然是一种奢侈。对于每个过滤器，都会消耗一个位集。比如缓存age=18，就是一个bitset，如果18<=age<25，另一个filter需要缓存一个bitset。所以秘诀就在于需要一个数据结构：可以压缩几亿位来表示对应的文档是否匹配过滤器；这个压缩后的bitset仍然可以快速执行AND和OR的逻辑运算。Lucene使用的数据结构称为RoaringBitmap。压缩的思路其实很简单。不要存储100个零，而是使用100位。最好存储一次0，然后声明这个0重复100次。这两种结合使用索引的方式各有用途。Elasticsearch对其性能进行了详细比较（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为参考帧编码非常高效，将简单相等条件过滤到纯内存位集中不如需要访问磁盘的跳跃列表快。如何减少文件数量？压缩和存储时间序列的一种常见方法是将多个数据点组合成一行。Opentsdb支持海量数据的技巧之一就是周期性地将多行数据合并为一行。这个过程称为压缩。类似vivdcortext存储到mysql时，也是将一分钟内的很多数据点合并存储到mysql的一行中，减少行数。这个过程的一个例子如下：12:05:001012:05:011512:05:021412:05:0316合并后变成：可以看到行变成了列。每列可以表示一分钟中一秒钟的数据。Elasticsearch有一个特性可以达到类似的优化效果，那就是NestedDocument。我们可以将一段时间内的很多数据点打包存储到一个父文档中，成为它嵌套的子文档。示例如下：{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}可以打包成：{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}]}所以将数据点公共维度字段向上移动到父文档，而不是重复存储在每个子文档中，从而减少索引的大小。在存储的时候，无论是父文档还是子文档，对于Lucene来说都是一个文档，都会有一个文档Id。但是对于嵌套文档，可以保存子文档和父文档的文档id是连续的，父文档永远是最后一个。有了这样的可排序性作为保证，就有了所有父文档的postinglist来跟踪所有的父子关系。在父文档ID和子文档ID之间进行转换也很容易。父子关系也可以理解为一个过滤器，所以在搜索查询时，无非就是与另一个过滤器进行AND运算。我们之前已经看到Elasticsearch可以非常高效地处理多个过滤器并充分利用底层索引。使用嵌套文档后，term的发布列表只需要保存父文档的docid，可以比保存所有数据点的docid少很多。如果我们可以在一个父文档中容纳50个嵌套文档，则发布列表可以是之前的1/50。
