一种内存数据库空间索引的设计与实现

论文摘要

由于空间数据往往是海量数据,考虑到内存价格昂贵以往要将空间数据存储在内存数据库中基本是不可能的。随着近年来计算机硬件技术的飞速发展,内存价格不断降低,其容量却不断提高,由于内存数据库在管理空间数据上巨大的实时性优势,可以预见在不久的将来,内存数据库会取代磁盘数据库成为空间数据的主要载体,故本课题的目标就是设计一种基于内存数据库使用的空间索引结构。传统的磁盘数据库的瓶颈在于磁盘I/O,故在设计时所有算法的一个重要目标是减少对磁盘访问次数,而在内存数据库中,系统对内存的读取速度问题成为了新的瓶颈。如果单纯的将传统基于磁盘数据库的索引套用到内存数据库中肯定是不合适的。针对这个问题近年来出现了缓存敏感（ Cache -Conscious）技术,最近的研究也证明通过对基于磁盘的单维索引进行缓存敏感改造完全可以应用于内存数据库且达到比传统内存数据库单维索引更好的性能。通过对现有缓存敏感技术的研究,并在对比分析了几种常见的空间索引结构后,以空间索引R树的结构为基础,提出了基于缓存敏感技术的一种新的空间索引树,叫做缓存敏感R树（CSR , Cache Sensitive -Tree）索引。为了达到缓存敏感的要求,CSR树通过几种方法对R树的节点进行压缩,具体方法有去除子节点中和父节点中重合的边界信息;对节点中最小外包矩形的坐标采用相对于父节点坐标的相对坐标表示;对坐标轴进行一定精度的量化等。最后给出了CSR树的详细数据结构与查询、插入、删除等常用的算法的伪代码,并在特定的环境和参数下对CSR树性能进行了算法测试,将结果与同等条件下的R树性能进行了比较,测试结果显示,内存数据库的环境下,CSR树在数据库最重要的性能指标查询性能上明显要优于普通的R树;在插入性能上由于消耗了必要的维护开销,故在速度上略微慢于R树;而在删除性能上缓存适配率的降低弥补了算法复杂索引器的维护所需要的开销,因此速度与R树接近,并在数据量增加时有性能提高的趋势。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题背景和意义
• 1.2 国内外研究现状
• 1.3 本文研究的内容及章节安排
• 2 空间索引与缓存敏感技术
• 2.1 空间索引现状
• 2.2 缓存敏感技术
• 2.3 本章小结
• 3 CSR 树的设计与实现
• 3.1 CSR 树的节点结构设计
• 3.2 节点内指针移除
• 3.3 压缩 R 树中 MBR 的信息
• 3.4 CSR 树的算法实现
• 3.5 本章小结
• 4 CSR 树性能分析
• 4.1 测试环境
• 4.2 参数设置
• 4.3 插入性能测试
• 4.4 查询性能测试
• 4.5 删除性能测试
• 4.6 本章小结
• 5 总结与展望
• 5.1 全文总结
• 5.2 工作展望
• 致谢
• 参考文献