本文承接索引文件的生成（十一），继续介绍剩余的内容，为了便于下文的介绍，先给出生成索引文件.dim&&.dii 的流程图以及流程点构建 BKD 树的节点值（node value）的流程图：

图 1：

图 2：

  在前面的文章中，我们介绍了图 2 中处理内部节点的所有流程点，在介绍处理叶子节点前，我们先填个坑，即当某个内部节点划分后生成的左右子树为叶子节点时，内部节点为左右子树提供哪些准备数据，即流程点 设置左子树的准备数据、设置右子树的准备数据。

设置左子树的准备数据、设置右子树的准备数据

左右子树为叶子节点

  在文章索引文件的生成（十一）之 dim&&dii 中我们提到，处理节点（叶子节点或者内部节点）需要的准备数据有好几个，这些准备数据在源码中其实就是 https://github.com/LuXugang/Lucene-7.5.0/blob/master/solr-8.4.0/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java 类中的 build(...)方法的参数：

图 3：

  对于左右子树为叶子节点的情况，我们只需要关心图 3 中的 leafBlockFPs 数组。

leafBlockFPs 数组

  每当处理完一个叶子节点，我们需要将叶子节点对应的信息写入到索引文件。dim 中，又因为所有叶子节点对应的信息以字节流形式存储在索引文件。dim 中，leafBlockFPs 数组正是用来记录每一个叶子节点对应的信息在索引文件。dim 中的起始位置，同样具体的内容将在下文中展开。

选出叶子节点的排序维度

图 4：

  选出叶子节点的排序维度前需要先计算两个数组：commonPrefixLengths 数组以及 usedBytes 数组。

commonPrefixLengths 数组

  commonPrefixLengths 为 int 类型的数组，该数组的下标用来描述维度编号（见文章索引文件的生成（十）之 dim&&dii），数组元素描述的是维度编号对应的所有维度值的最长公共前缀的长度。

usedBytes 数组

  usedBytes 为 FixedBitSet 类型数组，如果你不熟悉 FixedBitSet 对象也没关系，我们只需要知道 usedBytes 数组的下标同样用来表示维度编号，数组元素描述的是维度编号的对应的所有维度值的公共前缀后的下一个字节的种类数量（按照字节的不同值作为种类的划分），只是种类数量用 FixedBitSet 来统计而已。

图 5：

  假设叶子节点中有 3 个点数据，我们以维度编号 2 为例，图 4 中，点数据蓝色部分的字节是相同的，即点数据在这个维度的维度值的最长公共前缀的长度为 2（2 个字节），即在 commonPrefixLengths 数组中，下标值为 2 的数组元素的值为 3，其他维度同理，故 commonPrefixLengths 数组如下所示：

图 6：

  同样以维度编号 2 为例，除去相同的 2 个前缀字节的下一个字节的种类数量如图 4 中绿框与红框标注共有 2 个种类，即有两种，其他维度同理，故 usedBytes 数组如下所示：

图 7：

  在源码实现上，需要先计算出 commonPrefixLengths 数组，利用该数组再计算出 usedBytes 数组。

  在计算出 usedBytes 数组之后，遍历该数组，找到第一个数组元素最小的值，对应的数组下标，即维度编号，作为叶子节点的排序维度，在图 6 中，编号维度 1 将作为排序维度。

叶子节点的排序

图 8：

  使用内省排序（IntroSorter）对叶子节点中的点数据进行排序，而不是在文章索引文件的生成（十）之 dim&&dii 中提到的内部节点排序使用的最大有效位的基数排序(MSB radix sort)，源码中也给出了注释：

No need for a fancy radix sort here, this is called on the leaves only so there are not many values to sort

  简单来说就是叶子节点中的点数据的数量相对于内部节点较少而选择使用内省排序（IntroSorter）。

  叶子节点中的点数据数量的取值范围是什么

• 本文地址：Lucene 源码系列——索引文件的生成（十二）之 dim&&dii
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

  先给出源码中的注释：

The tree is fully balanced, which means the leaf nodes will have between 50% and 100% of the requested maxPointsInLeafNode

  上述注释中的 maxPointsInLeafNode 指的是叶子节点中最多包含的点数据数量，默认是 1024，也就说当内部节点中的点数据数量大于 1024 个时就需要继续切分，那么叶子节点中包含的点数据的数量区间为 [512, 1024]。

  同内部节点的排序一样，叶子节点中点数据之间的排序关系同样用 ord 数组（见文章索引文件的生成（十）之 dim&&dii）来描述，不赘述。

更新 leafBlockFPs 数组

图 9：

  到此流程点，我们即将开始把叶子节点的信息写入到索引文件。dim 中，故需要将索引文件。dim 当前可写入的位置记录到 leafBlockFPs 数组中，在读取阶段，就可以通过 leafBlockFPs 数组找到当前叶子节点的信息在索引文件。dim 中的起始读取位置，如下所示：

图 10：

  图 10 中，leafNodeData 为叶子节点的信息，leafBlockFPs 数组的下标值为叶子节点的差值节点编号。

  差值节点编号是什么

  在文章索引文件的生成（十）之 dim&&dii 我们介绍了节点编号的概念以及最左叶子节点的节点编号的获得方式，差值节点编号值的就是叶子节点编号跟最左叶子节点的节点编号的差值：

leafBlockFPs[nodeID - leafNodeOffset]

  上述代码中，nodeID 即节点编号，leafNodeOffset 为最左叶子节点的节点编号，如果当前处理的是最左叶子节点，那么差值节点编号为 0 ，即下标值为 0，那么对应的数组元素描述的就是最左叶子节点的信息在索引文件。dim 中的起始读取位置。

写入文档号信息到索引文件。dim 中

图 11：

  该流程点描述是将叶子节点中的点数据对应的文档号写入到索引文件。dim 中。

  如果获得每个点数据对应的文档号

  在文章索引文件的生成（八）之 dim&&dii 中我们说到，在点数据的收集阶段，使用了 docIDs 数组存储了文档号信息，该数组的数组元素为文档号，下标值为 numPoints，那么我们只需要知道点数据对应的 numPoints 就可以获取点数据对应的文档号，而在 ord 数组（见文章索引文件的生成（十）之 dim&&dii）中，数组元素正是 numPoints，所以我们只要遍历 ord 数组就能获得当前叶子节点中的文档号信息，并且这些文档号是有序的，注意的是：不是文档号的值有序，而是文档号对应的点数据是有序，排序规则即上文中的流程点 选出叶子节点的排序维度、叶子节点的排序 中的内容。

图 12：

  叶子节点中包含的文档号信息在索引文件。dim 中的位置如下所示：

图 13：

  上图中，红框标注的两个字段为当前流程点写入的信息，其中 Count 描述的是文档号的数量，DocIds 为文档号的集合。DocIds 的详细数据结构见文章索引文件之 dim&&dii 。

写入相同前缀信息到索引文件。dim 中

图 14：

  在当前流程点，我们根据在上文中计算出的 commonPrefixLengths 数组，将每个维度的最长相同前缀的值写入到索引文件。dim 中，对应在索引文件。dim 中的位置如下所示：

图 15：

  上图中，Length 描述的每一个维度的最长公共前缀的长度，Value 为最长公共前缀的值，在读取阶段就可以根据 Length 的值确定 Values 在索引文件。dim 中的位置区间。

  以图 5 的维度编号 2 为例，Length 跟 Value 的值如下所示：

Length: 2
Value: {10000000, 00000000}

结语

  基于篇幅，剩余的内容将在下一篇文章中展开。