Lucene – 索引文件格式

Index data file的组织方式我一直都认为是Lucene最值得去了解的部分。网上已经有了很多很好的这方面分析的文章(例如这一系列,下面的很多图都来自于此)。我只是将我自己理解的写成笔记,供将来查阅。

下文的分析都基于Lucene 3.1版本和它的文档,主要是因为我手头的项目是3.1版的。不过在最新的Lucene 4.1,index file的形式似乎有了不小的变化,将来有空再了解吧。

—————————

Segment是Lucene索引中一个很重要的概念,索引可能会被切分成多个segment,每个segment都是一个完整的部分,它们互相独立。基本上,你可以认为segment就是一个独立的索引,所以需要重点了解的是segment内部的构成。

image

表中列出了索引中可能包含的文件。Segments_File包含了segments的一些metadata;Lock_File则是用来做写锁的;.cfs就是可以选择将segment下的所有file合并到一个file中;.tvx, .tvd, .tvf 都是用来存储Term Vector数据的;

所以,最重要的是红框中的这些索引文件。基本上,每一个segment都包含了这些文件。

————————-

搜索的核心是一个倒排索引(inverted index),所以,Lucene索引文件的核心,就在于如何表达和存储这个倒排索引。如下图(这可是我自己画得):

lucene-indexfile

图中<1>就是一个概念上的倒排索引。每个Term,都对应于一组包含了它的documents,对于复杂一些的倒排索引,不仅仅有这些documents的ID,还可以包括Term在每篇doc中的频率(TermFreq),以及它在每篇doc中出现的位置信息(PosList)。简单用数据结构来表示,就是Map<Term, List<DocInfo> >。DocInfo包括了DocID,TermFreq,以及 TermPositions。

但是,将这么一个倒排索引写入文件中,且要求搜索的性能很好,就不是一件容易的事情了。

首先,每个Term所对应的List<DocInfo>,是一个顺序性的数据格式。但是,因为List可能很长,对List做查找操作性能会很差。因此,对于每个List<DocInfo>,lucene都建立了一个对应的SkipList,使得对List的查找变得高效。所以,原来的List<DocInfo>就变成了List<DocInfo> + SkipList。如图中<2>。

这还不够,最终在写入文件的时候,List<DocInfo>又被拆分成了两部分:TermPositions被独立了出来。因此,整个倒排索引的右边部分最终写入到了两个文件中。TermFreq 和 SkipList被写入到了.frq文件中,而TermPositions被写入到了.prx文件中。他们均按照Term的顺序依次写入。如图中<3>。

回到倒排索引的左半部分。如图中<4>所示,所有的Term信息会被依次写入到一个文件中,就是.tis文件。写入的每个Term信息,不仅包含Term的name和value,还包含了这个Term对应的TermFreq,SkipList 和 TermPositions在对应文件中的偏移。这个偏移相当于指针,使得能够在.frq 和 .prx 文件中快速的定位到对应Term的相关信息。可以简单的理解,.tis文件存储的是一组一组的Term和指针。

但是.tis文件仍然存在一个问题,很难在.tis文件中快速的定位到某个Term。为了解决这个问题,Lucene额外产生了一个.tii文件。文件.tii其实就是.tis文件的索引,它是根据.tis文件间隔固定数量采样生成的。例如.tis文件中的第1个,第51个,101个,151个. . .组成了.tii文件。.tii文件的数据格式几乎和.tis文件的一致,除了.tii文件中每个Term还会保存一个偏移值,指向Term在.tis文件中的对应位置。

.tii文件在Lucene搜索的时候,会被全部加载进内存。

总的看来,一个倒排索引在Lucene中,最终是被拆解成了4个文件:.tii, .tis, .frq, .prx。

—————-

具体分析每个文件的格式:

.tis文件的格式:
TermInfoFile (.tis)–> TIVersion, TermCount, IndexInterval, SkipInterval, MaxSkipLevels, TermInfos
TermInfos –> <TermInfo>^ TermCount
TermInfo –> <Term, DocFreq, FreqDelta, ProxDelta, SkipDelta>
Term –> <PrefixLength, Suffix, FieldNum>

TermCount是指文件中保存的Term的数量;IndexInterval就是前面提到的.tii的采样的间隔长度;SkipInterval 和 MaxSkipLevels都是和SkipList有关的参数;
TermInfos是.tis文件的核心。它包括了TermCount个TermInfo;而每个TermInfo中包含一个Term,一个DocFreq(表示这个Term在多少个doc中出现了)和三个“指针”:FreqDelta, ProxDelta, SkipDelta。

这里有两个有意思的地方:
第一,所谓的指针,其实就是数据在文件中的偏移值。例如FreqDelta就是这个Term对应的TermFreq在.frq文件中的偏移值。但是,FreqDelta记录的还不是绝对偏移值,而是一个相对值。“Delta”这个词,表示它保存的是相对于上一个Term的偏移。关于这一点,在引用的blog中有更加详细的说明,它将此称为“差值规则(Delta)”。Lucene中大量使用了这种做法,只要是记录文件偏移量的地方,几乎都采用Delta方式;
第二,一个Term是包括了field和value两部分内容。在.tis中,并没有记录field的字符串,而是记录的fieldNum。并且,在记录value的时候,也不是记录完整的字符串,而是拆成了PrefixLength 和 Suffix两部分。PrefixLength是指和前一个Term的value共有的字符串长度,Suffix则是和前一个Term的差异部分。这在引用blog中,称为“前缀后缀规则(Prefix+Suffix)”;
无论是“差值规则(Delta)”还是“前缀后缀规则(Prefix+Suffix)”,其实质都是为了尽可能的压缩文件的尺寸。

.tii文件的格式:
TermInfoIndex (.tii)–> TIVersion, IndexTermCount, IndexInterval, SkipInterval, MaxSkipLevels, TermIndices
TermIndices –> <TermInfo, IndexDelta>^IndexTermCount
IndexDelta –> VLong

和.tis文件的结构几乎一致,就是多了一个IndexDelta,指向.tis文件的偏移值,当然,这也是一个采用“差值规则”的偏移值;

lucene-tistii

.frq文件的格式:
FreqFile (.frq) –> <TermFreqs, SkipData>^TermCount
TermFreqs –> <TermFreq>^DocFreq
TermFreq –> DocDelta[, Freq?]
SkipData –> <<SkipLevelLength, SkipLevel>^NumSkipLevels-1, SkipLevel> <SkipDatum>
SkipLevel –> <SkipDatum>^DocFreq/(SkipInterval^(Level + 1))
SkipDatum –> DocSkip,PayloadLength?,FreqSkip,ProxSkip,SkipChildLevelPointer?

包含了TermCount数量的TermFreqs和SkipData,每个Term都有一个TermFreqs和SkipData。
TermFreqs中保存的是该Term在各个doc中出现的频率;
SkipData则是我们之前提到的跳表(SkipList),这部分是.frq文件最复杂的地方;
TermFreqs are ordered by term (the term is implicit, from the .tis file);
TermFreq entries are ordered by increasing document number;

lucene-frq

.prx文件的格式:
ProxFile (.prx) –> <TermPositions>^TermCount
TermPositions –> <Positions>^DocFreq
Positions –> <PositionDelta,Payload?>^Freq
Payload –> <PayloadLength?,PayloadData>

保存的就是一各个TermPositions,.tis中的每个Term都对应于其中的一个TermPositions;
TermPositions中包含DocFreq数量的Positions,每个包含Term的doc都有一个Positions;
每个Positions有包含了Freq个PositionDelta,因为这篇doc中的每个出现Term的地方都要记录一个Position;

从下图可以看到,.frq中的SkipList是有“指针”指向.prx的对应位置:

lucene-prx

——————————–

除了倒排索引以外,Lucene还有一些index file是保存“正向索引的”,包括:

.fnm文件:它保存了所有Field的相关信息,包括fieldName和它的属性,另外Field在这个文件中的位置,决定了它的Field Number值;

lucene-fnm

.fdt文件:他保存了索引中那些设置成stored field的数据。这些数据可能不需要在倒排索引中被检索,但是最后生成结果的时候需要用到;

.fdx文件:它是.fdt文件的索引;

lucene-fdtfdx

.nrm文件:它保存的是lucene scoring时候需要用到的norms。

— END. —

Advertisements
相册 | 此条目发表在Lucene分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s