SDBMS-基于二叉树的空间索引.ppt

基于二叉树的空间索引技术 —以kd-树为例 二叉查找树 二叉查找树是一种基本的索引数据结构，在随机的情况下，其平均查找时间为1+4logn；平衡二叉树的平均查找长度为logn，它具有很好的查找性能。因此，二叉查找树被采纳并得到推广，用于重复地划分数据空间，以期达到缩短查找时间、提高空间查找性能的目的。 目前，基于二叉树的索引技术主要有kd-树、K-D-B树、hB-树等。 kd-树的定义 kd-树(J.L.Bentley,1975)是k(k≥2) 维的二叉查找树（BST）, 是二叉查找树在多维空间的扩展。主要用于索引多属性的数据或多维点数据。 与BST不同的是，kd-树每一个结点表示k维空间的一个点，并且树的每一层都根据这一层的分辨器（discrimi-nator）做出分枝决策。kd-树的第i层的分辨器定义为i mod k（树的根结点所在层为第0层，根结点孩子所在层为第1层，依次递增）。 Kd-树的具体构建 Kd-树或者是一棵空树，或者是一棵具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的第d维的值均小于它根结点的第d维的值（其中d为根结点的分辨器值）； （2）若它的右子树不空，则右子树的所有结点的第d维的值均大于它根结点的第d维的值（其中d为根结点的分辨器值）； （3）左右子树也分别为kd-树。 Kd-树的查找 对于点的精确匹配查找，kd-树的查找过程与BST类似，不同的是分枝决策时需要考虑分辨器的值。例如要在图2的kd-树中查找点P(30,90)。首先，将P点坐标与根结点A(40,60)比较，如匹配则检索成功。在这个例子中不成功，则须比较P与A的x维的值（x为A的分辨），由于3040，由此进入A的左子树进行查找；比较P与B(10,75)的y维的值（y为B的分辨器），由于9075，由此进入B的右子树进行查找；比较P与D的坐标，匹配，检索成功。 区域查找与点的匹配查找过程类似，不同的是查找路径往往有多条。例如在图2中，查找落入矩形QR的所有点，有两条查找路径： (1)A → B → C → I；(2)A → E。查找结果为I与E。 kd-树查找的具体过程 待查找点P(30,90) kd-树的插入 向kd-树中插入一个新结点类似于BST的插入过程。插入的原则是若kd-树为空，则插入结点为新的根结点，否则继续在其左子树或右子树中查找，直到某个叶子结点的左子树或右子树空，插入结点作为一个新的叶子结点并成为该叶子结点的左孩子或右孩子。 图2中kd-树是点A、B、C、D、E、F、G、H、I依次插入的结果。当插入A时，由于kd-树为空，因此A成为根结点；插入B时，首先查找到结点A，由于B的x维的值比A小,因此B成为A的左孩子点，依此类推。 kd-树插入的具体过程 Kd-树为空 kd-树的删除 从kd-树中删除一个结点与从BST中删除一个结点类似，但却要复杂很多。这是因为kd-树中有分辨器参与分枝决策，删除一个结点时必须不违背kd-树的原则。 删除过程大致如下：先找到要删除的结点（设为N，并设N的分辨器的值为d），然后分三种情况处理： （1）如果N没有孩子结点，则将其父结点中指向N的指针域置空（如果N的父结点存在的话），并删除该结点； （2）如果结点N有右孩子，则从其右子树中找到第d维值最小的结点（设为N1）来代替结点N，然后再以与删除N相同的方法删除N1； （3）如果结点N只有左孩子，则从其左子树中找到第d维值最大的结点（设为N2）来代替结点N，然后再以与删除N相同的方法删除N2。 kd-树删除的具体过程 要删除E kd-树删除异常的问题 但是，用左子树中第d维值最大的结点N2代替结点N（即第三种情况）可能引起错误。因为在N的左子树中，对于第d维而言，可能有多个结点具有与N2相同的值。用N2代替N将违反kd-树的排序规则（用N2代替N以后，N2的左子树中具有与其第d维相同的结点）。例如在图3中，如果删除B时从其左子树中找出y维值最大的结点（无论是F或G）代替B都将违反kd-树的规则。所以，对于结点N只有左孩子的情况需要另外寻求解决办法。 小结与分析 从以上的介绍可知，kd-树是二叉查找树在多维空间的扩展。对于精确的点匹配查找，它继承了二叉查找树的优点，即平均查找长度为1+4logn。 但是当删除kd-树的中间结点时，处理过程特别复杂，时间开销很大。 此外，kd-树平衡化也是一个非常复杂的过程。 Kd-树是为索引空间点或多属性数据而提出的。如果索引其他非点状空间目标，则须采用目标近似与映射的方法。即先将任意空间目标用其MBR近似表示，并将其MBR映射为2k维空间的点进行索引。例如：对于二维空间矩形x1,y1,x2,y2，可以变换为四维空间的点，然