摘要: 空间索引机制¶ 索引概念¶ 栅矢一体化空间数据结构一个重要的研究领域是如何建立有效的空间索引结构。目前对线要素索引结构研究较多，主要有PMR四叉树、带树和桶方法等，而面要素的索引结构主要有四叉树和R树等。这些结构各有自己的应用领域和相对优势，同时也都存在...
空间索引机制¶
索引概念¶
栅矢一体化空间数据结构一个重要的研究领域是如何建立有效的空间索引结构。目前对线要素索引结构研究较多，主要有PMR四叉树、带树和桶方法等，而面要素的索引结构主要有四叉树和R树等。这些结构各有自己的应用领域和相对优势，同时也都存在着不足。
空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。常见大空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、K-D-B树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。
索引类型¶
格网型空间索引¶
格网型空间索引思路比较简单了，容易理解和实现。其基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。
BSP树空间索引¶
BSP树是一种二叉树，它将空间逐级进行一分为二的划分（图7-19）。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。
BSP树¶
KDB树空间索引¶
KDB树是B树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间映射或变换的方法部分地得到解决。空间映射或变换就是将2n维空间中的区域变换到2n维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的区域查询便转化为高维空间的点查询。但空间映射或变换方法仍然存在着缺点：高维空间的点查询要比原始空间的点查询困难得多；经过变换，原始空间中相邻的区域有可能在点空间中距离变得相当遥远，这些都将影响空间索引的性能。
R树和R+树¶
R树根据地物的最小外包矩形建立（图7-20），可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点N都对应着磁盘页D（N）和区域I（N），如果结点不是叶结点，则该结点的所有子结点的区域都在区域I（N）的范围之内，而且存储在磁盘页D（N）中；如果结点是叶结点，那么磁盘页D（N）中存储的将是区域I（N）范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。
R树中每个结点所能拥有的子结点数目是有上下限的。下限保证索引对磁盘空间的有效利用，子结点的数目小于下限的结点将被删除，该结点的子结点将被分配到其它的结点中；设立上限的原因是因为每一个结点只对应一个磁盘页，如果某个结点要求的空间大于一个磁盘页，那么该结点就要被划分为两个新的结点，原来结点的所有子结点将被分配到这两个新的结点中。
由于R树兄弟结点对应的空间区域可以重叠，因此，R树可以较容易地进行插入和删除操作；但正因为区域之间有重叠，空间索引可能要对多条路径进行搜索后才能得到最后的结果，因此，其空间搜索的效率较低。正是这个原因促使了R+树（图7-21）的产生。在R+树中，兄弟结点对应的空间区域没有重叠，而没有重叠的区域划分可以使空间索引搜索的速度大大提高；但由于在插入和删除空间对象时要保证兄弟结点对应的空间区域不重叠，而使插入和删除操作的效率降低。
R树¶
R+树¶
