- 1. 倒排索引的基本概念
- 2. 字段的倒排索引
- 3. 倒排索引的数据结构
- 3.1 为单词词典建立索引（FST）
- 3.2 为倒排列表建立索引（跳表）
本系列往期文章：
初识ElasticSearch - 01 认识搜索引擎
初识ElasticSearch - 02 ElasticSearch的基本概念
初识ElasticSearch - 03 集群的内部原理
初识ElasticSearch - 04 分布式文档存储
倒排索引在文章初识ElasticSearch - 01 认识搜索引擎中有具体的讲到，这里简单的再过一遍。
回顾在之前文章中我们介绍过的几个基本概念：
① 词项 Term：索引中最小的存储和查询单元，英文是指一个单词，中文是指使用分词系统分词后的一个词。
② 词典 Trem Dictionary： 是对Term进行排序后的集合，数据结构有很多种，各有优缺点。如可通过排序数组(通过二分查找来检索数据)，HashMap(哈希表，检索速度快，属于空间换时间的模式)，FST（Finite-State Transducer，有很好的压缩率）等来实现。
③ 倒排列表 Posting List：倒排列表记录了某个单词在哪些文章中出现过及单词在该文档中出现的位置信息。
倒排索引中需要记录的信息：
① 记录单词频率：单词在某个文档中出现的次数 。
② 记录文档频率：单词出现过的文档总数（有多少个文档包含这个单词）。
③ 记录单词位置：词项在文档中的排序（单词在文档中的位置信息）。
以单词谷歌为例，其单词编号为1，文档频率为3，代表有3个文档包含这个单词，对应的倒排列表为{(1;1;<1>), (2;1;<1>), (3;2;<1>)}，其含义为在文档1、2、3都出现过这个单词，文档1和文档2中该单词出现的频率都为1，出现位置也都是1，即文档中第1个单词是谷歌。文档3中该单词出现的频率为2次，出现的位置为1和5，即文档3的第1个和第5个单词是谷歌。
所以，倒排索引相比特定词项出现过的文档列表，会包含更多其它信息。它会保存每一个词项出现过的文档总数， 在对应的文档中一个具体词项出现的总次数，词项在文档中的顺序，每个文档的长度，所有文档的平均长度，等等。这些统计信息允许Elasticsearch决定哪些词比其它词更重要，哪些文档比其它文档更重要。
当讨论倒排索引时，我们会谈到文档索引，因为历史原因，倒排索引被用来对整个非结构化文本文档进行标引。 Elasticsearch中的文档是有字段和值的结构化JSON文档。事实上，在JSON文档中， 每个被索引的字段都有自己的倒排索引。
看完上面那句话，你肯定和我有一样的疑问？what?，每个被索引的字段都有自己的倒排索引？不是对文档建立索引吗？怎么文档中的每个字段还有自己的倒排索引？那我们继续聊聊呗，你准备好了吗？
在使用传统的关系型数据库时，需要把数据封装成数据库表中的一条记录，而在ES中对应的则是文档。一个ES集群可以包含多个索引，每个索可以包含多个文档，每个文档可以包含一个或多个字段。如图为MySQL和ES数据库的基础概念对应关系：
Elasticsearch 是面向文档的，意味着它存储整个对象或文档。ES不仅存储文档，而且索引每个文档的内容，使之可以被检索。在ES中，我们对文档进行索引、检索、排序和过滤—而不是对行列数据。这是一种完全不同的思考数据的方式，也是ES能支持复杂全文检索的原因。Elasticsearch使用 json作为文档的序列化格式。
在关系型数据库中，利用数据库的表存储User对象：
| name | sex | age |
|---|---|---|
| zhangsan | man | 25 |
在ElasticSearch中，利用json文档存储一个User 对象：
{
"name":"zhangsan",
"sex":"man",
"age":25
}
这样，虽然原始的 User 对象很复杂，但这个对象的结构和含义在json版本中都得到了体现和保留。在ES中将对象转化为json后构建索引要比在一个扁平的表结构中要简单的多。
向ES中插入一条记录时，其实就是添加一个文档，文档中有多个字段，在插入这些数据到ES的同时，ES会为这些字段建立倒排索引。假设User对象有这么3条数据：
为了查询Name=xxx的数据，ES会为Name字段建立一个倒排索引：
为了查询Age=xxx的数据，ES会为Age字段建立一个倒排索引：
为了查询Sex=xxx的数据，ES会为Sex字段建立一个倒排索引：
因此，在JSON文档中， 每个字段都有自己的倒排索引。
假如一个文章对象Article，包括tiltle，content，tag三个字段 ，现在我们利用ES来存储这个对象，并向索引里面插入3个文档 :
为了检索title=Father这条数据，ES为title字段建立了一个倒排索引：
词项term的集合为：
my，father，mother，brather
为了找到特定的单词，需要将所有的词项遍历一遍，时间复杂度为O(n)，排序之后的单词集合就变成了：
brather，father，mother，my
这个排序后的词项集合称为单词词典，因为是有序的，可以通过二分查找算法找到特定的term，时间复杂度为log(n)，从而提高查询效率。
单词词典是放在磁盘上的，可以用 logN 次磁盘查找得到目标term，但是磁盘的随机读操作仍然是非常昂贵的，所以为了尽量少的读磁盘，需要把单词词典放在内存中，但是如果单词词典中有几十万个单词会非常占据内存，不可能把整个单词词典都放进内存中，因此需要对单词词典的存储做适当的优化。
如果让你来设计单词词典的存储，你会怎么做呢？那就是对term建立索引（Term Index），通过索引找到term的位置，从而找到对应的倒排列表，然后将索引数据放在内存中，单词词典数据放在磁盘中，ElasticSearch对单词词典建立索引的索引结构是FST，在说FST之前先来看看前缀树。
前缀树又叫字典树，可以用于搜索时的自动补全、拼写检查、最长前缀匹配等，有以下三个特点：根节点不包含字符，除根节点外的其余每个节点都只包含一个字符；从根节点到某一节点，将路径上经过的所有字符连接起来，即为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。
首先将所有的词汇组织成一颗前缀树，某些叶子节点可能会很深。只保留比较浅的节点在内存中，也就是说如果某个节点很深，它将从前缀树中踢出去，如此内存就不会因为词汇太多而膨胀，这颗前缀树就好比一颗大树的主干部分，细枝末节都在磁盘上有序存储。
不过字典树存在一个问题，比如 brather 和 mother，father的最后四个字符是重复的，但是这些重复的字符串都单独存储了，并没有被复用，也就是说前缀树没有解决后缀共用问题，只解决了前缀共用，当数据量达到一定级别的时候，只共享前缀不共享后缀也会带来很多空间的浪费，那么如何来解决这个问题呢？
要解决上面字典树的缺陷其实思路也很简单，就是除了利用字符串的前缀，同时也将相同的后缀进行利用，这就是 FST ，它有两个优点：空间占用小，通过对词典中单词前缀和后缀的重复利用，压缩了存储空间； 查询速度快，O(len(str))的查询时间复杂度。如图为FST的结构，不仅利用了重复的前缀，还利用了重复的后缀。
因此，一个完整的倒排索引结构为：
如图，FST并不是将所有的词汇构成一颗树，而是保留单词中比较浅的节点在内存中，即单词的一些前缀，完整的单词词汇在磁盘上顺序存储， FST 的末端节点会存储一个指针指向磁盘上的位置，不同的节点指向不同的位置，相同前缀的词汇在磁盘上会连续有序存储。当一个词汇在匹配 FST 的过程中，匹配到了末端节点（offset）就会继续去磁盘上去顺序查找直到可以确定找到或者没找到这个词汇。如果找到了这个词汇，那么这个词汇的边上就会有一个指向倒排列表所在磁盘位置的指针，接着就可以去取得这个词汇对应的倒排列表将它加载到内存中。
为了加深理解，我们再从逆向角度来描述这个结构，key代表关键词，value代表该关键词对应的倒排列表。现在所有的 key/value 对都按照 key 排序好了紧凑地存储在磁盘上，如果将所有的key 都放在内存里作为索引那这就是没有经过优化的状态。如果我们不取所有的key，而是将连续若干个key 的前缀挑选出来作为「课代表」再放进内存中，那么内存就会明显少了许多。当需要定位具体的key 时，先找到课代表，再定位到「课代表」指向的磁盘位置去就近遍历查找目标key，找到目标key后再去找key对应的value。
现在我们就明白了为什么ElasticSearch检索比MySQL快了，MySQL不存在term index的概念，它直接对term dictionary建立B+树索引，并且索引是放在磁盘上的，检索一个term需要若干次的随机访问磁盘操作，如下图，假如我们要查k=38的这条数据，首先访问第一层的根节点，判断38>35，因此到p3指向的第二层节点中继续查找，判断38<41，因此到p1指向的第三层节点中继续查找，顺着单向链表即可找到k=38的这条数据存放着词项38，每查询一个节点就是一次磁盘 IO 操作。而term index是存在内存中的，它从 term index查到对应的 term dictionary 的 offset位置之后，再去磁盘上找 term，大大减少了磁盘的随机访问次数。
PostingList 可以很大，直接将整个 PostingList 加载到内存显然也是不合适的。
其实，PostingList 在内存中是以 Skiplist 「跳跃列表」的形式存在的。这个数据结构我们以前在 Redis 的 zset 数据结构中遇到过，Lucene 中的 Skiplist 和 Redis 中的 Skiplist 是一样的。只不过 Redis 的 Skiplist 全部在内存中，而 Lucene 的 PostingList 可能只是部分在内存中。Lucene 的策略是只将 Skiplist 中的高层节点放在内存中，当需要访问底层节点时需要额外的一次 IO 读取操作。这样可以显著降低内存压力，因为有些词汇关联的 PostingList 可能特别长，消耗内存会特别多，这属于时间换空间的折中优化。
Lucene 为什么要将 PostingList 设计成跳跃列表呢，这是为了做加速文档的交集运算。当查询的条件是两个MUST 时，需要对两个词汇的 PostingList 进行交集计算。计算交集时会选择短的列表作为「驱动列表」，驱动列表的指针在往前走时，另外一个列表也要跟着往前跳。就好比一个大人和一个小孩走路，大人走得快，小孩就得跟着跑才能追赶上。同时因为跳跃列表的高层都在内存中，所以跳起来会非常的快，这样的交集运算就会有比较好的性能。
因此，倒排索引的 Key 和 Value 都是部分放在内存中，从这点来说 FST 和 Skiplist 的结构具有一定的相似性，它们都是有高度的数据结构，高层的数据留在内存中，底层的数据淘汰到磁盘上，查找方向是先定位高层再定位底层。
关于跳跃表这种数据结构，有必要好好的学习和总结一下，毕竟很多技术都有用到它。
