基于R-树多维索引结构的优化研究与应用

论文摘要

随着计算机技术的研究和发展,空间数据库在计算机图形学,地理信息系统和多媒体数据库等各个领域都有广泛的应用,空间数据库的研究越来越受到人们的重视。传统的关系数据库虽然能够支持空间数据的存储,但却无法支持对其高效的访问,这是因为空间数据的多维特性与关系数据库中的一般索引不相适应。一般索引只适合对一维数据进行索引,因为其索引项是一维线性且严格有序的。空间数据的多维特性在任何方向上并不存在优先级问题,因此需要研究特殊的高效多维索引以适应多维特性的空间数据。多维索引由此应运而生,多维索引主要依靠空间对象之间的邻接性对数据进行组织,它的索引项通常是多维空间下的点或区域。由于空间数据本身的复杂性,以及目前对海量空间数据快速查询的要求日益提高,多维索引作为空间数据库中的重要组成部分,可以加快对空间对象的检索。因此,如何建立更有效的多维索引结构一直是空间数据库领域最现实、最紧迫、也是最前沿的研究课题之一。在论述了多维索引技术的相关概念以及多维索引技术的发展历程后,本文在研究R-树等有代表性且效率较高的多维索引技术的基础上,主要围绕两个问题进行了研究和取得的相应成果:第一:本文针对R*-树多维索引在强制重插算法上的不足,提出了一种新的强制重插算法用以改进R*-树多维索引结构。研究实验表明:改进后的R*-树与传统的R*-树相比在索引空间利用率,动态创建索引,索引检索等方面具有更高的性能。第二:R-树静态生成技术的Hilbert R-树算法在构建R-树的过程中容易造成结点之间的重叠。针对这一问题,本文提出了一种改进的静态生成算法。该算法具有存储利用率高,而且查询效率高的优点。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景与研究意义
• 1.2 国内外研究现状
• 1.3 国外几种常用的商业数据库的多维索引技术
• 1.3.1 Oracle 空间数据索引（Oracle Spatial）
• 1.3.2 IBM 空间数据刀片（Spatial DataBlade）
• 1.3.3 MySQL 空间数据扩展（MySQL Spatial Extensions）
• 1.3.4 ESRI 空间数据引擎（Spatial Data Engine）
• 1.4 本论文主要研究内容及组织
• 1.4.1 研究内容
• 1.4.2 论文的组织结构
• 第二章 多维索引技术相关概念
• 2.1 空间数据
• 2.1.1 空间数据的概念
• 2.1.2 空间数据的三个主要信息范畴
• 2.1.3 空间数据的特征
• 2.2 空间检索
• 2.2.1 空间查询
• 2.2.2 目标近似
• 2.2.3 基于目标近似的空间检索过程
• 2.3 多维索引
• 2.4 本章小结
• 第三章 R-树多维索引分析
• 3.1 R-树
• 3.1.1 R-树及其特点
• Seareh）算法'>3.1.2 查找（R_Seareh）算法
• Insert）算法'>3.1.3 插入（R_Insert）算法
• 3.1.4 ChooseLeaf 算法
• 3.1.5 AdjustTree 算法
• Delete）算法'>3.1.6 删除（R_Delete）算法
• 3.1.7 FindLeaf 算法
• 3.1.8 CondenseTree 算法
• 3.1.9 SplitNode 算法
• 3.1.10 PickSeed 算法
• 3.1.11 PickNext 算法
• 3.1.12 最近邻查询（Nearest Neighbors Query）算法
• *-树'>3.2 R^*-树
• *-树及其特点'>3.2.1 R^*-树及其特点
• 3.2.2 插入路径选择机制
• 3.2.3 结点有效分裂机制
• 3.2.4 强制重新插入策略
• 3.3 R-树性能分析
• 3.4 本章小结
• 第四章 R-树动态生成技术及其改进
• *-树分析'>4.1 R-树及R^*-树分析
• *-树强制重新插入算法的改进'>4.2 针对R^*-树强制重新插入算法的改进
• 4.2.1 相关概念定义
• *-树强制重新插入算法'>4.2.2 改进的R^*-树强制重新插入算法
• 4.2.3 影响多维索引结构性能的因素
• 4.3 实验结果与分析
• 4.3.1 实验环境
• 4.3.2 索引文件的设计
• 4.3.3 两种多维索引方法创建检索树性能比较
• 4.3.4 两种多维索引方法利用K-最邻近查询方法检索性能比较
• 4.4 本章结论
• 第五章 R-树静态生成技术及其改进
• 5.1 R-树的两类生成方法比较
• 5.2 R-树静态生成技术
• 5.2.1 通用自底向上的方式
• 5.2.2 Low-x R-树
• 5.2.3 Hilbert R-树
• 5.3 HILBERT R-树的改进的方法
• 5.3.1 New Hilbert R-树算法基本思想
• 5.3.2 New Hilbert R-树算法描述
• 5.4 实验结果与分析
• 5.4.1 实验环境
• 5.4.2 两种多维索引方法性能比较
• 5.5 本章小结
• 第六章 总结和展望
• 6.1 完成的主要工作
• 6.2 进一步要研究的方向
• 参考文献
• 致谢
• 附录A 攻读硕士学位期间公开发表的学术论文