每周学点大数据 | No.27高维外存查找结构——KD 树

No.27期

高维外存查找结构——KD 树

Mr. 王：以往我们在数据结构中进行的查找，都是查找某一个键值或者某一个区间内的值，这样的查找称之为一维查找。

小可：难道说还有多维查找吗？

Mr. 王：现在我们就来介绍一种高维查找结构——KD 树。

小可：可是什么样的查找是高维查找呢？

Mr. 王：举个简单的例子。你平时会用到位置服务的App 吗？

小可笑着说：我今天中午还用大众点评查找过周围的饭店，饱餐了一顿呢。

Mr. 王：你的位置在定位系统和定位服务中就是一个坐标，这个坐标就是一个二维数据项。

你在查找周围的饭店时，就已经进行了一次二维空间内查找。我们现在要考虑的，就是如何能让计算机中存储的这种二维的点，并且可以以非常高的效率查找出来。

小可：原来是这样。那么如何来实现二维空间内的高效查找呢？

Mr. 王：计算机工作者们曾经提出过很多种二维空间内查找的方法，像网格文件、R 树、四叉树等，在实际应用中使用最多的应该是R 树。今天我们要讲的二维空间内查找结构叫作KD 树，之所以讲它，是因为它的性质比较容易保证。

小可：那什么又是KD 树呢？

Mr. 王：简单来说，KD 树很像是将两个二叉树叠在一起。考虑一下：当我们进行一维数据查找时，需要在一维上对数据进行索引，建立的就是一棵二叉查找树；而当我们要查找的点是一个二维数据时，就需要在两个数据维度上都建立索引，这时就需要两棵二叉树，这两棵二叉树分别索引的是x 轴和y 轴，我们可以在两棵轴上面进行二分搜索。而将两棵二叉树的层次交替存储，就合并成了KD 树。

小可：KD 树具体是如何定义的呢？

Mr. 王：在一棵KD 树上，我们用树的偶数层中的节点来表示空间中的水平线；相应地，我们用奇数层中的节点来表示空间中的垂直线；这些垂直线和水平线会对整个区域进行分割，直到点集被划分为每个区域内只有一个点为止。那么水平线和垂直线也就相应地对应着KD 树的内部节点，而在二维平面上，我们要检索的这些点就对应着KD 树的叶子节点。

小可带着疑惑的表情说：我还是不太明白。

Mr. 王：我们来举个例子吧。

左边是一棵KD 树，右边是一个二维平面。下面我们分步演示它的过程。

我们将树根定义为一条水平线，在区域中画下它代表的水平线。

下一层中的节点代表的是垂直线，我们在图中标示出这两条垂直线。

依此类推，这样所有的点都被放进了单独的一个区域里。也就是说，每一片叶子都已经仅仅代表一个节点，KD 树就建好了。

小可：哦，这样我就明白多了。那么对一棵建好的KD 树又是怎样进行查询的呢？

Mr. 王：在查询一棵KD 树时，我们会递归访问节点的相应交叉查询区域，并且报告在树/节点中且在查询中完全包含的点。

这样说太抽象了，我们还是举个具体的例子吧。看图中的绿色区域，在这个检索中，我们希望找出绿色区域中的点。

首先我们来看绿色区域的下界。

对一棵KD 树来说，它的根是一条水平线，我们就可以根据绿色区域的下界画一条水平线。

然后比较这条水平线和根的高低，在KD 树上，就是比较树根代表的水平线的高度值和检索区域的高度值。比如在这个例子中，我们发现根节点的高度比下界要高，这说明根节点的右子树一定都是候选集合，而根节点的左子树只有一部分是候选集合。

但是为了确定这一部分，我们就要访问它的左子树。然而树的第1 层（根是第0 层）是用来表示垂直线的，我们无法用它来判断水平维度的高低。我们再去访问第2 层，在第2 层中，可以用这个下界和第2 层中的两个节点进行比较，从而得出下一次，我们继续向右子树查找。

同理，我们可以不断地用区域的四个边界在树上进行查找，根据树的层次交替采用横纵的线条树上查找，直到最终确定绿色区域内部所有的点，也就是KD 树上的叶子节点。

现在我们来考虑一下KD 树的查询效率如何。现在你觉得这棵树是不是适合磁盘存储呢？

小可：虽然KD 树来用特殊的设计有效地表示了空间中的二维点，在设计思想上非常的巧妙，但是从本质上说，依然是一棵二叉树，它依然存在着二叉树不适合存储在磁盘上的问题，比如有旋转调整这样的麻烦。

Mr. 王：的确。由于KD 树同样具有二叉查找树的种种性质，所以也就同样存在二叉查找树在磁盘上存储种种不方便的问题。不过正是由于它和二叉树相似，所以我们不妨也采取和二叉树相似的改进方法。为了将查找树结构引入到磁盘上，我们引入了B 树。这次我们也可以发展KD 树，引入一种适合存储在硬盘上的数据结构——kdB 树。

小可：kdB 树是不是就是把KD 树和B 树融合到一起啊？

Mr. 王：是的，kdB 树结合了KD 树和B 树的思想，使得KD 树更加适合磁盘存储。在具体的实现中，逻辑结构依然采用KD 树，当叶子包含B/2 到B 个点时停止分割。在内部节点的BFS 块。

小可：那么如何在计算机中实际构建一个kdB 树呢？

Mr. 王：其实如果不考虑复杂度的话，这个算法还是很容易设计的。首先从所有的点中找到纵坐标y 轴的中位数，以这个中位数作为根节点的值。然后分别在两个区域中，寻找x 轴的中位数，这样就又画出了第二级中的两条垂直线，也就得到了树的第二层中的两个节点的值。

依此类推，递归地在新划分出来的区域中交替寻找x 轴和y 轴的中位数，这样KD 树就建好了。当然，我们还要将一定大小（数量）的节点像B 树一样封装在BFS 块中，这样kdB 树也就建好了。

这个算法是比较直观的，它的复杂度是

，不过它还是有一定的可优化空间的，我们还能给出一个更快的算法，其基本思想就是尝试对全体扫描一次完成构建

层，而不是像现在一样只构建一层。

小可：这里面数学符号太多了，没听懂。

Mr. 王：我们先来看看这个算法是怎么做的吧。

内容来源：灯塔大数据