Fork me on GitHub

Lucene 源码系列——索引文件的生成(一)之 doc&&pay&&pos

在执行 flush()的过程中,Lucene 会将内存中的索引信息生成索引文件,其生成的时机点如下图红色框标注:

图 1:

1.png

  图一中的流程是 flush()阶段的其中一个流程点,完整的 flush()过程可以看系列文章文档提交之 flush索引文件的生成 系列文章将会介绍图一中红框标注的每一个流程点,本篇文章先介绍 生成索引文件 .tim、.tip、.doc、.pos、.pay 流程点。

生成索引文件。tim、.tip、.doc、.pos、.pay

  在添加文档阶段,一篇文档中的 term 所属文档号 docId,在文档内的出现次数 frequency,位置信息 position、payload 信息、偏移信息 offset,会先被存放到倒排表中,随后在 flush()阶段,读取倒排表的信息,将这些信息写入到索引文件.tim、.tip.doc.pos、.pay 中。

生成索引文件。tim、.tip、.doc、.pos、.pay 的流程图

图 2:

2.png

写入索引文件的顺序

图 3:

3.png

  在文章倒排表中我们知道,倒排表中的内容按照域进行划分,域之间可能存在相同的 term,但是一个域内 term 是唯一的,故其写入索引文件的顺序如图 3 所示, 域间(between filed)根据域名(field name)的字典序处理,域内(inner field)按照 term 的字典序进行处理。

生成索引文件.doc、.pos、.pay

图 4:

4.png

  我们先介绍在一个域内,生成索引文件.doc、.pos、.pay 的逻辑。

生成索引文件.doc、.pos、.pay 的流程图

图 5:

5.png

  图 5 描述的是同一个域内处理一个 term,生成索引文件.doc、.pos、.pay 的过程。

执行处理前的初始化的工作

图 6:

6.png

  依次处理当前域中所有的 term,并且是按照 term 的字典序处理。

为什么要按照 term 的字典序处理

  在处理一个 term 前,我们先要 执行处理前的初始化的工作,工作内容为获取上一个 term 后处理结束后的信息,包括以下信息:

  • docStartFP:当前 term 在索引文件.doc 中的起始位置,在后面的流程中,当前 term 的文档号 docId、词频 frequency 信息将从这个位置写入,因为索引文件是以数据流的方式存储,所以 docStartFP 也是上一个 term 对应的信息在索引文件.doc 中的最后位置 +1
  • posStartFP:当前 term 在索引文件.pos 中的起始位置,在后面的流程中,当前 term 的位置 position 信息从这个位置写入,因为索引文件是以数据流的方式存储,所以 posStartFP 也是上一个 term 对应的信息在索引文件。pos 中的最后位置 +1
  • payStartFP:当前 term 在索引文件.pay 中的起始位置,在后面的流程中,当前 term 的偏移 offset、payload 信息从这个位置写入,因为索引文件是以数据流的方式存储,所以 payStartFP 也是上一个 term 对应的信息在索引文件。pay 中的最后位置 +1
  • 重置跳表信息:该信息在后面介绍跳表时再展开介绍

图 7:

7.png

  图 7 中,如果当前开始处理第二个 term,那么此时 docStartFP(docStart File Pointer 缩写)、posStartFP、payStartFP 如上所示,这几个信息将会被写入到索引文件。tim、.tip 中,本文中我们只需要知道生成的时机点,这些信息的作用将在后面的文章中介绍。

是否还有文档包含当前 term?

图 8:

8.png

  按照文档号从小到大,依次处理当前 term 在一篇文档中的信息,这些文档中都包含当前 term。

记录当前文档号到 docSeen

图 9:

9.png

  使用 FixedBitSet 对象 docSeen 来记录当前的文档号,docSeen 在生成索引文件.tim、tip) 时会用到,这里我们只要知道它生成的时间点就行。

记录 term 所有文档中的词频 totalTermFreq

图 10:

10.png

  这里说的所有文档指的是包含当前 term 的文档,一篇文档中可能包含多个当前 term,那么每处理一篇包含当前 term 的文档,term 在这篇文档中出现的次数增量到 totalTermFreq,totalTermFreq 中存储了 term 在所有文档中出现的次数,同样增量统计 docFreq,它描述了包含当前 term 的文档数量。

  totalTermFreq、docFreq 将会被存储到索引文件.tim、tip) 中,在搜索阶段,totalTermFreq、docFreq 该值用来参与打分计算(见系列文章查询原理)。

是否生成了 PackedBlock?

图 11:

11.png

  每当处理 128 篇包含当前 term 的文档,就需要将 term 在这些文档中的信息,即文档号 docId 跟词频 frequency,使用 PackeInts 进行压缩存储,生成一个 PackedBlock。

图 12:

12.png

  图 12 中,红框标注的即 PackedBlock,关于 PackedBlock 的介绍以及几个问题在后面的流程中会介绍,这里先抛出这几个问题:

  • 为什么要生成 PackedBlock
  • 为什么选择 128 作为生成 PackedBlock 的阈值
写入到跳表 skipList 中

图 13:

13.png

  如果生成了一个 PackedBlock,那么需要生成跳表,使得能在读取阶段能快速跳转到指定的 PackedBlock,跳表 skipList 的介绍将在后面的文章中详细介绍,这里只要知道生成的时机点即可。

记录文档号跟词频信息

图 14:

14.png

  将文档号跟 term 在当前文档中的词频 frequency 分别记录到两个数组 docDeltaBuffer、freqBuffer 中,注意的是由于文档号是按照从小到大的顺序处理的,所以 docDeltaBuffer 数组存放的是与上一个文档号的差值,但是 term 在每个文档中的词频 frequency 是无序的,所以无法使用差值存储词频 frequency,故在 freqBuffer 数组中,数组元素是原始的词频值。

为什么使用差值存储

  能降低存储空间的使用量,如果我们有下面的待处理的文档号集合,数组中按照文档号从小到大有序:

    int[] docIds = {1, 3, 7, 10, 12, 13, 17}

  如果我们使用固定字节存储(见 PackedInts(一)),那么根据 17(数组中的最大值)的二进制为 00010001,最少可以使用 5 个 bit 位(有效数据位)才能描述 17,那么数组的其他元素都是用 5 个 bit 位存储的话,一共 7 个数组元素,共需要 5*7 = 35 个 bit,如果使用差值存储(当前数组元素与前一个数组元素的差值),在计算了差值后,数组 docIds 如下所示:

    int[] docIds = {1, 2, 4, 3, 2, 1, 4}

  docIds 数组中最大值为 4,二进制位 00000100,那么所有数组元素使用 3 个 bit 位存储,共需要 3*7 = 21 个 bit,可见能有效的降低存储空间。

生成 Block

图 15:

15.png

  当数组 docDeltaBuffer 中的数组元素个数达到 128 个以后,意味着已经处理了 128 篇文档,此时需要生成 Block,即将数组 docDeltaBuffer、freqBuffer 中的数据经过 PackeInts 处理后生成一个 PackedBlock,如下所示:

图 16:

16.png

结语

  基于篇幅,剩余的流程将在下一篇文档中展开。


本文地址:https://www.6aiq.com/article/1586658642369
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出