基于B+树的移动对象索引研究

论文摘要

随着移动通信和电子技术的发展,移动对象管理变得越来越重要,已经成为了近年来研究领域中的热点问题,具有重要的理论和现实意义。移动对象的特点是位置持续变化,索引中的索引结构不断变化,所以移动对象索引不仅要支持频繁的查询,更重要的是要支持频繁的更新。时空数据库有其独特的查询,如何使索引结构适用于各种不同的查询也是移动对象索引设计应该考虑的问题。本文对移动对象索引方面的相关工作进行了归纳总结,介绍了几种具有代表性的索引结构。详细介绍了两种基于B+树的移动对象索引（BX树和ST2B树）,二者都是基于时间片分割和网格分割的,其中BX树基于均匀网格,ST2B树将空间分割成几块区域,对每个不同的区域使用不同的网格。但这两种索引结构都存在着一些不足,针对现有移动对象索引结构具有的问题,本文提出了基于层网格的移动对象B+树索引。实际应用中,空间的移动对象往往分布很不均衡,而基于二层网格的移动对象B+树索引对移动对象的分布具有很好的适应性。基于二层网格的移动对象B+树索引（简称DGB树）,是先用均匀网格将整个空间分割成大小相等的单元格,称为第一层单元格,然后根据第一层单元格中移动对象的数量,用第二层网格将第一层单元格进行二次分割。论文同时对每一层网格的粒度选择进行了研究。索引结构需要不断变化以适应移动对象分布的变化,这也使索引维持的代价较大,为了减少这种代价,本文提出了懒惰更新的策略。实验结果显示,DGB树对移动对象的不均匀分布有很好的适应性,同时又有较高的查询效率。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 研究内容
• 1.3 本文主要工作及结构
• 第二章 移动对象索引相关工作
• 2.1 移动对象特点
• 2.2 移动对象索引分类
• 2.3 移动查询分类
• 2.4 空间索引方法
• 2.4.1 R树
• 2.4.2 四叉树
• 2.4.3 网格文件
• 2.5 相关索引结构
• x树'>2.5.1 B^x树
• 2B树'>2.5.2 ST²B树
• +树索引'>第三章 基于二层网格的B⁺树索引
• 3.1 索引结构
• 3.2 二层网格法的适应性
• 3.2.1 适应性分析
• 3.2.2 自适应框架
• 3.3 基本查询算法
• 3.3.1 Range查询
• 3.3.2 kNN查询
• 3.4 网格参数的选择
• 3.4.1 移动对象均匀分布
• 3.4.2 移动对象非均匀分布
• 第四章 实验
• 4.1 实验设置
• 4.2 基础网格参数的效果
• 4.3 DGB树的适应性
• 4.3.1 对对象分布的适应
• 4.3.2 对移动对象数量的适应性
• 4.4 RANGE查询
• 第五章 总结与展望
• 第六章 参考文献
• 致谢