![](https://csdnimg.cn/release/download_crawler_static/88360762/bg1.jpg)
R-Tree 空间索引算法的研究历程和最新进展分析
摘要:
本资源介绍了空间索引的概念、R-Tree 数据结构和 R-Tree 空间索引的算法描述,并从
R-Tree 索引技术的优缺点对 R-Tree 的改进结构——变种 R-Tree 进行了论述。最后,对
R-Tree 的最新研究进展进行了分析。
关键词:空间索引技术;R-Tree;研究历程;最新进展
当前数据搜索的一个关键问题是速度。提高速度的核心技术是空间索引。空间索引是由空间
位置到空间对象的映射关系。当前的一些大型数据库都有空间索引能力,像 Oracle,DB2。
空间索引技术并不单是为了提高显示速度,显示速度仅仅是它所要解决的一个问题。空间索
引是为空间搜索提供一种合适的数据结构,以提高搜索速度。
空间索引技术的核心是:根据搜索条件,比如一个矩形,迅速找到与该矩形相交的所有空间
对象集合。当数据量巨大,矩形框相对于全图很小时,这个集合相对于全图数据集大为缩小,
在这个缩小的集合上再处理各种复杂的搜索,效率就会大大提高。
所谓空间索引,就是指依据空间实体的位置和形状或空间实体之间的某种空间关系,按一定
顺序排列的一种数据结构,其中包含空间实体的概要信息如对象的标识、外接矩形及指向空
间实体数据的指针。简单的说,就是将空间对象按某种空间关系进行划分,以后对空间对象
的存取都基于划分块进行。
1 引言
空间索引是对存储在介质上的数据位置信息的描述,用来提高系统对数据获取的效率。空间
索引的提出是由两方面决定的:其一是由于计算机的体系结构将存贮器分为内存、外存 两
种,访问这两种存储器一次所花费的时间一般为 30~40ns,8~10ms,可以看出两者相差十
万倍以上,尽管现在有“内存数据库”的说法,但绝大多数数据是存储在外存磁盘上的,如果
对磁盘上数据的位置不加以记录和组织,每查询一个数据项就要扫描整个数据文件,这种访
问磁盘的代价就会严重影响系统的效率,因此系统的设计者必须将数据在磁盘上的位置加以
记录和组织,通过在内存中的一些计算来取代对磁盘漫无目的的访问,才能提高系统的效率,
尤其是 GIS 涉及的是各种海量的复杂数据,索引对于处理的效率是至关重要的。其二是 GIS
所表现的地理数据多维性使得传统的 B 树索引并不适用,因为 B 树所针对的字符、数字等
传统数据类型是在一个良序集之中,即都是在一个维度上,集合中任给两个元素,都可以在
这个维度上确定其关系只可能是大于、小于、等于三种,若对多个字段进行索引,必须指定
各个字段的优先级形成一个组合字段,而地理数据的多维性,在任何方向上并不存在优先级
问题,因此 B 树并不能对地理数据进行有效的索引,所以需要研究特殊的能适应多维特性
的空间索引方式。