Lucene 的索引文件格式

Lucene 的索引里面存了些什么，如何存放的，也即 Lucene 的索引文件格式，是读懂 Lucene源代码的一把钥匙。

当我们真正进入到 Lucene 源代码之中的时候，我们会发现:

（1）Lucene 的索引过程，就是按照全文检索的基本过程，将倒排表写成此文件格式的过程。

（2）Lucene 的搜索过程，就是按照此文件格式将索引进去的信息读出来，然后计算每篇文档打分(score)的过程。

本文详细解读了 Apache Lucene - Index File Formats (http://lucene.apache.org/java/2_9_0/fileformats.html) 这篇文章。

ps: 这里原文的版本比较低，时间久远，但是整体的思想是类似的。

我们先耐心跟着学习一遍。

基本概念

下图就是 Lucene 生成的索引的一个实例

_0.cfe  _0.cfs  _0.si  segments_1  write.lock

层次

Lucene 的索引结构是有层次结构的，主要分以下几个层次：

索引(Index)：

在 Lucene 中一个索引是放在一个文件夹中的。

上图，同一文件夹中的所有的文件构成一个 Lucene 索引。

段(Segment)：

一个索引可以包含多个段，段与段之间是独立的，添加新文档可以生成新的段，不同的段可以合并。

如上图，具有相同前缀文件的属同一个段，图中共两个段 “_0” 和 “_1”。

segments.gen 和 segments_5 是段的元数据文件，也即它们保存了段的属性信息。

文档(Document)：

文档是我们建索引的基本单位，不同的文档是保存在不同的段中的，一个段可以包含多个 document。

新添加的文档是单独保存在一个新生成的段中，随着段的合并，不同的文档合并到同一个段中。

域(Field)：

一篇文档包含不同类型的信息，可以分开索引，比如标题，时间，正文，作者等，都可以保存在不同的域里。

不同域的索引方式可以不同，在真正解析域的存储的时候，我们会详细解读。

词(Term)：

词是索引的最小单位，是经过词法分析和语言处理后的字符串。

正向与反向信息

Lucene 的索引结构中，即保存了正向信息，也保存了反向信息。

正向信息：

按层次保存了从索引，一直到词的包含关系：索引(Index) –> 段(segment) –> 文档(Document) –> 域(Field) –> 词(Term)

也即此索引包含了那些段，每个段包含了那些文档，每个文档包含了那些域，每个域包含了那些词。

既然是层次结构，则每个层次都保存了本层次的信息以及下一层次的元信息，也即属性信息，比如一本介绍中国地理的书，应该首先介绍中国地理的概况，以及中国包含多少个省，每个省介绍本省的基本概况及包含多少个市，每个市介绍本市的基本概况及包含多少个县，每个县具体介绍每个县的具体情况

如上图，包含正向信息的文件有：

1）segments_N 保存了此索引包含多少个段，每个段包含多少篇文档。

2）XXX.fnm 保存了此段包含了多少个域，每个域的名称及索引方式。

3）XXX.fdx，XXX.fdt 保存了此段包含的所有文档，每篇文档包含了多少域，每个域保存了那些信息。

4）XXX.tvx，XXX.tvd，XXX.tvf 保存了此段包含多少文档，每篇文档包含了多少域，每个域包含了多少词，每个词的字符串，位置等信息。

所谓反向信息：

保存了词典到倒排表的映射：词(Term) –> 文档(Document)

如上图，包含反向信息的文件有：

1) XXX.tis，XXX.tii 保存了词典(Term Dictionary)，也即此段包含的所有的词按字典顺序 的排序。

2) XXX.frq 保存了倒排表，也即包含每个词的文档 ID 列表。

3) XXX.prx 保存了倒排表中每个词在包含此词的文档中的位置。

在了解 Lucene 索引的详细结构之前，先看看 Lucene 索引中的基本数据类型。

基本类型

Lucene 索引文件中，用一下基本类型来保存信息：

Byte

是最基本的类型，长 8 位(bit)。

UInt32

由 4 个 Byte 组成。

UInt64

由 8 个 Byte 组成。

VInt：

1）变长的整数类型，它可能包含多个 Byte，对于每个 Byte 的 8 位，其中后 7 位表示数值，最高 1 位表示是否还有另一个 Byte，0 表示没有，1 表示有。

2）越前面的 Byte 表示数值的低位，越后面的 Byte 表示数值的高位。

3）例如 130 化为二进制为 1000, 0010，总共需要 8 位，一个 Byte 表示不了，因而需要两个 Byte 来表示，第一个 Byte 表示后 7 位，并且在最高位置 1 来表示后面还有一个 Byte，所以为(1) 0000010，第二个 Byte 表示第 8 位，并且最高位置 0 来表示后面没有其他的 Byte 了，所以为(0) 0000001。

Chars

是 UTF-8 编码的一系列 Byte。

String：

一个字符串首先是一个 VInt 来表示此字符串包含的字符的个数，接着便是 UTF-8 编码的字符序列 Chars。

基本规则

Lucene 为了使的信息的存储占用的空间更小，访问速度更快，采取了一些特殊的技巧，然而在看 Lucene 文件格式的时候，这些技巧却容易使我们感到困惑，所以有必要把这些特殊的技巧规则提取出来介绍一下。

在下不才，胡乱给这些规则起了一些名字，是为了方便后面应用这些规则的时候能够简单，不妥之处请大家谅解。

1. 前缀后缀规则(Prefix+Suffix)

Lucene 在反向索引中，要保存词典(Term Dictionary)的信息，所有的词(Term)在词典中是按照

字典顺序进行排列的，然而词典中包含了文档中的几乎所有的词，并且有的词还是非常的长的，这样索引文件会非常的大，所谓前缀后缀规则，即当某个词和前一个词有共同的前缀的时候，后面的词仅仅保存前缀在词中的偏移(offset)，以及除前缀以外的字符串(称为后缀)。

“Term Terminal” 的存储为：

Term4inal

比如要存储如下词:term，termagancy，termagant，terminal，

如果按照正常方式来存储，需要的空间如下：

[VInt = 4] [t][e][r][m]，[VInt = 10][t][e][r][m][a][g][a][n][c][y]，[VInt = 9][t][e][r][m][a][g][a][n][t]，[VInt = 8][t][e][r][m][i][n][a][l]

共需要 35 个 Byte.

如果应用前缀后缀规则，需要的空间如下：

[VInt = 4] [t][e][r][m]，[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y]，[VInt = 8 (offset)][VInt = 1][t]，[VInt = 4(offset)][VInt = 4][i][n][a][l]

共需要 22 个 Byte。

大大缩小了存储空间，尤其是在按字典顺序排序的情况下，前缀的重合率大大提高。

ps: 这是一种压缩空间非常巧妙的设计。

2. 差值规则(Delta)

在 Lucene 的反向索引中，需要保存很多整型数字的信息，比如文档 ID 号，比如词(Term)在文档中的位置等等。

由上面介绍，我们知道，整型数字是以 VInt 的格式存储的。

随着数值的增大，每个数字占用的 Byte 的个数也逐渐的增多。

所谓差值规则(Delta)就是先后保存两个整数的时候，后面的整数仅仅保存和前面整数的差即可。

比如要存储如下整数：16386，16387，16388，16389

如果按照正常方式来存储，需要的空间如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0100][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]

供需 12 个 Byte。

如果应用差值规则来存储，需要的空间如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]，[(0) 000, 0001]

共需 6 个 Byte。

大大缩小了存储空间，而且无论是文档 ID，还是词在文档中的位置，都是按从小到大的顺序，逐渐增大的。

ps: 利用差值存储数据也值得学习。比如每一个文档的只记录初始化的值，后面只记录差值，可以大大节约存储空间。

3. 或然跟随规则(A, B?)

Lucene 的索引结构中存在这样的情况，某个值 A 后面可能存在某个值 B，也可能不存在，需要一个标志来表示后面是否跟随着 B。

一般的情况下，在 A 后面放置一个 Byte，为 0 则后面不存在 B，为 1 则后面存在 B，或者 0则后面存在 B，1 则后面不存在 B。

但这样要浪费一个 Byte 的空间，其实一个 Bit 就可以了。

ps: 优秀的设计真实抠门。

在 Lucene 中，采取以下的方式：A 的值左移一位，空出最后一位，作为标志位，来表示后面是否跟随 B，所以在这种情况下，A/2 是真正的 A 原来的值。

如果去读 Apache Lucene - Index File Formats 这篇文章，会发现很多符合这种规则的：

1） .frq 文件中的 DocDelta[, Freq?]，DocSkip,PayloadLength?

2） .prx 文件中的 PositionDelta,Payload? (但不完全是，如下表分析)

3） 当然还有一些带 ?的但不属于此规则的：

4）frq 文件中的 SkipChildLevelPointer?，是多层跳跃表中，指向下一层表的指针，当然如果是最后一层，此值就不存在，也不需要标志。

5） .tvf 文件中的 Positions?, Offsets?。

  • 在此类情况下，带?的值是否存在，并不取决于前面的值的最后一位。

  • 而是取决于 Lucene 的某项配置，当然这些配置也是保存在 Lucene 索引文件中的。

  • 如 Position 和 Offset 是 否 存 储 ， 取 决 于 .fnm 文 件 中 对 于 每 个 域 的 配 置(TermVector.WITH_POSITIONS 和 TermVector.WITH_OFFSETS)

为什么会存在以上两种情况，其实是可以理解的：

1）对于符合或然跟随规则的，是因为对于每一个 A，B 是否存在都不相同，当这种情况大量存在的时候，从一个 Byte 到一个 Bit 如此 8 倍的空间节约还是很值得的。

2）对于不符合或然跟随规则的，是因为某个值的是否存在的配置对于整个域(Field)甚至整个索引都是有效的，而非每次的情况都不相同，因而可以统一存放一个标志。

文章中对如下格式的描述令人困惑： 
Positions --> <PositionDelta,Payload?> Freq
 
Payload --> <PayloadLength?,PayloadData> 
PositionDelta 和 Payload 是否适用或然跟随规则呢？如何标识 PayloadLength 是否存在呢？
其实 PositionDelta 和 Payload 并不符合或然跟随规则，Payload 是否存在，是由.fnm 文件中对
于每个域的配置中有关 Payload 的配置决定的(FieldOption.STORES_PAYLOADS) 。
当 Payload 不存在时，PayloadDelta 本身不遵从或然跟随原则。
当 Payload 存在时，格式应该变成如下：Positions --> <PositionDelta,PayloadLength?,PayloadData> Freq
从而 PositionDelta 和 PayloadLength 一起适用或然跟随规则。

跳跃表规则(Skip list)

为了提高查找的性能，Lucene 在很多地方采取的跳跃表的数据结构。

跳跃表(Skip List)是如图的一种数据结构，有以下几个基本特征：

  • 元素是按顺序排列的，在 Lucene 中，或是按字典顺序排列，或是按从小到大顺序排列。

  • 跳跃是有间隔的(Interval)，也即每次跳跃的元素数，间隔是事先配置好的，如图跳跃表的间隔为 3。

  • 跳跃表是由层次的(level)，每一层的每隔指定间隔的元素构成上一层，如图跳跃表共有 2 层。

需要注意一点的是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是大致相同的，但是定义稍有差别：

1) 对间隔(Interval)的定义：

如图中，有的认为间隔为 2，即两个上层元素之间的元素数，不包括两个上层元素；有的认为是 3，即两个上层元素之间的差，包括后面上层元素，不包括前面的上层元素；有的认为是 4，即除两个上层元素之间的元素外，既包括前面，也包括后面的上层元素。

Lucene 是采取的第二种定义。

2）对层次(Level)的定义：

如图中，有的认为应该包括原链表层，并从 1 开始计数，则总层次为 3，为 1，2，3 层；有的认为应该包括原链表层，并从 0 计数，为 0，1，2 层；有的认为不应该包括原链表层，且从 1 开始计数，则为 1，2 层；有的认为不应该包括链表层，且从 0 开始计数，则为 0，1 层。

Lucene 采取的是最后一种定义。

跳跃表比顺序查找，大大提高了查找速度，如查找元素 72，原来要访问 2，3，7，12，23，37，39，44，50，72 总共 10 个元素，应用跳跃表后，只要首先访问第 1 层的 50，发现 72大于 50，而第 1 层无下一个节点，然后访问第 2 层的 94，发现 94 大于 72，然后访问原链表的 72，找到元素，共需要访问 3 个元素即可。

然而 Lucene 在具体实现上，与理论又有所不同，在具体的格式中，会详细说明。

参考资料

《Lucene 原理与代码分析》