基于新型R*Q-树空间数据索引结构的研究

摘要

随着信息技术不断渗透到各个领域,它们对信息处理的需求也不断提高,因此,对空间数据库索引技术的研究愈发热门。其中,空间数据库索引技术是研究如何提高空间数据库的信息处理和信息管理性能的一种技术,目前它正处于趋于探索完善的重要阶段。
　　本文从当前比较流行的空间数据库索引技术着手。第一,详细阐述了各种空间数据库索引技术的基本原理,而且又分析了各种空间数据库索引结构的特点和优缺点。第二,在对典型四叉树、R*-树和常规 R*Q-树详细研究的基础上,本人设计出了一种新型 R*Q-树空间数据库索引技术。新型 R*Q-树通过在父结点加入VR*-树和HR*-树,使新型R*Q-树的数据集在分割线附近形成窄带,新型R*-树的子树重叠范围大大减小并且整个数据空间被分成一条条的窄带,查找效率显著提高。新型 R*Q-树的分裂技术也有所改进,具体思路是新型 R*Q-树在对象插入结点导致溢出时不立即进行分裂,而是将该数据项插入到邻近未满的兄弟结点中,如果该结点邻近的兄弟结点全部已满时,才利用聚类技术进行结点分裂,在邻近兄弟结点和分裂结点之间重新组合空间数据项。新型R*Q-树在确保查询性能的前提下,大大降低了构造代价,还大幅度提高了空间利用率。第三,实验分析证明了新型 R*Q-树查询性能和检索效率的高效性。在新型 R*Q-树之间以及子区域之间,不存在空间数据项的重复,使新型R*Q-树结构简单化。
　　论文在采用Java开发技术实现了对新型R*Q-树索引索引方法的仿真测试。然后依照该领域公认的有关索引算法性能评价标准,运用了大量随机性仿真空间数据库测试数据集,实现了对R*-树、新型R*Q-树索引算法与常规R*Q-树索引算法的仿真与比较。实验结果显示:新型R*Q-树有两棵R*-树即HR*-树和VR*-树,使其所划分子区的MBR面积最小,所以效率较高。另外,新型quad-tree不受固定分割极限的限制,它可以动态自适应地划分它的层次数,所以新型R*Q-树更具灵活性。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

1 引言

2 空间数据库索引技术的基础理论

2.1 空间数据库的基础理论

2.2 空间数据库索引技术的理论基础

2.3本章小结

3 主流空间数据库索引技术

3.1基于四叉树的空间数据库索引技术

3.2 基于B-树的空间数据库索引技术

3.3 常规R*Q-树

4 新型R*Q-树：基于常规R*Q-树的索引结构

4.1 新型R*Q-树的设计

4.2 新型R*Q-树算法

4.3 算法实现

4.4 本章小结

5 新型R*Q-树算法性能测试、分析

5.1 新型R*Q-树算法的实验测试平台

5.2 性能评估

5.3 本章小结

6 总结与展望

参考文献

作者简历

致谢