这段时间我在维护产品的搜索功能。每次在管理控制台看到Elasticsearch如此高效的查询效率，我都很好奇他是怎么做到的。图片来自Pexels这比我使用MySQL通过主键进行本地查询还要快。为此，我搜索了相关资料：网上对这类问题的回答很多，大致意思如下：ES是一个基于Lucene的全文搜索引擎。它将对数据进行分段并保存索引。擅长管理大量的索引数据。据说我不擅长频繁更新数据和相关查询。不是很透彻，也没有相关的原理分析；但是既然重复提到了索引，那我们就从索引的角度比较一下两者的区别吧。MySQL索引以MySQL开头。索引这个词大家一定不陌生。它通常存在于一些查询场景中，是典型的以空间换时间的情况。以下内容以InnoDB引擎为例。常见的数据结构假设我们自己设计MySQL的索引，我们会有哪些选择呢？①哈希表首先我们应该想到哈希表，它是一种非常通用且高效的查询和写入数据结构，对应在Java中是HashMap。这个数据结构应该不需要过多介绍。它的写入效率非常高O(1)。比如我们要查询id=3的数据，就需要对3进行哈希运算，然后找到对应的位置即可。但是如果我们要查询1≤id≤6这样的区间数据，哈希表就不能很好的满足。因为是无序的，所以我们要遍历所有的数据才能知道哪些数据属于这个区间。②有序数组有序数组的查询效率也很高。当我们要查询id=4的数据时，只需要使用二分查找就可以高效定位数据O(logn)。同时，由于数据也是有序的，自然可以支持区间查询；所以看起来有序数组适合索引？当然不是，它还有一个大问题；假设我们插入id=2.5的数据，那么后面的所有数据都必须同时移动一位，写入效率会变得很低。③平衡二叉树既然有序数组的写入效率不高，再来看看写入效率高，很容易想到二叉树。这里以平衡二叉树为例：由于平衡二叉树的特点：左节点小于父节点，右节点大于父节点。那么假设我们要查询id=11的数据，只需要查询10→12→11就可以最终找到数据，时间复杂度是O(logn)，写入数据时也是O(logn)。但是，它仍然不能很好地支持区间搜索。假设我们要查询5≤id≤20的数据，需要先查询10个节点的左子树，再查询10个节点的右子树，最后才能查询到所有数据。这样的查询效率不高。④跳表跳表可能不像上面提到的哈希表、有序数组、二叉树那么常见，但实际上Redis中的排序集合就是通过跳表来实现的。这里简单介绍下跳表实现的数据结构的优点。我们都知道即使是查询一个有序链表也是效率不高的，因为它不能使用数组下标进行二分查找，所以时间复杂度是o(n)。但是我们也可以巧妙的优化链表，变相实现二分查找，如下图：我们可以对底层数据提取一级索引和二级索引，我们可以提取N级索引根据数据量。我们在查询的时候，可以利用这里的索引，变相的实现二分查找。假设现在要查询id=13的数据，只需要遍历1→7→10→13这四个节点就可以查询到数据了。数量越大，效率提升越明显。同时也支持区间查询。类似于刚才查询单个节点，只需要查询起始节点，然后向后遍历（链表是有序的）到目标节点，就可以查询整个范围的数据了。同时，由于我们不会在索引中存储真正的数据，而只存储一个指针，因此底层存储数据的链表占用的空间可以忽略不计。平衡二叉树的优化但其实MySQL中的InnoDB并没有使用跳表，而是使用了一种叫做B+树的数据结构。这种数据结构不像二叉树，大学老师常说的二叉树是一种基础数据结构，因为这种数据结构是实际工程中的基础数据结构根据需求场景演化而来的。比如这里的B+树，可以认为是从平衡二叉树演化而来的。刚才我们提到二叉树的区间查询效率不高，我们可以优化这一点：在原来的二叉树基础上优化后：所有的非叶子都不存储数据，而是作为索引叶节点，所有数据都存储在叶节点中。这样所有叶子节点的数据都是有序存储的，可以很好的支持区间查询。只需要先查询起始节点的位置，然后在叶子节点中向后遍历即可。当数据量很大的时候，很明显索引文件无法存放在内存中。速度虽然快，但资源消耗也不小；所以MySQL会将索引文件直接存储在磁盘上。这和后面提到的Elasticsearch索引略有不同。由于索引是存储在磁盘上的，我们需要尽可能的减少与磁盘的IO（磁盘IO的效率和内存不在一个数量级）。从上图可以看出，我们查询一条数据至少需要进行4次IO。显然，IO的数量与树的高度密切相关。树的高度越低，IO数量越少，性能越好。好的。那么我们怎样才能降低树的高度呢？我们可以尝试把二叉树改成三叉树，这样树的高度会下降很多，这样查询数据时的IO次数自然会减少，查询效率也会提高很多。这其实就是B+树的由来。使用索引的一些建议，其实可以通过上图中B+树的理解，优化日常工作的一些小细节；后面写入的数据id可能比前面写入的要小，所以在维护B+树索引的时候可能需要移动写入的数据。如果数据是增量写入的，则不会考虑这个因素，每次只需要顺序写入即可。这就是为什么我们要求数据库的主键尽可能的增加趋势。最合理的做法是在不考虑表的情况下增加主键。整体思路和跳表类似，只是针对使用场景做了相关调整（比如所有数据都存储在叶子节点）。ESIndexMySQL说完了，现在我们来看看Elasticsearch是如何使用索引的。正向索引使用了ES中称为倒排索引的数据结构；在正式讲倒排指数之前，我们先来说说相反的正向指数。上图就是一个例子。我们通过doc_id查询具体对象的方式，叫做usingpositiveindex。其实也可以理解为哈希表。本质就是通过key找到value。比如通过doc_id=4，可以快速查询到数据name=jettywang,age=20。倒排索引，如果我要查询名字中包含li的数据呢？如何高效查询？仅仅通过上面提到的正向索引显然是没有用的，我只能依次遍历所有的数据。然后判断名字中是否包含li；这是非常低效的。但是如果我们重建一个索引结构：当我们要查询name中包含li的数据时，只需要通过这个索引结构查询PostingList中包含的数据，再通过mapping查询到最终的数据。这个索引结构其实就是一个倒排索引。TermDictionary但是如何在这个索引结构中高效查询li呢？结合我们之前的经验，只要把Term有序的排列起来，我们就可以使用二叉树搜索树数据结构来查询o(logn)下的数据。将一段文本拆分成单个词条的过程，其实就是我们常说的分词。将所有术语合并在一起就是一个术语词典，也可以称为单词词典。英语分词比较简单。您只需要用空格和标点符号分隔文本即可拆分单词。中文比较复杂，但也有很多开源工具支持（由于不是本文重点，对分词感兴趣的可以自行搜索）。当我们的文本量很大的时候，分词后的term会很多。这样的倒排索引数据结构如果放在内存中肯定不够用。但是如果像MySQL一样存储在磁盘上，效率就没有那么高了。TermIndex所以我们可以选择一个折衷的方法。由于我们不能把整个TermDictionary都放在内存中，所以我们可以为TermDictionary建立一个索引，然后放到内存中。这样就可以高效的查询TermDictionary，最终通过TermDictionary查询PostingList。与MySQL中的B+树相比，也会减少几次磁盘IO。我们可以用这样一棵Trie树，也就是我们常说的字典树，来存储这个TermIndex。如果我们要查找一个以j开头的Term，第一步就是通过TermIndex在内存中查询以j开头的Term在TermDictionary文件中的位置（这个位置可以是一个文件指针，也可以是一个区间范围）。然后取出这个位置区间内的所有term，由于已经排好序，可以通过二分查找快速定位到具体位置；这样就可以查询发帖列表了。最后，可以通过PostingList中的位置信息从原始文件中检索到目标数据。更多优化当然，Elasticsearch也做了很多有针对性的优化。当我们检索两个字段时，我们可以使用Bitmap进行优化。比如现在我们要查询name=li，age=18的数据。这时候我们就需要通过这两个字段来获取各自的结果PostingList。最简单的方法就是分别遍历两个集合，取出重复的数据，但是这样显然效率很低。这时候我们可以使用Bitmap的方式进行存储（节省存储空间），同时使用先天位和计算得到结果。[1,3,5]?10101[1,2,4,5]?11011可以将两个二进制数组相加得到结果：10001?[1,5]最后发布列表是[1,5]，这样的效率自然要高很多。对于相同的查询需求，MySQL中并没有做特别的优化。它只是先过滤掉数据量小的数据，然后再过滤第二个字段。效率自然没有ES高。当然，PostingList在最新版本的ES中也会被压缩。具体的压缩规则可以参考官方文档，这里不再介绍。总结最后总结一下：从以上内容可以看出，无论一个产品多么复杂，最终都是由基础数据结构组成的，只会针对不同的应用场景进行优化。只有有了新的技术或中间件，才能快速上手，甚至自己也能知道优化的方向。最后，画一个馅饼。我会尝试基于ES的倒排索引思想，搭建一个独立的搜索引擎。只有自己写，才能加深理解。作者：crossoverJie责任编辑：陶佳龙来源：转载自公众号crossoverJie（ID：crossoverJie）
