Lucene 倒排索引原理探秘 (1)

在全文检索领域， Lucene 可谓是独领风骚数十年。倒排索引构成全文检索的根基，只有深入理解了倒排索引的实现原理，才能算是入门了全文检索领域。本文将对 Lucene 的倒排索引的实现原理和技术细节进行详细的剖析，这些内容适用于 Lucene 5.x 至 7.x 系列版本。文章整体内容组织如下：

理论

在学术上，倒排索引结构非常简明易懂，如下：

也许你已接触过倒排索引，下面这张图你或许已经看过很多次了。本文将从你熟悉的部分开始，一步步深入去挖掘这张图的一个个细节。这里先介绍两个重要概念：

_1. 索引，索引词表。倒排索引并不需要扫描整个文档集，而是对文档进行预处理，识别出文档集中每个词。 _

2. 倒排表，倒排表中的每一个条目也可以包含词在文档中的位置信息（如词位置、句子、段落），这样的结构有利于实现邻近搜索。词频和权重信息，用于文档的相关性计算。

倒排索引由两部分组成，所有独立的词列表称为索引，词对应的一系列表统称为倒排表。 —— 来自《信息检索》

如上图所示，整个倒排索引分两部分，左边是 Term Dictionary(索引表，可简称为 Dictionary)，是由一系列的 Terms 组成的；右边为 Postings List(倒排表)，由所有的 Term 对应的 Postings 组成。

实际上 Lucene 所用的信息信息检索方面的术语基本跟 Information Retrieval（《信息检索》原版）保持一致。比如 Term、Dictionary、Postings 等。

首先，有必要解释一下，每个 Segment 中的每个字段 (Field) 都有这么一个独立的结构。其次，它是不可改写的，即不能添加或更改。至于为何选择不可改写的设计，简单说有两个方面：一是更新对磁盘来说不够友好；另一方面是写性能的影响，可能会引发各种并发问题。

我们可以用一个 HashMap 来简单描述这个结构：Map>，这个 Map 的 Key 的即是Term，那它的 Value 即是Postings。所以它的 Key 的集合即是Dictionary了，这与上图的描述太贴切了。由于 HashMap 的 Key 查找还是用了 HashTable，所以它还解决 Dictionary 的快速查找的问题，一切显得太美好了。这可以说是一个hello world版的倒排索引实现了。

Lucene 的实现

全文搜索引擎通常是需要存储大量的文本，Postings 可能会占据大量的存储空间，同样 Dictionary 也可能是非常大的，因此上面说的基于 HashMap 的实现方式几乎是不可行的。在海量数据背景下，倒排索引的实现都极其复杂，因为它直接关系到存储成本以及搜索性能。为此，Lucene 引入了多种巧妙的数据结构和算法。

Lucene 索引文件构成

我们知道 Lucene 将索引文件拆分为了多个文件，这里我们仅讨论倒排索引部分。

Lucene 把用于存储 Term 的索引文件叫 Terms Index，它的后缀是.tip；把 Postings 信息分别存储在.doc、.pay、.pox，分别记录 Postings 的 DocId 信息和 Term 的词频、Payload 信息、pox 是记录位置信息。Terms Dictionary 的文件后缀称为.tim，它是 Term 与 Postings 的关系纽带，存储了 Term 和其对应的 Postings 文件指针。

总体来说，通过 Terms Index(.tip) 能够快速地在 Terms Dictionary(.tim) 中找到你的想要的 Term，以及它对应的 Postings 文件指针与 Term 在 Segment 作用域上的统计信息。

postings: 实际上 Postings 包含的东西并不仅仅是 DocIDs（我们通常把这一个有序文档编号系列叫 DocIDs），它还包括文档编号、以及词频、Term 在文档中的位置信息、还有 Payload 数据。

所以关于倒排索引至少涉及 5 类文件，本文不会全面展开。

什么是 Terms Index?

下面引用了一张来自网络上的图，非常直观：

Terms Index 即为上图中.tip 部分，它实际上是由一个或多个FST组成的，Segment 上每个字段都有自己的一个 FST（FSTIndex）记录在.tip上，所以图中 FSTIndex 的个数即是 Segment 拥有字段的个数。另外图中为了方便我们理解把 FST 画成 Trie 结构，然后其叶子节点又指向了 tim 的 Block 的，这实际上是用了一种叫 Burst-Trie 的数据结构。

Burst-Trie

.tip看起来是像一棵 Trie，所以整张图表现出来就是论文上的 Burst-Trie 结构了。上面一棵 Trie，Trie 的叶子节点是 Container（即是 Lucene 中的 Block）。下图就是 Paper 上描述的 Burst-Trie 的结构：

来自 Burst-Trie 论文上的一张图

Burst-Trie，关于 Burst-Trie，网上有很多专业资料，这里只做简单介绍。Burst-Trie 可以认为是 Trie 的一种变种，它主要是将后缀进行了压缩，降低了 Trie 的高度，从而获取更好查询性能。

Lucene 工程上的实现方式

Burst-Trie 在 Lucene 是如何应用的？

前面提到了 Lucene 是采用Burst-Trie的思想，但在实现上存在一定的出入，Lucene 的 Burst-Trie 被拆成两部分。如果一定把它们对应起来的话，我认为 Burst-Trie 的 AccessTree 的实现是 FST，存在.tip 文件中；Container 的实现是 Block，存在.tim 文件里。Burst-Trie 的 Container 内部是开放性结构，可能是 Binary-Tree，可以也 List。Lucene 的 block 是数组，准确的说，就是把一系列的 Block 系列化写到文件上，这里好像并没有做特殊的处理。

FST

在 Lucene，Terms Dictionary被存储在.tim 文件上。当一个 Segment 的文档数量越来越多的时候 Dictionary 的词汇也会越来越多，那查询效率必然也会逐渐变低。因此需要一个很好的数据结构为 Dictionary 建构一个索引，将 Dictionary 的索引进一步压缩，这就是后来的 Terms Index(.tii)。这是在早期的版本中使用的，到 Lucene 4.0 之后做一次重构和升级，同时改名为.tip。

FST：Finite-State-Transducer，结构上是图。我们知道把一堆字符串放一堆，把它们的同共前缀进行压缩就会变成 Burst-Trie。如果把后缀变成一个一个节点，那么它就是 Trie 结构了。如果将后缀也进行压缩的话，那你就能发现他更变成一张图结构了。那么我们易知 FST 是压缩字典树后缀的图结构，她拥有 Trie 高效搜索能力，同时还非常小。这样的话我们的搜索时，能把整个 FST 加载到内存。

实际上，FST 的结构非常复杂，我们可以简单的将其理解为一个高效的 K-V 结构，而且空间占用率更高。这里想简单强调一下：Lucene 到底在 FST 里存了什么数据？ 如果你已经了解 FST 在 Lucene 中充当的角色和作用的话，我想你可能会误认为 FST 中存了 Dictionary 中所有的 Terms 数据，这样可以通过 FST 是找到具体的 Term 的位置，或者通过 FST 可以切实获知一个 Term 是否存在。

然而，事实并非如此。 FST 即不能知道某个 Term 在 Dictionary(.tim) 文件上具体的位置，也不能仅通过 FST 就能确切的知道 Term 是否真实存在。它只能告诉你，查询的 Term 可能在这些 Blocks 上，到底存不存在 FST 并不能给出确切的答案，因为 FST 是通过 Dictionary 的每个 Block 的前缀构成，所以通过 FST 只可以直接找到这个 Block 在.tim 文件上具体的 File Pointer，并无法直接找到 Terms。关于 FST 的详细细节，后面将以一篇独立的文章来讲解，这里暂时不展开过多细节。

下面会详细的介绍 Dictionary 的文件结构，这里先提一下。每个 Block 都有前缀的，Block 的每个 Term 实际不记录共同前缀的。只有通过 Block 的共同的前缀，这是整个 Block 的每个 Term 共同的，所以每个 Term 仅需要记录后缀可以通过计算得到，这可以减少在 Block 内查找 Term 时的字符串比较的长度。

简单理解的话，你可以把它当成一个高级的 BloomFilter，我们 BloomFilter 是有一定的错误率的；同时 BloomFilter 是通过 HashCode 实现的，只能用它来测试是否存在，并无法快速定位。在 FST 中，并无错误率且能快速定位。但是 BloomFilter 有更高的性能。

说了这么一大半天，Terms Index 到底带来哪些实质性的功能呢？ Terms Index 是 Dictionary 的索引，它采用了 FST 结构。上面已经提及了，FST 提供两个基本功能分别是：

1. 快速试错，即是在 FST 上找不到可以直接跳出不需要遍历整个 Dictionary。类似于 BloomFilter 的作用。

2. 快速定位 Block 的位置，通过 FST 是可以直接计算出 Block 的在文件中位置（offset,FP）。

上面已经介绍了 FST 的一种功能，此外，FST 还有别的功能，因为 FST 也是一个 Automation(自动状态机)。这是正则表达式的一种实现方式，所以 FST 能提供正则表达式的能力。通过 FST 能够极大的提高近似查询的性能，包括通配符查询、SpanQuery、PrefixQuery 等，甚至包括近期社区正在做的基于正则表达式的查询。

什么是 Terms Dictionary？

前面我们已经介绍了Terms Dictionary的索引，Terms Index。已经频频提到的 Terms Dictionary 到底是什么东东？Terms Dictionary 是 Segment 的字典，索引表。它能够让你知道你的查询的这个 Term 的统计信息，如tf-idf中df(doc_freq)和Total Term Frequence（Term 在整个 Segment 出现频率）；还能让你知道 Postings 的元数据，这里是指 Term 的 docids、tf 以及 offset 等信息在 Postings 各个文件的文件指针 FP。

Block 并不记录这个 Block 的起始和结束的范围，所以当 FST 最终指向多个 Block 时，就会退化为线性搜索。那什么时候会出现 FST 最终指向多个 Block 呢？最简单的一种情况是，超过 48 个的 Term，且出现首字母相同的 term 的个数不超过 25 个。这种情况下由于没有每个 Block 都没有共同前缀，所以构建出来的 FST 只有一个结束节点记录每个 Block 的文件寻址的偏移增量。

Lucene 规定，每个 Block 的大小在 25-48 范围内。

说这么多，还是觉得太抽象了，我们来看一下.tim文件结构示意图：

主要是大两部分信息，1. Block 信息，包含所有 Term 的详情；2. Field 的自有属性和统计信息。接下来我们将展开来介绍这两部分内容。

Block 信息 - NodeBlock

在整个.tim 文件上，我觉得比较复杂且值得拎出来讲的只有 NodeBlock。那么，Block 又是什么东东？它是如何被构建的？这部分代码，还是比较晦涩难懂得，我每次读时也都会产生一些新的疑问。

我们前面所有说的 Block 即是 NodeBlock 的一个 Entry。由上图可以知道，Block 中有两种 OuterNode 和 InnerNode。这里我想引用代码上两个类名来辅助我们接下来的剖析：PendingTerm/PendingBlock，我们暂且把它们叫作待写的Term和子Block的指针吧。

NodeBlock 从构建逻辑上来讲是它是树型结构，所以它由叶子节点和非叶子节点两种节点组成。叶子节点就叫 OutterNode，非叶子节点就叫 InnerNode。一个 Block 可能含有一堆的 Term(PendingTerm)和 PendingBlock(当它是非叶子节点时)，实际上 PendingBlock 也是不可能出现在叶子节点上的。如果是 PendingBlock，那么这个 Entry 只记录两个信息：后缀 (这个 Block 的共同后缀) 以及子 Block 的文件指针，此时就不必再记上所说的统计信息和 postings 信息了。

如图所示，一个 Block 记录的信息非常多，首先是 Block 的类型和 Entry 的条数等元数据信息，而后是该 Block 拥有的所有 Entry。

这里每个 Entry 含有后缀、统计信息 (对应为前面据说的权重，它含有 ttf 和 df)、Postings 的位置信息 (这就是反复提及 postings 相关的文件指针，postings 是拆分多文件存储的)。关于 Postings 更多细节，放到下个章节来讨论。

Field 信息 - FieldMetadata

相对来说FieldMetadata组织结构就简单多了，纯粹的线性写入即可。但 Field 信息记录的内容还是挺多的，包括字段本身的属性，如字段编号、Terms 的个数、最大和最小的 Terms；此外还记录了 Segment 级别的一些统计信息，包括 tdf、拥有该字段的文档总数（如果文档没有该字段，或者该字段为空就不计了）。

1. RootCode 实际上指向该字段第一个 Block 的文件指针。

2. LongsSize 这个名字有点隐晦，它是说该字段的字段存储哪些 Postings 信息。因为我们是可以指定 Postings 存储或者不存储诸如位置信息和 Payload 信息的，存与不存将被表现在这里了。

从搜索流程来看，Lucene 先读到 FieldMetadata 的信息，然后判断 Query 上 Terms 是否落在这里字段的 MinTerm 和 MaxTerm 之间。如果不在的话，完全不需要去读 NodeBlock 的。MinTerm 和 MaxTerm 可以有效的避免读取不必要的.tip 文件。

结束语

到这里，关于倒排索引结构中第一部分内容已经介绍完了，限于篇幅的原因，还有更多有趣的小细节没有呈现出来。简单总结一下：我们先从 _Information Retrieve_ 开始了解学术上倒排索引结构，接着我们又对 Luecne 的实现做了深入剖析。Lucene 对索引词表也做了索引（叫 Terms Index，文件后缀是.tip），索引词表的索引采用 Finite-State Transducer 这种数据结构。由于这种结构占用空间极小，所以它完成可以被加载到内存加速 Terms Dictionary 的查找过程。而后又介绍了 Terms Dictionary，Terms Dictionary 以 Terms Index 共同构成与 Burst-Trie 类似的数据结构，Terms Dictionary 含两部分信息：1. NodeBlock 记录 Dictionary 的所有 Terms；2. FieldMetadata 存储了 FieldInfos 信息和 Segment 的统计信息。

关于倒排索引还有 Postings List，这部分内容将在下篇文章中介绍。