转载本文请联系程序员李小兵公众号。熟悉MySQL的同学一定知道，MySQL对复杂条件查询的支持不是很好。MySQL最多使用条件涉及的一个索引进行过滤，剩下的条件只能在行遍历过程中在内存中进行过滤。对这个过程不熟悉的同学可以先看看?。上述处理复杂条件查询的方法只能通过一个索引进行过滤，因此需要大量的I/O操作来读取行数据，并且消耗CPU进行内存过滤，导致查询性能下降。由于其特性，ElasticSearch非常适合复杂的条件查询。是业界主流的复杂条件查询场景解决方案，广泛应用于订单、日志查询等场景。下面我们就来看看为什么ElasticSearch适用于复杂的条件查询。ElasticSearch简介Elasticsearch是一个开源的实时分布式搜索分析引擎，内部使用Lucene进行索引和搜索。提供“准实时搜索”能力，可动态扩展集群规模，弹性扩容。Elasticsearch使用Lucene作为其全文搜索引擎来处理纯文本数据，但Lucene只是一个提供索引和执行搜索等接口的库，并不包括分布式服务。这些正是Elasticsearch所做的。接下来介绍一下ElasticSearch的相关概念。为了方便初学者理解，我们先粗略对应一下ElasticSearch和MySQL中的概念。不过，在具体细节上，两者还是有不少差异。如果你对ElasticSearch有深入的了解，你就能把两者区别清楚，不能强行比较和划等号。ElasticSearch中的索引Index类似于MySQL中的数据库Database；ElasticSearch中的类型Type类似于MySQL中的表Table；需要注意的是，这个概念在7.x版本中被完全删除，这个概念和Table有很大区别；ElasticSearch中的文档类似于MySQL中的数据行Row。每个文档由多个字段Filed组成，类似于MySQL中的Column；ElasticSearch中的Mapping是索引字段及其在索引库中的数据类型定义的，类似于关系数据库中的表结构Schema；ElasticSearch使用自己的领域语言QueryDSL进行增删改查，而MySQL使用SQL语言进行申诉操作。ElasticSearch还有一系列关于它的分布式特性的概念，这里我们暂时不介绍，等到后面了解它的分布式特性的时候再介绍。倒排索引MySQL有B+树索引，而ElasticSearch是倒排索引（InvertedIndex），利用倒排索引实现比MySQL更快的过滤和复杂的条件查询。此外，全文搜索功能也依赖倒排索引来实现。接下来，我们来看看什么是倒排索引。根据维基百科的描述，倒排索引是一种数据库索引结构，用于存储文档内容与文档位置之间的映射关系。但是只看定义，我有点困惑。这不是类似于MySQL的非主键索引吗？为什么叫“倒置”呢？这个我还在想办法，可能要等到后面了解了它的具体实现。理解。我们还是以图书检索为例。假设有如下数据，每一行是一个Document，每个Document由id、ISBNnumber、authorname和rating组成。根据ISBN和Author为以上数据建立的倒排索引如下。倒排索引是为每个字段单独建立的，相互独立。有两个专门术语，indexTerm和postinglistPostingList。该字段的值为Term，如N0007，Term对应的文档ID列表为PostingList，对应图中红色部分。通常，术语按顺序排序。例如，作者姓名按字母顺序排序。排序后，我们在查找某个term时，不需要从头遍历，而是使用二分查找。一系列排序好的Term构成索引表TermDictionary。但是，TermDictionary通常太大而无法完全存储在内存中。这是为了更快的查询，需要为它创建一个索引，即TermIndex。ElasticSearch使用Burst-Trie结构来实现TermIndex，它是前缀树Trie的变体。主要是对后缀进行压缩，降低Trie的高度，以获得更好的查询性能。TermIndex不需要像MySQL索引那样包含所有的term，而是包含这些term的前缀。类似于词典的查询目录，可以快速定位到TermDictionary中的某个位置，然后从这个位置向后查询。综上，Alice、Alf、Arlan、Bob、Tom等词的倒排索引如下。绿色部分是TermIndex，蓝色部分是TermDictionary，红色部分是PostingList。一般来说，TermIndex都是缓存在内存中的。查询时，先用它快速定位到TermDictionary对应的大概范围，然后进行磁盘读取找到对应的Term，大大减少了磁盘I/O次数。联合索引查询了解了ElasticSearch的倒排索引后，我们来看看它是如何处理复杂的联合索引查询的。例如，在上面的图书示例中，我们需要查询评分等于2.2且作者姓名为Tom的图书。理论上我们只需要根据Score和Author字段的倒排索引进行查询，得到对应的PostingList，然后合并即可。这里又要吐槽一下MySQL了。它不支持此合并操作。它只能根据一个字段的索引进行查询，然后根据另一个字段的条件进行内存过滤。对了，MySQL的join功能也很弱。有兴趣的同学可以看看这篇文章，ElasticSearch支持使用SkipList和Bitset来合并数据集。使用SkipList结构同时遍历Score和Author查询到的PostingList，利用其SkipList结构进行跳过比较，得到一个集合。使用Bitset结构为Score和Author查询的PostingList的值计算各自的Bitsets，然后进行AND运算。跳表合并策略ElasticSearch在存储PostingList数据时，保存对应的多级跳表结构响应数据，这也体现了其以空间换时间的基本思想。这里先介绍一下跳表的基本概念，跳表其实就是一个可以进行二分查找的有序链表。跳表是在原来有序链表的基础上增加多级索引，通过索引实现快速查找。先在最高层索引上查找比当前查找元素小的最后一个位置，然后跳转到次高索引继续查找，直到最底层。这样查询速度就加快了。例如按Score查出的PostingList为[2,3,4,5,7,9,10,11]，按Author查出的结果为[3,8,9,12,13].跳表结构如下图所示。具体的合并过程是先选择最短的posting列表，即Author的结果集，从最小的id开始，作为当前的最大值。然后在剩余的posting列表中依次查找大于等于该值的位置。比如在上面的结果集中，先在Score结果集中搜索3。找到后，说明3是两者的合元素之一；然后重新开始一轮，在Author结果集中选择3的下一个值8，去Score结果集Query8发现大于等于8的最小值是9，所以不可能有共同点8的值，然后去Author结果集找9，发现大于等于9的最小值是12，于是去Score结果集找一个大于等于12的值，并且发现它不存在；最后两者的结合只有[3]。在查询过程中，每个postinglist可以根据当前id通过skiplist快速跳过不一致的id值，加速整个合并交集的过程。ElasticSearch还使用FrameOfReference对长发布列表进行压缩编码，从而减少磁盘使用和索引大小。具体存储结构的实现我们后面再说。Bitset合并策略ElasticSearch不仅在读取数据盘时使用skipList进行合并操作，还会将一些查询条件对应的结果集posting列表缓存在内存中，也就是所谓的FilterCache，以供后续重用。为了减少内存缓存消耗的内存空间，ElasticSearch没有使用简单的数组和bitsets来存储postinglist，而是使用了压缩效率更高的RoaringBitmap。我们可以先说说为什么不用简单的数组或者bitset数据结构。比如下面一道比较常见的面试题：给定区间[0,2^32-1]中的一组40亿个唯一整数，如何快速判断某个数是否在该集合中？如果我们要用unsignedlong数组来存储的话，需要消耗40亿*32位=160Byte，也就是大概16000MB。如果要使用位图Bitset来存储，即某个数在原集合中，将其对应位图中的位设置为1，否则保持为0。这样只需要消耗2^32位=512MB,仅为原来的3.2%左右。但是Bitset也有它的缺陷，就是存储稀疏的问题。比如上面的set不是40亿，而是只有2、3个，那么Bitset中只有几个位是1，其他位都是0，但还是占了512MB。而RoaringBitmap就是为了解决稀疏存储的问题。下图是RoaringBitmap的基本原理示意图。首先计算32位无符号整数和65536的除数和余数，如上图所示。其含义是指将32位无符号整数按照高16位进行分桶，即最多可能有2^16=65536个桶，术语称为容器。存储数据时，根据数据的高16位找到容器（找不到就新建一个），然后将低16位放入容器中。换句话说，一个RoaringBitmap是许多容器的集合。那么容器中具体的存储结构要根据其中存储的数据的基数来确定。当基数小于2^12，即4096时，使用unsignedshort类型的有序数组存储，最大占用空间8KB。当基数大于4096时，存储在大小为2^16的普通bitset中，固定消耗8KB。当然，有时会对bitset进行游程编码（RLE）压缩，进一步减少占用的空间。ElasticSearch使用RoaringBitmap缓存不同条件查询到的postinglist，然后进行AND运算计算出最终的结果集。后记至此，我们也明白了为什么ElasticSearch比MySQL更适合复杂条件查询，但是有利也有弊，因为在为查询做了这么多准备后，ElasticSearch的插入速度会比MySQL慢，而且数据将存储在ES之后不会立即检索。
