Bkd-Tree

Bkd-Tree 作为一种基于 K-D-B-tree 的索引结构，用来对多维度的点数据(multi-dimensional point data)集进行索引。Bkd-Tree 跟 K-D-B-tree 的理论部分在本篇文章中不详细介绍，对应的两篇论文在附件中，感兴趣的朋友可以自行下载阅读。本篇文章中主要介绍 Bkd-Tree 在 Lucene 中的实现，即生成树的过程。

预备知识

如果只是想了解 Bkd-Tree 生成过程，那么这节内容可以跳过，这块内容是为介绍索引文件。dim、.dii 作准备的。

点数据

点数据(Point Data)，源码中又称为点值(Point Value)，它是由多个数值类型组成。
图 1：

上图中由 4 个 int 类型数值组成一个点数据/点值，并且根据点数据中的数值个数定义了维度个数。上图中即有四个维度。同一个域名的点数据必须有相同的维度个数，并且在当前 7.5.0 版本中，维度个数最多为 8 个。

int numPoints

numPoints 是一个从 0 开始递增的值，可以理解为是每一个点数据的一个唯一编号，并且通过这个编号能映射出该点数据属于哪一个文档(document)。映射关系则是通过 docIDs[ ]数组实现。

int docIDs[ ]数组

docIDs[ ]数组在 PointValuesWriter.java 中定义，数组下标是点数据的编号 numPoint，数组元素是点数据所属的文档号。由于一篇文档中可以有多个点数据，所以相同的数组元素对应的多个数组下标值，即 numPoints，即点数据，都是属于同一个文档。
图 2：

上图中只添加了 2 篇文档，处理顺序按照文档号的顺序，所以文档 0 的点数据的 numPoints 的值为 0，另外一篇文档可以有多个点数，所以 numPoints 的值分别为 1、2。生成的 docIDs[]数组如下：
图 3：

int ord[ ]数组

ord 数组的数组元素为 numPoints，下面的一句话很重要：ord 数组中的元素是有序的，排序规则不是按照 numPoints 的值，而是按照 numPoints 对应的点数据的值。这里 ord 数组的用法跟 SortedDocValues 中的 sortedValues[]数组是一样的用法。例如根据图 2 中的点数据，如果我们按照第三个维度的值，即"99"、"23"、"12"来描述点数据的大小关系，那么 ord 数组如下图所示：
图 4：

这里先提一句，在生成 BKD-Tree 之后，叶子节点中的点数据会根据某个维度进行排序的，并且所有叶子节点中的点数据的大小关系就存放在 ord[]数组中，后面的内容会详细介绍这过程。

流程图

一句话概括整个流程的话就是：根据某一个维度将点数据集划分为两部分，递归式将两部分的点数据子集进行划分，最终生成一个满二叉树。
图 5：

点数据集

图 6：

点数据集即为待处理的点数据集合。

是否要切分？

图 7：

如果数据集的个数大于 1024 个，那么需要进行拆分。在源码中并不是通过判断数据集的个数，而是在建立 Bkd-Tree 之前就预先计算出当前数据会对应生成节点(node)的个数（可以认为每个节点中的数据都是空的），然后采用深度遍历方式处理每一个节点，通过节点编号来判断是否为叶子节点。如果不是叶子节点，说明要切分(节点赋值)。

选出切分维度

图 8：

一个点数据中有多个维度，例如图 1 中就有四个维度。

• 本文地址：Lucene 源码分析——BKD-Tree
• 本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

1. 先计算出切分次数最多的那个维度，切分次数记为 maxNumSplits，如果有一个维度的切分次数小于 (maxNumSplits / 2) ，并且该维度中的最大跟最小值不相同，那么令该维度为切分维度。
2. 计算出每一个维度中最大值跟最小值的差值，差值最大的作为切分维度(篇幅原因，下面的例子中仅使用了这种判定方式)。

条件 1 优先条件 2。

点数据集排序

图 9：

当确定了切分维度后，我们对当前节点中的点数据集进行排序，排序规则根据该每个点数据中的该维度的值，排序算法使用最大有效位的基数排序(MSB radix sort)。

切分出左子树点数据集、切分出右子树点数据集

图 10：

执行完排序操作后，当前节点中的点数据集数量为 N，那么将前 (N / 2)个的点数据集划分为左子树，剩余的划分为右子树。
这么划分的目的使得无论初始的点数据集是哪种数据分布，总是能生成一颗满二叉树。

是否退出

图 11：

当前节点不需要切分，需要判断下算法是否需要退出。

结束

• 当前节点是满二叉树的最右子树，那么算法结束，可以退出。
• 当前树中只有一个节点，且该节点不需要切分，那么算法结束，可以退出。

返回上一层

• 当前处理的节点是左子树节点或者是非最右子树节点，说明该节点是由 划分左右子树生成的，即算法还处在递归中，当不需要划分后，返回到递归的上一层。

例子

Lucene 7.5.0 版本源码中当一个节点中的点数据个数大于 1024 才会进行切分，为了能简单示例，例子中假设一个节点中的点数据个数大于 2 个才会进行切分，并且点数据的维度为 2。

点数据集

图 12：

上图中一共有 8 个点数据，每个点数据有两个维度。为了描述方便，下面统称为 x 维度，跟 y 维度。

处理节点 1

• 是否要切分：初始的数据集作为第一个节点，即节点 1 开始进行切分，该节点中有 8 个数据，大于节点切分的条件值 2，所以需要切分。
• 选出切分维度：x 维度的最大值跟最小值的差值为 7 ，而 y 维度的最大值跟最小值的差值为 9，所以当前节点的切分维度为 y 维度。
• 点数据排序：对 8 个点数据按照 y 维度的值进行排序，排序后的结果如下：

{1,2} -> {4,3} -> {3,4} -> {4,6} -> {6,7} -> {2,8} -> {8,9} -> {7,11}

• 切分出左子树数据集、切分出右子树数据集：当前节点个数为 8，从排序后的点数据中取前一半的点数据划为左子树(节点 2)，剩余的划为右子树(节点 3)。

左子树：{1,2}、{4,3}、{3,4}、{4,6}
右子树：{6,7}、{2,8}、{8,9}、{7,11}

图 13：

处理节点 2

• 是否要切分：节点 2 中有 4 个数据，大于节点切分的条件值 2，所以需要切分。
• 选出切分维度：x 维度的最大值跟最小值的差值为 3 ，而 y 维度的最大值跟最小值的差值为 4，所以当前节点的切分维度为 y 维度。
• 点数据排序：对 4 个点数据按照 y 维度的值进行排序，排序后的结果如下：

{1,2}、{4,3}、{3,4}、{4,6}

• 切分出左子树数据集、切分出右子树数据集：当前节点个数为 4，从排序后的点数据中取前一半的点数据划为左子树(节点 4)，剩余的划为右子树(节点 5)。

左子树：{1,2}、{4,3}
右子树：{3,4}、{4,6}

图 14：

处理节点 4、5

源码中对叶子结点还有一些处理，目的是为了生成索引文件作准备，在随后的介绍索引文件。dii、.dim 时候会介绍跟叶子节点相关的知识，这篇文章主要介绍生成 Bkd-Tree 的过程。

处理节点 3

• 是否要切分：节点 3 中有 4 个数据，大于节点切分的条件值 2，所以需要切分。
• 选出切分维度：x 维度的最大值跟最小值的差值为 6 ，而 y 维度的最大值跟最小值的差值为 4，所以当前节点的切分维度为 x 维度。
• 点数据排序：对 4 个点数据按照 x 维度的值进行排序，排序后的结果如下：

{2,8}、{6,7}、{7,11}、{8,9}

• 切分出左子树数据集、切分出右子树数据集：当前节点个数为 4，从排序后的点数据中取前一半的点数据划为左子树(节点 6)，剩余的划为右子树(节点 7)。

左子树：{2,8}、{6,7}
右子树：{7,11}、{8,9}

图 15：

处理节点 6、7

同节点 4、5

结语

本篇文件介绍了 Bkd-Tree 在 Lucene 中的实现，即生成满二叉树的过程，再以后介绍索引文件。dii、.dim 中会继续讲一些细节的东西。另外在随后的文章中会介绍 Bkd-Tree 插入和更新的内容。

原文地址：https://www.amazingkoala.com.cn/Lucene/gongjulei/2019/0422/52.html