Lucene倒排索引实现原理探秘(2)

上篇文章关于Lucene的倒排索引做了大体介绍，详细介绍了Lucene索引表的实现，包括Terms Index以及Term Dictionary的剖析：

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

此文将继续剖析Lucene倒排索引实现的另一部分核心内容： 倒排表（Postings）。Lucene的官方文档关于该内容的描述非常丰富，所以学习起来也相对轻松。

Postings编码

开始之前先介解Lucene在Postings采用了两个关键的编码格式，PackedBlock和VIntBlock。PackedBlock是在 Lucene 4.0 引入，带来向量化优化。

VIntBlock

VIntBlock是能够存储复合数据类型的数据结构，主要通过变长整型（Variable Integer）编码达到压缩的目的。此外VIntBlock还能够存储 byte[] ，比如.pay用VIntBlock存储了payloads数据等。

值得一提的是，VIntBlock可以存储变长数据结构，如.doc用它存储DocID和TermFreq时，由于在特定条件下(TermFreq=1)，Lucene会省略TermFreq以提高空间占用率。Lucene用一个VInt来表示DocID，VInt则用每个Byte左边第一个Bit来表示是否需要读取顺续到下个Byte。也就是说一个VInt有效位是 28bit ，这就说明VInt头部是有特殊含义的，因此Lucene只能在VInt最右边的一个bit下功夫。让VInt的右边第一Bit来表示是否有下个数据。

具体用法会在介绍.doc文件格式时介绍。

PackedBlock

PackedBlock只能存储单一结构，整数（Integer/Long）。这里主要介绍PackedInts，即让多个Int打包成一个Block。 Lucene规定PackedBlock是固定的128个Value（长度为128的int[]），每个Value的长度都是length个Bits。所以最后一个Byte可能是不满的，有可能多个Value共享一个byte。

PackedBlock需要把整个int[]的所有条目指定长度编码，所以PackedBlock只能选择int[]最大的数来计算长度，否则会让大数失真。反过来，PackedBlock都选择64位，则会浪费空间，不能达到压缩的目的。

Lucene预先编译了64个PackedFormat编码器和解码器，即针对Long以内的每种长度都数据都有自己的解码和编码器，以提高编解码的性能。

PackedPosDeltaBlock、PackedDocDeltaBlock以及PackedFreqBlock都采用了PackedInts结构，它能存储的信息实际上是很有限的，只能存储Int的数组。所以在PackedPosDeltaBlock的时候，只能存储position信息，在VIntBlock则会存储更多必要信息，减少搜索时的IO操作。

这也是为什么需要将DocId和TermFreq拆分成PackedDocDeltaBlock和PackedFreqBlock两个Block存储的原因了。

定长是指PackedBlock限定了 一个Block仅允许存储长度128的整型数组，而不是限定Block用多少个Bytes来存储编码后的结果 。另外Block存储占用的大小，是按数组中最大那个数的有效bits长度来计算整个Block需要占用多大的Bytes数组的。也就是Block的每个数据的长度都是一样，都按最长bits来计算。

简单总结一下，PackedBlock相当于实现了向量化优化，Lucene通常会将整个PackedBlock加载到内存，既可以减少IO操作数，又能提高解码的性能。相对而言VIntBlock则能够更丰富数据类型，比较适合存储少量数据。

Postings文件格式说明

进入正题，我们知道整个Postings被拆成三个文件存储，实际上它们之间也是相对独立的。基本所有的查询都会用.doc，且一般的Query仅需要用到.doc文件就足够了；近似查询则需要用.pox；.pay则是用于Payloads搜索（关于这个之前写一篇博客 《Solr 迟到的Payloads》 ，介绍了Payloads用法和场景)。

Frequencies And Skip Data(.doc文件)

在Lucene倒排索引中，只有.doc是Postings必要文件，即它是不能被省略的。除此之外的两个文件通过配置都是可以省略的。那么.doc到底存储了哪些关键信息呢？直接上图：

这里画得不够清晰，每个Term都有成对的TermFreqs和SkipData的。换言之，SkipData是为TermFreqs构建的跳表结构，所以它们是成对出现的。

TermFreqs — Frequencies

TermFreqs存储了Postings最核心的内容，DocID和TermFreqs，分别表示文档号和对应的词频，它们是一一对应的，Term出现在文档上，就会有Term在文档中出现次数（TermFreqs）。

Lucene早期的版本还没有PackedBlock结构，所以DocID与TermFreq是以一个二元组的方式存储的。这个结构简单，有助于理解，但却并不准确。既然是想深入剖析，还是有必要还原真相的。

TermFreqs采用的是混合存储，由Packed Blocks和VInt Blocks两种结构组成。由于PackedBlock是定长的，当前Lucene默认是128个 Integers 。所以在不满128个值的时候，Lucene采用VIntBlocks结构存储。需要注意的是当用Packed Blocks结构时，DocID和TermFreq是分开存储的，各自将128个值写入到一个Block。

当用VIntBlocks结构时，还是沿用旧版本的存储方式，即上面描述的二元组的方式存储。所以说，将DocID和TermFreq当成一条数据的说法是不完全准确的。

在Lucene4.0之前的版本，还没有引入PackedBlock时，DocID和TermFreq确定完全是成对出现，当时只有VIntBlock一种结构。

Lucene尽可能优先采用PackedBlocks，剩余部分（不足128部分）则用VIntBlocks存储。引入PackedBlock之后，PackedDocDeltaBlock跟PackedFreqBlock是成对的，所以它的写出来的示意图应该是如下：

每个PackedBlock由一个PackedDocDeltaBlock和一个PackedFreqBlock构成，它们都采用PackedInts格式。

例如，在同一个Segment里，某一个Term A在259个文档同一个字段出现，那么Term A就需要把这259个文档的文档编号和Term A在每个文档出现的频率一同记下来存储在 .doc 。此时，Lucene需要用到2个PackedBlocks和3个VIntBlocks来存储它们。

VIntBlock结构相对复杂一些，它以一种巧妙的方式存储复杂的多元组结构。在.doc文件中，用VIntBlock存储DocID和TermFreqs二元组。后面将介绍的Positions则用VIntBlock存储了Postition、Payload和Offset多元组， byte[]和VInt多种数据类型。

这里每一个PackedBlock结构都包含了一个 PackedDocDeltaBlock 和一个 PackedFreqBlock ，如果没有省略Frequencies（TermFreq）；如果用户配置了不存储词频（TermFreq），此时一个PackedBlock仅包含一个PackedDocDeltaBlock。PackedFreqBlock（TermFreq）的存储方式跟PackedDocDeltaBlock（DocID）完全一致，包括后面要讲的pos/pay也都一样的，都使用Packed Block这种编码方式。

在VIntBlock上如何存储DocDelta和TermFreq？如果设置了不存储TermFreq时，Lucene将所有DocDelta以Variable Integer的编码方式直接写到文件里。当设置为存储TermFreq信息时，实际上，TermFreq信息会被按需存储。Lucene做了一个小优化，即当TermFreq=1时，TermFreq将不被存储。那么原本DocDelta（DocID的增量）后面紧跟一个Frequencies的情况变得不再确定，因为压根无法知道DocDelta后面还有没有TermFreq信息。那应该如何识别TermFreq信息是否存在？Lucene先把数值向左移动一位，然后用最右的一个Bit的标记是否存储TermFreq。最后右边的一个 bit 为 1 表示没有存储， 0 作为有存储TermFreq。实际上这是Lucene的惯用手段。

左移一位，实际上等同于 X2 ，当最后一个bit是0，此时是一定是偶数，表示后面还存 储了TermFreq；左移一位再+1，相当于偶数+1，那就是奇数，此时最后一个bit是1，表示TermFreq=1，所以后面没有存储TermFreq。

DocFreq=1时，Lucene做一个叫Singletion（仅出现在一个文档中）的优化，此时就没有TermFreq和SkipData。因为TermFreq等同于TotalTermFreq（上篇文章介绍过，存储在.tim的FieldMetadata上）。

Multi-level SkipList — SkipData

SkipData是.doc文件核心部件之一，Lucene采用的是多层次跳表结构，首先我们先预热一下SkipList的逻辑结构图，最后剖析Lucene存储SkipList的物理结构图。下图(源自网图)很好的描述了SkipList的结构：

跳表的原理非常简单，跳表其实就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。 ——— 百度百科

将搜索时耗时转嫁给索引时，这就是Lucene索引的“空间换时间”的基本思想。为此Lucene为Postings构建SkipList ，并把按层级将它系列化存储。第一个SkipLevel是最高，拥有最少的索引数。

Lucene在索引时构建了SkipList，在Segment中每个Term都有自己唯一的Postings，每个Postings都有需要构建一个SkipList，这三者是一一对应的。所以画出来结构图如下：

除了第0层之外所有SkipLevel的每个跳表数据块（SkipDatum）会存储了指向下一个SkipLevel的指针。图中SkipChildLevelFPg带 ? 的原因是在 Level 0 时，SkipDatum没有下一级可以记录。如果Postings有存储positions、payloads和offsets的话，在跳表数据块中也会记录它们的Block所有文件指针。

通过SkipList可以找到DocID和TermFreq之外，还能找到Positions、Payloads和Offsets这三部分信息。因此，在搜索时通过SkipList可以快速定位Postings的所有相关信息。

关于Lucene构建SkipList的诸多细节(Lucene规定SkipList的层级不超过10层)：

1. 第0层，SkipList为每个Block增加索引，所以VIntBlock不在SkipList上。
2. 第9层，SkipList的第一个节点是在第8 ⁹ (2 ²⁷ )Block。（这个数确实有点大）
3. 第n层，SkipList的第m个节点的位置是第 8^n * m8n∗m 个Block。

跳表的第一层是最密的，越高层越稀疏。按层级从低到高依次系列化为写入.doc的SkipData部分。换言之，SkipDatum个数越多，SkipLevelLength则会越大。

SkipLevelLength说明当前层次Skip系列化之后的长度，SkipLevel是包含该层的所有节点的数据SkipDatum。SkipDatum包含四部分信息，doc_id和term_freq、positions、payloads、以及下一层开始的位置（是第N层指向第N-1层的前一个索引）。

SkipList主要是搜索时的优化，主要是减少集合间取交集时需要比较的次数，比如在Query被分词器分成多个关键词时，搜索结果需要同时满足这些关键词的，此时需要将每个Term对应的DocId集合进行析取操作，通过跳表能够有效有减少比较的次数。

Postitions(.pos文件)

.pos文件存储所有Terms出现文档中的位置信息。为了更好的搜索性能，Lucene还在VIntBlock上存储了部分payloads和offsets信息。实际上只有VIntBlock才有能力来存储复杂的数据结构，PackedBlock是不具备这样的能力的。具体请参考下面的示意图：

Lucene把同一个Term的所有position信息存储在同一个TermPositions上，并没有逻辑或者物理上的划分。将在一个文档里出现的所有位置信息，按出现的先后顺序依次写入。 关键在于，position与TermFreq并不是在一维度上，TermFreq的数值就是position的个数。也就是说，通过.pos文件无法知道每个position的具体含义，PostingsReader通过.doc文件的DocID和TermFreq信息才能算出Postition的是在哪个文档上的哪个位置。

Payloads and Offsets(.pay文件)

Payloads，可以理解为Term的附加信息，它是与Term成对出现的，类似于Map。在用法上也是如此，Payloads的信息需要用byte数组存储，所以在TermPayloads并不能用PackedBlock结构来存储。TermOffsets由2个int来表示Offset的开始位置和长度，可以将它们拆成两个等size的int[]，因此可以用PackedBlock存储。如下图：

总结

开篇先学习了Lucene用于存储Postings的两种结构，PackedBlock和VIntBlock。PackedBlock是Lucene4.0引用的，它的核心就是一个int[]，为Postings提供向量化优化，VIntBlock也是一种很巧妙且优雅的结构，能存储复杂的类型。

而后，在介绍.doc文件格式的同时，又对上面的两大结构深入剖析，了解这两个结构是理解postings的基础。接下来剖析了.doc文件上采用的SkipList数据结构，主要是搜索时集合间 AND 操作上的一个优化。至于postings中其它两个文件格式，仅做了简单介绍。

Lucene倒排索引部分内容到这里全部结束，包含很多优雅的设计和巧妙的结构，其中蕴含的Lucene设计之美，值得我们反复研读。