Lucene之倒排索引简述(1)

前言

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

1. 倒排索引理论
2. Lucene倒排索引实现
3. Lucene索引文件构成
4. 什么是Terms Index？
5. 什么是Terms Dictionary?
6. 结束语

理论

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

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

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

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

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

我们可以用一个HashMap来简单描述这个结构： Map<String, List<Integer>>， 这个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，这部分内容将在下篇文章中介绍。