前言

这段时间在保护产品的搜寻性能，每次在治理台看到 elasticsearch 这么高效的查问效率我都很好奇他是如何做到的。

这甚至比在我本地应用 MySQL 通过主键的查问速度还快。

为此我搜寻了相干材料：

这类问题网上很多答案，大略意思呢如下：

• ES 是基于 Lucene 的全文检索引擎，它会对数据进行分词后保留索引，善于治理大量的索引数据，绝对于 MySQL 来说不善于常常更新数据及关联查问。

说的不是很透彻，没有解析相干的原理；不过既然重复提到了索引，那咱们就从索引的角度来比照下两者的差别。

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 中的 sort set 就采纳了跳表实现。

这里咱们简略介绍下跳表实现的数据结构有何劣势。

咱们都晓得即使是对一个 有序链表 进行查问效率也不高，因为它不能应用数组下标进行二分查找，所以工夫复杂度是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+ 树 索引时便有可能须要挪动曾经写好数据。

如果是依照递增写入数据时则不会有这个思考，每次只须要顺次写入即可。

所以咱们才会要求数据库主键尽量是趋势递增的，不思考分表的状况时最正当的就是自增主键。

整体来看思路和跳表相似，只是针对应用场景做了相干的调整（比方数据全副存储于叶子节点）。

ES 索引

MySQL 聊完了，当初来看看 Elasticsearch 是如何来应用索引的。

正排索引

在 ES 中采纳的是一种名叫 倒排索引 的数据结构；在正式讲倒排索引之前先来聊聊和他相同的 正排索引。

以上图为例，咱们能够通过 doc_id 查问到具体对象的形式称为应用 正排索引，其实也能了解为一种散列表。

实质是通过 key 来查找 value。

比方通过 doc_id=4 便能很快查问到 name=jetty wang,age=20 这条数据。

倒排索引

那如果反过来我想查问 name 中蕴含了 li 的数据有哪些？这样如何高效查问呢？

仅仅通过上文提到的正排索引显然起不到什么作用，只能顺次将所有数据遍历后判断名称中是否蕴含 li；这样效率非常低下。

但如果咱们从新构建一个索引构造：

当要查问 name 中蕴含 li 的数据时，只须要通过这个索引构造查问到 Posting List 中所蕴含的数据，再通过映射的形式查问到最终的数据。

这个索引构造其实就是 倒排索引。

Term Dictionary

但如何高效的在这个索引构造中查问到 li 呢，联合咱们之前的教训，只有咱们将 Term 有序排列，便能够应用二叉树搜寻树的数据结构在o(logn) 下查问到数据。

将一个文本拆分成一个一个独立Term 的过程其实就是咱们常说的分词。

而将所有 Term 合并在一起就是一个 Term Dictionary，也能够叫做单词词典。

• 英文的分词绝对简略，只须要通过空格、标点符号将文本分隔便能拆词，中文则绝对简单，但也有许多开源工具做反对（因为不是本文重点，对分词感兴趣的能够自行搜寻）。

当咱们的文本量微小时，分词后的 Term 也会很多，这样一个倒排索引的数据结构如果寄存于内存那必定是不够存的，但如果像 MySQL 那样寄存于磁盘，效率也没那么高。

Term Index

所以咱们能够抉择一个折中的办法，既然无奈将整个 Term Dictionary 放入内存中，那咱们能够为Term Dictionary 创立一个索引而后放入内存中。

这样便能够高效的查问Term Dictionary，最初再通过Term Dictionary 查问到 Posting List。

绝对于 MySQL 中的 B+ 树 来说也会缩小了几次 磁盘 IO。

这个 Term Index 咱们能够应用这样的 Trie 树 也就是咱们常说的 字典树 来寄存。

更多对于字典树的内容请查看这里。

如果咱们是以 j 结尾的 Term 进行搜寻，首先第一步就是通过在内存中的 Term Index 查问出以 j 打头的 Term 在 Term Dictionary 字典文件中的哪个地位（这个地位能够是一个文件指针，可能是一个区间范畴）。

紧接着在将这个地位区间中的所有 Term 取出，因为曾经排好序，便可通过二分查找疾速定位到具体位置；这样便可查问出 Posting List。

最终通过 Posting List 中的地位信息便可在原始文件中将指标数据检索进去。

更多优化

当然 ElasticSearch 还做了许多针对性的优化，当咱们对两个字段进行检索时，就能够利用 bitmap 进行优化。

比方当初须要查问 name=li and age=18 的数据，这时咱们须要通过这两个字段将各自的后果 Posting List 取出。

最简略的办法是别离遍历两个汇合，取出反复的数据，但这个显著效率低下。

这时咱们便可应用 bitmap 的形式进行存储（还节俭存储空间），同时利用先天的 位与 * 计算便可得出后果。*

[1, 3, 5] ⇒ 10101

[1, 2, 4, 5] ⇒ 11011

这样两个二进制数组求与便可得出后果：

10001 ⇒ [1, 5]

最终反解出 Posting List 为[1, 5], 这样的效率天然是要高上许多。

同样的查问需要在 MySQL 中并没有非凡优化，只是先将数据量小的数据筛选进去之后再筛选第二个字段，效率天然也就没有 ES 高。

当然在最新版的 ES 中也会对 Posting List 进行压缩，具体压缩规定能够查看官网文档，这里就不具体介绍了。

总结

最初咱们来总结一下：

通过以上内容能够看出再简单的产品最终都是根底数据结构组成，只是会对不同利用场景针对性的优化，所以打好数据结构与算法的根底后再看某个新的技术或中间件时能力疾速上手，甚至本人就能晓得优化方向。

最初画个饼，后续我会尝试依照 ES 倒排索引的思路做一个单机版的搜索引擎，只有本人写一遍能力加深了解。

更好的浏览体验请拜访此处：https://www.notion.so/Elastic…

你的点赞与分享是对我最大的反对