空间索引结构(遥感)新编.ppt

空间索引结构空间索引技术是提高空间数据查询和各种空间分析效率的关键技术。空间索引可缩小空间数据的搜索范围,使访问不需要遍历整个空间数据集。索引文件中的数据称为索引数据,索引结构是索引数据的数据结构及索引创建与维护算法的总称。空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。空间索引结构空间索引结构应满足下列三个要求: 一、存储效率高: 相对于被索引的数据集而言,索引数据的数据量应尽量小。否则,访问索引数据可能成为数据查询与更新的效率瓶颈。二、查询效率高: 选择良好的索引数据结构,设计具体的基于索引的空间访问方法( SAM Spatial Access Method ),高效实现以下的查询: 1、点选择:从数据集中找出包含给定点的所有空间对象。 2、范围查询:查询与给定对象间的距离小于某个给定值的所有空间对象。空间索引结构 3、区域(窗口)查询:查找含在区域内、与区域相交或部分位于区域中的所有空间对象, 窗口是一个特殊的区域。 4、 K- 最邻近查询:给定一个参照对象(点、线或区域),查询距离参照对象最近的 K ? 1个空间对象。 5、空间关系查询:相交、相邻、包含等拓扑关系查询,方位关系和基于距离的各种查询。 6、其他查询:将满足一定空间条件的两个空间对象集合进行空间连接,空间集合运算等也是一种空间访问。空间索引结构三、更新效率高: 数据对象的增加、修改和删除将导致索引数据更新,索引数据与被索引的数据集必须保持一致。索引数据的更新操作包括:插入索引项、删除索引项和修改索引项(先删除再增加)。数据集经常变化时,需要考虑新增索引项和删除索引项时, 索引结构的快速更新能力。很难设计一种空间索引结构同时能提供高效的存储、高效的查询和高效的更新,实际应用中总是牺牲某些方面的效率来换取另外方面的效率。索引结构可分为静态索引和动态索引结构,还分为内存索引和外存索引,外存索引需要考虑磁盘页面访问的效率瓶颈问题。空间索引技术的基本原理空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法,把研究空间划分为若干区域,每个区域为一个索引单元, 存储多个空间索引项,按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空间索引数据。空间索引按照对空间的划分方式分为空间驱动的索引和数据驱动的索引;按照索引文件的数据结构又分为线性索引和非线性索引。空间索引技术的基本原理空间对象的几何形状错综复杂,表示几何形状的坐标序列是变长的,直接以形状数据为索引字段将导致索引项很复杂。为此,首先将空间对象的几何形状采用某种近似的简单图形来表示,平行于坐标轴且包含特定空间对象的最小外接矩形 MBB ( Minimal Bounding Box ) 或 MBR(Minimum Bounding Rectangle) 是空间对象几何形状的一种近似表示。以[MBB , OID , PRT] 为索引项建立空间索引,可使每个空间索引项具有固定长度。其中: OID 为对象标识, MBB 为对象的最小外接矩形, PRT 为指向几何数据的指针, OID 直接将 MBB 映射到存放几何形状和属性的物理页。空间索引技术的基本原理空间索引介于空间计算算法与空间数据之间,用于过滤大量与空间计算无关的数据,以提高空间操作的效率。 SAM 只加速了索引项中 MBB 的查找(过滤),在此基础上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成: 第一步利用空间索引结构和空间访问方法 SAM 对数据集进行过滤(初选),在索引表中查找满足查询条件的 MBB ,结果为对象的一个超集(多个 OID )。第二步对初选结果进行准确查找,在超集中通过空间计算算法,求取满足查询条件的精确对象。空间驱动的索引结构空间驱动索引结构的主要特征是采用某种格网对 2D 空间进行划分,将空间划分成小区域,每个小区域为一个索引单元,每个索引单元包含多个索引项, 每个索引项索引一个空间对象。索引单元按照一定的数据结构来组织。如果组织成线性结构,则相应的空间索引为线性索引,如果组织成非线性结构,则相应的空间索引为非线性索引。网格索引网格索引是一种空间驱动的非线性索引结构,其基本特征是用正方形或矩形格网对研究区域的 2D 空间进行划分,每个网格单元为一个索引单元,索引多个空间对象,索引单元按行列号组织成 2D 目录。网格索引包括??网格索引和网格文件索引,??网格?合于索引空间点对象;网格文件是??网格的改进,是一种多关键字索引, 可索引点对象和对象的 MBB ,能?与 B+ ?简单集成,在?用数据? Oracle 中?实现。均匀网格索引一、??网格的特征设几何对象?为点对象。研究区域为一个[ Sx * Sy ]大小的空间,将其划分为 nx * ny 个相同大小的网格,每个网格