基于4R-树双时态索引的研究与改进

论文摘要

4R-树索引是当前较为实用的双时态索引技术，它由R1、R2、R3和R4四棵相互独立的R-树构成。4R-树索引能够有效地处理时间变元Now和UC，且可在任何支持R-树的数据库管理系统上使用。4R-树索引中的R2树负责索引时间区域为线段的数据，但由于R-树本身对线段索引的缺陷，致使在R2树上查询时需要大量不必要的I/O操作，进而影响了4R-树索引的整体查询性能。所以，本文主要针对R2树查询性能较差的缺点提出了改进方案。该方案的主体思想是将R2树上中间节点中的索引项和叶子节点中的数据项所包含的最小边界矩形由原来的二维空间——有效时间维和事务时间维，提升至三维空间——有效时间起始值维、有效时间截止值维和事务时间维。这样，R2树所负责索引的双时态数据经4R数据变换消除时间变元后在该三维空间上的时间区域表现为空间点，而不再是原先二维空间上所表现的线段。改进后的R2树回避了R-树在二维空间上对线段索引的劣势，充分利用了其在三维空间上对点查询的优势。本文最后，直接利用实验对改进后4R-树索引的整体更新和查询代价进行评测。由于4R-树索引的4棵R-树之间是相互独立的，且本文只改进了R2树，所以改进后4R-树索引整体性能的变化也正反映出了改进后R2树的性能变化。实验结果表明，改进后4R-树索引虽然在更新代价上有所提高，但是却非常有效地抑制了查询代价，使得4R-树索引整体查询性能提高了许多，这同时也表明了改进后R2树的查询性能得到了提高的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 国内外研究现状
• 1.3 研究意义及热点
• 1.4 研究内容及论文结构
• 第2章 时态数据库
• 2.1 基本概念
• 2.1.1 时间模型
• 2.1.2 事件与状态
• 2.1.3 时间粒度与时间量子
• 2.1.4 有效时间与事务时间
• 2.2 时态数据库分类
• 2.2.1 快照数据库
• 2.2.2 回滚数据库
• 2.2.3 历史数据库
• 2.2.4 时态数据库
• 2.3 时态数据表示模式
• 2.3.1 Snodgrass的元组时标表示模式
• 2.3.2 Jensen的基于Backlog表示模式
• 2.3.3 Gadia的属性值时标表示模式
• 2.3.4 Ben-Zvi的元组时标表示模式
• 2.4 本章小结
• 第3章 双时态索引技术
• 3.1 R-树索弘
• 3.1.1 R-树的数据结构
• 3.1.2 R-树的特征
• 3.1.3 R-树节点分裂
• 3.1.4 R-树基本操作
• 3.1.5 R-树分析
• 3.2 2R-树索引
• 3.3 GR-树索引
• 3.4 本章小结
• 第4章 4R-树索引的研究与改进
• 4.1 4R-树索引
• 4.1.1 4R数据变换
• 4.1.2 4R查询变换
• 4.1.3 4R-树索引的实现
• 4.2 综合分析
• 4.3 R2树的改进
• 4.3.1 改进思想
• 4.3.2 三维空间的定义
• 4.3.3 改进R2树的建立
• 4.3.4 查询变换的修改
• 4.4 本章小结
• 第5章 实验结果与分析
• 5.1 实验数据的产生
• 5.2 改进前后4R-树索引比较
• 5.2.1 更新代价
• 5.2.2 查询代价
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢