理解KD树

  • 时间:
  • 来源:互联网

1. 概述

KD树是一种查询索引结构,广泛应用于数据库索引中。从概念的角度讲,它是一种高纬数据的快速查询结构,本文首先介绍1维数据的索引查询,然后介绍2维KD树的创建和查询,相关定理和推论也简单列出,本文争取用15分钟的时间,让大家快速理解KD树。

2. 1维数据的查询

假设在数据库的表格T中存储了学生的语文成绩chinese、数学成绩math、英语成绩english,如果要查询语文成绩介于30~93分的学生,如何处理?假设学生数量为N,如果顺序查询,则其时间复杂度为O(N),当学生规模很大时,其效率显然很低,如果使用平衡二叉树,则其时间复杂度为O(logN),能极大地提高查询效率。平衡二叉树示意图为:


图1:平衡二叉树示意图

对于1维数据的查询,使用平衡二叉树建立索引即可。如果现在将查询条件变为:语文成绩介于30~93,数学成绩结余30~90,又该如何处理呢?

如果分别使用平衡二叉树对语文成绩和数学成绩建立索引,则需要先在语文成绩中查询得到集合S1,再在数学成绩中查询得到集合S2,然后计算S1和S2的交集,若|S1|=m,|S2|=n,则其时间复杂度为O(m*n),有没有更好的办法呢?

3. KD树

针对多维数据索引,是否也存在类似的一维的索引方法呢?先看2维数据的集合示意图:

图2: 2维数据示意图

如果先根据语文成绩,将所有人的成绩分成两半,其中一半的语文成绩<=c1,另一半的语文成绩>c1,分别得到集合S1,S2;然后针对S1,根据数学成绩分为两半,其中一半的数学成绩<=m1,另一半的数学成绩>m1,分别得到S3,S4,针对S2,根据数学成绩分为两半,其中一半的数学成绩<=m2,另一半的数学成绩>m2,分别得到S5,S6;再根据语文成绩分别对S3,S4,S5,S6继续执行类似划分得到更小的集合,然后再在更小的集合上根据数学成绩继续,...

上面描述的就是构建KD树的基本思路,其构建后的KD树如下图所示:


图3: KD树示意图

如图所示,l1左边都是语文成绩低于45分,l1右边都是语文成绩高于45分的;l2下方都是语文成绩低于45分且数学成绩低于50分的,l2上方都是语文成绩低于45分且数学成绩高于50分的,后面以此类推。下面的图示,更清晰地表示了KD树的结构及其对应的二叉树:


图4: KD树及对应的二叉树

在了解了KD树的基本原理后,剩下的工作就是如何构建KD树以及如何在KD树上查询了。

3.1 KD树构建算法

相对而言,构建KD树是针对高维数据,需要针对每一维都进行二分,针对二维数据的KD树构建算法如下图5所示:


图5:KD树构建算法

其中的P表示待构建的元素集合,depth表示当前是KD树的第几层,如果depth是偶数,通过纵向线对集合进行划分;如果depth是奇数,通过横向线进行划分(3~5行);第6、7行递归进行KD树中子树的构建。

本文链接http://element-ui.cn/news/show-1176.html