介绍

动态索引结构

介绍

空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。

空间索引的提出是由两方面决定的:其一是由于计算机的体系结构将存贮器分为内存、外存 两种，访问这两种存储器一次所花费的时间一般为30~40ns，8~10ms，可以看出两者相差十 万 倍以上，尽管现在有“内存数据库”的说法，但绝大多数数据是存储在外存磁盘上的，如果 对磁盘上数据的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访 问磁盘的代价就会严重影响系统的效率，因此系统的设计者必须将数据在磁盘上的位置加以 记录和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能提高系统的效率 ，尤其是GIS涉及的是各种海量的复杂数据，索引对于处理的效率是至关重要的。其二是GIS 所表现的地理数据多维性使得传统的B?树索引并不适用，因为B?树所针对的字符、数字等 传统数据类型是在一个良序集之中，即都是在一个维度上，集合中任给两个元素，都可以在 这个维度上确定其关系只可能是大于、小于、等于三种，若对多个字段进行索引，必须指定 各个字段的优先级形成一个组合字段，而地理数据的多维性，在任何方向上并不存在优先级 问题，因此B?树并不能对地理数据进行有效的索引，所以需要研究特殊的能适应多维特性 的空间索引方式。

动态索引结构

1984年Guttman发表了《R?树:一种空间查询的动态索引结构》，它是一种高度?平衡的树 ，由中间节点和页节点组成，实际数据对象的最小外接矩形存储在页节点中，中间节点通过 聚集其低层节点的外接矩形形成，包含所有这些外接矩形。其后，人们在此基础上针对不同 空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。