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

在文章索引文件的生成(一)中我们说到,在生成索引文件.doc.pos、.pay 的过程中,当处理了 128 篇文档后会生成一个 PackedBlock,并将这个 PackedBlock 的信息写入到跳表 skipList 中,使得在读取阶段能根据文档号快速跳转到目标 PackedBlock,提高查询性能。

  将 PackedBlock 的信息写入到跳表 skipList 的时机点如下图红色框所示:

图 1:

1.png

  本篇文章介绍下 skipList 的写入/读取的过程,在介绍之前,我们先大致的描述下跳表是什么,如下图所示:

图 2:

2.png

  图 2 中每一层中的数值描述的是信息的编号,例如在 level=0 中的数值"3"描述的是第 3 条信息,在写入的过程中,每处理 skipMultiplier 个信息就在上一层生成一个索引,例如在 level=1 中的第 6 条信息中有一个索引,他指向 level=0 的一个位置;level=2 中的第 38 条信息,它包含一个索引,指向 level=1 中的一个位置。由此可见跳表是一个多层次的数据结构,除了第 0 层外,其他层中的每一条信息中拥有一个指向下一层的索引。

  接着我们开始介绍在 Lucene 中如何生成以及读取 SkipList。

写入到跳表 skipList 中的流程图

图 3:

3.png

初始化

图 4:

4.png

  需要初始化的内容如下所示:

  • skipInterval:该值描述了在 level=0 层,每处理 skipInterval 篇文档,就生成一个 skipDatum,该值默认为 128
  • skipMultiplier:该值描述了在所有层,每处理 skipMultiplier 个 skipDatum,就在上一层生成一个新的 skipDatum,该值默认为 8

  skipInterval、skipMultiplier、skipDatum 的关系在索引文件.doc 中的关系如下所示:

图 5:

5.png

  • numberOfSkipLevels:该值描述的是我们即将生成的 skipList 中的层数,即图 2 中的 level 的最大值

如何计算 numberOfSkipLevels

  根据上文中,skipInterval 跟 skipMultiplier 的介绍,可以看出我们根据待处理的文档数量就可以计算出 numberOfSkipLevels,计算公式如下:

    int numberOfSkipLevels = 1 + MathUtil.log(df/skipInterval, skipMultiplier)

  上述公式中,df(document frequency)即待处理的文档数量。

待处理的文档数量是如何获得的

  在索引文件的生成(一)中我们介绍了生成索引文件.doc 的时机点,即在 flush 阶段,所以就可以根据的段的信息获得待处理的文档数量。



  • skipBuffer[ ]数组:该数组中存放的元素为每一层的数据,根据图 2 可以知道,该数据就是 SkipDatum 的集合,并且数组的元素数量为 numberOfSkipLevels,skipBuffer[ ]中每一个元素在索引文件.doc 中对应为一个 SkipLevel 字段,如下所示:

图 6:

6.png

计算写入的层数 numLevels

图 7:

7.png

  根据当前已经处理的文档数量,预先计算出将待写入 SkipDatum 信息的层数,计算方式如下:

int numLevels = 1;
// 计算出在level=0层有多少个SkipDatum
df /= skipInterval;
while ((df % skipMultiplier) == 0 && numLevels < numberOfSkipLevels)
{
    numLevels++;
    // 每skipMultiplier个SkipDatum就在上一层生成一个SkipDatum
    df /= skipMultiplier;
}

是否还有未处理的层?

图 8:

8.png

  在上一个流程中,如果 numLevels 的值 > 1,那么按照 level 从小到大依次处理。

层内处理

图 9:

9.png

  在 层内处理 的流程中,首先将在图 1 中 是否生成了PackedBlock 流程中生成的 block 信息生成一个 SkipDatum 写入到 skipData 中,block 包含的信息如下图红框所示:

图 10:

10.png

  另外,在图 10 中,如果在 level>0 的层写入一个 SkipDatum 后,相比较在 level=0 中的 SKipDatum,它多了一个字段 SkipChildLevelPointer,它是一个指针,指向下一层的一个 SkipDatum。

  SkipDatum 中的字段含义在文章索引文件之.doc 中已经介绍,不赘述,另外图 10 中的 SkipDatum 中的信息除了 SkipChildLevelPointer,其他所有的字段都是用差值存储,所以在图 9 中,我们需要执行 记录当前层的skipData信息 的流程,使得下一个同一层内的新生成的 SkipDatum 可以用来进行差值计算。

SkipDatum 中的字段干什么用的

  这些字段的作用正是用来展示跳表 SkipList 跳表在 Lucene 中的功能,它们作为指针来描述当前 block 在的其他索引文件中的位置信息。在文章索引文件的生成(二)中我们介绍图 1 中的 处理完一篇文档后的工作 流程点时,说到在该流程点生成了几个信息,他们跟 SkipDatum 中的字段的对应关系如下:

  • lastBlockDocID:记录刚刚处理完的那篇文档的文档号,即 DocSkip
  • lastBlockPayFP:描述是处理完 128 篇文档后,在索引文件。pay 中的位置信息,即 PayFPSkip
  • lastBlockPosFP:描述是处理完 128 篇文档后,在索引文件。pos 中的位置信息,即 PosFPSkip
  • lastBlockPosBufferUpto:在 posDeltaBuffer、payloadLengthBuffer、offsetStartDeltaBuffer、offsetLengthBuffer 数组中的数组下标值,即 PosBlockOffset
  • lastBlockPayloadByteUpto:在 payloadBytes 数组中的数组下标值,即 PayLength

  另外还有 DocFPSkip 值并没有在 处理完一篇文档后的工作 流程中获取,该值描述的是在索引文件.doc 当前可写入的位置,故直接可以获取。

  SkipDatum 中的字段与索引文件.doc、.pos、.pay 的关系如下所示:

图 11:

11.png

  图 10 中,由于是按照每处理 128 篇文档才执行 写入到跳表skipList中 的流程,那么有可能此时位置信息 position、偏移信息 offset,payload 信息没有生成一个 PackedBlock,那么 SkipDatum 需要两个指针的组合才能找到在索引文件。pos、.pay 中的位置,比如说我们需要 PosFPSkip+PosBlockOffset 的组合值才能找到位置信息(没明白的话说明你没有看文章索引文件的生成(一)以及索引文件的生成(二)

结语

  基于篇幅,读取的 SkipList 的逻辑将在下一篇文章中展开。


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