Elasticsearch黑鸟教程15：倒排索引原理介绍

1、什么是倒排索引？

倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。

先来回忆一下我们是怎么插入一条索引记录的：

curl -X PUT "localhost:9200/user/_doc/1" -H 'Content-Type: application/json' -d
'
{
    "name" : "Jack",
    "gender" : 1,
    "age" : 20
}
'

其实就是直接PUT一个JSON的对象，这个对象有多个字段，在插入这些数据到索引的同时，Elasticsearch还为这些字段建立索引——倒排索引，因为Elasticsearch最核心功能是搜索。那么，倒排索引是个什么样子呢？其整体结构如下所示：

假设有一下几条数据：

ID是Elasticsearch自建的文档id，那么Elasticsearch建立的索引如下：

如上所示，Elasticsearch分别为每个字段都建立了一个倒排索引，Kate, John, 24, Female这些叫Term，而[1,2]就是Posting List。Posting list就是一个int的数组，存储了所有符合某个Term的文档id。通过Posting List这种索引方式似乎可以很快进行查找，比如要找age=24的同学。

2、Term Dictionary介绍

Elasticsearch为了能快速找到某个Term，将所有的Term排个序，二分法查找Term，这就是Term Dictionary。

3、Term Index介绍

如果Term太多，Term Dictionary也会很大，全部放在内存不现实，只能部分存储到磁盘上。这是又出现了新的问题，磁盘寻道次数太多也会严重影响查找效率，为了减少磁盘寻道次数来提高查询性能，于是有了Term Index，就像字典里的索引页一样，A开头的有哪些Term，分别在哪页，可以理解Term Index是一颗树：

这棵树不会包含所有的Term，它包含的是Term的一些前缀。通过Term Index可以快速地定位到Term Dictionary的某个offset，然后从这个位置再往后顺序查找。如下图所示：

Term Index不需要存下所有的Term，而仅仅是它们的一些前缀与Term Dictionary的Block之间的映射关系，再结合相关的压缩技术，可以使Term Index缓存到内存中。从Term Index查到对应的Term Dictionary的Block位置之后，再去磁盘上找Term，大大减少了磁盘随机读的次数。

4、为什么 Elasticsearch/Lucene 检索可以比 MySQL 快呢？

为什么 Elasticsearch/Lucene 检索可以比 MySQL 快呢？MySQL 只有 Term Dictionary 这一层，是以 B+Tree 排序的方式存储在磁盘上的。检索一个 Term 需要若干次的 Random Access 的磁盘操作。而 Lucene 在 Term Dictionary 的基础上添加了 Term Index 来加速检索，Term Index 以树的形式缓存在内存中。从 Term Index 查到对应的 Term Dictionary 的 Block 位置之后，再去磁盘上找 Term，大大减少了磁盘的 Random Access 次数。

另外，值得一提的两点是：Term Index 在内存中是以 FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term Dictionary 在磁盘上是以分 Block 的方式保存的，一个 Block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 Term Dictionary 可以比 B-Tree 更节约磁盘空间。