空间索引结构(遥感)

1、空间索引结构空间索引结构 空间索引技术是提高空间数据查询和各种空间索引技术是提高空间数据查询和各种空间分析效率的关键技术。空间索引可缩小空间分析效率的关键技术。空间索引可缩小空间数据的搜索范围，使访问不需要遍历整空间数据的搜索范围，使访问不需要遍历整个空间数据集。个空间数据集。索引文件中的数据称为索引数据，索引结索引文件中的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护构是索引数据的数据结构及索引创建与维护算法的总称。算法的总称。空间索引结构是按照空间数据在空间分布空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。上的特性来组织和存储索引数据的索引结构

2、。空间索引结构空间索引结构 空间索引结构应满足下列三个要求：空间索引结构应满足下列三个要求：一、存储效率高：一、存储效率高：相对于被索引的数据集而言，索引数据的数相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，访问索引数据可能成为数据量应尽量小。否则，访问索引数据可能成为数据查询与更新的效率瓶颈。据查询与更新的效率瓶颈。二、查询效率高：二、查询效率高：选择良好的索引数据结构，设计具体的基于选择良好的索引数据结构，设计具体的基于索引的空间访问方法（索引的空间访问方法（SAM Spatial Access Method），高效实现以下的查询：），高效实现以下的查询：1、点选择：从数据集中

3、找出包含给定点的所、点选择：从数据集中找出包含给定点的所有空间对象。有空间对象。2、范围查询：查询与给定对象间的距离小于、范围查询：查询与给定对象间的距离小于某个给定值的所有空间对象。某个给定值的所有空间对象。空间索引结构空间索引结构 3、区域（窗口）查询：查找含在区域内、区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象，与区域相交或部分位于区域中的所有空间对象，窗口是一个特殊的区域。窗口是一个特殊的区域。 4、K-最邻近查询：给定一个参照对象（点、最邻近查询：给定一个参照对象（点、线或区域），查询距离参照对象最近的线或区域），查询距离参照对象最近的K 1个个空间对象

4、。空间对象。 5、空间关系查询：相交、相邻、包含等拓、空间关系查询：相交、相邻、包含等拓扑关系查询，方位关系和基于距离的各种查询。扑关系查询，方位关系和基于距离的各种查询。 6、其他查询：将满足一定空间条件的两个、其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也空间对象集合进行空间连接，空间集合运算等也是一种空间访问。是一种空间访问。空间索引结构空间索引结构 三、更新效率高：三、更新效率高：数据对象的增加、修改和删除将导致索引数据数据对象的增加、修改和删除将导致索引数据更新，索引数据与被索引的数据集必须保持一致。更新，索引数据与被索引的数据集必须保持一致。索引数据的

5、更新操作包括：插入索引项、删除索引数据的更新操作包括：插入索引项、删除索引项和修改索引项（先删除再增加）。数据集经索引项和修改索引项（先删除再增加）。数据集经常变化时，需要考虑新增索引项和删除索引项时，常变化时，需要考虑新增索引项和删除索引项时，索引结构的快速更新能力。索引结构的快速更新能力。很难设计一种空间索引结构同时能提供高效的很难设计一种空间索引结构同时能提供高效的存储、高效的查询和高效的更新，实际应用中总是存储、高效的查询和高效的更新，实际应用中总是牺牲某些方面的效率来换取另外方面的效率。牺牲某些方面的效率来换取另外方面的效率。索引结构可分为静态索引和动态索引结构，还索引结构可分为静态

6、索引和动态索引结构，还分为内存索引和外存索引，外存索引需要考虑磁盘分为内存索引和外存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。页面访问的效率瓶颈问题。 空间索引技术的基本原理空间索引技术的基本原理空间索引技术的基本原理是采用基于空间空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法，把研究空间位置或基于空间对象的分割方法，把研究空间划分为若干区域，每个区域为一个索引单元，划分为若干区域，每个区域为一个索引单元，存储多个空间索引项，按照空间位置邻近的对存储多个空间索引项，按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空象其索引项的位置也应该邻近的原则来组织空间索

7、引数据。间索引数据。空间索引按照对空间的划分方式分为空间空间索引按照对空间的划分方式分为空间驱动的索引和数据驱动的索引；按照索引文件驱动的索引和数据驱动的索引；按照索引文件的数据结构又分为线性索引和非线性索引。的数据结构又分为线性索引和非线性索引。空间索引技术的基本原理空间索引技术的基本原理空间对象的几何形状错综复杂，表示几何形状的坐空间对象的几何形状错综复杂，表示几何形状的坐标序列是变长的，直接以形状数据为索引字段将导致索标序列是变长的，直接以形状数据为索引字段将导致索引项很复杂。为此，首先将空间对象的几何形状采用某引项很复杂。为此，首先将空间对象的几何形状采用某种近似的简单图形来表示，平行

8、于坐标轴且包含特定空种近似的简单图形来表示，平行于坐标轴且包含特定空间对象的最小外接矩形间对象的最小外接矩形MBB（Minimal Bounding Box）或或MBR(Minimum Bounding Rectangle) 是空间对象几是空间对象几何形状的一种近似表示。何形状的一种近似表示。以以 MBB，OID，PRT为索引项建立空间索引，可为索引项建立空间索引，可使每个空间索引项具有固定长度。其中：使每个空间索引项具有固定长度。其中：OID为对象标为对象标识，识，MBB为对象的最小外接矩形，为对象的最小外接矩形，PRT为指向几何数据为指向几何数据的指针，的指针，OID直接将直接将MBB映射

9、到存放几何形状和属性的映射到存放几何形状和属性的物理页。物理页。 空间索引技术的基本原理空间索引技术的基本原理空间索引介于空间计算算法与空间数据之间，用于过空间索引介于空间计算算法与空间数据之间，用于过滤大量与空间计算无关的数据，以提高空间操作的效率。滤大量与空间计算无关的数据，以提高空间操作的效率。 SAM只加速了索引项中只加速了索引项中MBB的查找（过滤），在此基础的查找（过滤），在此基础上还要对几何图形进行精确查找。上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成：基于空间索引的空间查询分两步完成：第一步利用空间索引结构和空间访问方法第一步利用空间索引结构和空间访问方法SA

10、M对数据对数据集进行过滤（初选），在索引表中查找满足查询条件的集进行过滤（初选），在索引表中查找满足查询条件的MBB，结果为对象的一个超集（多个，结果为对象的一个超集（多个OID）。）。第二步对初选结果进行准确查找，在超集中通过空间第二步对初选结果进行准确查找，在超集中通过空间计算算法，求取满足查询条件的精确对象。计算算法，求取满足查询条件的精确对象。 空间驱动的索引结构空间驱动的索引结构空间驱动索引结构的主要特征是采用空间驱动索引结构的主要特征是采用某种格网对某种格网对2D空间进行划分，将空间划分空间进行划分，将空间划分成小区域，每个小区域为一个成小区域，每个小区域为一个索引单元索引单元，每

11、个索引单元每个索引单元包含多个索引项，包含多个索引项，每个索引每个索引项项索引一个空间对象索引一个空间对象。索引单元按照一定的索引单元按照一定的数据结构数据结构来组织。来组织。如果组织成线性结构，则相应的空间索引如果组织成线性结构，则相应的空间索引为线性索引，如果组织成非线性结构，则为线性索引，如果组织成非线性结构，则相应的空间索引为非线性索引。相应的空间索引为非线性索引。网格索引网格索引网格索引是一种空间驱动的非线性索引结网格索引是一种空间驱动的非线性索引结构，其基本特征是用正方形或矩形格网对研究构，其基本特征是用正方形或矩形格网对研究区域的区域的2D空间进行划分，每个网格单元为一空间进行划

12、分，每个网格单元为一个索引单元，索引多个空间对象，索引单元按个索引单元，索引多个空间对象，索引单元按行列号组织成行列号组织成2D目录。目录。网格索引包括均匀网格索引和网格文件索网格索引包括均匀网格索引和网格文件索引，均匀网格适合于索引空间点对象；网格文引，均匀网格适合于索引空间点对象；网格文件是均匀网格的改进，是一种多关键字索引，件是均匀网格的改进，是一种多关键字索引，可索引点对象和对象的可索引点对象和对象的MBB，能够与，能够与B+树简树简单集成，在商用数据库单集成，在商用数据库Oracle中已实现。中已实现。 均匀网格索引均匀网格索引 一、均匀网格的特征一、均匀网格的特征 设几何对象均为点

13、对象。研究区域为一个设几何对象均为点对象。研究区域为一个Sx*Sy大小的空间，将其划分为大小的空间，将其划分为nx*ny个相同大个相同大小的网格，每个网格的边长为小的网格，每个网格的边长为Sx/nx*Sy/ny，起始，起始坐标为坐标为(Xo,Yo)。每个网格为一个索引单元，对应于磁盘上一个每个网格为一个索引单元，对应于磁盘上一个物理页，每个网格中的点存入相应的磁盘页中。物理页，每个网格中的点存入相应的磁盘页中。每个索引单元包含的索引项数量是有限制的，每个索引单元包含的索引项数量是有限制的，不能超过一个物理页的存储容量。不能超过一个物理页的存储容量。 均匀网格索引均匀网格索引图图7-3 均匀网格

14、均匀网格 如图如图7-3，索引组织成，索引组织成2D数组数组DIR1:nx,1:ny形式的目形式的目录表，每个目录项录表，每个目录项DIRi，j 对应一个索引单元。一个索引对应一个索引单元。一个索引单元包含形式为单元包含形式为OID, PageID的多个索引项，存储为一个的多个索引项，存储为一个物理页。物理页。OID为空间对象的主码，为空间对象的主码，PageID为该索引单元对为该索引单元对应的物理页标识。应的物理页标识。均匀网格索引均匀网格索引（二）基于均匀网格索引的空间访问（二）基于均匀网格索引的空间访问1、插入新点：假设新点的坐标为（、插入新点：假设新点的坐标为（x，y），计算新点），计

15、算新点所在网格（索引单元）的行列号。新点的索引目录项为所在网格（索引单元）的行列号。新点的索引目录项为DIRi，j，假设对应的磁盘页，假设对应的磁盘页DIRi，j.PageID为为(a，b)所所在的页在的页P(a，b)，将新点插入，将新点插入P(a，b)页中。页中。2、点查询：假设鼠标当前位置的坐标为、点查询：假设鼠标当前位置的坐标为 (x，y)，计算，计算鼠标位置所属索引单元的行列号鼠标位置所属索引单元的行列号i=(X-Xo)/(Sx/nx)+1和和j=(Y-Yo)/(Sy/ny) +1，读入对应的磁盘页，读入对应的磁盘页DIRi，j.PageID，扫，扫描该页中所有点对象，判断哪些点对象与

16、描该页中所有点对象，判断哪些点对象与(x，y)点重叠。点重叠。3、窗口查询：计算窗口、窗口查询：计算窗口W覆盖的网格集合覆盖的网格集合S=Ci,j，对对S中的每个读取中的每个读取DIRi，j.PageID，返回这些页中包含的，返回这些页中包含的所有点对象，即为窗口所有点对象，即为窗口W范围内包含的点对象。范围内包含的点对象。 均匀网格索引均匀网格索引格网分辨率的选择取决于被索引点对象的数量。格网分辨率的选择取决于被索引点对象的数量。假设共有假设共有N个点对象，每页存储的最大点数为个点对象，每页存储的最大点数为M，则至少需要有则至少需要有N/M个网格。如果某个网格中的点数个网格。如果某个网格中的

17、点数超过超过M，多出的点放到溢出区，溢出区与索引区域，多出的点放到溢出区，溢出区与索引区域用指针相连。用指针相连。所有的网格共用一个溢出区，溢出区可能由多所有的网格共用一个溢出区，溢出区可能由多个磁盘页连接成溢出区链。如果个磁盘页连接成溢出区链。如果o点存储在溢出区链点存储在溢出区链的第的第q页，则点查询的页，则点查询的I/O数为数为q。最坏的情况下，所。最坏的情况下，所有点都位于同一网格中，索引结构为磁盘页的线性有点都位于同一网格中，索引结构为磁盘页的线性列。点的频繁插入会导致较长的溢出链，而点删除列。点的频繁插入会导致较长的溢出链，而点删除会导致空页。对于某些具体分布，这种索引不能满会导致

18、空页。对于某些具体分布，这种索引不能满足磁盘存储的要求足磁盘存储的要求。均匀网格索引均匀网格索引如图如图7-4中例子，每个网格所存的最大点数中例子，每个网格所存的最大点数M=4，k,l,m,n,o五个点对象位于同一个网格中，对应于磁盘五个点对象位于同一个网格中，对应于磁盘页页P。将。将k,l,m,n四个点放入四个点放入P页，页，o放入溢出区，将溢放入溢出区，将溢出区与出区与P页相连。页相连。图图7-4 均匀网格中的溢出页均匀网格中的溢出页 网格文件索引网格文件索引二、点对象的格网文件二、点对象的格网文件格网文件与均匀格网的相同之处是采用平行于坐标轴的格网格网文件与均匀格网的相同之处是采用平行于

19、坐标轴的格网对空间进行完全划分，每个网格单元为一个索引单元，索引单元对空间进行完全划分，每个网格单元为一个索引单元，索引单元组织成组织成2D目录形式。与均匀格网不同的是，每次发生溢出时，动目录形式。与均匀格网不同的是，每次发生溢出时，动态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单元中点对象的分布情况来选择进行纵向还是横向划分；网格文件元中点对象的分布情况来选择进行纵向还是横向划分；网格文件中的网格单元为大小不相同的矩形单元，多个网格单元可对应同中的网格单元为大小不相同的矩形单元，多个网格单元可对应同一个磁盘页。一个磁盘页。 （

20、一）格网文件的数据结构（一）格网文件的数据结构 格网文件由三种数据结构来实现，索引目录格网文件由三种数据结构来实现，索引目录DIR是一种与均是一种与均匀网格中的索引目录类似的匀网格中的索引目录类似的2D数组，差别是两个相邻单元可共享数组，差别是两个相邻单元可共享同一磁盘页；同一磁盘页；Sx,Sy是两个线性数组，表示沿两坐标轴的划分。是两个线性数组，表示沿两坐标轴的划分。图图7-5中的例子描述了这种结构，假设网格的最大容量中的例子描述了这种结构，假设网格的最大容量M=4。 网格文件索引网格文件索引图7-5均匀网格文件的插入 网格文件索引网格文件索引网格文件索引网格文件索引网格文件索引网格文件索引

21、三、格网文件索引三、格网文件索引MBB用网格文件对用网格文件对MBB进行索引，最简单的情况是每个覆盖进行索引，最简单的情况是每个覆盖MBB的的网格单元都保存该网格单元都保存该MBB的索引项。的索引项。MBB与网格单元的关系有三种：与网格单元的关系有三种：MBB包含网格单元、网格单元与包含网格单元、网格单元与MBB相交、网格单元包含相交、网格单元包含MBB。前两。前两种情况，每个网格单元都建立种情况，每个网格单元都建立MBB的索引项，一个的索引项，一个MBB有多项索引。有多项索引。例子：有例子：有15个个MBB，每页的最大容量为，每页的最大容量为4。图。图7-6为用均匀网格建为用均匀网格建立的索

22、引：立的索引： 图图7-6 基于基于MBB的均匀网格索引的均匀网格索引 网格文件索引网格文件索引图图7-7为用网格文件建立的索引：为用网格文件建立的索引： 图图7-7 基于网格文件的基于网格文件的MBB索引索引 网格文件索引网格文件索引（一）索引项插入（一）索引项插入1、插入对象、插入对象14如图如图7-8，将对象，将对象14插入图插入图7-7中的索引单元中的索引单元DIR1，3时，时，DIR1，3中的索中的索引项超过引项超过4项，对应的磁盘页项，对应的磁盘页p5也溢出。在也溢出。在X3处对处对DIR1，3进行水平分裂，将进行水平分裂，将X3存入存入Sx中，现有中，现有3*（2+1）= 9 个

23、目录项。目录单元个目录项。目录单元DIR1，1和和DIR2，1 同指同指向向p1页，页，DIR1，2和和DIR2，2同指向同指向p3页。原来页。原来p5页中的对象由于对象页中的对象由于对象14的插的插入，分裂成了入，分裂成了p5和和p6两页，两页，DIR1，3指向指向p5，DIR2，3指向指向p6。对象。对象5有两个有两个索引项分别存储在索引项分别存储在p5和和p6两页中，对象两页中，对象6 有四个索引项分别存储在有四个索引项分别存储在p5、p6和和p3中。中。 图图7-8 对象对象14的插入的插入 网格文件索引网格文件索引2、插入对象、插入对象15图图7-9为目录不分裂而磁盘页溢出的情况。为

24、目录不分裂而磁盘页溢出的情况。插入前插入前DIR3，2和和DIR3，3同指向同指向p4，将对象，将对象15分别插入分别插入DIR3，2和和DIR3，3中。插入后中。插入后DIR3，2和和DIR3，3中的索引中的索引项均不超过项均不超过4个，目录不用分裂，但磁盘页个，目录不用分裂，但磁盘页p4溢出。创建新页溢出。创建新页p7，DIR3，2 指向指向p4，DIR3，3 指向指向p7。 图图7-9 对象对象15的插入的插入 网格文件索引网格文件索引（二）点查询算法（二）点查询算法 1、工作过程、工作过程 第一步：给定点坐标第一步：给定点坐标P(xp，yp)，沿，沿X，Y两个两个方向在方向在Sx和和S

25、y中查找中查找P(xp，yp)位置，得到含有位置，得到含有P的网格单元。的网格单元。第二步：进行一次磁盘操作将这个索引单元对第二步：进行一次磁盘操作将这个索引单元对应的磁盘页调入内存，读取该页所存对象的应的磁盘页调入内存，读取该页所存对象的(MBB，OID)，构成集合，构成集合E。对。对E中的每个对象中的每个对象e，测试，测试e.mbb是否含有点是否含有点P。第三步：对于包含点第三步：对于包含点P的的e.mbb，通过，通过e.oid获取获取其几何边界数据，精确测试其几何边界数据，精确测试P是否位于是否位于e.oid的几何的几何边界之内。边界之内。 网格文件索引网格文件索引2、例子：图、例子：图7-10为一个格网文件点查询的例子。点为一个格网文件点查询的例子。点P位于位于DIR3，2范围之