Elasticsearch原理解析--倒排索引

倒排索引是搜索引擎的核心，本篇文章介绍了ES中倒排索引是如何实现的。
ES默认为字符串会创建倒排索引，具体的实现功能在lucene相关代码中。
倒排索引主要分成两个部分:

lucene使用FST tree实现term的查找。

term查找分成2个文件（8.7的lucene把metadata分开，多了一个文件）。

term存储时会将一批term存储在一个block中，最少25个，最多48个，这批term的共同前缀作为FST Tree的一个item。

term的索引文件后缀是tip，用来保存FST Tree。

term的数据文件后缀是tim，用来保存term block。

tip文件和tim文件内容见：

term查找流程如下：

1、根据FST Tree找到termPrefix对应在tim文件中position。FST之前是全内存的，现在是off-heap存储，使用MMap映射。

image.png

FST tree构建出上面的树形结构，记录在一个bytes array中，以前lucene是全内存的存储这个bytes array，现在是off-heap存储，使用MMap映射。

2、根据termPrefix位置加载term block，然后遍历每个termSuffix，检查term是否存在。存在的话就能获取到term对应的posting信息。

Lucene使用skipList实现posting的快速查找。

posting包括了doc、pos、pay后缀的三个文件，docId list主要是实现在doc文件中，pos存储了一些全文检索的position信息，pay存储了一些附加信息。

doc、pos、pay文件内容见：

docId list在doc文件存储两部分内容：

docId链表结构存储方式：每BLOCK_SIZE（默认为128）个doc压缩存储为一个block，最后一个小于128个doc的block使用vint方式。

skipList最多存储MAX_SKIP_LEVELS层(默认为10)，每一层记录若干个docId的postion。第0层记录的是每个docId block的postion。每一层创建了skipMultiplier（默认为8）个doc pos，就在下一层创建一个doc pos。

image.png

上图实例的skipList中，一个block存储3条记录，skipList每3个doc创建下一层的item。

posting查找docId主要有两个方法：

nextDoc：查找下一个docId，这个只要往下遍历docId list即可。

advance：查找某个docId指定的位置。在取交、取差时，需要跳着查docId，这时候要用到skipList，加快docId的查找。

倒排索引查询产生IO的地方：

FST tree现在是offHeap存储，如果查到了不在内存的块，则会产生IO。
一个term查询，如果前缀没命中，则不产生IO，前缀命中则只会产生一次IO，加载term block，在term block中查找term是否匹配。
找到的term接下来会去获取posting，如果是一个term，则直接在doc文件中获取docId列表，此时是顺序IO获取数据。如果有多个term要做and、not query，则会有skipList的IO。