（计算机应用技术专业论文）基于r树索引的空间数据库引擎设计与实现.pdf

中国科学技术大学硕士学位论文 摘要 近年来，随着计算机的普及和i n t e m e t 的飞速发展，地理信息系统在房地产 管理、汽车o p s 自动导航、三维虚拟现实仿真等领域得到广泛应用，并具有越 来越大的市场。这些应用都需要空间数据库提供对空间数据进行存储、索引、检 索等方面的支持。 本文首先简单介绍空间数据库研究和发展的现状；对空间对象近似处理、空 间对象之间的关系运算和空间分析运算进行详细介绍，在此基础上给出空间查询 和的定义；对基于r - 树及r 树的空间数据索引技术进行详细的论述；对空间数 据库的缓冲机制进行研究；根据这些理论，给出了空间数据库引擎的详细设计和 实现方案。最后对空间数据库在房地产管理和三维虚拟现实两个领域的应用作了 介绍。 关键词；空间数据库；r - 树；r + - 树；缓冲管理；空间查询。 。 ! 曼翌兰茎查查兰堡主堂垡堕苎 a b s t r a c t r e c e n t l y , w i t ht h ep r o l i f e r a t i o no fc o m p u t e r sa n d t h er a p i dd e v e l o p m e n to f i n t e r n e t , g e o g r a p h i ci n f o r m a t i o ns y s t e m sh a db e e nw i d e 时a p p f i e di nr e a le s t a t e m a n a g e m e n t , v e h i c l eg p sa u t o m a t i cn a v i g a t i o n ，3 dv i r t u a lr e a l i t ys i m u l a t i o n a n do t h e rf i e l d sw i t hag r o w i n gm a r k e t t h e s ea p p l i e a t i o mn e e dt h es p a t i a l d a t a b a s et op r o v i d es p a t i a ld a t as t o r a g e , i n d e x i n g , r e t r i e v a la n do t h e rk i n d so f s u p p o r t t h i sp a p e rf i r s tg i v e sab r i e fi n t r o d u c t i o ni nt h er e s e a r c ha n de v o l u t i o n a r y s t a t u so fs p a t i a ld a t a b a s e ；t h e ni n t r o d u c et h es p a t i a lo b j e c ta p p r o x i m a t i o n ， s p a t i a lr e l a t i o n s h i p sa n ds p a t i a la n a i y s i si nd e t a i l ；b a s e do nt h “，g i v e st h e d e f i n i t i o no fs p a t i a lq u e r i e s ；a c c o r d i n gt ot h e s et h e o r i e s ，w eg i v ead e t a i l e d d e s i g np l a na n di m p l e m e n t a t i o np r o g r a mo ft h es p a t i a ld a t a b a s ee n g i n e f i n a l l y , i n t r o d u c et h ea p p l i c a t i o no fs p a t i a ld a t a b a s ee n g i n ei nt w oe a s e s ：r e a le s t a t e m a n a g e m e n ta n d3 dv i r t u a lr e a l i t y k e y w o r d s ：s p a t i a ld a t a b a s e ；r - t r c e ；r * - t r e e ；b u f f e rm a n a g e m e n t ；s p a t i a l q u e r y n 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：叁! 盟 砰6 月f 日 谚簟k 7 ，“ 哟7 ，b 易 中目科学技术大学硕士学位论文 1 1 课题背景 第1 章绪论 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m , g i s ) 是能够收集、管理、查询、 分析、操作以及表现与地理相关的数据信息的计算机信息系统，能够为分析决策 提供重要的支持平台【l 】。它广泛地应用于地学、房地产管理、资源管理、土地 规划、环境监测、防灾减灾、电力行业、交通管理、城市规划、科研、教育和国 防等领域，在我国国民经济建设中发挥着越来越重要的作用。 当前随着信息技术的发展以及应用领域的不断扩大，地理信息系统技术得到 了飞速的发展。由于g i s 是“关系到国家安全的战略性技术”，因此开发拥有 自主知识产权的国产g i s 系统平台，研究和掌握g i s 中的前沿关键技术，对我 国g i s 的发展和应用有着非常重要的意义【2 】。 g i s 的一个重要功能就是对空间数据进行管理、查询、分析。一般来说，空 间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据，常用 于表示空间目标的位置、形状、大小和分布特征等各个方面的信息，空间数据的 获得是建立在数据的空间关系基础上的【3 ，4 】。根据空间数据的几何形体特征， 空问数据可以粗略地分为点、线、面等几种基本类型。空间数据是多维的，它不 仅要表达空间目标的属性信息，而且要存储目标的几何信息以及目标问的空间关 系( 如相邻、相交、包含等) 。另外，空间数据的操作，如几何运算( 旋转与变 换等) 和空闻运算( 交与包含等) 具有较高的复杂度，这些操作往往与空间数据 的空间位置和形状有关。这使得主要针对一维属性数据而设计的传统关系数据库 系统无法再有效地表示、存储、管理和检索多维的空间数据【3 】。 1 2 空间数据库及其特点 为了更方便有效地处理空间数据，必须提出一种更适合处理空间数据的数据 库系统，空间数据库系统应运而生。其重要的一部分工作是提出一种能高效处理 空间数据的索引机制简单的说，空间数据库系统是一个通用的软件系统，它管 中田科学技术大学硕士学位论文 理空间数据的存储、检索、修改，确保数据的一致性、完整性、安全性，并提供 依据空间数据的位置和范围定位它们的工具【5 】。空间数据库是对传统数据库的 扩展，它除了应具有传统数据库的所有功能之外，还必须具备对空间数据的描述、 存储、检索等能力。 目前，空间数据库己经广泛地应用于g i s 、c a d 、机器人、计算机视觉等领 域。随着数字城市、数字地球等概念的提出与应用，空问数据库，特别是大型的 空间数据库受到越来越多的关注，具有广阔的应用前景。 与传统的数据库系统相比，空间数据库的存储量更大，空间运算及其复杂。 空间数据库中存储的空间物体之间的拓扑关系更为复杂、空间次序难以定义。空 间数据库和普通数据库相比具有其特殊性【5 】： 1 空间数据库的存储量巨大。一个空间物体由许多个点、线、面之类的 简单几何体组成，所以用来表示一个空间物体的数据量远远大于传统 数据库中一个条目的数据量。 2 空间物体往往具有不规则的几何形状。物体之间具有如相交关系、相 邻关系和包含关系等复杂的空间拓扑关系。而不是像普通数据那样简 单的大小关系。 3 对空间数据的空间运算比传统数据库的选择或连接操作复杂且运算 量大得多。例如查询某一个区域之内的空间物体、包含某一个坐标的 空间物体，都需要经过及其复杂的运算。这是由空间物体的不规则性 及空问物体的维数所决定的。 4 难以定义合理的空间物体的空间次序，无法像普通的一维数据那样使 用常规的排序技术。因此对空间数据的检索是一项时间开销很高的操 作。 基于以上观点，空间数据库必须使用有效的空问索引和磁盘缓存机制，来提 高对空间数据的处理效率，特别是提高对海量空间数据的检索效率。 1 3 研究现状 空间数据库需要提供高效的空问数据查询功能，空间索引的引入可以解决这 一阀题。空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关 2 中国科学技术大学硕士学位论文 系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息如空间对象 的外接矩形区域等。作为一种辅助性的空间数据结构，空间索引介于空间操作算 法与空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被捧 除，从而提高空间操作的速度和效率。空间索引的性能优劣直接影响空间数据库 引擎和g i s 软件的整体性能【6 】，它是空间数据库的一项关键技术。 空间索引技术大致分为如下四类【7 】 1 ) 基于二叉树的索引技术 基于二叉树索引结构的典型范例有k d 树、k - d b 树、l s d 树等。这种索引 结构的典型k d 树是一种二分索引树结构，主要用于索引多维数据点，但对复杂 的空间物体，如折线，多边形、多面体等的索引却必须采用近似方法和空间映射 技术。由此针对空间关系的查询效率将非常低，另外索引树需要的量庞大。为了 能索引复杂的空间目标，提出了适合索引二维空间物体的基于实体标志重复存储 技术的m k d - 树；为了将k d - u e e 存储组织到外存，将k d 树与& 树结合，提出了 k - d - b 树；s k d - 树的提出避免了空间物体的重复存储和空间映射，用空间目标的 中心点来对空间目标集进行二分索引。但是所有这些方法对非点状空间目标的索 引效率都较低。 2 ) 基于b 树的索引技术。 b 一树及其变体，被广泛应用于常规的数据库管理系统之中，实践证明其对大 型数据库的索引具有出色表现。目前韵空间数据索引技术，很多都基于b 树， 如g u t t m a n 提出的r - 树。黜树的思想是将空间目标及索引空间用其最小包围矩 形区域来近似表示，可以简化计算、减少存储空间；将空间上邻近的目标组织在 同一结点或同一分枝，可以减少外存访问次数。然而由于允许区间重叠，导致了 搜索路径的平均数量的增加；每一维的区间都要储存，需要较多的存储空间。为 此，为了避免索引空间重叠的问题，提出了r | 树；为了减少了查询中对外存的 访问次数出现了c e l l - 树等；为了对动态物体提供查询支持出现了t p r - 树。总之 这类索引结构需要解决的主要问题仍然是减少区域的重叠，提高搜索效率。 3 ) 基于哈希的格网技术 这种方法的基本思路是将索引空间划分为相等或不相等的一些小方格网，与 每个格网相关联的空间物体则存储在同一磁盘页，而格网的访问地址则可以直接 中田科学技术大学硕士学位论文 通过某种哈希算法得到。如网格文件，r - 文件等。这类方法主要适用子索引多维 空间点。 4 ) 空间目标排序法。 其基本思想是将索引空间划分为许多小的格子，然后每个格子指定一个惟一 的数字或编码，空间目标则用与其相交的一个或多个格子的数字来表示，或用与 其相交格子的编码求得另一惟一编码来表示。实质是将k 维空间的实体映射到 一维空间。用一维的数值对多维的空间目标进行排序，常见的方法有：l o c a t i o n k e y s ，z - o r d i n g 等。 目前国内外主要的空间数据库大都采用r - 树和四叉树空间索引方法。e s r i 的a r c c l e w 、m a p i n f o 公司的m a p i n f o 和i n f o r m i x 的o e o s l a t i a l d a t a b l a d 采用的 是r _ 树及其变体作为空间索引；国内中国地质大学的m 蛐和中科院的 s u p e r m a p 则采用的是四叉树。而著名的o r a c l e 公司的s p a t i a l w a r e 则同时采 用这两类索引方法。 1 4 本论文的工作 本文主要对空间数据库中的概念、r - 树系列索引技术和数据库的缓冲交换算 法进行介绍，设计并实现了一个基于r - 树索引的空间数据库引擎。 本人完成了如下工作： 1 对地理信息系统概念和现状、空间数据库理论进行了深入的探讨； 对空间数据库中的关键技术，如空间查询、空间分析、r 树索引、 缓冲管理也进行了研究和探讨 2 完成空间数据库引擎的需求分析，架构设计。对空间数据库引擎的 基本功能、主要架构、接口定义进行了深入研究。 3 实现空问数据库引擎的具体功能：包括文件管理、缓冲管理、r _ 树 索引、空间检索和空间数据存储等模块。 4 空间数据库引擎的应用：包括空间数据库在房地产管理系统、虚拟 三维房屋场景显示系统中的应用。 4 中国科学技术大学硕士学位论文 1 5 论文的组织结构 本论文共五章，各章的主要内容如下： 第一章绪论 第二章空间数据库中的相关概念 第三章理论基础。 第四章系统实现与应用。 第五章总结与展望。 1 6 小结 本章主要介绍了课题的研究背景，指出了本课题在实际应用中的意义。并介 绍了空间数据库在国内外的研究现状及本人所做的工作和本文的安排 中国科学技术大学硕士学位论文 第2 章空间数据库中的相关概念 空间数据库的最大特点就是提供空间检索和空间运算。 空间查询( s p a t i a lq u e r y ) 。又叫做空间检索，是指同对象所占据的空间位置 有关的检索，从已有的、特定的数据源中查找满足某种空间约束条件的数据子集。 而这种空间约束条件一般来说和空间物体的位置关系运算有关。 空间运算，包含空间关系运算和空间分析运算。空间关系运算，指判定空间 物体之间是否具有某种位置关系，如相交、相切、相等、包含等。空间分析运算， 是基于地理对象的位置和形态特征的空间数据分析技术。其目的在于提取和传输 空间信息。 在空间数据库中，由于数据量大，而且空间物体一般由为数众多的空间几何 体( 如点、线、多边形、平面、球面) 等组成，所以空间物体之间的位置关系运 算复杂度比较高。我们有必要对空间物体进行近似处理，由包含空问物体的最小 球形或者长方体代替复杂的空间物体进行运算，以简化空间运算的复杂度，提高 效率。 2 1 空间物体近似处理 由于空间目标一般由具有复杂的空间几何体( 如折线、多边形、多面体、球 面，柱面等) ，因而针对空间目标的精确空间位置关系判断( 如相交判断、包含 判断) 时间开销极大，并且不同的几何体具有不同的判定算法。为了有效的降低 计算量和设计上的复杂度，很多空间索引结构都采用了对空间物体进行空间近似 ( s p a t i a l a p p r o x i m a t i o n ) 处理的技术：即用个能够完全包围空间目标的最小的 简单几何体( 如长方体、球形等) 来近似表达空间目标，如果这个简单形体满足 查找的要求，则提取其对应空间目标的几何信息进行计算，以判定该目标是否为 查找目标，否则不需做进一步的处理，这样就可以减少查找过程中很多不必要的 复杂的空问操作【8 】。 以二维和三维空间数据为例，目前空间数据库中最常用的空间物体近似处理 有以下几种【8 】： 6 中嗣科学技术大学硕士学位论文 最小边界区域( m b r ，m i n i m a lb o u n d i n gr e g i o n ) 用边与空间坐标轴平行 的最小包围空间物体的矩形( 或者长方体) 区域来近似表示空间物体。如图2 - 1 圈2 1 量小边界区域( m b r ) 近似处理 最小外接圆最小外接球( m b c 枷b s ，m i n i m a lb o u n d i n gc i r c l e s p h e r e ) ： 用半径最小的包围空间物体的圆( 或者球形) 来近似表示空间物体。如图2 - 2 。 圈2 - 2 量小外接皿近似处理 最小外接凸n 边形( m i n i m a lb o u n d i n gn - c o r l 3 e rc o n v e x ) ：只针对二维空间 对象，用面积最小的、完全包围空间物体的凸n 边形来近似表示空间物体。如图 2 3 ( n = 6 的情况) 。 圈2 4 量小 卜接凸n 边形近似处理 7 中国科学技术大学硕士学位论文 凸包( c o n v e xh 1 i l l l ) ：用空间物体的凸包来近似表示空间物体。如图2 - 4 。 圈2 - 4 凸包近似处理 对于一个给定的查询区域r ，如果r 与空间物体的m b r m b s ，最小外接凸n 边形凸包不相交，那么该区域必然不与该空间物体相交。由于判定复杂空间物 体相交非常耗时，所以使用上述近似处理，可以极大的简化运算步骤，降低运算 量。 从图2 - 1 、2 - 2 、2 - 3 、2 4 可以看出，就以上四种近似处理方法的精确度丽言， 凸包的精确度最高：覆盖掉的多余空白面积( 或体积) 最小对于最小外接凸n 边形，当n 越大，精确度越接近凸包。 就空间位置关系判定算法丽言，基于m b r 和m b c m b s 近似的算法复杂 度最低，因为矩形伥方体区域之间位置关系判定和圆形，球形的位置关系判定相 对于多边形和凸包的位置关系判定更简单。 就存储需求而言，m b r 和m b c m b $ 也占有优势。m b r 只需要在每一个 维度上记录包含空问物体的两个区间的值；m b c 和m b s 只需要记录圆心球心 的坐标和半径的大小；最小外接凸n 边形需要记录n 个点的坐标。 由以上分析可知，凸包和最小外接凸n 边形的构造复杂；m b c ，m b $ 虽然 在某些情况下近似效率较高，但对于一般的空间目标及查询类型而言并没有优 势。所以很多空间索引技术采用m b r 的近似策略。在本文以下各章节中，主要 介绍的是基于m b r 近似策略的空间关系运算和索引技术。 2 2 空间运算 给定一个几何对象a ，分别用i ( a ) 、b ( a ) 和e ( a ) 表示该几何对象的内部、边 界和外部，d i m ( a ) 表示a 的维数点为零维几何对象，边界为空集，内部即为点 0 中国科学技术大学硕士学位论文 本身；线为一维几何对象，其边界为线的两个端点，内部则为除端点以外的线几 何对象；面为二维对象，其边界为面的轮廓线，内部为除边界以外面积和对象部 分；对于三维几何体，其边界为几何体的表面，内部则为除表面以外的几何对象。 根据o p e ng i s 标准( o p e ng i ss i m p l ef e a t u r es p e c i f i c a t i o nf o rs q l ) ，空间运算 可以分为空间关系运算和空间分析运算两大类。 2 2 1 空间关系运算 所谓空间关系运算，是指判断两个几何对象是否满足给定的空间位置关系的 运算。主要分为如下几种： 相离( d i s j o i n t ) ：如果两个几何对象a 和b 没有公共点，则称a 和b 满足相 离关系( 见图2 5 ) 。即： 、 d 蠲。锄瓴b ) 铸o ( a l n l 嘞= 仍 o ( o ) n b 嘞一仍) 僵( a 固一仍，、徊砷n b 氆) - o 田2 4 相( d 埘o i n t ) 美系 相切( t o u c h ) ：如果两个几何对象a 和b 的内部没有交点，且a 的边界与b 的内部有交点，或者a 的内部与b 的边界有交点，或者a 的边界和b 的边界有交 点，则称a 和b 满足相切( t o u c h ) 关系( 见图2 - 6 ) 。即： t o u c h nb ) l l 磅n l 嘞；鳓 f 国n l l b ) 卿、，l ( 口) n b 彻季幼v b 鲫n b 秭强”) 墨2 相切( 1 o u d h ) 关系 穿越( c r o s s ) 关系：对于几何对象a 和b ，如果i ( a ) n i 的维数小于i ( a ) 和 i c o ) 较大的维数，a 和b 的交集不等于8 和b ，且不为空，则称a 与b 满足穿越关 9 中田科学技术大学硕士学位论文 系( 见图2 - 7 ) 。即： c r o s s 向印 ( d t m ( i c a ) n 即功 m a x ( d i m ( 1 ( a ) ) , 幽 伪2 删 向nb 口j 向n b 印 r 4 nb 和功 田2 - 7 穿越( c r o u ) 关系 被包含( 狮t 1 1 i n ) 关系：对于几何对象a 和b ，如果a 和b 的交集就是a ，并 且a 的内部和b 的边界没有交点，那么称a 被b 包含( 见图2 8 ) 。即： w i t h i n ( a , 桫营向n b 一矽 口纠n 删和2 p 圈2 - 8 被包含( w i t h i n ) 关系 重叠( o v e r l a p ) 关系：对于几何对象a 和b ，如果a b 、a 和b 的交集具有 相同的维数，并且a 和b 的交集不等于a ，也不等于b ，则称a 和b 满足重叠关 系( 见图2 - 9 ) 。m p - o v l a p ( a , 砂营细州? 俐i 蕊州? 黝l d t m ( 1 ( a ) n 例 ( a n 6 矽 向n 6 缈 围2 哥重叠( o v e r l a p ) 关系 包含( c o n t a i n ) 关系：对于几何对象a 和b ，如果a 被包含( w i t h i n ) 于b ， 则称b 包含a 。 相交( i n t e r s e c t ) 关系：对于几何对象a 和b ，如果不满足相离( d i s j o i n t ) 关系，则称a 和b 相交。 相等关系：如果几何对象a 和b 在空间位置和属性上完全一样，则称a 和b 1 0 中田科学技术大学硕士学位论文 满足相等关系。 2 2 2 空间分析运算 空间分析运算，是基于地理对象的位置和形态特征的空间数据分析技术，其 目的在于提取和传输空间信息。空间分析运算主要有如下几种： 最短距离( d i s t a n c e ) 运算：对于几何对象a 和b ，d i s t a n c e ( a , b ) 返回a 和b 中任意两点间的最短距离 缓冲( b u f f e r ) 运算：对于几何对象a 和给定的距离d ，b u f f e r 伉d ) 返回所 有与a 距离小于或等于d 的点所组成的几对象。 凸包( c o n v e xh u l l ) 运算：对于几何对象a ，c o n v e x h u l l ( a ) 返回包含a 的最 小凸多边形。 交集( i n t e r s e c t i o n ) 运算：对于几何对象a 和b ，i n t e r s e c t i o n ( a , b ) 返回a 和b 的公共部分所组成的几何对象。 并集( u n i o n ) ：对于几何对象a 和b ，u n i o n ( a , b ) 返回a 和b 中所有点所组 成的几何对象。 差( d i f f e r e n c e ) ：对于几何对象a 和b ，d i f f e r e n c e ( a , b ) 返回所有属于a 但不 属于b 的点所组成的几何对象。 对称差( s y m m e t r i cd i f f e r e n c e ) ：对于几何对象a 和b ，s y m m e l r i e d i f f e r e n c e 吼b ) 返回所有属于a 但不属于b ，或者属于b 但不属于a 的所有点组成的几何对 象。 2 3 空间查询 空间信息的查询是地理信息系统中的一项基本内容，其效率和方便性是衡量 一个g i s 平台好坏的重要指标之一对于空间数据库而言，它除了具有普通数 据库的基本特征外，还具有其自身的特殊性，因此，空间数据库的查询兼有普通 数据库的查询能力并同时具备空间信息的查询能力。根据应用领域的不同，空间 数据库的查询方式也各不相同。对于给定的数据库d b ，基于m b r 的常用的查 询方式有【9 】； 1 ) 精确匹配查询( e m q ，e x a c tm a t c hq u e r y ) ：对于给定的查询数据q ，从 中田科学技术大学硕士学位论文 d b 中找出所有与q 相同的数据： 丑斯q ( 口) = 【o d b i o = 订 2 ) 点查询( p q ，p o i n tq u e r y ) ：给定点数据q ，从数据库中找出所有包含 点q 的数据： ，q ( 口) = ( o v b l w f e , t ( q , o ) 3 ) 相交查询( i q ，i n - - o n q u e r y ) ：给定一个d 维的矩形查询区间r = 1 0 w t ， h i g h l i x 1 0 w 2 ，h 讪2 】 1 0 w d ，h i g h d ，从数据库中找出和r 相交的所有 数据： j 口) = ( o d b l i n t e r s e c t ( r , o ) 4 ) 包含查询( e q ，e n c l o s u r eq u e r y ) ：给定一个d 维的矩形查询区间r = p o w t ， h i g l l l 】 1 0 w 2 ，h i g h 2 】x 1 0 w d ，h i g m ，从数据库中找出所有包含r 的 数据： 阳伪) = t o d f i 耽缃讹d ) 】 5 ) 被包含查询( c q ，c o n t a i n m e n tq u e r y ) ：给定一个d 维的矩形查询区间 r = 1 0 w l ，h i g l l l 】 1 0 w 2 ，h i g h 2 x 1 0 w d ，h i g m ，从数据库中找出所有 被r 包含的数据： c q ( e ) = 【o d b l c o m ：m n ( r ，o ) 6 ) 邻接查询( a q ，a d j a c e n c y q u a ) ：给定一个d 维的矩形查询区间r = p o w l ， h i g h t x 1 0 w 2 ，h i g h 2 】p o w d ，h i g 嘲，从数据库中找出所有同r 相切 的数据： a q ( r ) = f o d s i r o u o l ( r , o ) 7 ) k 近邻查询o 澍n q ，kn e a r e s t - n e i g h b o rq u e r y ) , 给定一个d 维的矩形查 询区间r - - 1 0 w i ，m # dx 1 0 w 2 ，i l i g h 2 x x 1 0 w d ，h i g l l d 】及正整数k ，从 数据库中找出距离i 最近的k 个数据： 触v j v 口( 月) = ( o 舢o k i d b i y e ed b f o 咖川o k 一1 l d 擂缸m a o ，骨) s d n 亡l c e ，曰) ) 2 4 小结 本章主要对空间数据库中的相关概念作了详细介绍，包括复杂空间物体的近 似处理，以及在m b r 近似处理基础上的空间关系运算和空间分析运算，最后介 中犀科学技术大学硕士学位论文 绍空间数据库所需要实现的各种空间查询。 中田科学技术大学硕士学位论文 第3 章理论基础 3 1 基于r 树的空间索引结构 3 1 1r - 树基本结构 g u t t m a n 在b 树的基础上，提出了r - 树【l o 】。r - 树是一种使用最小边界矩形 ( m b r ) 来索引空间对象的数据结构。由于r - 树的查询效率高，且适用范围广， 能支持多维对象，所以得到了广泛的应用。其后人们对r 树进行了深入研究， 又提出了r - 耦j 的许多变体。在r - 树的改进过程中，一种思路是对r 树原有的结 构作改动；另一种思路则在保持r - 树的基本结构不变的情况下，对r - 树的生成 和动态维护算法进行改进，其中r 树 1 1 】是被公认为最好的一个改进。 1 基本概念 在r 树中，一个数据对象由包围它的最小边界矩形m b r ，它限定了数据对 象的边界。在r 树中，每一个中间结点关联一个完全包含它的孩子结点的m b r 。 树的叶结点中包含指向数据库中对象的指针，而不是像中间结点那样指向该结点 的孩子。如图3 1 和3 - 2 根节点、r i r 2 指向的节点为中间结点，r 3 一r 7 指向 的节点为叶予结点，r s - - , r 1 9 指向具体的空间数据。 田3 - tr 嗣索引结构 1 4 中田科学技术大学硕士学位论文 r 树中的术语定义： 结点( n o d e ) ：用n 表示，结点又分为叶子结点l n ( l e a fn o d e ) 和中间结点 i n ( i n t e r n a ln o d e ) 项( e n t r y ) 用e 表示，位于叶子结点l n 中的项称为索引记录项i r e ( i n d e x r e c o r d e n u y ) ，位于中间结点玳中的项称为索引项m o n d e x e n t r y ) 。一个结点由 多个项组成。 在r 树中，叶子结点l n 的索引记录项i r e 的形式如下： ( i ，o b j e o t - i d e n t i f i e r ) ，i 代表几何对象实体的m b r ，o b j e c t - i d e n t i f i e r 代表唯一 标识一个几何对象实体。 中问结点i n 的索引项i e 的形式如下： o ，c h i l d - p o i n t e r ) ，1 是矩形区域，它代表此项所指下一层结点中所有项所构 成的m b r ，c h i l d - p o i n t e r 指向下一层结点。 m ：表示一个结点所能容纳的最大项数。 m ：表示一个非根结点必须容纳的最小项数，m 小于或等于m 2 。 中田科学技术大学硕士学位论文 2 r 埘的相关性质 r - 树具有以下性质： 除根结点外，每个结点的项数介于m 和m 之间； 根结点至少有两个孩子，除非它是叶子结点； 所有叶子结点位于同一层； 同一结点中项，其排列没有序的要求； 拥有n 个索引记录项i r e 的r 树的高度最大为l o g a n - 1 。比如，n = 1 0 0 0 0 0 0 0 0 ， m - - 2 0 ，m f f i l 0 ，则在最坏的情况下，叶子结点数为1 0 0 0 0 0 0 0 ，树的高度为8 。即 在最坏情况下，只需要做8 次磁盘操作即可索引到相应的几何对象。 使用r - 树作为空间数据访问的结构，可以实现对点、线、面所组成的复杂 空间几何体的高效索引 以下是r _ 树的基本算法【l o 】。其中，对于项e ，用e i 表示项中的矩形区域， e p 表示项中的o b j e c t - i d e n t i f i e r 或者c h i l d p o i n t e r 。 3 1 2r 树相关算法 1 插入算法 从本思想：找到合适的叶子结点，插入之，并可能产生分裂，在插入，分裂 过程中需要调整相关结点的m b r 。 算法i n s e r t ：插入一个新项e 到r - 树中 n ；调用c h o o s e l e a f 来选择一个合适的叶子结点l 以容纳项e ； 1 2 ；若l 中还能容纳e ，将e 加入l ，否则调用s p l i t n o d e 来获得两个结点l 和u ，它们包含了e 和l 中原有的所有项； 1 3 ；调用a d j u s t t r e e ，传递参数l ，l l ( 若产生了分琴1 ) ； 1 4 ：若结点分裂向上传播导致根结点的分裂，则生成新的根结点。 算法c h o o s e l e a f ：选择一个合适的叶子结点以放置新项e c l l 设n 指向根结点r o o t ； 中田科学技术大学硕士学位论文 c l 2 ：若n 是叶子结点，返回n ； c l 3 ：若n 不是叶子结点，让f 表示n 中的一项，该项f 容纳e 后，f i 在 面积上只需作最小扩展； c l 4 ：设n 指向f p 所指的孩子结点，转至c l 2 算法a d j u s t t t c e ：从叶子结点向上至根结点进行调整 a t i ：设n = l ，若l 进行了分裂，则设n n = l l ； a r 2 ：若n 为根结点，返回； a t 3 ：设p 为n 的双亲结点，e n 为结点p 中指向n 的项，调整e n i ； a t 4 ：若n n 存在，建一个新项d 州，使其指向n n ，同时计算出e m 盯，将 d m 加入到结点p 中，若不能容纳，则调用s p l i t n o d e ( 结点分裂算法) 产生结 点p 和p p ，它们包括了e n n 和原p 中所有的项 a = r 5 ：设n - - p ，n n = p p ，转至a t 2 。 结荫分裂o 妯d es p l i t i n g ) ：当某个结点含有m 项时，木能继续往里面加入新 的项，所以必须将m + i 项分成两组，将它们加入到两个新结点中。 判断结点分裂好坏的一个标准为：分裂后，两个新结点对应的m b r 的面积 之和最小。图3 - 3 就是一个结点分裂的一个例子： ( a ) 坏的分裂好的分裂 圈3 - 3 结点分裂好坏比较 最直接的分裂方法就是生成所有可能的，然后选择最好的一种分裂组合。但 是有2 川种可能，所以如果m 的值很大( 例如超过1 0 0 ) 就很难进行下去所 以这只是一种理论上和其他分裂算法进行比较判别的标准，不具有可行性。 下面介绍一种二次时间复杂度的分裂算法( q u a d r a t i cs p l i t a l g o r i t h m ) 。这个 中田科学技术大学硕士学位论文 算法的目的是为了得到小面积的分裂，但是不能保证分裂以后的面积之和最小。 算法q u a d r a t i c s p l i t ： q s i # 调用p i c k s e e d s 选出两项，将它们分别作为两组的第一个元素； q s 2s 若所有项都已分配完，则返回；若一组中的项如此之少，以至于将剩 下的所有项添至其中才能满足项数达到m 的要求，则进行分配且返回； q s 3 ：调用p i e k n e x t 选择下一项，将其分配到某组中，该组在容纳该项后， m b r 只需作最小的扩展。转至q s 2 ； 算法p i c k s e e d s ： p s i ：对每一对项e l 和e 2 ，设j 是容纳e 1 和e 2 后的m b r ，计算 d = a r e a ( j ) - a r e a ( e 1 i ) - a r c a ( e 2 i ) ； p s 2 ：选择d 值最大的一对项。 算法p i c k n e x t ： p n l ：对每一项e ，计算d l = “将e 加入到组l 后，其m b r 增加的面积一 同理计算d 2 ； ， p s 2 ：选出d l 和d 2 值差距最大的项。 我们可以对p i c k s e e d s 进行优化，使得结点分裂的时间复杂度降低到线性； 算法l i n e a r p i c k s e e d s ： l p s l ：在每一个维度上，选择最低点坐标最大( h i g h e s tl o ws i d e ) 和最高 点坐标最小( l o w e s t 碰g hs i d e ) 的两项。并记录两者之差： l p s 2 ；将差值除以m b r 在这一维上的区间宽度； l p s 3 ：选择最大者，返回这两项 2 删除算法 算法d e l e t e ：从r - 树中删除项e d i ：调用f i n d l e a f 来寻找存放e 的叶子结点l ；若没有找到则停止； d 2 ：从l 中删去e 中田科学技术大学硕士学位论文 d 3z 调用c o n d e n s e t r e e ，传递参数l ； d 4 ：若根结点只有一个孩子，则让该孩子结点成为新根。 算法f i n d l e a f i 在t 及其孩子结点中，查找项e f l l 着t 不是叶子结点，则对于t 中每一个与e 相重叠的项，将该项所指 的结点作参数，递归调用f i n d l e a f f l 2 ：若t 是叶子结点，则检查t 中是否有与e 相等的项，若有，则返回t 。 算法c o n d e n s e t r e e ：调整进行过删除操作的结点l c t i - 设n = l ，将存储被删结点的集合q 置为空； c t 2 ：若n 是根，转至饥6 ；否则，设p 为n 的父结点，e n 为p 中指向n 的项； c t 3 ：若n 中的项数小于m ，在p 中删去e n ，并把n 加入到集合q 中； c t 4 ：若n 没有被删除，缩小n 的m b r ，使其刚好包含到叶子结点； c t 5 ：设n = p ，转向c t 2 ； c t 6 重新插入集合q 中所有结点中的所有项，对于叶子结点中的项仍插入 到叶子结点中，但对于中间结点的项需要插入到其原来所在的那一层。 在b 树种，当某个结点中的项小于m 的时候，通常采用的是将该结点与邻 居结点合并。丽在r - 树种，采用了重新插入的方法。这是因为： 重新插入能够动态的保持整个树的良好结构，而不会因为某一项固定在其父 结点下而导致结构的逐步恶化；可以有效的利用插入算法；重新插入的项大部分 已经在缓冲当中，因为在以前的操作中已经被访问到( 见下一章) 。 3 查询算法 r - 树是一种高效的空间索引结构，它能够为空间数据库提供多种多样的查询 功能。以相交查询和最近k 邻居查询为例，以下是r - 树的查询算法： 中国科学技术大学硕士学位论文 ( 1 ) 相交查询 相交查询算法从根结点开始，对于每一棵与查询窗口8 有交集的子树都进行 搜索，直至叶子结点 算法i n t e 撇c t q u e r y 在根结点t 中查找和s 相交的所有叶子结点 i q l ：若t 不是叶子结点，则检查t 中的每一项e ，看e i ( e 所代表的m b r ) 是否和s 相交，对于相交的项，则对以e p 饵的c h i l d - p o i n t e r ) 所指的结点为根的 子树调用m t e r c t i 溯算法； i q 2 ；若是叶子结点，则检查t 中的每一项e ，看e i 和s 是否符合某种空间 关系( 此处为相交) ，若是，则将e 加入结果集中。 同理，对于第二章中介绍的包含、被包含、邻接查询，我们只需修改以上算 法中的第二步e i 和s 的空问关系判断条件，改为e i 是否包含s 或e i 是否被s 包含或者e i 是否和s 相切，而第一步不变。 ( 2 ) 最近邻居查询 在r 树上进行最近邻居查询实际上是搜索整棵树以寻求最优解。若要快速 找到最优解，则需使用剪枝的方法减小搜索范围 2 2 】。为此，给定一个查询点p 和一个几何对象o 及其m b r ，我们定义分支限界法中的代价函数，下界函数以 及上界函数( 如图3 - 4 ) ： 代价函数d i s t ( p , o ) ：查询点p 与几何对象o 之间的最近距离； 下界函数m i n d i s t ( p , o ) ：查询点p 与几何对象o 的m b r 之间的最近距离： 设点p - - - ( p l ，p 2 ，p k ) ，设矩形r 的两个顶点为s ( s l ，s 2 ，s k ) ，t ( t l ，t 2 ，墩) ， 且s l t l ，s 2 t 2 ，s k t k ，则 m i n d i s t t p , r ) f f i l p i - r 1 1 2 + 1 1 ) 2 - r 2 1 2 + 叫p k - r k 2 其中： 卜i ( 如果p l t 1 ) i - 皿( 其他情况) ! 里登兰垫查盔竺塑圭堂垡丝苎 上界函数m i n l 讧a x d i s t o ) ：查询点p 与几何对象o 的m b r 的四个顶点之 中距离p 第二近的点与p 点之间的距离，此函数保证肯定存在一个m b r 内的几 何对象，与p 点之间的距离小于或等于m i n m a x d i s t 假设对象x 代表最优解，如果对象0 是搜索过程中获得的一个解，那么d i s t 假 x ) 则n m a x d i s t ( p , o ) 。因而当任何结点的m i n d i s t 大于m i n m a x d i s t 0 , o ) 时，以 该结点为根的子树都没有必要进行搜索，从而达到快速剪枝的目的。 一一 m m i m i n l v l a 加i s t ( p ，a ) m i n d i 哗，a ) m 如m 麟d i s 自a p ，b ) m h l d i s t ( p ，b ) = o 田3 一量近邻居查询代价函数定义 算法n e a r e s t n e i g h b o r s e a r c h ：在r - 树t 中查找和p 最邻近的空间几何体， 返回