由于之前被面试官吊打过es的索引原理，所以本人对es的倒排索引进行一个学习和总结。 学习小册子：

Elasticsearch 从入门到实践 - spoofer - 掘金小册 (juejin.cn)

索引从本质来讲就是一种为了加快检索数据的存储结构，就像书的目录一样，可以很快地帮助我们查找到某个章节所在的位置。 常见的索引有哈希表、B+树、有序数组等等，像这种实体 ID 到数据实体内容的关联关系的索引我们称为正排索引，正排索引非常适合处理键值查询的场景。 与正排索引不同，倒排索引是把保存词项到实体ID关系的索引，倒排索引设计中使用到了很多数据结构和算法，使查询效率更高，同时也能够处理大批量的数据。

如果有以下几个短语：

如果我们要找包含学习的短语，没有索引的话，那么我们需要对文档进行遍历才能找到对应的文档id，为了提高效率需要为所有数据建立索引,比如倒排索引。 虽然索引会对我们的数据进行排序，使我们筛选查询的时候定位到数据，一旦数据量大的时候，我们遍历的数据就很庞大，索引占用空间也很庞大，查询效率不高，就会面临以下几种问题：

倒排索引为了解决以上几个问题，使用词项索引（Term Index）来解决上述 1 和 2 的问题，而对于 3 和 4，Lucene 对数据进行了压缩处理，使用 Roaring Bitmaps、跳表等技术来进行快速求交集。 倒排索引的组成主要有3部分， Term Index、Term Dictionary、Posting List 如下图：

其中，Term Dictionary 保存的是词项，随着词项越来越多，从 Term Dictionary 中查找一个词项势必越来越慢，所以必须对这些词项做索引，从而有了 Term Index，它是 Term Dictionary 的索引，最好设计得越小越好，这样缓存在内存中也没有压力。Posting List 保存着每个词项对应的文档 ID 列表（其实还有其他信息，这里为了方便理解，只显示 ID）。

Term Index作为Term Dictionary的索引，需要尽量确保资源消耗小，使之可以缓存在内存中，并且还要确保查询数据有较低的复杂度。 如下图所示，Term Index 只使用公共前缀做索引，那本身要存储 coach、cottage 两个字符串的索引，现在只需要存储 co 一个就行了。这样的话，拥有同一公共前缀的 Term 越多，实际上就越省空间，并且这种设计在查找的时候复杂度是公共前缀的长度：O(len(prefix)) 。对于前缀索引的实现，业界使用了 FST 算法来解决。FST（Finite State Transducers）是一种 FSM（Finite State Machines，有限状态机），并且有着类似于 Trie 树的结构，可以直接根据前缀就找到对应的term在词典中的位置。使用 FST有以下好处：

事实上，FST算法很复杂，有时间我会再研究！！！

Term Dictionary 保存着 Term 与 Posting List 的关系，存储了 Term 相关的信息，如记录了包含该 Term 的文档数量（DocFreq）、Term 在整个 Segment 中出现的频率等，还保存了指向 Posting List 文件的指针（文档 ID 列表的位置、词频位置等）。Term Dictionary为所有Term做好排序，并且进行分块保存，并且只保存Term的后缀。

Posting List不仅保存了文档的Id，还有词频、位置等等，Lucene 把这些数据分成 3 个文件进行存储：

Posting List 主要面临着两个问题：

核心的思想都是：用最少的位数表示原数据，并且兼顾数据读取效率

以上的方式的过程中，就是文档 ID 使用增量编码，数据分块存储、数据按需分配存储空间，而这整个过程叫做 FOR（Frame Of Reference）

ES为了提高查询速率和节省空间，做了很多工作。 Es倒排索引组成包含：Term Index，Term Dictonary，Posting List.