doc文件

索引文件doc中按块(block)的方式存放了每一个term的文档号、词频,并且保存了skip data来实现块之间的快速跳转。

doc文件的数据结构

图1: TermFreqs保存了term的所有文档号、词频信息,TermFreqs中按块存储,所以SkipData实现这些块之间的快速跳转。

TermFreqs

图2:

PackedBlock

PackedDocDeltaBlock
PackedFreqBlock

这里注意是由于在每篇文档中的词频值无法保证递增,而在使用PackedInts时会用统一大小的字节数来存放每一个词频值,并且这个字节数取决于词频最大的那个。

VIntBlocks && VIntBlock

DocDelta
Freq

在介绍SkipData前先介绍下跳表(SkipList)的概念 图3: 在每一层中,每skipInterval个数据块就会在上一层中添加一个索引,实现了对数级别的时间复杂度。 比如我们要找文档号为33的值。那么查找的过程如下图。 图4:

SkipData

图5:

SkipLevelLength

SkipLevel

SkipDatum
DocSkip
DocFPSkip
PosFPSkip
PosBlockOffset
PayLength
PayFPSkip
SkipChildLevelPointer

多个域的doc文件的数据结构

图6:

结语

.pos、.pay、.doc、.tim、.tip文件都是通过读取内存倒排表的过程中一起生成的,在处理完每个term的信息并写入.pos、.pay、.doc文件后,开始生成.tim、.tip文件,在最后的文章中会更新这部分内容。

点击下载Markdown文件