空间自适应动态平衡QER～+-树的设计与实现

论文摘要

在空间数据库设计中，为了提高数据存取和管理的效率，一般都要为空间数据库建立索引，不同的空间数据索引结构和索引管理技术，直接影响系统的性能。空间数据的复杂性决定了其索引结构的复杂性。空间数据索引作为一种辅助性的空间数据结构，介于空间操作算法和空间对象之间，它通过筛选，排除大量与特定空间操作无关的空间对象，从而缩小了空间数据的操作范围，提高了空间操作的速度和效率。空间数据索引技术是提高空间数据查询和各种空间分析操作等方面效率的关键技术。二十多年来，国内外学者提出了许多不同的空间索引方法，包括R树系列，四叉树系列，网格索引等等，这些索引方法各有优缺点。本文对空间索引的研究现状进行了粗略的总结，并对多种典型的索引方法进行了深入的研究和分析，主要分析了其结构，操作算法及性能。本文结合已有索引技术的优点，提出了一种新的基于四叉树，R-树及R+-树的空间索引结构：QER+-树，给出其结构说明和相关算法的描述与实现，并通过实验测试其性能。QER+-树可以限制查询范围，减少索引空间重叠。此外，在结点分裂时，还采用了强制重插入机制，优化了树的结构。因此整体上提高了索引性能。研究成果表明，QER+-树是一种有效的空间数据索引结构，采用这种结构，空间数据的插入，删除，特别是检索性能与R-树及R+-树相比得到很大提高。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 前言
• 1.1 空间数据库简介
• 1.2 空间索引技术的研究意义
• 1.3 空间索引技术的研究现状
• 1.4 本文的研究内容和创新之处
• 1.5 本文的组织结构
• 第二章 空间数据库索引技术
• 2.1 空间索引相关知识
• 2.1.1 空间查询分类
• 2.1.2 目标近似技术
• 2.1.3 空间查询过程
• 2.2 R 树系列空间索引技术
• 2.2.1 R-树
• +-树'>2.2.2 R⁺-树
• 2.2.3 R*-树
• 2.2.4 以上索引结构的比较
• 2.3 四叉树系列空间索引技术
• 2.3.1 点四叉树
• 2.3.2 区域四叉树
• 2.3.3 小结
• 2.4 二叉树系列空间索引技术
• 2.5 其他空间索引技术
• 2.6 总结
• +-树的设计与实现'>第三章 QER⁺-树的设计与实现
• +-树'>3.1 QER⁺-树
• +-树的提出'>3.1.1 QER⁺-树的提出
• +-树的结构'>3.1.2 QER⁺-树的结构
• +-树的构建和实现'>3.2 QER⁺-树的构建和实现
• +-树 CreateTreeQER 类的定义'>3.2.1 构建 QER⁺-树 CreateTreeQER 类的定义
• 3.2.2 类 createTreeQER 定义中的几个关键算法
• +-树的插入'>3.3 QER⁺-树的插入
• +-树的删除'>3.4 QER⁺-树的删除
• +-树的查找'>3.5 QER⁺-树的查找
• +-树结点的分裂'>3.6 QER⁺-树结点的分裂
• 3.7 小结
• 第四章 实验与性能分析
• 4.1 实验环境
• 4.1.1 开发环境
• 4.1.2 实验数据的设计
• 4.1.3 主要测试指标
• 4.2 试验结果与分析
• 4.3 小结
• 第五章 总结与下一步工作展望
• 5.1 总结
• 5.2 下一步工作展望
• 参考文献
• 致谢