（计算机软件与理论专业论文）空间自适应动态平衡QERltgt树的设计与实现.pdf

空间自适应动态平衡q e r + - 树的设计与实现 摘要 在空间数据库设计中，为了提高数据存取和管理的效率，一般都要为空 间数据库建立索引，不同的空间数据索引结构和索引管理技术，直接影响系 统的性能。空间数据的复杂性决定了其索引结构的复杂性。空间数据索引作 为一种辅助性的空间数据结构，介于空间操作算法和空间对象之间，它通过 筛选，排除大量与特定空间操作无关的空间对象，从而缩小了空间数据的操 作范围，提高了空间操作的速度和效率。空间数据索引技术是提高空间数据 查询和各种空间分析操作等方面效率的关键技术。 二十多年来，国内外学者提出了许多不同的空间索引方法，包括r 树系 列，四叉树系列，网格索引等等，这些索引方法各有优缺点。本文对空间索 引的研究现状进行了粗略的总结，并对多种典型的索引方法进行了深入的研 究和分析，主要分析了其结构，操作算法及性能。 本文结合已有索引技术的优点，提出了一种新的基于四叉树，r - 树及r 树的空间索引结构：q e r + - 树，给出其结构说明和相关算法的描述与实现， 并通过实验测试其性能。q e r + 树可以限制查询范围，减少索引空间重叠。 此外，在结点分裂时，还采用了强制重插入机制，优化了树的结构。因此整 体上提高了索引性能。 研究成果表明，q e r + - 树是一种有效的空间数据索引结构，采用这种结 构，空间数据的插入，删除，特别是检索性能与r - 树及r + 树相比得到很大 提高。 关键字：空间数据库空间索引r - 树r + 树q e r + - 树 空臼适应动态平衡q e r + 树的设计与实现 a b s t r a c t i nt h ep r o c e s so fd e s i g n i n gs p a t i a ld a t a b a s e s , s p a t i a li n d e xi su s u a l l yc r e a t e df o r i m p r o v i n gt h ee f f i c i e n c yo fd a t aa c c e s sa n dm a n a g e m e n t d i f f e r e n ti n d e x i n g s t r u c t u r e so fs p a t i a ld a t aa n dd i f f e r e n tt e c h n i q u e so fi n d e xm a n a g e m e n th a s d i f f e r e n ts y s t e mp e r f o r m a n c e 1 1 c o m p l e x i t yo f i n d e x i n gs t r u c t u r ei sd e c i d e db y t h ec o m p l e x i t yo fs p a t i a ld a t a s p a t i a li n d e x ，a sa l la s s i s t a n ts p a t i a ld a t as t r u c t u r e b e t w e e ns p a t i a lo p e r a t i o na l g o f i t h m sa n ds p a t i a lo b j e e t s , c a ne l i m i n a t eal o to f s p a t i a lo b j e c t st h a th a v en or e l a t i o nw i t ha p p o i n t e ds p a t i a lo p e r a t i o n sv i af i l t e r i n g s os p a t i a li n d e xc a nn o to n l yd e c r e a s et h eo p e r a t i o nr a n g eo f s p a t i a ld a t a , b u ta l s o i m p r o v et h es p e e da n de f f i c i e n c yo f s p a t i a lo p e r a t i o n s s p a t i a li n d e xi st h ep i v o t a l t e c h n i q u et oi m p r o v et h ee f f i c i e n c yo f s p m i a lq u e r ya n ds p a t i a lo p e r a t i o n se t e i nt h ep a s tt w e n t yy e a r s ，d o m e s t i ca n do v a s e a ss c h o l a r sp r o p o s e dal o to fs p m i a l i n d e x i n gt e c h n i q u e s ，i n c l u d i n gt h es e r i e so fr - t r e e ，t h es e r i e so fq u a d - t r e e ，g r i d i n d e xa n ds of o r t h e a c ho n eo ft h e mh a ss t r e n g t h sa n dw e a k n e s s e s t h i sp a p e r s u m su pt h er e s e a r c hp r o c e e d i n go fs p a t i a li n d e xs i m p l y i na d d i t i o n , i ts t u d i e s m a n yt y p i c a li n d e x i n gt e c h n i q u e sd e e p l y ，a n dm a i n l ya n a l y s e st h es t r u c k u o s , o p e r a t i o na l g o r i t h m sa n dp e r f o r m a n c e t l l i sp a p e rp r o p o s e dq e r + - t r e e , an o wq u i c ks p e e ds p a t i a li n d e x i n gs t r u c t u r e b a s e do nq u a d - t r e e ，r - t r e ea n dr + - t r e e ，b yw a yo fc o m b i n i n gt h es t r e n g t h so f s o m ei n d e xt e c h n i q u e s n 峙d a t as t r u c t u r ea n di n t e r r e l a t e da l g o r i t h m sa r es t a t e d 1 1 ”p e r f o r n m n c ei sa l s ot e s t i f i e db ye x p e r i m e n t s q e r + - t r e eb r e a k sd o w nal a r g e r - t r e 圯t oa1 0 to fs m a l lr - t r e 圮a n dr 十- t r c e s oi tc a nr e s t r a i nt l l eq u e r ys p a c ea n d d e c r e a s et h eo v e r l a po fi n d e xs p a c e i na d d i t i o n , q e r + - t r e eu s e st h ew a yo f r e i n s e r t i n gb yf o r c ew h i l es p l i t t i n gn o d e s i tc a nb e t t e rt h et r e e s s t r u c t u r e s o q e r + - t r e 贮r a i s e st h ei n d e x i n gp e r f o r m a n c ei ns od o i n g t h es t u d yr e s u l t ss h o wt h a tq e r + - t r e ei sa ne f f i c i e n ts p a t i a ld a t ai n d e xs t r u c t u r e t h ep e r f o r m a n c eo fi n s e r t i o n , d e l e t i o na n d e s p e c i a l l ys e a r c h i n g i sm o r e s u p e r i o r i t yt h a nr - t r e ea n dr + - e eb yu s i n gt h i ss t r u c t u r e k e yw o r d s ：s p a t i a ld a t a b a s e ；s p a t i a li n d e x ；r - t r e e ；r + - t r e e ；q e r + - t r e e i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名： 新誓 日期：坌2 ：! 乡 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名皿导师签名陲塑日 期：型 空间自适应动态f 衡q e r + 树的设计与实现 1 1 空间数据库简介 第一章前言 空间数据库的研究始于2 0 世纪7 0 年代的地图制图与遥感图像处理领 域，如今已被广泛地应用于g i s 、c a d 、天气预报系统、计算机视觉、机器 人、自动制图、三维建模、计算几何等领域。一般来说，空间数据是指用于 表示空间物体的位置、形状、大小和分布特征等方面信息的数据。空间数据 库就是以描述空间位置和点、线、面、体等特征拓扑结构的位置数据及描述 这些特征的属性数据为对象的数据库，空间数据库系统则是描述、存储和处 理空间数据及其属性数据的数据库系统。由于传统数据库在空间数据的表 示、存储和检索上存在许多缺陷，因此迫切需要一种更方便有效地处理空间 数据的数据库系统，从而形成了空间数据库这一新的数据库研究领域。 随着数字城市、数字地球等概念的提出与应用，空间数据库，特别是大 型的空间数据库受到越来越多的关注，具有广阔的应用前景。同时，随着空 间数据库的应用与发展，对大型空间数据库的性能提出了更高的要求，其中 重要的一部分工作是提出一种能高效处理空间数据的索引机制。 1 2 空间索引技术的研究意义 所谓空间索引，就是指依据空间实体的位置和形状或空间实体之间的某 种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信 息，如对象的标识、外接矩形及指向空间实体数据的指针等。简单地说，就 是将空间对象按某种空间关系进行划分，以后对空间对象的存取都基于划分 块进行【。 空间数据包括点、线段、区域，三维或更高维中的多面体。空间数据库 包含带有对象的外在知识、对象的扩展以及对象在空间的位置等多维数据。 空间数据被视为一种特殊的数据，它们具有以下几个特点 2 3 1 ： 空间对象结构的复杂性。 空间数据的动态性。 空间自适应动态平衡q e r + - 树的设计与实现 空问数据库不断增长，存储空间需求量大。 没有空间代数标准，对空间目标的空间操作复杂且运算量很大 空间操作不封闭。如两个空间对象的交集可能是一组点、线或区域。 空间数据的多维性。该特性使传统数据库索引不适合索引空间数据。 难以定义合理的空间目标的空间次序，无法应用通常的排序技术。 因此，对空间数据的处理是一项时间和空间开销都很高的操作。在空间 数据库设计中，为了提高数据存取和管理的效率，一般都要为空间数据库建 立索引，不同的空间数据索引结构和索引管理技术，直接影响系统的性能。 空间数据索引作为一种辅助性的空间数据结构，它通过筛选，排除大量与特 定空间操作无关的空间对象，缩小了空间数据的操作范围，提高了空间操作 的速度和效率。空间数据索引技术是提高空间数据查询和各种空间分析操作 等方面效率的关键技术。 1 3 空间索引技术的研究现状 随着空间数据库的发展以及实际应用的需要，二十多年来，国内外学者 越来越重视对空间数据库索引技术的研究，并相继提出了多种空间索引结构 与索引方法。图1 1 按空间索引结构之间的关系演变，展示了空间索引结构 在国外最近二十年的进展情况【2 ，4 】。 目前，研究出的索引方法可归纳为如下几种【5 】： ( 1 ) 空间映射法 低维空间向高维空间映射。对于k 维空间具有n 个顶点的目标，可以 映射成n k 维空间的点。经过这种映射方法后，可以直接采用点索引技术。 但是经过空间目标的映射，k 维空间目标的空间邻近性在n k 维空间的点之间 不再保持，且插入、删除操作的复杂度也会随着维数的增加而增加。 高维空间向一维空间映射。通常数据空间被划分成大小相同的网格单 元，然后用某种空间填充曲线填充方法，给这些网格单元编码。每个坐标是 空间填充曲线轨迹中表示空间位置的一个简单数值。这样，空间目标可以表 示为数字编码的集合或一维目标。经过这种映射方法后，可以利用传统的数 据库索引技术，但是存在重复存储，实体近似表达精度较差，空间映射后实 2 空间自适应动态平衡q e r + - 树的设计与实现 体间空间关系部分丢失，相交查询效率低等问题。 二义树 良树 哈希表 率鲥填允曲线 一 卅| 1 9 8 3 以前驾r 、卧懈 e x c e l l b d - t r c c s l 1 9 斛m i 。d - t 点秭 1 | r - t og r i d f i l e s 黼谂嗽腩沁遗洲g f | 灶 | j | i n碴。妇n g 牵f f p 腌h i n gk 。k j 沁击i n g f 。l 黼 烈| 。 t漶毒 k 氘 jk 匹1 | d o t 彰 i 三 蕊k 、 f - l r 蕊舛993zd 墅蝉 1 9 8 5 4 a - t e e s 1 9 8 6 1 9 8 7 s k d -黼瓜 1 9 8 8 c 蝠 1 9 8 9l s d k tk h 簖 - 蜘k 嘲厶缀丝 - 盼t 么殁。 e 慨 z ：z p r j _ 削 _ - _ _ _ - 一 ! ：2 ： 嬲磁虿一 - 。 _ - - t 舢厶上。“ c r 肆t 雌s 高h f 玉k 堍b 味u l k 幽- l o a d i 鸭一 1 9 9 7轰 i， | | i 1 9 9 8 o p t i n i 一母均l i | l g k 赫 h r 吨c s讧 呼l t 1 9 9 9 k 删 z o o o n 彰施鸭 t b i 雠a p r 。仃粥p 2 0 0 l c o m p a c t l f 旆，、嘲d 每馘 2 0 0 2c r 七ss t t a r 是龆 | 空问自适应动态平衡q e r + 树的设计与实现 目标复制：目标标识重复存储在与该目标相交的所有子空间中。 目标裁切：目标被分解成几个不相交的小目标，从而使每一个分解的 小目标完全包含在某一子空间中。 ( 3 ) 空间界定法 这种方法的典型代表是r - 树【刁，r 树嘲，它允许空间重叠，将索引空间 划分为多级的子空间，这些子空间允许重叠，一个空间对象完全包含在某一 子空间。其优点是目标不需要重复存储，主要缺点是如果索引空间的划分策 略选取不当，索引子空间的重叠和覆盖将得不到控制，从而影响查找性能。 以上只是现有索引技术分类的一种，空间索引技术的分类方法很多，如 从数据结构类型来分，可以分为基于地址计算的非层次的空间索引与递归的 空间索引树【9 】，从数据结构来分，可以分为基于二叉树的空间索引技术，基 于四叉树的索引技术，基于b 树的空间索引技术 2 1 。 事实上，很多索引技术采用多种结构来提高效率，如x - t r e e t l 0 】综合了线 性组织机构与r - 树层次组织结构的优点，提出了超结点的概念。再如 c e l l q 仃e c 【9 】就采用了四叉树与线性链表的二级索引机制。 1 4 本文的研究内容和创新之处 本文对空间索引的研究现状进行了粗略的总结，并针对大型空间数据库 的应用需求及已有空间索引技术的不足，提出了一种基于四叉树、r 树及 r + 树的空间索引结构：q e r + - 树，并通过实验验证了其性能。 本文主要的研究内容包括以下三个方面： ( 1 ) 介绍了各类空间数据索引技术的基本思想及相关算法，包括基于b 树的索引结构，基于四叉树的索引结构等等； ( 2 ) 提出了一种面向大型空间数据库的空间索引结构：q e r + 树，并给出 其结构说明及相关算法的描述与实现。q e r + - 树是结合了四叉树( 即 q u a d t r c e ，准确地说应该是2 。叉树，k 为空间的维数) 和r 树以及r + 树的 优缺点提出的一种空间索引结构，其实质是将一棵大的r _ 树分解成多棵小的 r 树和r + 树，从而减少索引空间重叠，提高查找性能。 ( 3 ) 设计了q e r + - 树索引与r - 树以及r + 树索引的实验程序，通过q e r + - 4 空间自适应动态平衡q e r + 树的设计与实现 树与r - 树、r + - 树索引的多种性能指标对比，测试q e r + - 树的性能表现。 本文的创新之处包括： ( 1 ) 本文首次系统全面地介绍和分析了近二十多年来发展的各种空间索 引方法的基本原理及它们之间的内在联系。 ( 2 ) 首次结合q u a d t r e e 和r 树系列对索引空间进行分级处理，对不同级 别的索引空间采用不同的索引策略，对最底层索引空间采用剪裁机制，把对点 的查询控制在一条路经上，减少非点查询的失败路径，并解决了失败路径的 扩散问题，提高查询效率。 ( 3 ) 在q e r + - 树的结点分裂时，引入了强制重插入策略，利用这种动态插 入，保证了树的结构优化，达到了树的良好平衡自适应性。 研究成果表明，q e r + - 树是一种有效的空间数据索引结构，采用这种结 构，空间数据的插入，删除，特别是检索性能与r - 树及r + 树相比能够得到 很大提高。 1 5 本文的组织结构 第一章：简要介绍了空间数据库，空间数据索引技术的研究意义及其研 究现状，接着阐述了本文的主要研究内容和创新之处。 第二章；主要介绍了空间数据库索引技术的相关概念，并根据它们所基 于的数据结构分类讨论了几种典型的空间索引结构、算法及性能分析。 第三章：结合四叉树、r 树及r 树的优缺点，提出了一种面向大型空 间数据库的索引结构：q e r + - 树。给出其结构及算法实现。 第四章：性能测评。在这一章中给出了实验结果，并通过实验对比的方 式验证了q e r + 树是一种有效的空间数据索引结构。 第五章：总结和下一步研究工作展望。主要对本论文的研究工作进行总 结，并对下一步的工作进行展望。 空问自适应动态平衡q e r + _ 树的设计与实现 第二章空间数据库索引技术 虽然空间数据索引技术和非空间数据索引技术相比更加复杂，空间数据 索引仍然发展于这些基本的索引结构。本章首先阐述与空间数据库索引技术 有关的一些知识，然后分类介绍常用的空间索引技术。对每一种空间索引技 术，将首先介绍其结构，接着描述查找、插入、删除处理过程及实现算法， 最后分析其性能与优缺点。 2 1 空间索引相关知识 2 1 1 空间查询分类 空间查询( s p a t i a lq u e r y ) 是指从空问数据库中查找出满足查找条件的 空间目标的处理过程。又称空间查找或空间检索。根据一般应用系统的需求， 总结出空间索引应提供的最常用的三类空间查询，它们是【1 1 1 ： ( 1 ) 空间范围查询( s p a t i a lr a n g eq u a ) = 在一个图层内，给定一个查询区 域r ，找出与此查询区域满足一定空间关系的所有空间目标； ( 2 ) 最近邻居查询( n e a r e s tn e i g h b o rq u e r y ) - 在一个图层内，找出距离给 定查询点最近的空间目标； ( 3 ) 空间连接查询( s p a t i a lj o i nq u e r y ) 针对两个或两个以上的图层，找出 满足查询条件的若干对空间目标。 2 1 2 目标近似技术 空问目标一般具有复杂的空间形体，因而针对空间目标的精确空间位置 与扩展的操作时间开销很大。为了降低计算量，很多索引结构都采用了对空 间目标进行近似的技术( a p p r o x i m a t i o n ) ：即用一个能够完全包围空间目标的 最小的简单形体来近似表达空间目标。常用的目标近似技术有以下几种： ( 1 ) 最小约束矩形m b r m b b ( m i n i m u mb o u n d i n gr e c t a n g l e b o x ) ：用空 间目标的最小约束矩形( 边与空间轴平行) 近似表达空间目标，如图2 1 ( a ) 。 ( 2 ) 最小约束圆m b s m b c ( m i n i m u mb o u n d i n gs p h e r e c i r c l e ) ：用空间 6 空间自适应动态，1 7 衡q e r 树的设计与实现 目标的最小约束圆近似表达空间目标，如图2 1 ( b ) 。 ( 3 ) 最小约束多边形m o c o r n e r ( m i n i i n u l nb o u n d i n gm - c o m e r ) ：用完全包 围空间目标的最小m 边形近似表达空间目标，如图2 1 ( c ) 。 这里，矩形、圆、多边形在多维空间就扩展成为“超矩形”、“超球”和 “空间多面体”。本文主要介绍的是基于m b r 近似策略的索引技术。 图畸 ( a ) m b g ( ”m b s( c ) 5 - c o m e r 图2 1 二维空间目标近似表达的一个例子 2 1 3 空间查询过程 对于采用了空间目标近似的空间索引技术，如图2 2 所示，其空间查询 过程分两步进行： ( 1 ) 筛选：通过空间索引减少进行比较的空间目标的数量，空间索引在筛 选过程中以一种“大致”的方式进行，因为空间目标采用了近似技术，而非 空间目标本身。但是通过空间索引筛选出的结果集必定包含查询所需要的精 确结果集； ( 2 ) 细化；对筛选出的空间目标进行精确的几何计算，得到查询结果。 糟确结果集 图2 2 空间查询过程 显然，筛选步骤中通过索引机制有效地减少了外存页的访问以及多余数 据的提取，通过近似机制有效地减少了计算时间。而且从空间索引在进行空 间查询的作用可以看出，空间索引与传统索引的不同之处在于：对于查询， 空间索引无法精确定位，无法提供精确的结果集。 2 2r 树系列空间索引技术 r 树7 1 最早是由a g u t t m a n 在1 9 8 4 年提出的，其后又有了许多变形，形 7 空问自适应动态平衡q e r 树的设计与实现 成了由r - 树、r + 树、r ，树、h i l h e r tr - 树【1 2 】、s r - 树【1 3 1 等组成的r 树系列空 间索引。r - 树及其众多变形都是一种平衡树，结构非常类似于b 树，也具有 类似于b 树的一些性质。本节主要介绍了最典型的基于b 树的空间索引结 构r - 树川，及其两种交体r + 树 6 1 和酣树i s 。 2 2 1r - 树 r 树是一种动态的空间索引算法，现已成为空间索引中应用最广泛的算 法之一。r 树较好解决了许多传统算法未解决的空间数据动态索引问题i 阐。 2 211r - 树的结构及特点 对于一棵m 阶的r 树，其结点结构可描述如下： 叶子结点：( c o u s t , l e v e l ， ， ， ) 中间结点：( c o u n t , l e v e l ， ，( c p 2 ，t l b p , 2 。 ) 其中，c o u n t 。 ，0 表示该结点 在树中的层数( o 表示叶结点) 。叶子结点存储了一组结构为( o i d ，m b r ) 的数据项，其中o i d 为对象标识符，m b r 为该目标在k 维空间中的最小约 束矩形，简称为数据矩形；中间结点则存储了一组结构为( c p ，m b r 的 索引项，其中c p 为指向子树根结点的指针，m b r 表示包围c p 所指向的子 结点的所有条目的最小约束矩形，简称为目录矩形。 设m ( 2 m m ，2 ) 为结点包含索引项或者数据项的最小数目( m 通常取 m 2 ，如果结点包含项目数小于m ，则称结点下溢( u n d e r t t o w ) ，如果结点包 含项目数大于m ，则称结点上溢( o v e r f l o w ) ) 。r - 树有如下几个特性【1 5 】： ( 1 ) 若根结点不是叶子结点，则至少有两棵子树； ( 2 ) 除根之外的所有中间结点至多有m 棵子树，至少有m 棵子树； ( 3 ) 每个叶子结点均包含m 至m 个数据项； ( 4 ) 所有的叶子结点都出现在同一层次； ( 5 ) 所有结点都需要同样的存储空间( 通常为一个磁盘页) 。 由以上特性可知：r - 树的数据矩形和目录矩形都有可能重叠，查找路径 也往往是多条的，即使对于精确匹配查找，而且r 树是完全动态的，插入、 8 空间自适应动态平衡q e r + - 树的设计与实现 删除、查询可以交叉进行，不需定期进行全局结构重组。 图2 3 是一棵r - 树的示意图。其中，f 1 以，p 表示空间目标的m b r ， 即数据矩形，p 1 ，p 2 ，, p 9 表示空间点( 点的m b r 就是点本身) ，r 1 , r 2 , - - - , r 8 表示中间结点( 包括根结点) 索引项对应的索引空间，即目录矩形。从图中 可以看出，目录矩形允许重叠。如r 1n r 2 空。 图2 3 ( a ) r 树平面示意图( b ) r - 树结构示意图 2 2 1 2 查找 查找与某一给定区域相交的所有空间目标时必须从根结点开始，递归遍 历所有索引空间与查找区域相交的子树，当遇到叶子结点时，数据矩形首先 与查找区域进行比较，如果数据矩形与查找区域相交，则再提取对应目标的 几何信息进行计算。 r 树的查找算法的形式化描述如下： a l g o r i t h mr _ s e a r c h ( w ) ，在根结点为r 的r - 树中查找所有与w 相交的数据矩形吖 r s l 【查找叶子结点】 球限是叶子结点) 返回该结点中所有与w 相交的数据矩形； r s 2 查找中间结点】 i f ( r 是中间结点) f o r ( r 的每一个索引项( c p ，m b r ) ) i f ( m b r n w ：0 ) r 。s e a r c h c p ，v o ； 由以上归纳的r - 树特性及其查找过程可知，在构建一棵查找效率高的 9 空间自适应动态平衡q e r + 树的设计与实现 r - 树时，尽量追求以下几点啊： ( 1 ) 目录矩形覆盖的“面积”应尽可能小，“死空间( d e a ds p a c e ) ”( 没有对 象存在的空问称为死空间峄也应尽可能小； ( 2 ) 为了减少查找路径分支，各目录矩形间的重叠应尽可能小； ( 3 ) 目录矩形的“周长”应尽可能地小。因为在“面积”一定时，“周长” 最小的形体是“方形”，而“方”的目录矩形可以从根本上改善树的结构： ( 4 ) 空间利用率应尽量提高。 以上这四条优化准则往往以非常复杂的方式相互影响，优化某一因素往 往影响其它因素而导致整体性能下降。 2 2 1 3 插入 在r - 树中插入一个空间目标跟许多有关树的操作一样是一个递归的过 程，首先从根结点开始，检查所有的目录矩形，按照“最小覆盖面积”的优 化原则找出一个索引项，即首先选择包围新的增量目标后，目录矩形的“面 积”增量最小的索引项，如果增量相同，目录矩形的“面积”最小的索引项。 然后对选中的索引项对应的子树按照“最小覆盖面积”的优化原则进行递归 地搜索，直至叶子结点。如果叶结点未满，直接在该叶子结点插入新增目标 的索引信息，然后向上依次调整其父结点对应索引项的目录矩形直至根结 点：如果叶结点己满，插入新增目标将会导致叶结点上溢，故需要分裂该叶 子结点。分裂操作是将溢出的结点按一定的规则分为若干个部份，在其父结 点删除原来对应的单元，并加入由分裂产生的相应的多个单元，并在其父结 点中增加相应的索引项。如果这样引起父结点的溢出，则继续对父结点进行 分裂操作。也就是说，结点的溢出及分裂操作可能向上传播直至根结点。分 裂操作也是个递归操作。 r 树的插入算法的形式化描述如下： a l g o r i t h mrh l r t ( rw ) + 向根结点为r 的r - 树中插入数据矩形w ， r i i 【查找叶子结点】 i f 很是叶子结点) 限己有m 个数据项) s p l i t n o d e ( r ) ： 1 0 空间自适应动态平衡q e r + 树的设计与实现 e l s e 插入w 于r ； r 1 2 查找中间结点】 球限是中间结点) 按照“最小覆盖面积”的优化原则选择r 中某一矩形，插入数据矩形 w ，依次向上调整包含新矩形w 的目录矩形直至根结点； 2 2 14 结点分裂算法 对于结点的分裂，g u t t m a n 提出了时间复杂度分别为结点索引项个数的 指数级、平方级、线性级的三个算法。这三个分裂算法都追求最小化结点分 裂产生的两个目录矩形的“面积”。其中，指数级算法找到的是全局最优解， 但算法的时间复杂度太高，另外两个算法得到次优解。设空间的维数为k ， 要分裂的结点为n 。n i j 表示结点n 第i 项第j 维的值。 平方阶分裂算法的处理过程如下f 1 1 】： ( 1 ) 对m + 1 个索引项重复以下步骤，从中挑出具有最大a 值的两个 索引项，放入n o d e l 和n o d e 2 中： 依次从m 十1 个索引项中选择两个索引项e l 和e 2 ； 构造包围e i 和e 2 的最小矩形m b r ，记为r e e ； 计算：a = r e c 的面积- e l 的面积e 2 面积。 ( 2 ) 重复以下操作共m - 1 次，每一次把一个索引项“分”到n o d e l 或 n o d e 2 中：对当前余下的所有索引项重复步骤，从中挑出具有最大d e f 值的一个索引项e t ，把它放入具有较小差值的结点( n o d e l 或n o d e 2 ) 。 依次从余下的索引项中选择一个索引项，记为e ； 假设把e 加入n o d e l 。构造e 加入n o d e l 后的m b r ，并计算加入 e 前后，m b r 的差值d e f l ； 假设把e 加入n o d e 2 。构造e 加入n o d e 2 后的m b r ，并计算加入 e 前后，m b r 的差值d e f 2 ； 计算：d e f = i d e f l d e f 2j 。 2 215 删除 从r 树中删除一个目标，首先找到存放该目标的叶结点，这就是r - 树 空间自适应动态平衡q e r 匕树的设计与实现 的一个查找过程，荐删除该目标对应数据项，并向上依次调整父结点对应索 引项的目录矩形直至根结点。如果删除该目标对应数据项后叶结点下溢，则 需要进行r - 树的压缩操作f 1 6 1 ，它使r - 树的每个结点单元数不低于m 这个下 限，从而保证了r - 树结点的利用率。 r 树的删除算法的形式化描述如下： a l g o r i t h mrd e l e t e ( r , p 1 ，从根结点为r 的r - 树中删除数据矩形p * r d i 【查找叶子结点】 偎是叶子结点) 如果r 包含p ，直接从r 中删除p ； r d 2 查找中间结点】 i f ( r 是中间结点) f o r ( r 的每一个索引项( c p ，m b r ) ) i f ( m b r a w o )r _ d e l e t e c p ，v o ； 如果结点n 下溢，则重新插入该叶结点中剩余的所有数据 项于叶结点层； 依次向上调整父结点的目录矩形直至根结点； 2 2 1 6 分析 r - 树是b 树在多维空间的扩展，它具有b 树的优点，如自动平衡、空 间利用率较高、适合于外存存储等。但是，由于目录矩形允许重叠，因此往 往存在多条查找路径，而其中的有很多失败路径，这就影响了查找性能。而 且随着索引空间维数和索引数据量的增加，树的高度及目录矩形的重叠均会 增加，这会严重影响查找性能。因此，对于r - 树而言，减少中间结点目录矩 形的覆盖与重叠是关键所在。 2 2 2r 7 树 为了克服r - 树在动态插入数据时造成的重叠空间过大和存在死空间等 空问自适应动态平衡o e w - 树的设计与实现 现象，ts e l l i s ，nr o u s s o p o u l o s 等于1 9 8 7 年提出了r 树【6 】。它将空间分割 为子空间，这种分割避免了重叠问题，但要以略微增加树的高度为代价。 2 2 2 1r + 树的结构及特点 r + - 树与r 树的结点结构基本相同，但构建的数据结构又有所差别，如 图2 4 ，2 5 是对于同一空间数据集的r - 树与r + 树的对比示意图。 图2 4r - 树( a ) 平面示意图结构示意图 图2 5r + - 树( a ) 平面示意图 结构示意图 在图2 5 中，数据矩形g 被分裂成两个子矩形，第一个子矩形包含在结 点a ，第二个包含在结点p ，避免t 0 e n 结点目录矩形的重叠( o v a d a p ) 。 由对比示意图可以看出，r + - 树与r 树的区别在于结点中对数据项和索 引项的填充个数有无严格限制以及目录矩形的有无重叠。 2 2 2 2 查找 在r + 一树中的查找与r - 树的查找不同的是：对于区域查找，查找路径应 该可以减少，但依旧可能有多条；对于点查找，则可以通过一条路径得到查 找结果。 r + 树的查找算法与r - 树相同，简单描述如下： 空何自适应动态平衡q e r + 树的设计与实现 a l g o r i t h ms e a r c h ( r , 、聊 ，幸在根结点为r 的r + 树中查找所有与w 相交的数据矩形 s 1 【查找叶子结点】 是叶子结点) 检查r 的每一数据项( o i d ，m b r ) ； r e t u r n 所有与w 相交的数据矩形； s 2 查找中间结点】 伍限是非叶结点) f o r ( r 的每一索弓l 项( c p , m b r ) ) i f ( m b m q w o ) s e a r c h ( c p ，w a m b r ) ： 2 2 2 3 插入 r + 树的插入算法与r 树的插入算法不同的是：r - 树的分裂操作是只向 上传播，r + 树不仅可能向上传播，也可能向下传播。r + 树父结点的分裂可 能会引起子结点的分裂，是因为父结点的分裂须引入一个合适的空间划分方 法，而这一划分可能同时影响其子结点。 r + 树的插入算法的形式化描述如下： a l g o r i t h mt n s e r t 飘飞 严向根结点为r 的r + 树中插入数据矩形w * 1 1 【查找叶子结点】 礤限是叶结点) i f ( r e 有m 个数据项) s p l i t n o d e ( r ) ： e l s e 插入w 于r ； 坨 查找中间结点】 限是非叶结点) f o r 的每一索引项( c p , m b r ) ) i f ( m b r n # 0 ) i m e r t ( c p ，聊 2 2 2 4 结点分裂算法 分裂一个结点时，首先必须找到一个合适的超平面将其索引空间一分为 1 4 空闻自适应动态平衡q e r + - 树的设计与实现 二，这一过程称为划分( p a r t i t i o n ) 。划分的选择要依据目录矩形的覆盖面积及 “死空间”的大小来决定。 r + 树的结点分裂算法的形式化描述如下： a l g o r i t h ms p l i t n o d e ( r ) s n l 【寻找一个划分】 调用p a r t i t i o n ； 【设( c p , m b r ) 为与r 相关联的索引项，s l 与s 2 表示划分得到的两个子 区域。创建两个新结点n l = ( c p l ，m b r l ) 与n 2 = ( c p 2 m b p 2 ) ， m b r i = m b r f ) s i ，i2 l ，2 ；】 s n 2 【填充新结点】 f o r 的每一项( c p j ，m b r j ) ) i f ( m a r j n m b m m b 琦) , ，i w r j 完全包含于m b r i p u t ( c 巧，m b r j ) i nn i l e l s e m b r j 与m b r l 及m b r 2 都重叠 球限是叶结点) n ，r ( c p j ，m 内) i n n i 与n 2 ： e l s e 用划分线继续分裂( c 巧，m s r j ) 所指结点，设得到的新结点为： 划1 = ( c p p ，m b r j l ) , n k 2 = ( c p j 2 ，m b r j 2 ) ，m b r j i 完全包含于m b r i ； 将n j i 加入到n i ，i - 1 , 2 ；】 s n 3 向上传播结点分裂操作】 球限是根结点) 创建一新根结点，n 1 与n 2 为其两孩子结点； e l s e 在r 的父结点p r 中，用n l 与n 2 替换r 。如果p r 的索引项个数超过 m ，那么再调用s p l i t n o d c ( p r ) 。】 2 2 2 5 删除 从r + t 树中删除一个目标，由于数据矩形可能被插入到多个叶结点，因 此r + 树的删除算法必须同时删除一个数据矩形的多个拷贝。 空问自适应动态平衡q e r 村的设计与实现 r + 树的删除算法的形式化描述如下： a l g o r i t h md e l e t e ( r , n ，从根结点为r 的r + 树中删除数据矩形w d 1 【查找叶子结点】 环但是叶结点) 从r 中删除w 且调整r 的父结点中对应的目录矩形； d 2 【查找中间结点】 m 偎是非叶结点) f o r 假的每一索引项( c p , m b r ) ) i f ( m b r n i r 0 ) d e l e t e ( c p ，w ) ； 2 2 2 6 分析 r 树主要的不同之处是能将m b r 分解成更小的子矩形，以避免最小边 界矩形间的重叠。所有从属于同一个矩形的子矩形，其指针指向同一个对象。 因为这些子矩形能够被有所判断地选择，所以在任意层次的边界矩形并不需 要被扩大。同样的分解方法还可以推广到非叶结点层次，这样，重叠就能够 被避免了。在有少量的额外的空间代价下，与r - 树比较起来，r + 树显示出 非常好的检索性能。 2 2 3r 树 r 树【8 】是由n b e c k m a n n ，h p k r i e g e l 等于1 9 9 0 年提出的。r 树在r - 树的交体中具有最好的性能。r ，树在结构上与r - 树完全相同，在树的构造， 查找，插入，删除算法上也基本相同，主要区别包括如下三点： ( 1 ) 插入路径的选择：r 树在插入数据选择插入路径时只考虑了目录矩形 的“面积”这个因素，酣- 树除了考虑“面积”之外，还考虑了目录矩形的 重叠，周长等等。 ( 2 ) 结点的分裂：r 一树考虑了三种“优势值”的计算方法，分别是： ( 1 ) a r e a - v a l u e = a r c a m b r ( g r o u p l ) 】+ a r e a m b r ( g r o u p 2 ) 】 ( 2 ) m a r g i n - v a l u e = m a r g i n 【m b r ( g r o u p l ) 】+ m a r g i n m b r ( g r o u p 2 ) 1 6 空间自适应动态平衡q e r + - 树的设计与实现 ( 3 ) o v e r l a p - v a l u e = a r e a m b r ( g r o u p l ) nm b r ( g r o u p