Lucene 源码系列——索引文件的生成（三）之跳表 SkipList
在文章索引文件的生成（一）中我们说到，在生成索引文件.doc、.pos、.pay 的过程中，当处理了 128 篇文档后会生成一个 PackedBlock，并将这个 PackedBlock 的信息写入到跳表 skipList 中，使得在读取阶段能根据文档号快速跳转到目标 PackedBlock，提高查询性能。
将 PackedBlock 的信息写入到跳表 skipList 的时机点如下图红色框所示：
图 1：
本篇文章介绍下 skipList 的写入/读取的过程，在介绍之前，我们先大致的描述下跳表是什么，如下图所示：
图 2：
图 2 中每一层中的数值描述的是信息的编号，例如在 level=0 中的数值"3"描述的是第 3 条信息，在写入的过程中，每处理 skipMultiplier 个信息就在上一层生成一个索引，例如在 level=1 中的第 6 条信息中有一个索引，他指向 level=0 的一个位置；level=2 中的第 38 条信息，它包含一个索引，指向 level=1 中的一个位置。由此可见跳表是一个多层次的数据结构，除了第 0 层外，其他层中的每一条信息中拥有一个指向下一层的索引。
接着我们开始介绍在 Lucene 中如何生成以及读取 SkipList。
写入到跳表 skipList 中的流程图
图 3：
初始化
图 4：
需要初始化的内容如下所示：
- skipInterval：该值描述了在 level=0 层，每处理 skipInterval 篇文档，就生成一个 skipDatum，该值默认为 128
- skipMultiplier：该值描述了在所有层，每处理 skipMultiplier 个 skipDatum，就在上一层生成一个新的 skipDatum，该值默认为 8
skipInterval、skipMultiplier、skipDatum 的关系在索引文件.doc 中的关系如下所示：
图 5：
- 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：
计算写入的层数 numLevels
图 7：
根据当前已经处理的文档数量，预先计算出将待写入 SkipDatum 信息的层数，计算方式如下：
int numLevels = 1;
// 计算出在level=0层有多少个SkipDatum
df /= skipInterval;
while ((df % skipMultiplier) == 0 && numLevels < numberOfSkipLevels)
{
numLevels++;
// 每skipMultiplier个SkipDatum就在上一层生成一个SkipDatum
df /= skipMultiplier;
}
是否还有未处理的层？
图 8：
在上一个流程中，如果 numLevels 的值 > 1，那么按照 level 从小到大依次处理。
层内处理
图 9：
在 层内处理 的流程中，首先将在图 1 中 是否生成了PackedBlock 流程中生成的 block 信息生成一个 SkipDatum 写入到 skipData 中，block 包含的信息如下图红框所示：
图 10：
另外，在图 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：
图 10 中，由于是按照每处理 128 篇文档才执行 写入到跳表skipList中 的流程，那么有可能此时位置信息 position、偏移信息 offset，payload 信息没有生成一个 PackedBlock，那么 SkipDatum 需要两个指针的组合才能找到在索引文件。pos、.pay 中的位置，比如说我们需要 PosFPSkip+PosBlockOffset 的组合值才能找到位置信息（没明白的话说明你没有看文章索引文件的生成（一）以及索引文件的生成（二））
结语
基于篇幅，读取的 SkipList 的逻辑将在下一篇文章中展开。
