Lucene 源码系列——索引文件的生成(四)之跳表 SkipList

在文章索引文件的生成(三)中我们介绍了在 Lucene 中生成跳表 SkipList 的流程,通过流程图的方法介绍了源码中的实现方式,而对于读取 SkipList 的内容,决定直接以例子的方式来介绍其读取过程,下文中出现的名词如果没有作出介绍,请先阅读文章索引文件的生成(三)

例子

  直接给出一个生成后的跳表:

图 1:

1.png

  在图 1 中,为了便于介绍,我们处理的是文档号 0~3455 的 3456 篇文档,我们另 skipInterval 为 128,即每处理 128 篇文档生成一个 PackedBlock,对应一个 datum;另 skipMultiplier 为 3(源码中默认值为 8),即每生成 3 个 datum 就在上一层生成一个新的索引,新的索引也是一个 datum,它是 3 个 datum 中的最后一个,并且增加了一个索引值 SkipChildLevelPointer 来实现映射关系(见索引文件的生成(三)),每一层的数值为 PackedBlock 中的最后一篇文档的文档号,例如 level=2 的三个数值 1151、2303、3455。

哨兵数组 skipDoc

  哨兵数组 skipDoc 的定义如下所示:

    int[] skipDoc;

  该数组用来描述每一层中正在处理的 datum,datum 对应的 PackedBlock 中的最后一篇文档的文档号作为哨兵值添加到哨兵数组中,在初始化阶段,skipDoc 数组中的数组元素如下所示(见图 2 红框标注的数值):

    int[] skipDoc = {127, 383, 1151, 3455}

  初始化阶段将每一层的第一个 datum 对应的 PackedBlock 中的最后一篇文档的文档号作为哨兵值。

docDeltaBuffer

  docDeltaBuffer 是一个 int 类型数组,总是根据 docDeltaBuffer 中的文档集合来判断 SkipList 中是否存在待处理的文档号。

  在初始化阶段,docDeltaBuffer 数组中的数组元素是 level=0 的第一个 datum 对应的 PackedBlock 中文档集合。

SkipList 在 Lucene 中的应用

  了解 SkipList 在 Lucene 中的应用对理解读取跳表 SkipList 的过程很重要,在 Lucene 中,使用 SkipList 实现文档号的递增遍历,每次判断的文档号是否在 SkipList 中时,待处理的文档号必须大于上一个处理的文档号,例如我们在文章文档号合并(SHOULD)中,找出满足查询要求的文档就是通过 SkipList 来实现。

Lucene 中使用读取跳表 SkipList 的过程

  读取过程分为下面三步:

  • 步骤一:获得需要更新哨兵值的层数 N
    • 从 skipDoc 数组的第一个哨兵值开始,依次与待处理的文档号比较,找出所有比待处理的文档号小的层
  • 步骤二:从 N 层开始依次更新每一层在 skipDoc 数组中的哨兵值
    • 如果待处理的文档号大于当前层的哨兵值,那么另当前层的下一个 datum 对应的 PackedBlock 中的最后一篇文档的文档号作为新的哨兵值,直到待处理的文档号小于当前层的哨兵值
    • 在处理 level=0 时,更新后的 datum 对应的 PackedBlock 中的文档集合更新到 docDeltaBuffer 中
  • 步骤三:遍历 docDeltaBuffer 数组
    • 取出 PackedBlock 中的所有文档号到 docDeltaBuffer 数组中,依次与待处理的文档号作比较,判断 SkipList 中是否存在该文档号

读取跳表 SKipList

  我们依次处理下面的文档号,判断是否在跳表 SKipList 中来了解读取过程:

    文档号{23, 700, 701, 3000}

文档号:23

  更新前的 skipDoc 数组如下所示:

    int[] skipDoc = {127, 383, 1151, 3455}

  当前 skipDoc 数组对应的 SkipList 如下所示:

图 2:

2.png

  由于文档号 23 小于 skipDoc 数组中的所有哨兵值,故不需要更新 skipDoc 数组中的哨兵值,那么直接遍历 docDeltaBuffer,判断文档号 23 是否在该数组中即可。



文档号:700

  更新前的 skipDoc 数组如下所示:

    int[] skipDoc = {127, 383, 1151, 3455}

  文档号 700 小于 1151、3455,执行了步骤一之后,判断出需要更新哨兵值的层数 N 为 2(两层),即只要从 level=1 开始更新 level=1 以及 level=0 对应的 skipDoc 数组中的哨兵值。

  对于 level=1 层,在执行了步骤二后,更新后的 skipDoc 数组如下所示:

    int[] skipDoc = {127, 767, 1151, 3455}

图 3:

3.png

  随后更新 level=0 层,在执行了步骤二后,更新后的 skipDoc 数组如下所示:

    int[] skipDoc = {767, 767, 1151, 3455}

图 4:

4.png

  这里要注意的是,level=0 层的 datum 更新过程如下所示:

图 5:

5.png

  从图 5 中可以看出,在更新的过程中,跳过了两个 datum,其原因是在图 3 中,当更新完 level=1 的 datum 之后,该 datum 通过它包含的 SkipChildLevelPointer 字段(见索引文件的生成(三))重新设置在 level=0 层的哨兵值,随后在处理 level=0 时,根据待处理的文档号继续更新哨兵值。

文档号:701

  更新前的 skipDoc 数组如下所示:

    int[] skipDoc = {767, 767, 1151, 3455}

  文档号 701 小于所有的哨兵值,所以直接遍历 docDeltaBuffer 数组即可。

文档号:3000

  不重复用文字描述其更新过程了,直接以下图给出每一层最终的哨兵值以及更新过程,自己品...,更新后的 skipDoc 数组如下所示:

    int[] skipDoc = {3071, 3071, 3455, 3455}

图 6:

6.png

结语

  可以看出,SkipList 在 Lucene 中的实现适用于存储有序递增的文档号,性能上取决于待处理的文档号在 datum 的分布,分布在越少的 datum,性能越高。


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