gis空间数据库索引技术.ppt.pptVIP

空间数据库技术的现状与展望 ——空间数据库索引 组员：汪军林，邓丁杰，白利锋 任云志，毛盈方 一、空间数据库索引 传统的数据库索引技术包括了B树、B+树、二叉树、哈希索引等，都是针对一维属性数据的主关键字索引而设计的。 空间数据库索引基于这些技术分别取得了发展。 空间索引大致分为四大类： 1.基于二叉树的索引技术 2.基于B树的索引技术 3.基于哈希的格网技术 4.空间目标排序法 1.基于二叉树的索引技术 主要有Kd树、KDB树等。 其中，典型的Kd树是一种二分索引树结构，主要用于索引多维数据点，但对于复杂的空间目标，如折线、多边形等必须采用近似方法和空间映射技术。 为了能索引复杂的空间目标，Mkd树被提出；为了将Kd树存储到外存，将Kd树与B树结合，得到KDB树。 所有的方法对于非点状空间目标的索引效率都很低。 2.基于B树的索引技术 目前很多空间数据索引技术，都是B树发展来的。例如R树、 R+树、R*树等。 利用最小外包矩形表示空间目标。 3.基于哈希的格网技术 基本思路是将索引空间划分为相等或不相等的一些小方格网，与每个格网相关连的空间目标则存在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。 4.空间目标排序法 将多维空间映射为一维空间，包括了Z序、Hilbert排序等。 二、二叉树检索 （一）Kd树 1.定义 Kd树的每个节点表示K维空间的一个点，并且树的每一层都根据这层的分辨器（Discriminator）作出分枝决策。 Kd树的第i层的分辨器定义为：i MOD k（根节点为0层，下面依次加1）。 特征如下： （1）左子树的所有节点的d维数值，均小于根节点的d维数值。 （2）右子树的所有节点的d维数值，均大于根节点的d维数值。 （3）左右子树也分别为kd树。 d为根节点的分辨器。 A点分辨器的值为0（x轴），左子树的所有结点的x值都比A的x值小；右子树反之。 分辨器的值是指对应空间中的哪一维。因此，k层之后就是新的循环。 首先是从第一维分成两个部分；然后是第二维分成两个部分；再次是第三维分成两个部分，直至第k维。然后重新按照第一维… Kd树查询：需要按照分辨器的值进行比较。 Kd树插入：与二叉树同。 Kd树删除：与二叉树类似，但是，对于结点的d维数值，存在相同情况，这就需要处理。 （二）K-D-B树 KD树与B树结合，解决分页策略。 （三）HB树 HB树是一种有效的多维动态索引结构,其结点间有哪些信誉好的足球投注网站和增长过程模拟B树的处理方法,结点内采用k维树组织和进行高效有哪些信誉好的足球投注网站。 结点分裂要求k维树分裂,于是抽取一个大小介于1/3～2/3间并尽可能平衡的k维子树,并以此子树表示一个新结点。 因此HB树结点空间是有孔(holey)的k方体,即每个结点空间是被抽取若干个小k方体的k方体. (b)中结点W的k维树是从结点Z的k维树抽取的，如Z的k维树中的ex标识，它相当于(a)中粗线框内的矩形从整个大矩形中抽取.结点P是该HB树的根,其k维树表示下层HB结点W,Z的导向路径,意为满足x＜x1且y＜y1的记录应存于结点W,其它记录则存于结点Z。符合二叉树原理，左边小于右边 HB树能很好地支持精确匹配有哪些信誉好的足球投注网站和范围有哪些信誉好的足球投注网站。进行精确匹配有哪些信誉好的足球投注网站,要经过自HB树根到一叶子的单一路径，访问的结点数是HB树的高度。在HB树结点内通过比较k维树结点值与有哪些信誉好的足球投注网站的相应属性值，最终确定唯一的下层HB树结点。范围有哪些信誉好的足球投注网站可能涉及HB树每层的多个结点。范围的标界是在若干个属性上取值的上下界。结点内有哪些信誉好的足球投注网站时将k维树结点的比较值与有哪些信誉好的足球投注网站范围的相应属性上下界进行比较，以决定转向k维树结点的左子树、右子树或两者。 　　 尽管HB树对于大多数情况能取得较好效果,但它有两个问题: (1) 空间利用率不理想; (2) 可能出现多处结点,使HB树不再是严格的树结构。 三. 四叉树检索 点四叉树 区域四叉树 MX四叉树 PR四叉树 CIF四叉树 1.点四叉树 以空间点为划分点，将索引空间分为两两不相交的的2k个子空间，依次与它的2k个子结点相对应，对于位于某一子空间的点，则分配给对应的子树。 点四叉树的构造过程： （1）输入空间点A，以A为根节点并进行划分空间。 （2）输入空间点B，B落入A的NW象限，并且A的NW象限为空，则B直接放入A的NW象限孩子结点。同理，C是A的SW孩子结点。 （3）输入D，由于D落入A的NW象限，但是NW不为空，所以继续往下查找，得到B的NE象限为空，因此，D作为B的NE孩子结点。