分享每一天-Elasticsearch查询速度为什么这么快？

Elasticsearch查询速度为什么这么快？

工具推荐 3221 0 创建时间：2020-10-17 09:37:51

Elasticsearch

##### ES 索引

###### 正排索引

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

![](http://www.seedblog.cn/uploads/article/2020-10-17/l4X0ZZyUsLsA3jAtMKtctOnLniMUtfzeziRSjxwS.jpeg)

以上图为例，我们可以通过 doc_id 查询到具体对象的方式称为使用正排索引，其实也能理解为一种散列表。

本质是通过 key 来查找 value。比如通过 doc_id=4 便能很快查询到 name=jetty wang，age=20 这条数据。

###### 倒排索引
那如果反过来我想查询 name 中包含了 li 的数据有哪些?这样如何高效查询呢?

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

但如果我们重新构建一个索引结构：

当要查询 name 中包含 li 的数据时，只需要通过这个索引结构查询到 Posting List 中所包含的数据，再通过映射的方式查询到最终的数据。

![](http://www.seedblog.cn/uploads/article/2020-10-17/mrHuLzYlP5woFLM9Qd9b1fqiMveSGH6TcQe7eDFZ.jpeg)

这个 Term Index 我们可以使用这样的 Trie 树，也就是我们常说的字典树来存放。

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

##### 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。

![](http://www.seedblog.cn/uploads/article/2020-10-17/XH5mx4aybMJquPQu44D0UXW4tWO4c709ggZQBGZ1.jpeg)

这个 Term Index 我们可以使用这样的 Trie 树，也就是我们常说的字典树来存放。

![](http://www.seedblog.cn/uploads/article/2020-10-17/kW5eftLzNpjF9hloL790FwEORM0BUSnQoagvQZVZ.jpeg)

如果我们是以 j 开头的 Term 进行搜索，首先第一步就是通过在内存中的 Term Index 查询出以 j 打头的 Term 在 Term Dictionary 字典文件中的哪个位置(这个位置可以是一个文件指针，可能是一个区间范围)。

紧接着在将这个位置区间中的所有 Term 取出，由于已经排好序，便可通过二分查找快速定位到具体位置;这样便可查询出 Posting List。

最终通过 Posting List 中的位置信息便可在原始文件中将目标数据检索出来。

##### 更多优化
当然 Elasticsearch 还做了许多针对性的优化，当我们对两个字段进行检索时，就可以利用 Bitmap 进行优化。

比如现在需要查询 name=li and age=18 的数据，这时我们需要通过这两个字段将各自的结果 Posting List 取出。
![](http://www.seedblog.cn/uploads/article/2020-10-17/GtHzOENB3DL1Z2QkEI8pNiCbooLSB2x2B2a61US3.jpeg)

最简单的方法是分别遍历两个集合，取出重复的数据，但这个明显效率低下。

这时我们便可使用 Bitmap 的方式进行存储(还节省存储空间)，同时利用先天的位与计算便可得出结果。

```php
[1, 3, 5] ⇒ 10101 
 
[1, 2, 4, 5] ⇒ 11011 
```
这样两个二进制数组求与便可得出结果：

```php
10001 ⇒ [1, 5]
```

最终反解出 Posting List 为 [1, 5]，这样的效率自然是要高上许多。同样的查询需求在 MySQL 中并没有特殊优化，只是先将数据量小的数据筛选出来之后再筛选第二个字段，效率自然也就没有 ES 高。

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

Elasticsearch查询速度为什么这么快？

商品推荐

广告推荐

推荐文章