Lucene的基本规则

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

大大缩小了存储空间,尤其是在按字典顺序排序的情况下,前缀的重合率大大提高。
差值规则(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,还是词在文档中的位置,都是按从小到大的顺序,逐渐增大的。
或然跟随规则(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)甚至整个索引都是有效的,而非每次的情况都不相同,因而可以统一存放一个标志。

跳跃表规则(Skip list)

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

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

[list]
[]元素是按顺序排列的,在Lucene 中,或是按字典顺序排列,或是按从小到大顺序排列。
[
]跳跃是有间隔的(Interval),也即每次跳跃的元素数,间隔是事先配置好的,如图跳跃表的间隔为3。
[*]跳跃表是由层次的(level),每一层的每隔指定间隔的元素构成上一层,如图跳跃表共有2 层。
[/list]

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

[list]
[]对间隔(Interval)的定义: 如图中,有的认为间隔为2,即两个上层元素之间的元素数,不包括两个上层元素;有的认为是3,即两个上层元素之间的差,包括后面上层元素,不包括前面的上层元素;有的认为是4,即除两个上层元素之间的元素外,既包括前面,也包括后面的上层元素。Lucene 是采取的第二种定义。
[
]对层次(Level)的定义:如图中,有的认为应该包括原链表层,并从1 开始计数,则总层次为3,为1,2,3 层;有的认为应该包括原链表层,并从0 计数,为0,1,2 层;有的认为不应该包括原链表层,且从1 开始计数,则为1,2 层;有的认为不应该包括链表层,且从0 开始计数,则为0,1 层。Lucene 采取的是最后一种定义。
[/list]

跳跃表比顺序查找,大大提高了查找速度,如查找元素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 原理与代码