倒排索引的精致结构

前文提到倒排索引就是一个字典，字典的 Key 是关键词，字典的 Value 是文档 ID 列表（PostingList）。但是如果再深入一些，就完全不是这么回事，不论是 Key 还是 Value 其内部的实现结构都要比一个简单的字典复杂的太多。

class InvertedIndex {
  Map<String, PostingList> mappings;
}

class PostingList {
  List<Integer> docIds;
}

首先对于 Key 而言，它代表的只是一堆关键词。但是关键词多了内存就是个问题，会非常消耗内存，特别是对于海量的中文文档而言，这个词汇量可能多达几十万上百万。所以 Lucene 必须对 Key 的存储进行适当优化。

class PostingList {
  List<PostingHeader> docHeaders;
}

class PostingHeader {
  int docId;
  int freq;
  ...
}

其次对于 Value 而言，只存储一个文档 ID 列表是不够的。比如搜索的结果需要排序，排序要有依据。一个最简单的算法就是计算文档中出现关键词的频率，频率多的得分就高。如果只存储了文档 ID 列表，那么计算文档的评分时，就需要获取文档的原始内容进行分词后实时计算频率，这个性能无疑会差很多。如果在添加文档时就将这个频率提前记录下来，那么在查询计算评分的时候就可以明显节省很多计算量。除了频率这个数据可以提前记录在索引里之外，还有很多其它可选数据也可以提前存储。

接下来我们先分析一下 Key 的存储结构。如果让你来设计 Key 的存储，你会怎么做呢？一个很简单的想法就是使用 LRU 算法，将常用的 Key 放在内存里，不常用的 Key 淘汰到磁盘上。那么对应内存的结构就是 LRUMap。

class InvertedIndex {
  LRUMap<String, PostingList> mappings;
}

但是只有这个 LRUMap 是不够的，当一个查询关键词到来的时候你无从判定这个词汇是否存在，这时候就会出现「缓存穿透」，你需要去磁盘里去探一探才能确定，这就需要付出额外的 IO 成本。也许你会很快想到「布隆过滤器」，通过牺牲一小部分内存空间来存储关键词的指纹信息以有效减轻「缓存穿透」现象，降低 IO 压力。

class InvertedIndex {
  LRUMap<String, PostingList> mappings;
  BloomFilter<String> blooms;
}

但是 Lucene 不是这么做的，它使用的是 FST ，也就是「有限状态机」，它有点类似于「字典树」、「前缀树」。FST 内部实现非常复杂，这里我只能粗略描述一下大概的结构。

首先将所有的词汇组织成一颗前缀树，某些叶子节点可能会很深。FST 只保留比较浅的节点在内存中，也就是说如果某个节点很深，它将会从 FST 中踢出去。如此内存就不会因为词汇太多而膨胀。

FST 就好比一颗大树的主干部分，细枝末节都在磁盘上有序存储。FST 的末端节点会存储一个指针指向磁盘上的位置，不同的节点指向不同的位置，相同前缀的词汇在磁盘上会连续有序存储。当一个词汇在匹配 FST 的过程中，匹配到了末端节点就会继续去磁盘上去顺序查找直到可以确定找到或者没找到这个词汇。如果找到了这个词汇，那么这个词汇的边上就会有一个指向 Value 所在磁盘位置指针，接着就可以去取得这个词汇（关键词）对应的 Value（PostingList） 将它加载到内存中。

为了加深理解，我们再从逆向角度来描述这个结构。现在所有的 Key/Value 对都按照 Key 排序好了紧凑地存储在磁盘上，如果将所有的 Key 都放在内存里作为索引那这就是没有经过优化的状态。如果我们不取所有的 Key，而是将连续若干个 Key 的前缀挑选出来作为「课代表」再放进内存中，那么内存就会明显少了许多。当需要定位具体的 Key 时，先找到课代表，再定位到「课代表」指向的磁盘位置去就近遍历查找目标 Key。

另外 PostingList 也可以很大，直接将整个 PostingList 加载到内存显然也是不合适的。

Lucene 当然考虑了这一点，PostingList 在内存中是以 Skiplist 「跳跃列表」的形式存在的。这个数据结构我们以前在 Redis 的 zset 数据结构中遇到过，Lucene 中的 Skiplist 和 Redis 中的 Skiplist 是一样的。只不过 Redis 的 Skiplist 全部在内存中，而 Lucene 的 PostingList 可能只是部分在内存中。Lucene 的策略是只将 Skiplist 中的高层节点放在内存中，当需要访问底层节点时需要额外的一次 IO 读取操作。这样可以显著降低内存压力，因为有些词汇关联的 PostingList 可能特别长，消耗内存会特别多，这属于时间换空间的折中优化。

Lucene 为什么要将 PostingList 设计成跳跃列表呢，这是为了做加速文档的交集运算。当查询的条件是两个 MUST 时，需要对两个词汇的 PostingList 进行交集计算。计算交集时会选择短的列表作为「驱动列表」，驱动列表的指针在往前走时，另外一个列表也要跟着往前跳。就好比一个大人和一个小孩走路，大人走得快，小孩就得跟着跑才能追赶上。同时因为跳跃列表的高层都在内存中，所以跳起来会非常的快，这样的交集运算就会有比较好的性能。

综上所述，倒排索引的 Key 和 Value 都是部分放在内存中，从这点来说 FST 和 Skiplist 的结构具有一定的相似性，它们都是有高度的数据结构，高层的数据留在内存中，底层的数据淘汰到磁盘上，查找方向是先定位高层再定位底层。

本文介绍的 FST 和 Skiplist 的知识点是不准确的，但是这并不妨碍我们理解他们的大致功用。关于 FST 和 Skiplist 的更多细节，后面再继续深入研究。