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

例子

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

图 1：

  在图 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 的定义如下所示：

1

    int[] skipDoc;

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

1

    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 中来了解读取过程：

1

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

文档号