b mino为什么退出block_java面试必问——为什么Elasticsearch查询速度比B-tree块？

Elasticsearch是基于Lucene的倒排索引的技术来实现比关系型数据库更快的过滤，特别是对多条件的过滤支持非常好，那么下面我们就来细致的描述下倒排索引实现的具体细节。

这里每一行代表一条document,每个document都有一个docId,那么给这些document建立的倒排索引如下

从上图可以看到，每个字段都有自己的倒排索引，age=12,23,35的这些叫做term，[1,4],[2],[3]

这些叫做posting list 倒排列表，posting list 是一个文档id的列表，存放了所有符合某个term的文档id。

Term dirtionary 和term index?

什么是term dirtionary ?

为了快速查找某个term，将所有term排个序，二分法查找trem,logN的查找效率，就像通过字典查找一样，这就是Term dictionary,现在看起来和传统数据库类似，为什么说查询快呢？

Term index

假设我们有很多歌term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照这样的排序查找某个term会很慢，因为term没有排序，需要全部过滤一遍才能找到特定的term，排序之后变成了 Ada,Carla,Elin,Kate,Patty,Sara,Selena

这样我们可以用二分查找的方法，比全遍历更快的找出目标的term，这个是term dictionary

有了term dictionary 以后，可以用logN次磁盘查找得到目标，但是磁盘的随机读操作任然是昂贵的(一次random access大概需要10ms)所以尽量少的读磁盘，有必要把一些数据放到缓存里面，但是整个term dictionary 又太大，无法完整的存放到内存里，于是就有了term index

Term index 像字典的单词表比如：

A开头的term…………Xxx页

B开头的term…………Xxx页

C开头的term…………Xxx页

实际的term index是一颗树

这棵树不会包含所有的term，它包含term的前缀，通过term index可以快速定位到term dictionary某个offset然后从这个位置在快速查找

所以term index 不需要存下所有的term，只需要存下term的前缀和term dictionary的block之间的映射关系再结合FST(finite state Transducers)的压缩技术，可以使得term index 缓存到内存中去。

那么现在我们就可以说为什么elasticsearch 比mysql检索快了。Mysql只是term dictionary 这一层，是一树的形式存放到磁盘上的，检索一个term 需要若干次的random access的磁盘操作，而lucene在term dictionary的基础上添加了term index 来增加检索速度，term index 以树的形式缓存到内存中，从term index 查到对应的term dictionary的block位置之后，再去磁盘上找term 大大减少了random access 的次数。

在这里需要注意的一点是：term index在内存中是以FST的形式保存的，特点是非常节省内存，Term dictionary在磁盘上是以分block的方式保存的，一个block 利用公共前缀压缩，比如Ab 开头的单词就可以把Ab省去，这样term ditionary就可以节省磁盘空间。

Lucene/Elasticsearch就是尽量将磁盘里的东西搬进内存，减少磁盘随机读取次数(同时也利用磁盘顺序读特性)，结合各种压缩算法，高效使用内存，从而达到快速搜索的特性