Lucene学习总结之三：Lucene的索引⽂件格式（1）
Lucene的索引⾥⾯存了些什么，如何存放的，也即Lucene的索引⽂件格式，是读懂Lucene源代码的⼀把钥匙。
当我们真正进⼊到Lucene源代码之中的时候，我们会发现:
Lucene的索引过程，就是按照全⽂检索的基本过程，将倒排表写成此⽂件格式的过程。
Lucene的搜索过程，就是按照此⽂件格式将索引进去的信息读出来，然后计算每篇⽂档打分(score)的过程。
本⽂详细解读了Apache Lucene - Index File Formats() 这篇⽂章。
⼀、基本概念
下图就是Lucene⽣成的索引的⼀个实例：
Lucene的索引结构是有层次结构的，主要分以下⼏个层次：
索引(Index)：
在Lucene中⼀个索引是放在⼀个⽂件夹中的。
如上图，同⼀⽂件夹中的所有的⽂件构成⼀个Lucene索引。
段(Segment)：
⼀个索引可以包含多个段，段与段之间是独⽴的，添加新⽂档可以⽣成新的段，不同的段可以合并。 如上图，具有相同前缀⽂件的属同⼀个段，图中共两个段 "_0" 和 "_1"。
<和segments_5是段的元数据⽂件，也即它们
保存了段的属性信息。
⽂档(Document)：
⽂档是我们建索引的基本单位，不同的⽂档是保存在不同的段中的，⼀个段可以包含多篇⽂档。
新添加的⽂档是单独保存在⼀个新⽣成的段中，随着段的合并，不同的⽂档合并到同⼀个段中。
域(Field)：
⼀篇⽂档包含不同类型的信息，可以分开索引，⽐如标题，时间，正⽂，作者等，都可以保存在不同的域⾥。
不同域的索引⽅式可以不同，在真正解析域的存储的时候，我们会详细解读。
词(Term)：
词是索引的最⼩单位，是经过词法分析和语⾔处理后的字符串。
Lucene的索引结构中，即保存了正向信息，也保存了反向信息。
所谓正向信息：
按层次保存了从索引，⼀直到词的包含关系：索引(Index) –> 段(segment) –> ⽂档(Document) –> 域(Field) –> 词(Term)
也即此索引包含了那些段，每个段包含了那些⽂档，每个⽂档包含了那些域，每个域包含了那些词。
既然是层次结构，则每个层次都保存了本层次的信息以及下⼀层次的元信息，也即属性信息，⽐如⼀本介绍中国地理的书，应该⾸先介绍中国地理的概况，以及中国包含多少个省，每个省介绍本省的基本概况及包含多少个市，每个市介绍本市的基本概况及包含多少个县，每个县具体介绍每个县的具体情况。
如上图，包含正向信息的⽂件有：
segments_N保存了此索引包含多少个段，每个段包含多少篇⽂档。
XXX.fnm保存了此段包含了多少个域，每个域的名称及索引⽅式。
XXX.fdx，XXX.fdt保存了此段包含的所有⽂档，每篇⽂档包含了多少域，每个域保存了那些信息。
XXX.tvx，XXX.tvd，XXX.tvf保存了此段包含多少⽂档，每篇⽂档包含了多少域，每个域包含了多少词，每个词的字符串，位置等信息。
所谓反向信息：
保存了词典到倒排表的映射：词(Term) –> ⽂档(Document)
如上图，包含反向信息的⽂件有：
糖康福散XXX.tis，XXX.tii保存了词典(Term Dictionary)，也即此段包含的所有的词按字典顺序的排序。
XXX.frq保存了倒排表，也即包含每个词的⽂档ID列表。
XXX.prx保存了倒排表中每个词在包含此词的⽂档中的位置。
典当行管理办法在了解Lucene索引的详细结构之前，先看看Lucene索引中的基本数据类型。
⼆、基本类型
Lucene索引⽂件中，⽤⼀下基本类型来保存信息：
中国司法独立Byte：是最基本的类型，长8位(bit)。
UInt32：由4个Byte组成。
UInt64：由8个Byte组成。
VInt：
变长的整数类型，它可能包含多个Byte，对于每个Byte的8位，其中后7位表⽰数值，最⾼1位表⽰是否还有另⼀个Byte，0表⽰没有，1表⽰有。
越前⾯的Byte表⽰数值的低位，越后⾯的Byte表⽰数值的⾼位。
例如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，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。
⼤⼤缩⼩了存储空间，尤其是在按字典顺序排序的情况下，前缀的重合率⼤⼤提⾼。
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，还是词在⽂档中的位置，都是按从⼩到⼤的顺序，逐渐增⼤的。
3. 或然跟随规则(A, B?)
Lucene的索引结构中存在这样的情况，某个值A后⾯可能存在某个值B，也可能不存在，需要⼀个标志来表⽰后⾯是否跟随着B。
⼀般的情况下，在A后⾯放置⼀个Byte，为0则后⾯不存在B，为1则后⾯存在B，或者0则后⾯存在B，1则后⾯不存在B。
但这样要浪费⼀个Byte的空间，其实⼀个Bit就可以了。
在Lucene中，采取以下的⽅式：A的值左移⼀位，空出最后⼀位，作为标志位，来表⽰后⾯是否跟随B，所以在这种情况下，A/2是真正的A 原来的值。
如果去读Apache Lucene - Index File Formats这篇⽂章，会发现很多符合这种规则的：
.frq⽂件中的DocDelta[, Freq?]，DocSkip,PayloadLength?
.prx⽂件中的PositionDelta,Payload? (但不完全是，如下表分析)
当然还有⼀些带?的但不属于此规则的：
.frq⽂件中的SkipChildLevelPointer?，是多层跳跃表中，指向下⼀层表的指针，当然如果是最后⼀层，此值就不存在，也不需要标志。
.tvf⽂件中的Positions?, Offsets?。
在此类情况下，带?的值是否存在，并不取决于前⾯的值的最后⼀位。
⽽是取决于Lucene的某项配置，当然这些配置也是保存在Lucene索引⽂件中的。
如Position和Offset是否存储，取决于.fnm⽂件中对于每个域的配置(TermVector.WITH_POSITIONS和
TermVector.WITH_OFFSETS)
为什么会存在以上两种情况，其实是可以理解的：
对于符合或然跟随规则的，是因为对于每⼀个A，B是否存在都不相同，当这种情况⼤量存在的时候，从⼀个Byte到⼀个Bit如此8倍的空间节约还是很值得的。
对于不符合或然跟随规则的，是因为某个值的是否存在的配置对于整个域(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⼀起适⽤或然跟随规则。
幼学纪事4. 跳跃表规则(Skip list)
为了提⾼查的性能，Lucene在很多地⽅采取的跳跃表的数据结构。
跳跃表(Skip List)是如图的⼀种数据结构，有以下⼏个基本特征：
元素是按顺序排列的，在Lucene中，或是按字典顺序排列，或是按从⼩到⼤顺序排列。
跳跃是有间隔的(Interval)，也即每次跳跃的元素数，间隔是事先配置好的，如图跳跃表的间隔为3。
跳跃表是由层次的(level)，每⼀层的每隔指定间隔的元素构成上⼀层，如图跳跃表共有2层。
需要注意⼀点的是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是⼤致相同的，但是定义稍有差别：
对间隔(Interval)的定义：如图中，有的认为间隔为2，即两个上层元素之间的元素数，不包括两个上层元素；有的认为是3，即两个上层元素之间的差，包括后⾯上层元素，不包括前⾯的上层元素；有的认为是4，即除两个上层元素之间的元素外，既包括前⾯，也包括后⾯的上层元素。Lucene是采取的第⼆种定义。
句柄
对层次(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在具体实现上，与理论⼜有所不同，在具体的格式中，会详细说明。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议