第四节 可视化与空间查询
四、空间信息查询
空间信息查询是按一定的要求对地理信息系统所描述的空间实体及其空间信息进行访问，从众多的空间实体中挑选出满足用户要求的空间实体及其相应的属性。查询交互进行时，其结果能动态地通过两个视窗（图形窗和属性表格窗口）进行显示。根据信息查询的出发点不同，可分为三种不同的查询方式：基于空间关系特征的查询，基于属性特征的查询，基于空间关系和属性特征的查询。
提到空间信息查询，必然联系到空间数据模型、空间实体间的空间关系描述、空间索引。由于空间数据模型和空间关系描述已在前面的章节做了讲解，本节只对空间索引进行介绍。
1．空间索引
空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。
常见大空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、K-D-B树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。
1）格网型空间索引
格网型空间索引思路比较简单明了，容易理解和实现。其基本思想是将研究区域用横竖线条划分为大小相等和不等的网格，记录每一个网格所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在网格，然后再在该网格中快速查询所选空间实体，这样一来就大大地加快了空间索引的查询速度。
2）BSP树空间索引
BSP树是一种二叉树，它将空间逐级进行一分为二的划分（图3．12）。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。
3）KDB树空间索引
KDB树是B树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支持占据一定空间范围的空间对象，如二维空间中的线和面。该缺点可以通过空间映射或变换的方法部分地得到解决。空间映射或变换就是将Zn维空间中的区域变换到Zn维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的区域查询便转化为高维空间的点查询。但空间映射求变换方法仍然存在着缺点：高维空间的点查询要比原始空间的点查询困难的多；经过变换，原始空间中相邻的区域有可能在点空间中距离变得相当遥远，这些都将影响空间索引的性能。
4）R树和R+树
R树可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点N都对应着磁盘页H（N）和区域I（N），如果结点不是叶结点，则该结点的所有子结点的区域都在区域I（N）的范围之内，而且存储在磁盘页D（N）中；如果结点是叶结点，那么磁盘页D（N）中存储的将是区域I（N）范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。
R树中每个结点所能拥有的子结点数目是有上下限的。下限保证索引对磁盘空间的有效利用，子结点的数目小于下限的结点将被删除，该结点的子结点将被分配到其它的结点中；设立上限的原因是因为每一个结点只对应一个磁盘页，如果某个结点要求的空间大于一个磁盘页，那么该结点就要被化分为两个新的结点，原来结点的所有子结点将被分配到这两个新的结点中。
由于R树兄弟结点对应的空间区域可以重叠，因此，R树可以较容易的进行插入和删除操作；但正因为区域之间有重叠，空间索引可能要对多条路径进行搜索后才能得到最后的结果，因此，其空间搜索的效率较低。
正是这个原因促使了R+树的产生。在R+树中，兄弟结点对应的空间区域没有重叠，而没有重叠的区域划分可以使空间索引搜索的速度大大提高；但由于在插入和删除空间对象时要保证兄弟结点对应的空间区域不重叠，而使插入和删除操作的效率降低。
5）CELL树
考虑到R树和R+树在插入、删除和空间搜索效率两方面难于兼顾，CELL树应运而生。它在空间划分时不再采用矩形作为划分的基本单位，而是采用凸多边形来作为划分的基本单位，具体划分方法与BSP树有类似之处，子空间不在相互覆盖。CELL树的磁盘访问次数比R树和R+树少，由于磁盘访问次数是影响空间索引性能的关键指标，故CELL树是比较优秀的空间索引方法。