一种基于多级网格和改进QR-树的混合索引

摘要

随着信息技术的深入发展,各领域不断产生大量的空间数据,面对海量的空间数据,针对其特殊性以及空间查询的高度复杂性,应用中必须引进空间索引技术来提高空间数据库的查找性能。作为空间数据库的关键技术之一,空间索引性能的优劣直接影响到空间数据库的整体性能。
　　本文研究了目前主流的空间数据库索引技术。首先,详细阐述了各类空间索引技术的基本原理,并且分析了各种索引结构的优势和劣势。其次,在对网格索引和QR-树索引详细研究的基础上,本文提出了一种基于多级网格和改进QR-树的混合索引,该索引的基本思想是:首先对整个研究空间进行多级网格划分,这是整个索引结构的关键,适当层次的划分可以有效地减少存储空间,提高系统的效率,然后对最后一级的网格建立QR-树索引,减少了空间的重叠,提高查询的效率。
　　本文还在结点分裂时引入了惰性分裂技术。该项技术的核心思想是在结点溢出时不马上进行分裂,而是将索引项插入到邻近的未满的兄弟结点中。当邻近的兄弟结点都已满时再执行结点的分裂操作,进行分裂时利用聚类技术重组空间数据项,以获得更高的效率。采用了此项技术后多级混合索引可以提高整体的查询性能和检索效率,也大大提高了系统的空间利用率,具有重要的研究价值和良好的应用前景。
　　最后对该多级混合索引本文采用Java开发技术进行了仿真测试。然后依照该领域公认的有关索引算法性能评价标准,运用了大量随机性仿真空间数据库测试数据集,实现了对多级混合索引和常规 QR-树索引算法的仿真与比较。实验结果显示:多级混合索引的构造代价相对较低,并且拥有较好的时间复杂性和空间复杂性。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

1 引言

1.1问题的提出

1.2国内外研究现状

1.3本文研究的内容和结构

1.4本章小结

2 空间数据库基础理论

2.1空间数据存储

2.2空间数据查询

2.3空间数据库索引技术的基本概念

2.4本章小结

3 主流空间索引技术分析

3.1 基于树的索引结构

3.2 基于网格的索引结构

3.3 本章小结

4 基于多级网格和改进QR-树的混合索引

4.1 混合索引的结构设计

4.2索引机制和数据结构

4.3 实现算法

4.4 本章小结

5 算法性能分析和算法实现

5.1 算法分析

5.2 算法实现

5.3 本章小结

6算法性能测试

6.1 算法的实验测试平台

6.2 实现算法测试的工具

6.3 性能评估

6.4 本章小结

7 总结与展望

7.1 研究工作总结

7.2 未来展望

参考文献

作者简历

学位论文数据集