1、索引总体结构
1.1、索引层次结构
Lucene的索引结构主要分以下几个层次:
在Lucene中一个索引是放在一个文件夹中的。同一文件夹中的所有的文件构成一个Lucene索引。
一个索引可以包含多个段,段与段之间是独立的,添加新文档可以生成新的段,不同的段可以合并。具有相同前缀文件的属同一个段。
文档是我们建索引的基本单位,不同的文档是保存在不同的段中的,一个段可以包含多篇文档。新添加的文档是单独保存在一个新生成的段中,随着段的合并,不同的文档合并到同一个段中。
一篇文档包含不同类型的信息,可以分开索引,比如标题,时间,正文,作者等,都可以保存在不同的域里。不同域的索引方式可以不同。
词是索引的最小单位,是经过词法分析和语言处理后的字符串。
1.2、索引文件结构
1.3、索引文件说明
名称
|
扩展名
|
数据结构
|
说明
|
Segments File
|
segments.gen segments_N
|
SegmentInfos
|
保存当前索引中所有的段信息的集合,索引中所有可用的段信息都存储在段文件segment_N中。
|
Lock File
|
write.lock
|
|
写锁,用于阻止多个IndexWriter写同一个索引文件
|
Segment Info
|
.si
|
Lucene70SegmentInfoFormat
|
segment的元数据信息,指明这个segment都包含哪些文件
|
Compound File
|
.cfs, .cfe
|
Lucene50CompoundFormat
|
如果启用compound功能,会压缩索引到2个文件内
|
Fields
|
.fnm
|
Lucene60FieldInfosFormat
|
存储有哪些Field,以及相关信息
|
Field Index
|
.fdx
|
Lucene50StoredFieldsFormat
|
Field数据文件的索引
|
Field Data
|
.fdt
|
Lucene50StoredFieldsFormat
|
Field数据文件
|
Term Dictionary
|
.tim
|
BlockTreeTermsWriter
|
Term词典
|
Term Index
|
.tip
|
BlockTreeTermsWriter
|
指向Term词典的索引
|
Frequencies
|
.doc
|
Lucene50PostingsWriter
|
保留包含每个Term的文档列表
|
Positions
|
.pos
|
Lucene50PostingsWriter
|
Stores position information about where a term occurs in the index
|
Payloads
|
.pay
|
Lucene50PostingsWriter
|
offset偏移/payload附加信息
|
Norms
|
.nvd, .nvm
|
Lucene70NormsFormat
|
.nvm保存加权因子元数据;.nvd存储加权数据
|
Per-Document Values
|
.dvd, .dvm
|
Lucene70DocValuesFormat
|
.dvm存文档正排元数据;.dvd存文档正排数据
|
Term Vector Index
|
.tvx
|
Lucene50TermVectorsFormat
|
指向tvd的offset
|
Term Vector Data
|
.tvd
|
Lucene50TermVectorsFormat
|
存储term vector信息
|
Live Documents
|
.liv
|
Lucene50LiveDocsFormat
|
活着的文档列表。位图形式
|
Point values
|
.dii, .dim
|
Lucene60PointsFormat
|
多维数据,地理位置等信息,用于处理数值型的查询
|
2、索引数据类型
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。
3、索引数据编码规则及数据结构
Lucene为了使的信息的存储占用的空间更小,访问速度更快,采取了一些特殊的技巧。
3.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。
大大缩小了存储空间,尤其是在按字典顺序排序的情况下,前缀的重合率大大提高。
3.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.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)甚至整个索引都是有效的,而非每次的情况都不相同,因而可以统一存放一个标志。
3.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在具体实现上,与理论又有所不同,在具体的格式中,会详细说明。
4、索引构建的数据流逻辑
5、Segments文件
Lucene的索引可以由多个复合的子索引或者片断组成。每一个segment都是一个完全独立的索引,它能够被分离地进行检索。当新添加文档时,会创建新的段文件;当段文件比较多时,会合并小的段文件为大的段文件;检索可以涉及多个复合的segments,或者多个复合的indexes。每一个index潜在地包含多个segments。
5.1、segment.gen文件格式
segments.gen文件包含了该索引中当前生成的代(segments_N中的_N)。这个文件仅用于一个后退处理以防止当前代不能被准确地通过单独地目录文件列举来确定(由于某些NFS客户端因为基于时间的目录的缓存终止而引起)。
5.2、segment_N文件格式
Lucene查找segment_N流程:
-
在所有的segments_N中选择N最大的一个。并将其作为genA。
-
打开segments.gen,其中保存了当前的N值。读出版本号(Version),然后再读出两个N,如果两者相等,则作为genB。
-
在上述得到的genA和genB中选择最大的那个作为当前的N,打开segments_N文件。
其中N作为后缀,是36进制的数字,segments_N里通过SegName记录了这索引里所有.si文件名。
segment_N格式说明:
-
Header(IndexHeader):
可编解码的索引头,记录索引文件格式,版本号,文件实例Id等。
-
LuceneVersion(VInt):
记录提交时的Lucene代码版本,由3个VInt组成:major,minor,bugfix;
-
Version(Int64):
索引被修改的计数;
-
NameCounter(Int32):
用于新的段文件名字的生成;
-
SegCount(Int32):
段文件个数计数;
-
MinSegmentLuceneVersion(VInt):
记录提交时最老的Lucene版本,由3个VInt组成:major,minor,bugfix;索引中有多个段时记录此字段;
-
[SegmentCommitInfo]:
保存段提交信息;
-
CommitUserData(Map<String,String>):
存储用户提供的可选数据;
-
Footer(CodecFooter):
可编解码的索引脚,记录校验算法的id及校验结果值;
[SegmentCommitInfo]格式说明:
-
SegName:
段的名称,同时也是构成这个段索引的所有文件的名称前缀;
-
SegID:
编解码此段对应的编解码的id;
-
SegCodec:
编解码此段的编解码器的名称;
-
DelGen:
删除文件的分代年龄计数,如果为-1则表示无删除的文件;
-
DeletionCount:
记录当前段删除的文档数;
-
FieldInfosGen:
fieldInfos 文件的分代计数;
-
DocValuesGen:
可更新的DocValues的分代计数;
-
UpdateFiles:
记录当前段每个域更新的文件集合;
5.3、si格式:
segmentInfo文件,就是一个独立的子索引,其中Files是一个列表,里面存储了本segment所有相关的索引文件。
Lucene70SegmentInfoFormat格式说明:
-
Header(IndexHeader):
可编解码的索引头,记录索引文件格式,版本号,文件实例Id等。
-
SegVersion(String):
创建当前段的代码版本;
-
SegSize(Int32):
此段索引包含的文件数量;
-
IsCompoundFile(Int8):
记录当前段是非被写入混合的文件中;
-
Diagnostics(Map<String,String>):
IndexWriter写入的私有信息,可用于debug,其包括lucene版本,OS信息,java版本等待;
-
Files(Set<String>):
当前段相关的文件的集合;
-
Attributes(Map<String,String>):
-
IndexSort(Int32):
-
Footer(CodecFooter):
6、Compound文件格式
从Lucene 1.4版本开始,compound文件格式成为缺省信息。这是一个简单的容器,其服务所有除delete文件外的文件。
6.1、cfs文件格式
此文件为可选的虚拟文件,其包含了其他所有的索引文件,其主要是为某些文件句柄耗尽的系统使用。
FileData(raw file data):文件数据;
6.2、cfe文件格式
FileCount(VInt):
标识当前的cfs混合文件包含的文件个数;
FileName(String):
文件名
DataOffset(UInt64):
数据偏移;
DataLength(UInt64):
文件大小;
7、Fild相关文件
7.1、域名称格式(.fnm)
存储了Document所包含的FieldName以及Field的内部表示FieldNumber(可以理解为ID)。 同时,每个Field相关索引配置,都通过byte来存储保存下来。其中DocValueBits里,不同类型的Field, 处理DocValue数据是不一样的。
Lucene50FieldInfosFormat格式说明:
-
Header(IndexHeader):
头部标识;
-
FieldsCount (VInt):
文件中存储测域个数;
-
FieldName (String):
UTF-8格式的Field的名称;
-
FieldNumber (VInt):
field的编号;
-
FieldBits(Byte):
一系列标志位,表明对此域的索引方式;
-
IndexOptions(Byte):
一系列标志位,表明对此域的索引方式;
-
DocValuesBits (Byte):
存储每个文档的值包含的类型;
-
DocValuesGen (Int64):
保存DocValues的分代计数;
-
Attributes (Map<String,String>):
编解码相关的私有数据;
-
Footer(CodecFooter):
尾部标识;
7.2、域数据相关信息(.fdx .fdt)
Lucene50StoredFieldsFormat通过压缩文档块以提高文档的压缩比,其压缩算法为LZ4,每个压缩块为16KB,LZ4压缩算法的压缩及解压速度都很快。当压缩配置选项为:BEST_SPEED,使用LZ4压缩算法,此算法更注重的压缩速度;当压缩配置为:BEST_COMPRESSION,使用DEFLATE(同ZIP)压缩算法,其更注重数据压缩比。
域数据文件(fdt):
文件保存文档的压缩数据,每个压缩块为16KB或更大。当数据写入段时,文档就会被扩充到内存缓冲区中,当缓冲区大小大于16KB时,文档相关的配置信息会被刷写到硬盘中,同时一个压缩的域数据文件也被写入。
域索引文件(fdx):
8、Tearm相关信息
8.1、词向量数据信息(tvx tvd)
词向量文档文件(tvd):
-
一个段(segment)包含N篇文档,此文件就有N项,每一项包含了此文档的所有的域的信息。
-
每一项首先是此文档包含的域的个数NumFields,然后是一个NumFields大小的数组,数组的每一项是域号。然后是一个(NumFields - 1)大小的数组,由前面我们知道,每篇文档的第一个域在tvf中的偏移量在tvx文件中保存,而其他(NumFields - 1)个域在tvf中的偏移量就是第一个域的偏移量加上这(NumFields - 1)个数组的每一项的值。
词向量索引文件(tvx):
-
一个段(segment)包含N篇文档,此文件就有N项,每一项代表一篇文档。
-
每一项包含两部分信息:第一部分是词向量文档文件(tvd)中此文档的偏移量,第二部分是词向量域文件(tvf)中此文档的第一个域的偏移量。
8.2、词典及词典索引数据(tim tip )
tim文件为词典文件,tip为词典索引文件;
tim中包含包含了每个域的词统计信息及元数据信息;tip包含词典的索引信息,通过索引可随机访问词数据信息。
8.3、文档号及词频(frq)
Lucene内部通过一个整数的文档编号(document number)来表示文档。第一篇被添加到索引中的文档编号为0,每一篇随后被添加的document获得一个比前一篇更大的数字。 需要注意的是一篇文档的编号(document’s number)可以更改,所以在Lucene之外存储这些编号时需要特别小心。
8.4、量化因子信息
参考博客:
http://www.shenyanchao.cn/blog/2018/12/04/lucene-index-files/
https://lucene.apache.org/core/8_2_0/core/org/apache/lucene/codecs/lucene50/Lucene50PostingsFormat.html#Termindex
https://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623599.html
参考文档:
《Lucene实战》
《AnnotatedLucene》
《开放源代码的全文检索引擎Lucene》