近年来，空间数据库索引的研究引起了人们越来越多的兴趣和关注，其中1984年Guttman提出的R-树是目前最流行的动态空间索引结构，广泛应用于原型研究和商用空间数据库系统。 R-树是一种层次数据结构，是B-树在k维空间上的自然扩展。近年来，许多学者致力于R-树的研究，在R-树的基础上衍生出了许多变种，比较典型的有R+树，压缩R-树等。基于R-树索引结构需要解决的主要问题仍然是减少区域的重叠，提高搜索效率。从而确立本论文的研究内容： 本文首先从空间数据特征和空间检索出发，系统地总结常用的空间索引技术，如KDB-树、R-树及其变种等。重点介绍R-树的定义、查找、插入及删除算法。 通过对基于四叉树的空间索引技术的研究，深入分析基于四叉树和R-树的空间索引结构-QR-树，与R-树相比，QR-树以略大（有时甚至略小）的空间开销代价换取更高的性能，且索引目标数越多，QR-树的整体性能越好。 然后一般空间聚类的定义出发，将k-均值聚类算法引入R-树的生成算法中，提出一种R-树结点分配的新算法。该算法定义了空间实体间距离的计算方法，与原始算法相比，产生的交叠会更小，从而有效的控制多路查询的几率，较明显的提高了空间查询的效率。 最后针对空间数据的特点和R-树的性能对传统的k-均值聚类算法进行改进和扩充，提出R-树生成的新算法，该算法对均匀分布和非均匀分布的空间对象都能给出很好的R-树生成。提出QROO-树，此结构针对现有的四叉树和R-树的空间索引结构中存在的问题，采用面向对象的分割技术对数据空间进行分割而建立的一种索引结构。在QROO-树的生成算法中考虑了中间节点问交叠的极小化问题，使生成的QROO-树中同层中间节点间的交叠尽可能小，从而加快查询的速度。