基于R-树的空间数据索引技术的研究与实现

摘要

近年来，地理信息系统获得了迅猛的发展，已广泛应用于公共管理、科学研究、商业及与人们同常生活密切相关的领域。地理信息系统对海量空间数据的存储、访问、表达和评估也变的越来越重要。传统的关系数据库能够支持空间数据的存储，却无法支持对其高效的访问，这是因为空间数据的多维特性与关系数据库的一般索引不相适应性，空间索引由此应运而生。 在空间数据库的关键研究问题中，空间数据的索引与查询占据着重要的位置。查询是数据库中的基本操作，所以查询的性能决定了数据库的性能，而要得到高的查询性能就必须建立一个好的索引机制，对于数据量庞大的空间数据库而言，建立一个高效的索引机制更是重中之重。 本文从当前业界普遍认同的主流空间数据库索引技术入手。首先，详尽地阐述各种空间数据库索引技术的基本原理和主要方法，并且剖析了各种空间数据库索引技术的主要设计思想和优缺点，针对R-树索引分析了它的各种优化方法。 其次，基于对经典的R*-树的研究与讨论，提出一种改进的空间数据索引结构R0-树，并给出相关算法。其主要思想是在内部树结点存储外部对象，如果将这样的对象存储在树的更高层，则低层结点的最小边界矩形MBR的面积更小，从而有效地提高空间数据的索引效率。 最后，基于相关索引算法的性能评价标准，采用大量真实的空间数据库实验测试数据集，完成了对所提出的R0-树索引与R*-树索引的测试与评估工作。测试结果表明，R0-树索引能够很有效地提高空间利用率，减少I/O访问次数，使索引性能得到大幅提升。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景和意义

1.2国内外研究现状

1.3课题的来源及研究内容

1.3.1课题来源

1.3.2研究的主要内容

1.4本文的结构组织

第2章空间数据索引相关技术研究

2.1空间数据库的基础理论

2.1.1空间数据

2.1.2空间数据库

2.1.3空间查询

2.1.4空间数据的目标近似

2.1.5基于目标近似的空间查询过程

2.2空间索引技术的分类

2.2.1按对目标处理方法的不同

2.2.2按索引结构的发展

2.2.3按处理数据的类型

2.3常用空间索引技术介绍

2.3.1格网索引

2.3.2 KD树及其变形树

2.3.3四叉树及其变形树

2.3.4 R-树及其变形树

2.4本章小结

第3章R-树索引的研究及改进

3.1 R-树索引

3.1.1 R-树的定义

3.1.2 R-树的相关算法

3.2 R+-树

3.3 R*-树

3.3.1插入路径的选择

3.3.2结点的分裂算法

3.3.3强制重新插入

3.4 R-树索引的优化改进

3.4.1空间聚类思想

3.4.2 R-树优化的相关讨论

3.5本章小结

第4章利用外部对象存储技术改进R*-树

4.1 Ro-树结构

4.2相关指标的定义

4.3插入和溢出处理

4.3.1外部对象的选择算法

4.3.2改进的贪心算法

4.4删除和下溢处理

4.5存储空间的分配

4.6本章小结

第5章实验及性能分析

5.1实验环境及说明

5.2实验结果

5.2.1建立索引的时间

5.2.2范围查询性能

5.2.3评价与分析

5.3本章小结

结论

参考文献

攻读学位期间发表的学术论文

致谢