希望长大对我而言，是可以做更多想做的事，而不是被迫做更多不想做的事...... 首页

Elasticsearch倒排索引比mysql快

丁D
学无止境
2019-12-13 10:30
37147已阅读

摘要本文将介绍倒排索引为什么比mysql的索引快的原理。

### 正排索引
一个文档中，有什么单词。是以文档作为维度。
![](/upload/855959-20170706154309815-1724421988.png)
### 倒排索引
这个单词在哪些文档中。以单词作为维度。
![](/upload/855959-20170706154505378-610589524.png)

es使用的是倒排索引

### 倒排索引是怎么构成的
 如下图所示倒排索引由  term index 、term dictionary、posting list组成
 ![](/upload/20180715124329682.png)
 
 我们下面来看一个例子
 数据如图所示 有3个文档
 ![](/upload/20180715121642442.png)
 
 倒排索引的矩阵 
 ![](/upload/20180715121729443.png)
 
 18,20，男，女这种分词后的单词就做term。
 【1,3】，【2】，【1,2】，【3】，这个是文档的id叫做posting list
 
 那什么是term index，或者是term dictionary呢？
 假设我们有这么一句话：`This guy is great. `分词后可能变成（不考虑去掉停用词等）

```
  this、 guy 、is 、great
```

如果我们就这个去查询可能要扫描所有的term，如果我们排序一下变成
```
 guy、 great、 is、 this
```
 这样的话我们就能使用二分法去查询快速找到单词了，这个就是 **term dictionary**
 
有了term dictionary，可以用logN次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的（一次random access大概需要10ms的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了，无法完整地放到内存里。于是就有了**term index**。term index有点像一本字典的大的章节表。比如：A开头的term ……… Xxx页；C开头的term ……… Xxx页；E开头的term ………Xxx页。
term index不会包含所有的term，它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。是以树的形式存在内存中的。
 
 ![](/upload/20180715122024111.png)
 
 到这里我们就可以解释为什么es比mysql块了。因为mysql只有term dictionary这一层，以树的形式存储在磁盘中，检索一个term需要若干次的random access的磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的random access次数。
 
 >PS:
 term index在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b-tree更节约磁盘空间。

上一篇：k8s滚动升级和扩缩容

下一篇：MySQL优化看这篇就对了