本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：
“转自：灯塔大数据；”
编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！
上期回顾查看方式：
在上一期中，我们介绍了一种性质非常好的数据结构——外存数据结构B树，通过例子来说明它的插入和删除。在本期，我们将介绍一种高维查找结构——KD树，并讲解如何在计算机中实际构建一个kdB树。
PS：了解上期详细内容，请在自定义菜单栏中点击“文章精选”—“文章连载”，进行查看。
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.王：我们先来看看这个算法是怎么做的吧。
下期精彩预告：
经过学习，我们介绍了一种高维查找结构——KD树，并讲解了如何在计算机中实际构建一个kdB树，在下一期中，我们将介绍关于磁盘中图算法的问题，通过详细介绍“独立集”来解释一种基础的算法——“表排序”。更多精彩内容，敬请