基于改进四叉树空间索引的优化研究与应用

摘要

本文围绕四叉树空间索引技术的优化展开，介绍了空间索引技术的基础理论知识和目前的主要实现方法，重点讨论了四叉树空间索引的结构和算法。针对四叉树空间索引面对海量空间数据I/O开销过大的主要缺点提出了自己的优化算法。
　　 本文利用Hilbert曲线的特征并且结合四叉树空间索引技术的特点，通过四叉树结点的对调和反转使得中序遍历优化后的四叉树的结点顺序完全符合Hilbert曲线的特征，而且在这样一种结构的四叉索引树上进行空间查询得到的查询结果顺序也符合Hilbert曲线的特征，可以看作是完整Hilbert曲线序列的顺序截取段。最后按照符合Hilbert曲线特征的顺序重新组织空间数据的存储格式。这样的数据存储格式和索引结构的结合可以很好的减少四叉树空间索引的I/O次数从而优化系统的查询性能。
　　 本文在第五章设计了一个以SHAPE文件为基础的实验程序，实现了基于本文提出的优化算法的四叉树空间索引，同时以GIS中开窗选择查询为例进行的大量的实验，得出了不同数据量情况下的各种查询时间。实验数据表明经过优化后的四叉树索引结构在查询海量空间数据时性能有很大的提高，从而论证了基于四叉树空间索引的优化方案的可行性。最后，对所做的工作和取得的成果进行了总结，并对本文提出的优化算法的未来发展方向做出了设想。