（计算机应用技术专业论文）空间数据库的索引技术研究.pdf

一 c a n did a t e： z h a n gz e b a o s u p e r v i s o r ：p r o f z h a n gj i a n p e i a c a d e m i cd e g r e ea p p li e df o r：d o c t o ro fe n g i n e e r i n g s p e c i a l i t y ： c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m is s i o n ：d e c e m b e r ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ： f e b r u a r y ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y - 。 ， r ， 、 1 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：私率 日期：2 心d 年弓月日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文旧在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：芗k 串f 乞 日期： 叫分年弓月日 ， r q 一 7 l i h 1 空间数据库的索引技术研究 摘要 空间索引技术是空间数据库领域中的一个重要的研究内容，索引的性能 将直接影响数据库的性能，且数据的检索和查询是应用最多的操作，为了提 高查询的速度，必须建立高效的空间索引结构支持相关的操作，空间索引技 术经历了多年的研究和发展，形成了一套较完整的体系结构，但由于空间数 据的海量性、复杂性和多样性的特点，对索引结构提出了更高的要求，对空 间数据库中索引结构的研究成为一个研究的热点问题，如何建立高效的索引 结构、提出有效的查询处理算法是迫切的研究课题。本文从空间索引的建立 和基于索引的空间对象查询两个方面进行了研究，提出了一些较为有效的解 决方法。 针对现有的索引方法不能较好的保持空间数据的映射相关性，相邻的空 间对象不能存储在索引中相近的结点上，引入了批量加载的方法对数据进行 预处理，在分析影响空间索引性能的指标因素的基础上，对相对变化不多的 静态数据，提出了一种静态的批量加载方法，减少索引覆盖区域的大小，通 过实验对算法进行了验证，实验结果表明，提出的方法获得较好的空间利用 率，性能较以前算法有了改善和提高。 空间索引结构要随着数据进行动态的调整，动态索引结构的创建本质是 聚类问题。对已有的聚类算法的分析，引入基于网格和密度的聚类算法对数 据进行聚类，改进了原有聚类算法中的一些缺陷，将对象按照聚簇进行划分， 通过两级的索引机制进行组织索引，每个聚簇都建立各自的索引结构，通过 全局的r 树索引结构建立整个索引，实验结果表明，提出的算法进一步提高 了索引的时间和空间复杂度。 针对现有的基于方向关系模型的查询处理过程，在过滤阶段不能获得较 好的过滤结果，导致求精步骤的时间复杂度较高。根据对象m b r 之间的方 向关系的定义，在过滤和求精步骤之间插入一个中间步骤，根据参考对象落 在空间区域的不同划分，判断目标和参考对象的方位关系，通过对所有的可 能组合的情况进行分析，给出了解决方法，实现了更好的过滤候选对象目的， 减少进入求精步骤的数据对象，从而提高了基于方向关系的查询速度。通过 哈尔滨工程大学博十学位论文 实例对提出的方法进行了分析，性能有了很大的提高，验证了算法的有效性， 又通过实验进行验证，实验结果表明，算法在查询时间和i o 访问上均都有 了提高。 针对在近邻查询中参考对象被简化为一个点，使得查询的结果受到一定 程度的影响，且现有的k 近邻的查询算法不能很好的处理对象之间近邻查询 的问题。提出了基于等距离线的k 近邻查询算法，给出了更准确的过滤边界 值和对象之间的距离定义，提出了新的剪枝策略，减少了计算实际对象距离 的计算量，通过实例和实验对算法进行了分析和验证，分析的结果表明，算 法有较好的过滤性能，能够提高基于对象的k 近邻查询效率，进一步验证了 算法在时间和空间上的性能。 关键词：空间数据库；空间索引；批量加载技术；聚类分析；方向关系查询； 近邻查询 f 0 r _ h 哈尔滨丁程大学博十学位论文 m e t h o dc a ni m p r o v et h et i m ea n ds p a c ec o m p l e x i t y a c c o r d i n gt ot h ee x i s t e dq u e r yp r o c e s s i n gb a s e do nd i r e c t i o n a lr e l a t i o n s h i p q u e r ym o d e li t c a n t a c h i e v eb e t t e rf i l t e rr e s u l t si nf i l t e r p h a s e t h et i m e c o m p l e x i t yi sh i g hi nt h er e f i n es t e p o nt h eb a s i so ft h ed e f i n i t i o no fo b j e c t s m b r ，a ni n t e r m e d i a t ep r o c e s si si n s e r t e di nt h em i d d l eo ft h ef i l t e ra n dr e f i n e m e n t s t e p t h ed i r e c t i o n a lr e l a t i o n s h i po ft a r g e to b j e c ta n dr e f e r e n c eo b j e c t c a nb e j u d g e db yt h er e f e r e n c eo b j e c tf a l l i n gi nt h ed i f f e r e n ts e g m e n t a t i o n a l lt h e p r o b a b i l i t yc o m b i n a t i o nc a s e sa r ea n a l y s i s e da n dg i v et h es o l u t i o nm e t h o d t h e i m p r o v e dm e t h o dc o u l dd e c r e a s et h es i z eo fc a n d i d a t es e ti nt h ef i l t e rs t e p ，a n d t h u si tc a nr e d u c et h ew o r k l o a do ft h e r e f i n e s t e pa n di m p r o v et h es p e e do f d i r e c t i o n a lr e l a t i o n s h i p t h ev a l i d i t yo fm e t h o di sb ep r o v e db yi n s t a n c ea n a l y s i s a n di m p r o v et h ep e r f o r m a n c eo fi n d e x a n dt h e n ，i tu s e se x p e r i m e n t st op r o v et h e v a l i d i t y t h ee x p e r i m e n t sr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o dp e r f o r m sw e l l w i t hr e s p e c tt ob o t hi 0 - a n dc p u - t i m e t h er e f e r e n c eo b j e c ti ss i m p l i f i e dt oap o i n ti nn e a r e s tn e i g h b o rq u e r y t h e q u e r yr e s u l t sh a v ee f f e c ti nac e r t a i ne x t e n t t h ee x i s t e dk l mm e t h o dc a l l tw e l l h a n d l et h en e a rn e i g h b o u rq u e r ya m o n go b j e c t s akn e i g h b o rq u e r ym e t h o db a s e d o nt h ee q u i d i s t a n c ei sp r o p o s e d t h em o r ee x a c tb o u n d a r yv a l u ea n dd e f i n i t i o no f o b j e c t sa r ep r e s e n t e d t h ep r o p o s em e t h o dr e d u c et h ew o r k l o a do ft h er e a l d i s t a n c eo fo b j e c t s t h ev a l i d i t yo fm e t h o di sb ep r o v e db yi n s t a n c ea n a l y s i s t h e a n a l y s i sr e s u l t ss h o wt h a tt h ea l g o r i t h ma c h i e v eb e t t e rf i l t e re f f e c t t h em e t h o d i m p r o v e dt h ekn e i g h b o rq u e r ye f f i c i e n c ya n dp e r f o r m sw e l lw i t hr e s p e c tt ob o t h i nt i m ea n ds p a c 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 ；b u l k - l o a d i n g ；c l u s t e ra n a l y s i s ； d i r e c t i o n a lr e l a t i o n s h i pq u e r y ；n e a r e s tn e i g h b o rq u e r y 一 ， - 、l 空间数据库的索引技术研究 目录 第1 章绪论。 1 1 研究背景、目的及意义 1 2 国内外研究现状 1 2 1r 树家族的索引建立 1 2 2 批量加载的索引建立8 1 2 3 索引的查询方法1 1 1 2 4 索引技术的应用1 2 1 3 空间索引存在的问题1 2 1 4 论文的组织结构与研究内容1 3 第2 章空间数据索引概述1 5 2 1 空间数据及索引结构特点1 5 2 1 1 空间数据的特点1 6 2 1 2 空间索引结构的特点1 7 2 2 空间索引的发展和分类1 8 2 2 1 空间索引的发展1 8 2 2 2 空间索引的分类1 9 2 3 典型的空间索引结构2 1 2 3 1k - d 树索引结构2 1 2 3 2k - d b 树索引结构2 2 2 3 3 四叉树索引结构2 2 2 3 4 网格索引结构2 3 2 3 5r 树家族索引结构2 4 2 3 6 典型的索引结构对比2 8 2 4 空间数据查询方式2 9 2 5 空间查询代价模型3 1 2 6 本章小结3 4 哈尔滨t 程大学博士学位论文 第3 章基于批量加载技术的索引建立方法3 6 3 1 问题的提出3 6 3 2 相关研究3 7 3 2 1 静态的批量加载技术3 8 3 2 2 动态的批量加载技术4 1 3 3 基于批量加载的索引建立方法4 2 3 3 1 算法的描述4 3 3 3 2 算法的分析4 4 3 4 仿真实验与结果分析4 5 3 4 1 实验的数据集和性能指标。4 5 3 4 2 结果对比分析4 6 3 5 本章小结4 8 第4 章基于改进聚类的索引建立方法。4 9 4 1 问题的提出4 9 4 2 相关研究。5 0 4 2 1 聚类分析。5 0 4 2 2 聚类方法的比较5 9 4 2 3 基于聚类的索引构建。6 1 4 3 基于改进聚类的索引建立方法6 2 4 3 1 算法思想6 2 4 3 2 改进的聚类方法6 3 4 3 3 树型索引结构的建立6 5 4 3 4 算法描述6 6 4 4 仿真实验与结果分析6 7 4 4 1 性能指标和数据集6 7 4 4 2 结果对比6 8 4 4 2 性能分析。6 9 4 5 本章小结7 1 第5 章方向关系查询过滤方法7 2 4 一 i 人 5 3 方向查询精过滤方法8 0 5 3 1m b r 的方向关系8 0 5 3 2 算法的方向模型8 2 ，5 3 3 方向关系查询处理过程8 2 5 3 4 精过滤查询处理方法8 4 5 4 仿真实验与结果分析。8 8 5 4 1 实验的性能指标和数据集8 8 5 4 2 结果对比分析8 9 5 5 本章小结9 l 第6 章基于等距离线的近邻查询方法9 2 6 1 问题的提出9 2 6 2 相关研究9 3 6 2 1b a b 算法9 4 6 2 2b f 算法。9 6 6 2 3 其他的近邻算法9 7 6 3 基于等距离线的近邻查询方法9 8 6 3 1 相关概念9 8 6 3 2 近邻算法的剪枝规则。1 0 2 6 3 3 近邻查询处理过程1 0 4 6 3 4 算法描述1 0 5 6 4 实例分析1 0 5 6 5 实验结果与性能分析1 0 8 6 6 本章小结。1 1 1 结论1 1 2 哈尔滨_ t 程大学博七学位论文 参考文献1 1 4 攻读博士学位期间发表的论文和取得的科研成果1 2 6 j i 定谢1 2 8 个人简历1 2 9 人 奎 第1 章绪论 第1 章绪论 1 1 研究背景、目的及意义 空间数据库的研究始于2 0 世纪7 0 年代i z i 2 l r a l ，主要应用于地图的制图、遥 感图像处理等领域，主要是为了有效的利用卫星遥感资源迅速绘制出各种经 济专题地图，传统数据库对于空间数据的表示、存储、管理和检索等问题上 均有很多的缺陷，无法满足这些数据的处理要求，从而形成了空间数据库这 一研究领域，随着地理信息系统( g i s ) 、计算机辅助设计与制造( q 讧删) 、 多媒体系统、机器人、数字地球、移动通信以及定位服务等应用领域的发展， 对空间数据的研究越来越多的受到了人们的重视和青睐。 空间数据库在许多的领域当中都有着重要的应用，是数据的采集、存储 和管理的中心，与传统的关系型数据库的区别在于，其存储和处理的对象是 空间数据，空间数据是指与二维、三维或者高维空间的坐标或者范围相关的 数据，例如地图上的湖泊、城市、地理信息等，人们不仅希望可以检索到准 确的数据信息，而且希望检索的速度尽可能快，在空间数据库中，空间的查 询效率是衡量空间数据库性能的一个重要标志，由于空间数据库处理的数据 量十分庞大、处理的空间对象具有复杂性和多样性，因此为了更加高效处理 这些复杂的数据，必须引入一种提高空间数据库查询性能的技术空间索 引技术1 4 1 1 5 。 空间数据库中空间索引的提出主要是基于两个方面：一是在计算机的体 系结构中，将存储器分为内存和外存两种，访问外存与访问内存所需要花费 的代价差异是非常大的，虽然随着技术的发展和硬件技术的进步，内存的容 量也逐渐增加，但也不可能将所有的数据都载入到内存中，若想更好的处理 一个大型的数据库，大部分的数据仍然被存储在外存上，如果没有更好的索 引结构对数据进行组织，访问一个数据就需要遍历所有的数据集或整个的数 据文件，这样会严重的影响数据库的查询效率，这样的方式是不可取的。因 此必须对存储在外存的数据进行更好的记录和组织，通过对内存中存储的一 哈尔滨t 程大学博+ 学位论文 宣暑宣置i ；昌宣i i ；宣皇i i i 暑i 宣i i i i i i i ；i ；i i i ；宣i i i ；i ；i i ；i i i i i i 宣宣i i ；宣；i i i i i i i i i 宣暑宣暑i i i 宣i 宣 些信息的计算，可以直接定位到要访问数据的位置，这样才能提高访问数据 的效率，由于空间数据库中，所要处理的数据都是空间数据，要涉及的是海 量的复杂数据，所以空间索引结构对于提高空间数据库的查询性能是至关重 要的；二是空间数据库中处理的数据具有多样性和不能排序性，空间中的数 据不能在保持相关性的前提下映射到低维空i n - 中，这使得传统数据库中典型 一 的索引结构已经不再适用。在传统数据库中典型的索引结构所处理的数据类 - 型都是原子的数据类型，无论是字符型还是数值型都是一个有序集，数据集 中的任何两个数据的关系都可以在某一个维度上确定，但其关系只能大小关 系，而空间数据的多样性使得其不能很直接的得到排序关系，因此传统的对 于低维上的索引结构已经不能满足空间数据库中的要求，需要一种能够更好 的处理高维数据的空间索引结构，本文的主要研究内容就是如何能够建立更 好的索引结构以适应高维数据，同时尽可能的保持空间数据的各种特性，在 一些重要的性能指标上提高索引结构的效率。 空间索引就是依据空间对象的位置和形状等信息，或者基于空间对象的 某种关系，按照一定的组织顺序进行排列的数据结构，其中包含了对象的大 部分信息，比如对象的标识、近似表示的外接图形以及指向具体的某个空间 实体的指针。随着地理信息系统应用更加的普及，对数据库的性能要求也是 越来越高，而且空间索引技术一直是空间数据库研究领域的一个重要组成部 分，研究与空间操作相适应的空间索引机制，适应大规模的空间数据库的空 间索引机制已经迫在眉睫。 空间的索引技术是空间数据库研究领域的一个重要的内容，也是比较困 扰研究者的难点之一，而开发出一种能够支持海量、复杂、多样的空间数据 的高效空间索引结构是所有研究者的共同愿望，如何建立更高效的空间索引 结构是这些领域内最现实、最迫切也是最前沿的研究课题，本文主要是针对 空间索引结构的建立、检索和查询等方面进行了研究，提出了一些较为有效， 的解决方案。 一 1 2 国内外研究现状 目前m 多 l - 的许多学者对空间索引的研究较多，尽管有许多的技术和方法 2 第1 章绪论 都有不同程度的提高，但至今仍未找到一个最佳的空间索引技术。而国内在 空间索引技术方面的研究相对较少，同时也提出了不少的方法，在不同的应 用领域都有重要的应用。 空间数据库的研究经过了几十年的发展1 6 l ，涌现了大量的空间数据索引 方法i t i ，传统的索引方法都是基于b 树和散列索引的，这些索引方法比较适 用于线性的结构，在空间的索引方法中有格子文件及其变形、四叉树及其变 形、k - d 树及其变形1 8 1 、r 树及其变形等1 9 1 ，还可以划分为基于点数据的索引 结构和基于非点数据的索引结构两大类，基于点数据的索引结构包含有：四 叉树及其变形、k - d 树及其变形、k - d b 树和格子文件等索引结构；基于非 点数据的索引结构有：r 树、r 树1 1 0 l 、p 树、r + 树0 1 1 、g r a y 码的索引结构、 h i l b e r t 码的索引结构、z 序索引结构等。除了以上的索引结构外，还有一些 其他的索引结构，如位图索引等，空间索引结构是空间数据库的重要组成部 分，也是影响空间数据库性能的一个重要方面，由于应用领域的多种多样， 很难找到一种通用的、完美的索引结构来组织空间数据，所以空间索引结构 仍然是当前相关研究领域的热点问题。， 在近几十年的对向量空间高维数据索引的研究中，根据索引的特点，一 些专家和学者们提出了大量的索引结构，将索引进行分类，主要有以下的几 种方式旧： t ( 1 ) 根据索引结构可以处理的对象类型进行分类，可以分为点数据类和 空间数据类。点数据类是指那些只能处理点数据的索引结构，如k d t r e e ， m k d 树，t v - t r e e 等嘲；空间数据类是指可以处理空间对象的索引结构，不 仅可以处理点对象还可以处理线对象、面对象等具有一定形状的数据的索引 结构，如r t r e e ，r * - t r e e 等。 ( 2 ) 根据索引创建时的组织形式进行分类，可以分为静态索引结构和动 态索引结构。其中静态索引结构是指用批处理方式将全部数据构建成索引， 对于索弓 中数据的插入和删除操作比较少，一旦建立索引，数据相对是静态 的，变动比较少，不能很好的支持动态的插入和删除，可以通过预处理的方 式对数据进行批量的构建索引结构，这类索引结构典型的代表如p a c k e d r t r e e 【1 ；动态的索引结构是指，在创建索引的过程中，数据是依次插入而 3 哈尔滨t 程大学博十学位论文 生成的整个索引结构，而且可以支持数据一定程度的插入和删除操作，其前 提是要保持r 树的特性，如动态r t r e e 、动态r 宰t r e e 等。 ( 3 ) 根据划分方法的不同，可以分为数据划分类、空间划分类和混合划 分类。数据划分方法是根据数据所在的位置层次进行划分，然后进行索引的 创建，索引中结点之间可能会存在相互重叠的现象，典型的索引结构如r 树 等；空间划分类是指将整个对象空间进行分割，划分成互不相交的若干区域， 因此对象有可能分布在多个区域上，这类索引结构的典型代表如k d 树；混 合划分类是指既根据空间进行划分又根据数据进行划分，两者兼有的一种方 法，典型的索引结构如h y b r i d t r e e 等i t 习。 ( 4 ) 根据索引结构划分空间是否为线性结构，将索引分为线性和非线性 的空间索引，非线性的索引结构还可以分为网格类的索引和基于树索引类两 类，基于树索引类按照其空间对象的近似技术的不同分为基于凸多边形的、 基于约束的和基于m b r 的空间索引结构，r 树系列的索引结构都是基于 m b r 类的，也是基于树索引结构的典型代表，其他类的代表有c e l l 树、 b s p 树和、a f i l e 等i - 6 l 。 ( 5 ) 根据结点近似表达对象的类型不同，可以分为矩形、球形和混合型。 对不同的近似图形的选择将会直接影响到对象的检索和查询速度，矩形的表 示对象不是十分精确，但由于计算简单，仍然被广泛的采用和选择，选择矩 形的索引结构包括有k d 树、r 树和r 树等：选择球形的有s s 树1 1 7 1 、t v 树 等；混合类的有s r 树等【t 田。 1 2 1r 树家族的索引建立 在研究的若干空间索引结构中1 1 9 1 ，r 树是当前最流行的空间索引结构之 一，在原始的研究和一些商用的数据库中被广泛的应用，而r 树的构建方法 又是r 树的研究重点之一，在传统的r 树中从一棵空树开始，利用顺序插入 的算法逐个的插入对象1 2 0 l ，从而生成整个r 树，这种方法所带来的插入代价 十分的巨大，尤其对于规模较大的数据来说，索引创建的过程要耗费大量的 时间，所以许多的专家学者提出了很多关于r 树构建方法的改进，其中有一 些索引结构在性能上有了提高，并且算法也相对简单，得到了一定程度的应 用，但依然存在自身的缺点，对于查询效率并未取得较好的效果，可以采用 4 埠 第1 章绪论 一些批量的加载技术或者引入聚类的方法来提高索引的性能，所以其研究和 发展的空间还是很大的。 近些年来，人们对于空间数据库中的索引结构产生了浓厚的兴趣，为了 更加高效和快速的存储和检索空间数据库中的海量数据，专家学者提出了大 量的空间索引结构，综合的概述这些索引结构方法，将其内容大概分为几个 方面内容进行阐述：( 1 ) 基于填充曲线的空间索引结构( 2 ) 基于网格的空间 索引( 3 ) 基于树的空间索引结构。 1 2 1 1 基于填充曲线的索引结构 在高维的空间中，空间数据之间并不能进行很好的排序，数据之间无法 进行大小的比较，但数据在存储设备上的逻辑关系是一维的，因此需要找到 一种从空间的高维数据到低维的存储空间的映射关系，这种映射关系要保证 距离不变( d i s t a n c e p r e s e r v i n g ) 的原则，使得空间相邻的对象在一维空间上 保持相近的位置，而且还要保证空间映射的一对一关系，空间上两个不同的 对象不能映射到一维空间上同一个点，为了达到这样的效果，提出了许多的 映射方法，这就是线性索引方法，也称为空间填充曲线索引。 空间填充( s p a c e f i l l i n g ) 曲线是通过一条曲线来填充整个空间，计算空 间对象所对应的曲线的索引值，用其来代表一个对象或者一个单元，每种填 充曲线都有自己的计算方法，根据计算得到的索引值，建立整个的空间索弓i 结构，主要的空间填充曲线有h i l b e r t 曲线1 1 4 l 、z 序( z - o r d e r ) 曲线和格雷码 ( g r a yc o d e ) 等，其中是以h i l b e r t 曲线为代表，由于其能够很好的保持空间 距离映射不变的特性，因此得到比较广泛的应用1 2 1 1 1 兹1 。 陆锋和周成虎等提出了一种基于h i l b e r t 排列码的g i s 空间索引方法1 2 3 1 ， 分析了基于栅格格网的空间索引方法在空间查询中的重要的地位，对基于 g r a y 码、m o r t o n 码等的空间索引结构进行了分析和比较，得出了i - i i l b e r t 码 在空间查询中效率是最高的，在兼顾内存索引和磁盘索引的基础上，提出了 基于h i l b e r t 空间排列的点特征二叉平衡排序树动态索引结构和基于角点回 溯的线性特征索引结构，并对其在g i s 空间中的应用进行了讨论。 江崇礼和刘天建等人利用h i l b e r t 曲线的良好聚类特性解决了r 树查询路 径的非唯一性问题，通过最小外接矩形的分解技术确定多边形的形状，直 5 哈尔滨工程大学博十学位论文 接获得空间对象的具体结构信息，从而取得较为精确的查询结果，采用了改 进的分裂算法，提高了结点的分配效率和饱和度，减少i o 的访问次数，取 得了一定的成果。 1 2 1 2 基于网格的索引结构 网格空间索引结构的思想是：将空间区域进行划分，划分为大小相等或 不等的网格，每个网格都包含一定数量的空间对象，在进行查询操作时，先 确定查找范围所对应的网格，然后在从这些网格中快速查找满足条件的空间 对象。为了获得更好的灵活性和更高的性能，引入了网格文件( g r i df i l e ) ， 网格文件的引入可以使得精确匹配查询和部分匹配查询都有良好的f o 性 能。网格文件是采用多属性的索引技术将n 维空间进行分割，网格文件的使 用目标是可以实现二次磁盘访问原则：一次访问获得数据的目录项，另外一 次根据索引项中的内容定位到具体的实际桶以获得实际的对象。所以一般网 格文件通常都是由两部分组成的：一部分包括n 维网格目录( g r i dd i r e c t o r y ) ， 目录中每一项都对应一个具体的网格，另一部分是由称为线性比例的一维数 组组成的结构，这个数据是用来标识网格目录的索引，这个索引引用了包含 对象的块或桶，可以一次性的定位到具体的存储单元，对单元的数据进行相 关的操作。 基于网格的空间索引结构的搜索速度是比较快，对于精确的匹配查询， 只需要做两次访问即可，一次是对目录的磁盘访问，另一次是访问实际的数 据对象，然后网格文件也会造成目录非常松散，因而浪费主存缓冲区和二级 存储空间，也就是在存储的过程中，可能有些空间只有非常少或者根据就没 有数据，而相邻的目录项可能均指向同一个网格单元，也就是对于局部匹配 和范围查询来说，需要多次扫描很多只包含少量数据的目录项。文献【2 5 】分 析了网格空间索引机制存在的问题，给出了具有自适应能力的改进型的网格 空间索引结构，提出了一种自适应的层次网格空间索引算法。文献【2 6 】则在 深入研究层次网格空间索引技术的基础上，提出了一种基于内外块算法的层 次网格空间索引查询算法，通过其实验进行了验证，结果表明算法大大地提 高了层次网格索引结构的效率。文献 2 7 1 提出了一种改进的网格索引生成算 法，避免了在生成网格索引时遗漏目标覆盖的网格格子。 6 一 ， 第1 章绪论 1 2 1 3 基于树的索引结构 基于树的空间索引技术的主要思想是：先采用空间多边形对空间对象进 行近似，空间中的空间对象就可以用近似的多边形进行表示，然后将近似的 多边形根据索引结构的组织形式构建为树形结构，按照空间对象的近似不同 可以分为凸多边形的空间索引、基于约束的空间索引和基于m b r 的空间索 引，其中基于m b r 的索引结构是现在最流行，也是应用最为广泛的一种， 大部分的树形索引结构都是基于m b r 的近似表示。 基于凸多边形的空间索引是将数据空间划分为多个凸多边形，依次对凸 多边形再进行同样的划分，一直达到满意的精度为止。若每次都将索引空间 进行一分为二的划分，每次一分为二的便形成了一颗b s p 树1 2 a l ，其可以很好 的适应空间对象在整个空间的分布情况，但由于深度较大，操作的过程中需 要多次的进行i 帕访问。c e l l 树是将索引空间划分为多个凸多边形例，然后 再依次进行划分，直至达到满意的精度为止，虽然其f o 的访问次数比较少， 但需要更多的存储空间，并且在精确匹配的过程中计算也比较复杂。c p 树是 c e l l 树的变种侗，其允许子空间的部分覆盖，虽然具有较少的i o 访问次数， 但同样需要比较多的存储空间和复杂的精确计算。 基于约束的空间索引的主要代表是o 树1 3 0 l ，采用空间近似算法，将空间 对象按照公式表示为一组约束表达式，然后根据空间对象之间的关系建立空 间索引树，优势在于可以自然地表示空间对象之间的关系，但对于空间对象 的精确匹配仍然需要大量的计算。 r 树的变种和改进是最为普遍的一种，s e u i s 等设计了r + 树1 3 l l ，避免了 重叠，规定了兄弟结点之间的m b r 不能有交叠，这使得搜索性能较好，但 由于不能重叠，对象被存放在多个结点中，因此又使得插入和删除操作的效 率较低，数据的冗余度增加，降低了性能。b e c k m a n 等设计了r 。树1 1 0 l ，指出 区域重叠并不是影响检索性能的直接因素，插入过程才是关键，提出了结点 的强制重新插入技术。文献【3 2 】中提出r 1 i n k 树，将树中同一父结点的所有 子结点用一个右兄弟指针连接起来，当发生结点分裂时，采用h a l f - s p l i t 结点， 保证了结点分裂期间r 树的有效访问。文献f 3 3 1 中提出了q r 树，主要的方 法是将索引空间i s 0 分成四个子索引空间i s l ，i s 2 ，i s 3 和i s 4 ，再对每个子 7 哈尔滨工程大学博十学位论文 空间i s i 建立一个r 树s r i 。对空间对象s o ，若其m b r 完全包含于某个i s i ， 则将其插入i s i 对应的r 树s r i 中。s r 树将空间对象分割为多个部分，索引 中结点的m b r 包含的或者和树中某个结点m b r 相交的部分称为s p a n n i n g 部分，其余部分称为残余部分，将s p a n n i n g 部分插入相应结点中，残余部分 插入树叶中，其减少了死空间，但增加了树的高度。x 树将覆盖范围比较广 的特大空间对象存储在树或者子树的根结点，其他占据比较小范围的空间对 象存储在树或者子树的叶结点，当空间中大的空间对象较多时，会占据较多 的磁盘空间，使得索引的顺序访问性能下降。h u a n g 等提出了c o m p a c tr 树， 其特殊的分裂算法，使得该变体可以达到几乎1 0 0 的存储利用率，并导致 结点分裂的次数明显减少，构建索引的开销低于r 树，且易于实现和维护， 但其检索性能仅与r 树相仿，不及某些变体优良。有关r 树的优化改进的r 树变种还有很多，如基于移动空间对象的q + rt r e e t n ，基于多维数据仓库的 r 。树的改进版d c a - t r e e l 3 5 l ，基于执行成本模型的c u r t r e e l 3 6 1 ，用于实现空 间连接的s e e d e dt r e e l a n ，基于o l a p 范围查询的r a t r e e 等。 1 2 2 批量加载的索引建立 专家学者提出了r 树批量操作技术，其中h i l b e r tp a c k e dr 树由于其性 能上的优越和算法简单的特点而被广泛应用。但是，和其他空间排列码一样， 它不能完全保证对二维空间关系的维护位置上相邻的空间数据所对应的 h i l b e r t 值并不一定相邻，这种状况会使得构造的r 树的结点之间产生重叠， 从而降低其查询效率。空间数据库用以存储点、线、区域等非结构化空间数 据，对这些空间数据进行查询是最普遍的操作。常见的查询有点查询、窗口 查询、相交查询等，其中空间查询是最重要、最耗时的空间查询1 3 8 1 1 3 9 1 。 对空间索引的要求是要支持动态的更新以使索引和数据库保持一致，一 般讨论的都是动态的索引机制，随着数据进行动态的更新，但这些索引都会 随着更多的操作而导致性能的下降，甚至达到了无法忍受的地步。对r 树家 族的索引结构而言，在索引中插入一个对象会导致结点的分裂，不同的索引 机制处理分裂的方式不同，这样无疑增加了结点之间的相关性，在查找的过 程中会降低查找的效率，对某些可以非平衡的索引结构来说，插入某个结点 8 第1 章绪论 会使得某个分支的深度远大于其他的分支，这样的方式对于数据的插入顺序 会有很高的要求，而且查询的时间复杂度会逐渐退化到线性的地步，就失去 了索引的意义了，因此要改进已有的索引，提高其查询的性能。 对于空间数据库中数据的更新操作较少的情况下，可以将这些数据进行 一定的预处理，然后通过批量的方式一次性的建立整个索引结构，而非像动 态索引结构那样一次一个的插入，这种算法是压缩算法。r 树的压缩方法通 常的做法是，将所有对象的外包矩形共r 个进行排序，并且依次按照分组规 则分为若干组，每个组中包含有n 个对象( n 是结点的最大容量) ，将每组的 对象存放在一个结点中，得到每组包含所有对象的最小夕卜接矩形，再对这些 矩形进行递归操作，直至生成整个索引。 压缩的算法中主要有以下的几种；根据矩形中心的x 轴坐标的大小进行 排序；根据矩形中心的h i l b e r t 值进行排序f l 飞依次根据各坐标轴的坐标进行 排序 4 0 l 。压缩方法可以更好的提升空间利用率，而且这样的处理方法，会得 到较为全局的优化效果，较一些局部的优化有了整体上的考量，性能也有一 定程度的提高，所以相对来说查询的效率也较高。 r o u s s o p o u t o s 和l e i f k e r 最早提出了i o 复杂度为0 ( n l o g n ) 的实用r 树的批生成算法1 4 q ，采用矩形的某个顶点坐标或者矩形的中心点的x 或y 坐 标进行一维的顺序排序，按照排序后的矩形顺序的添加到r 的结点中，顺序 的将每个结点都填充满，直至到最后一个结点可能不满，因此是一颗非常紧 缩的r 树，其空间存储效率可以达到近似1 0 0 ，算法的问题是由于只考虑 了单个方向的排序结构，导致生成的r 树的结点都偏向于长条形，通常对于 点查询比较有效，对范围查询的处理能力不高。 b e r c k e n 提出了一种基于缓冲区的批量加载方法1 4 2 l ，这种方法是区别与基 于排序的加载方法的，也可以看作是基于种子树方法的推广1 4 3 1 ，其不仅局限 于对r 树适用，而且适用于所有基于树的空间索引结构，该方法借鉴了b u f f e r 树的思想【4 4 l ，通过l a z yb u f f e r 技术，利用一个有效的临时数据结构，一次一 层地建立整个索引结构，避免数据排序的预处理过程。 b e r c h t o l d 等提出了一种自顶向下的的空间划分方法 4 s l ，首先对整个空间 进行划分，再按照后序遍历的方式对分支进行深度优先搜索，自底向上地的 9 哈尔滨工程大学博士学位论文 逐层生成整个的r 树结点的索引结构，算法在进行划分的时候采用比较灵活 的方式避免了进行死板的划分，可以根据实际对象的分布状况进行划分，可 以较为自由的选择从任一超平面方向的任意位置开始，按照任意比例对空间 进行划分，选择不同比例会得到不同的效果，过分失衡的比例是不可取的， 会使得无法获得一定存储效率。 l e u t e n e g g e r 等提出了一种s t r ( s o r t t i l e r e c u r s i v e ) 压缩算法1 4 0 l ，可以 称为递归的网格排序算法，其基本的思想是假设在二维空间中有n 个矩形， m 是结点的最大容量，用矩形中心点的x 坐标对数据进行排序，用s = m 个垂直切片切割数据空间，使得每个切片有s 个结点和s m 个矩形，随后 在每个切片中，再用矩形的y 坐标进行排序，将每m 个矩形作为一组依次压 入到结点中，自上而下的一次一层的建立，递归的生成整