6.5. 空间索引¶

在GIS系统中，常常需要根据空间位置进行查询，例如，“找出通过某个区域的所有公路”，“检索在某个区域内的所有湖泊”等等。为了处理这类空间查询，数据库需要检查每一个可能满足条件的空间要素的记录，看它是否与查询区域相交或是在查询区域内，这种空间相交运算需要先读出空间要素几何形状的边界坐标，然后再与空间区域进行空间关系运算。由于传统数据库的这种穷尽式搜索方法花费的磁盘访问时间和空间运算时间都很长，往往达到令人无法忍受的程度。

传统的关系数据库为了提高检索效率，一般都建立一系列的索引机制，如B+树。但是这些都是一维索引，无法处理空间数据库中的二维和多维的空间数据。所以必须为空间数据库另外建立专门的索引机制――空间索引。

空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。这里，外包络矩形是指空间要素的封装边界，它是每一种空间索引必不可少的要素。

空间索引的目的是为了在GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。空间索引的技术和方法是GIS关键技术之一，是快速、高效的查询、检索和显示地理空间数据的重要指标，它的优劣直接影响空间数据库和GIS系统的整体性能。

6.5.1. 矩形范围索引¶

1.索引原理

矩形范围索引是一种高效、实用的空间索引方法。其基本原理就是对空间要素的外包络矩形进行索引。在进行空间范围查询时，分为两级过滤（筛选）。初次过滤根据空间要素外包络矩形来过滤掉大部分不在查询范围的空间要素，因为空间要素外包络矩形已被索引，所以初次过滤过程比较快，花费的代价比较小。第二级过滤则用查询空间范围直接和初次过滤结果集中空间要素的二进制边界坐标比较，从而得到查询的准确结果。

对外包络矩形进行索引的方法有多种，其中在SDE中最简单、直接的一种就是利用关系数据库的索引方法来索引外包络矩形。建立矩形范围索引SQL模型如下（假设空间要素的外包络矩形坐标用XMIN，YMIN，XMAX，YMAX表示）：

CREATE INDEX idx_rect ON owner.GeoObjTbl (XMIN， XMAX， YMIN，YMAX);

（1）假设给定查询范围为矩形，坐标为gxmin， gymin， gxmax， gymax，查询矩形范围相交的空间要素（包括矩形范围内的空间要素和交到了矩形范围边界的空间要素）

利用矩形范围索引初次过滤的SQL模型如下：

SELECT id0 from owner.GeoObjTbl WHERE ((gxmin< = XMAX AND gxmin > =

XMIN) OR (gxmax< = XMAX AND gxmax> = XMIN)) AND ((gymin<=YMAX AND

gymin>=YMIN) OR (gymax< =YMAX AND gymax>=YMIN))

（2）假设给定查询范围为矩形，坐标为gxmin， gymin， gxmax， gymax，查询仅在矩形范围内的空间要素（不包括交到了矩形范围边界的空间要素）

利用矩形范围索引初次过滤的SQL模型如下：

SELECT id0 from owner.GeoObjTbl WHERE (gxmin<XMAX AND gxmin >XMIN) AND (gxmax<XMAX AND gxmax>XMIN) AND (gymin<YMAX AND gymin>YMIN) AND (gymax<=YMAX AND gymax>=YMIN)

2.索引维护及适应性

矩形范围索引由关系数据库直接维护，用SQL语句模型可以直接创建和删除，在添加、更新和删除空间要素时，不需要SDE来维护索引的变化。所以该索引具有很好的适应性，无需预知整个空间要素的空间范围，就能很容易建立空间索引；由大量实验结果表明，该索引在空间要素的个数在30万以下时，具有很高的效率，矩形范围查询初次过滤的响应时间均在1秒之内。但是空间要素的个数超过30万，索引的效率将随着空间要素的增长而下降，由试验数据表明，空间要素个数在200万左右时，利用该索引查询进行初次过滤，响应时间在5~18秒之间。所以该类型索引在中小型数据量的GIS系统中使用，具有较好的实用价值。

6.5.2. 单元格网索引¶

单元网格索引思路比较简单。基本思想是将研究区域用横竖划分为大小相等或不等的网格，记录每一个网格所包含的空间要素。当用户进行空间查询时，首先计算出查询空间要素所在的网格，然后通过该网格快速定位到所选择的空间要素。

1.传统单元网格索引编码

在建立地图数据库时需要用一个平行于坐标轴的正方形数学网格覆盖在整个数据库数值空间上，将后者离散化为密集栅格的集合，以建立制图物体之间的空间位置关系。通常是把整个数据库数值空间划分成32×32（或64×64）的正方形网格，建立另一个倒排文件——栅格索引。每一个网格在栅格索引中有一个索引条目(记录)，在这个记录中登记所有位于或穿过该网格的物体的关键字，可用变长指针法或位图法实现。在图6-15中有三个制图物体：一条河流、一个湖泊和一条省界，它们的关键字分别为5，11和23。河流穿过的栅格为2，34，35，67，68；湖泊覆盖的栅格为68，69，100，101；省界所通过的栅格为5，37，36，35，67，99，98，97。这种物体与栅格的关系可用位图法来表示。由图6-17看出，一个栅格中包含的物体个数就是该栅格在栅格索引的对应记录中存贮的比特“1”的个数。这是定位(开窗)检索的基本工具。此外，物体与栅格的关系亦可用变长指针法表示，如图6-16。

图 6-15 数据库数值空间的栅格网图6-16 变长指针法

图6-17 栅格索引

利用传统单元网格索引查询的SQL模型如下： (GCODE为网格编码列名称)SELECT id0 from owner.GeoObjTbl WHERE GCODE IN (…) 由于传统型单元网格编码方式过于简单，使得编码值在空间上不能保持连续性，即空间上相邻的网格编码不连续，所以在使用SQL模型进行查询时，只能使用IN语法。这样，如果查询涉及的网格编码太多，则容易超出SQL模型的长度。

2.改进型单元网格索引编码

改进型单元网格索引将传统型编码由1维升至2维，变成X和Y方向上的编码；将空间要素的标识、空间要素所在的网格的X和Y方向上的编码、以及空间要素的外包络矩形作为一条数据库记录存储。如果一个空间要素跨越多个网格，则同样存储多条记录。如图6-18所示，[X1，Y1]，[X2，Y2]是5的外包络矩形；[X3，Y3]，[X4，Y4]是11的外包络矩形；[X5，Y5]，[X6，Y6]是23的外包络矩形。

改进型单元网格索引的编码方式就很好的保持了网格在空间上相邻则编码值也相邻的特性，这样在构造查询的SQL模型时，就可以使用连续表示方式。而且该索引存储了空间要素的外包络矩形，可以为查询过滤非查询范围的要素提供进一步依据。

假设给定查询范围为矩形，坐标为gxmin， gymin， gxmax， gymax，其网格编码范围为：X方向(gcodexmin—gcodexmax)，Y方向（gcodeymin－gcodeymax），gcodex和gcodey分别是网格编码列名称。查询矩形范围相交的空间要素（包括矩形范围内的空间要素和交到了矩形范围边界的空间要素）

图6-18 改进型单元网格编码示意图

利用单元网格索引过滤的SQL模型如下：

SELECT id0 from owner.GeoObjTbl WHERE （gcodex>= gcodexmin AND gcodex<=gcodexmax AND gcodey>= gcodeymin AND gcodey<=gcodeymax）AND (((gxmin<=XMAX AND gxmin >=XMIN) OR (gxmax<=XMAX AND gxmax>= XMIN)) AND ((gymin<=YMAX AND gymin> =YMIN) OR (gymax<= YMAX AND gymax>=YMIN)))

索引工作机制如下：

SDE在执行该空间查询时，从客户端接收查询多边形的外包络矩形以及查询多边形外包络矩形所跨的网格单元，这些信息通过SQL模型的WHERE子句传递给DBMS。

第一步，DBMS从SDE接收SQL语句（该语句包括网格单元和外包络矩形的坐标）。WHERE子句定义了在空间索引中需要选择的网格单元。一旦在空间索引表中确定了网格单元，外包络矩形的搜索就从所选择的网格边界开始；

第二步，利用查询多边形的外包络矩形和空间索引表中的空间要素的外包络矩形，DBMS可减少最初的选择集。DBMS比较查询多边形的外包络矩形和空间要素的外包络矩形是否有重叠，如果有，则该空间要素被选择来做下一步的空间要素边界比较，形成一个最初选择集；

第三步，在SDE中，用查询多边形的外包络矩形与最初选择集中的空间要素的边界坐标进行比较，如果查询多边形的外包络矩形与第二步选择集中的空间要素边界不重叠，该空间要素就从最初选择集中过滤掉，结果形成中间选择集；

第四步，将查询多边形的边界坐标和中间选择集的空间实体边界坐标进行比较，一旦有重叠发生，比较的结果记录就形成最终结果集。该步比较过程是一个二进制比较过程，将花费较多的时间和空间。（如果查询多边形为矩形，则该步操作可省略，中间选择集直接升级为最终结果集）。

第一步和第二步是用来减少由SDE执行的空间要素边界比较的次数，减少返回的数据记录有助于减少空间要素比较的数量，因而可以缩短空间查询的时间。

3.网格单元大小因素

单元网格索引是一种多对多的关系，即一个网格单元可以包含多个空间要素，且一个空间要素可以跨越多个网格单元。在这种多对多的关系下，网格的大小是影响索引效率的最主要因素。

与空间要素的外包络矩形大小相比，网格单元很大时，将导致每个网格单元内包含有很多空间要素。第一阶段选择的网格虽少，但导致第二阶段将不得不处理大量网格内的空间要素的边界比较，潜在地增加了查询的时间。

如果网格单元太小，小于空间要素外包络矩形的平均大小，将会导致空间索引表产生大量的网格单元，并且很多网格单元都索引出相同的空间要素。当大量的空间要素外包络矩形被网格单元切割时，空间索引表变大，因而查询网格单元时间增长。

网格单元的大小不是一个确定性的问题，需要多次尝试和努力才会得到好的结果。有一些确定网格初始值的原则，用它们可以进一步确定最佳网格大小，可在任何时候重新计算网格的大小，使DBMS重建空间索引表。如果空间要素外包络矩形的大小变化比较大，可以选择多种网格大小，但在空间索引搜索的过程中DBMS必须搜索所有网格单元级，这将消耗大量时间。

最佳网格的大小可能受图层平均查询的影响，如果用户经常对图层执行相同的查询，经验数据表明，网格的大小为查寻空间范围的1.5倍时，效率较高。

经验数据表明，网格单元的大小取空间要素外包络矩形平均大小的3倍时，可极大的减少每个网格单元包含多个空间要素外包络矩形的可能性，获得较好的查询效率。

4.索引维护和适应性

单元网格索引由于网格编码与区域相关，所以需要预测整个空间要素所在空间范围，然后根据此范围建立空间索引，一旦空间要素需要超出此范围，则需重新建立索引。在整个空间范围确定的情况下，索引的维护工作比较容易。

添加空间要素时，按规则计算出该空间要素的网格编码，添加到索引表中；更新空间要素时，删除该空间要素的索引记录，重新计算网格编码，添加到索引表中；删除空间要素时，直接删除该空间要素的索引记录即可。

单元网格空间索引的效率在网格单元大小适中的时候非常高。由试验数据表明，空间要素个数在200万左右时，如果网格单元大小划分合理的话，利用该索引查询进行过滤，响应时间最短可在2秒之内。所以该类型索引适用于大型数据量的，空间范围确定的GIS应用。

6.5.3. R-树索引¶

R树最早是由A.Guttman在1984年提出的，随后又有了许多变型，构成了由R树，R＋树，Hibert R树，SR树等组成的R系列树空间索引。R系列树都是平衡树的结构，非常像B树，也具有B树的一些性质。下面以Guttman的 R树为例介绍一下R树的结构。

1.R树的结构

R树的每个结点不存放空间要素的值。叶结点中存储该结点对应的空间要素的外包络矩形和空间要素标识，这个外包络矩形是个广义上的概念，二维上是矩形，三维空间上就是长方体，以此类推到高维空间。非叶结点（叶结点的父亲、祖先结点）存放其子女结点集合的整体外包络矩形和指向其子女结点的指针。注意，空间要素相关的信息只存在叶结点上。

图6-19是二维空间中一个R树示意图，图中的例子表示了三组多边形（矩形，用实线画出）及对应于这三组多边形的R树中结点的外包络矩形（用虚线画出），R树本身画在右边。

2.索引维护（R树的插入，删除操作）

R树的插入与许多其他树的操作一样，可以归纳为一个递归过程。首先从根结点出发，按照一定的标准，选择其中一个孩子插入新的空间要素，然后再从以孩子为根的子树的根结点出发重复进行上面操作，直到叶子结点。设 M和 m( m≤ M)为 R树结点中单元个数的上限和下限，当新的空间要素的插入使叶子结点中的单元个数超过M时，需要进行结点的分裂操作。分裂操作是将溢出的结点按照一定的规则分为若干部分。在其父结点删除原来对应的单元，并加入由分裂产生的相应的单元。如果这样引起父结点的溢出，则继续对父结点进行分裂操作。分裂操作也是一个递归过程，它保证了空间要素插入后R树仍能保持平衡。

图6-19 R树结构示意图

从R树中删除一个空间要素与插入类似，首先从R树中查找到记录该空间要素所在的叶子结点，这就是R树的查找。从根结点开始，依次检索包含空间要素的单元所对应孩子结点为根结点的子树。查询方式利用了R树的结构特征，减少了检索的范围，提高了检索的效率。查找到该空间要素所在的叶子结点后，删除其对应的单元。如果删除后该叶子结点单元个数少于m，需要进行R树的压缩操作，将单元数过少的结点删除。如果父结点因此单元数也少于m，则继续对父结点重复进行该操作。最后将因进行结点调整而被删除的空间要素重新插入到R树中。这就是R树的压缩操作，它使得R树的每个结点单元数不低于m这个下限，从而保证了R树结点的平衡和利用率。

3.索引分析

从R树的结构可以看出，让空间上靠近的空间要素拥有尽可能近的共同祖先，能提高R树的查询效率。在构造R树的时候，尽可能让空间要素的空间位置的远近体现在其最近的共同祖先的远近上，形象的说就是让聚集在一起的空间要素尽可能早的组合在一起。插入中选择子树的标准，分裂操作、插入操作中选择子树的标准，分裂操作中的分裂算法，都是为了体现这一目标。但是用什么样的规则来衡量空间要素的聚集，是一个非常复杂的问题。由于衡量的方法不一样，由此产生了众多的R树的变型。

Guttman使用面积这个指标来衡量空间上的聚集。在插入操作时，选择插入空间要素后外包络矩形面积增长最小的结点为根结点的子树。而在分裂溢出结点时，选择各种分裂组合中各部分外包络矩形面积之和最小的结合方式。而R+树^[54]在插入操作时则将叶子结点和非叶子结点分开考虑，采用不同的标准。并提出同时考虑外包络矩形的周长和其相互重叠的面积来衡量空间上的聚集。在分裂溢出结点时提出了更为复杂的算法。而Hilbert R树则利用分形中的一种空间填充曲线－Hilbert曲线，将多维空间的空间要素映射到一维空间，利用该变换保持空间聚集的特性来解决这个问题。

让R树的结构尽可能的合理是一个非常复杂的问题。上面众多的方法都不能很完善的衡量空间的聚集，他们都只能做到局部的优化，无法保证由此形成的R树的整体结构最优。空间要素插入顺序的不同会形成不同结构的R树，所以随着空间要素的频繁插入和删除，会将R树的查询效率带向不可预知的方向。

但R树空间索引具有其他索引方法无法比拟的优势：

它按数据来组织索引结构。这使其具有很强的灵活性和可调节性。无需预知整个空间要素所在空间范围，就能建立空间索引；

由于具有与B树相似的结构和特性，使其能很好地与传统的关系型数据库相融合，更好的支持数据库的事务、回滚和并发等功能。这是许多国外空间数据库选择R树作为空间索引的一个主要原因。

6.5.4. 四叉树编码索引¶

四叉树空间索引的基本原理是将已知的空间范围划成四个相等的子空间，将每个或其中几个子空间继续按照一分为四的原则划分下去，这样就形成了一个基于四叉树的空间划分。四叉树索引有满四叉树索引和一般四叉树索引。以下的两个四叉树索引均为满四叉树索引。

1.基于固定网格划分的四叉树索引

（1）索引原理

在基于固定网格空间划分的四叉树空间索引机制中，二维空间范围被划分为一系列大小相等的棋盘状矩形，即将地理空间的长和宽在X和Y方向上进行2^N等分，形成2^N×2^N的网格，并以此建立N级四叉树。其中，树的非叶结点（即内部结点）数的计算公式为：MAX_NONLEAFNODE_NUM= ；叶结点（即外部结点）数的计算公式为：MAX_LEAFNODE_NUM= 2^N×2^N=4^N。若非叶结点从四叉树的根结点开始编号，从0到MAX_NONLEAFNODE_NUM-1，叶子结点则从MAX_NONLEAFNODE_NUM开始编号，直到MAX_ NONLEAFNODE_NUM+MAX_LEAFNODE_NUM-1。如图6-20所示为二维空间的二级划分（即N＝2）及其四叉树结构。根据计算公式，N=2时，非叶结点数为5，编码从0到4，叶结点数是16，编码从5到20。

在四叉树中，空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中，但是，当同一父亲的四个兄弟结点都要记录该空间要素标识时，则只将该空间要素标识记录在该父亲结点上，并按这一规则向上层推进。如图6-20所示，面空间要素R1的外包络矩形同时

图6-20 N＝2时的空间划分及其四分树结构

覆盖5、6、7、8四个兄弟子空间，根据以上规则，只需在他们的父亲结点――1号结点的面空间要素索引结点表中记录R1的标识；面空间要素R2的标识则记录在叶子结点10和12的面空间要素索引结点表中；线空间要素L1的标识符记录在13，14，15，16的父亲结点――3号结点的线空间要素索引结点表中；点空间要素P1的标识记录在叶结点17的点空间要素索引结点表中。

（2）索引分析

基于网格划分的四叉树索引的构成方式与网格索引有些类似，都是多对多的形式，即一个网格可以对应多个空间要素，同时一个空间要素也可以对应多个网格。但与一般网格索引不同的是它有效的减少了大的空间要素（跨越多个网格）在结点中的重复记录。并且这种索引机制空间要素的插入和删除都较简单，只需在其覆盖的叶结点和按照上面的规则得到父亲和祖先结点中记录或删除其标识即可，没有像R树一样的复杂耗时的分裂和重新插入操作。同时，其查询方式也比较简单，例如要检索某一多边形内和与其边相交的空间要素，只需先检索出查询多边形所覆盖的叶结点和其父亲和祖先结点中所有的空间要素，然后再进行必要的空间运算，从中检索出满足要求的空间要素。

2.线性可排序四叉树索引

（1）索引原理

线性可排序四叉树索引是Supermap研制出来的一种扩展型四叉树索引。它与传统四叉树索引的不同之处有两点：一点是四叉树结点编码方式不同，另一点是结点和空间要素的对应关系不同。

线性可排序四叉树索引在编码上放弃了传统的四叉树编码方式，其编码方式如图6-21所示，首先将四叉树分解为二叉树，即在父结点层与子结点层之间插入一层虚结点，虚结点不用来记录空间要素。然后按照中序遍历树的顺序对结点进行编码，包括加入的虚结点。

进行空间查询的时候，首先根据查询区域生成所要搜索的结点编号的集合。由于新的

编码方式，孩子和父亲结合编号的连续性将结点编号集合变换成连续的结点编号的范围，

这样就可以很容易的用SQL模型构造条件，从索引表中检索出满足要求的空间要素。

假设某个结点位于四叉树的第N层，可排序四叉树编码为Index。它的四个子结点位于树的第N-1层，编码从左到右分别为：Index_C1，Index_C2，Index_C3，Index_C4，则它们之间有如下关系：

Index_C1=Index－3×4×(N－1) Index_C2=Index－4×(N－1)

Index_C3=Index＋4×(N－1) Index_C4=Index＋3×4×(N－1)

通过编码值很容易确定结点在树中的层数。在进行查询时，给定一个查询范围，假定为矩形，这个矩形范围唯一的对应一个四叉树结点。通过结点的编码，可以快速计算出在这棵子树下的所有子结点。

找子结点的范围的程序伪代码如下：
GetIndexRange(long Index，long Min，long Max)

{

long n = GetLayerNum(Index)；

Min = Max = Index；

While(n>0)

{

Min = Min－ 3×4×(n－1);

Max = Max－3×4×(n－1);

n = n –1;

}

}

在获得子树下所有结点编码的范围以后，利用如下SQL模型可以查询出相应的空间要素来。

Select * From 表名 Where (ID0>Min and ID0<Max)

利用四叉树编码大致的确定空间数据的位置后，就可以在此基础上，通过空间算子进行空间运算和空间分析了。

（2）索引分析

线性可排序四叉树结点和空间要素的对应关系为一对多。一个结点可以对应多个空间要素，但是一个空间要素只能对应一个结点。它将空间要素记录在包含它的最小子空间所对应的结点中。这样可以免除由于多对多机制所带来的查询时需要重排的麻烦。

线性可排序四叉树编码的连续性特点避免了采用传统编码方式的以下缺点：四叉树划分较深、查询时涉及的结点太多时、很容易使检索的SQL模型超过允许的长度。

线性可排序四叉树的不足之处是当四叉树结构发生变化时，例如向下再划分一层，则必须给所有的结点重新编码，即重新构造索引表。这使得该索引缺少一定的灵活性，而采用传统编码的四叉树就不存在这种问题。

6.5.5. 多级索引¶

多级索引是将多个不同或相同的索引方法组合使用，对单级索引空间或者空间范围进行多级划分，解决超大型数据量的GIS系统检索、分析、显示的效率问题。多级索引由于其多级的结构特性，往往可以很好地利用计算机硬件资源的并行工作特性，如多CPU，磁盘阵列等，来提高检索的效率。

多级索引方法很多，不同的单级索引组合便可以构成不同的多级索引方法。但是由于每种索引的特性不同，所以如何将多种索引融合成一体构成一种高效的多级索引也是空间索引的一个研究方向。

1.索引原理

索引分割单元格网索引是一种简单高效的多级索引方法，其基本原理类似于四叉树，将空间范围进行多级划分，每一级划分的空间均采用单元网格索引，构成一个多级网格空间，以适应不同范围的高效查询；与四叉树不同的是每一次空间划分均为物理分割，一旦该级的网格确定，则需建立相应的物理表格存储该级的索引信息。

空间范围的每一级划分原理就是通过规则划分（矩形或正方形）将索引区域划分为不重叠的许多子空间（矩形或正方形），对于该索引区域建立一个范围索引表，记录每个子空间的范围、划分的级别和子空间索引表名称；对每个子空间单元再按照以上规则进行再次划分；对于最后一级的子空间，则为每个子空间单元建立一个子空间索引表，存储落在这个子空间之内的空间要素标识、外包络矩形；并且对于最后一级的子空间，如果包含的空间要素个数太多，可直接将该子空间物理分割成多个。

通过该方式索引，在进行空间检索时，可以直接访问空间区域覆盖的和与空间区域相交的子空间的索引表，然后对空间索引表进行进一步求精判断，以检索出符合要求的空间实体。由于进行了物理分割，那么单个空间索引表维持恒定且较少的记录数，而且空间索引表的字段域也只有几个，数据量大大减少，因此检索效率也就会比单级网格索引要高。

2.索引实现

在索引实现时，采用编写数据库存储过程的方法，这样可以大大减少客户端SQL语句的构造难度和在网络上的传输量。以下为两级索引分割单元格网索引的实现过程。

l 创建索引表的存储过程：（mp_Idx_InitCrtIdxTbl）

第一步，判断是否存在索引管理表，若不存在则创建索引管理表；

第二步，将索引管理表名称，X方向网格数，Y方向网格数添加到索引数据字典中；

第三步，创建相应的索引表集合，索引表名规则：空间要素表名_idx+001，+002，….；

第四步，将各个索引表名称和划分的网格范围信息（xmin，xmax，ymin，ymax）插入到索引表管理表中；

l 填充网格索引数据存储过程：（mp_Idx_FillGridData）

首先，对每一个空间要素：

第一步，计算空间要素外包络矩形；

第二步，判断空间要素外包络矩形相对网格的位置信息，得到该空间要素所在的索引表名称集合（可能空间要素跨多个网格）；

第三步，将该空间要素的标识(id0)和外包络矩形(xmin， ymin， xmax， ymax)插入到计算得到的索引表集合中；

然后，对每个空间索引表的id0，xmin，xmax，ymin，ymax字段域建立数据库联合索引。

l 指定子空间物理再分的存储过程：（mp_Idx_Subdivide）

第一步，计算指定子空间索引表的记录数；

第二步，如果记录数超过索引统计信息中索引表的平均记录数（或者是比较合适的经验数据值），则根据该记录数创建再分的索引表集合。

第三步，重复填充网格索引数据过程；（注意，此时空间要素信息直接从需要划分的索引表中取得）。

l 索引矩形范围查询存储过程：（mp_Idx_SelEntity）

第一步，根据给定矩形范围，在索引管理表中查找出对应的索引表名称集合(一个或多个)；

第二步，在查出的索引表集合中，通过联合索引快速找出满足条件的实体标识号。

创建好存储过程后，在客户端应用程序中调用上述存储过程，可以完成索引的建立和查询操作。如果查询效率不满意，则可以对那些分布密集的区域进行再次划分（调用mp_Idx_ Subdivide），以达到满意的效果为止。

3.索引分析

索引分割单元格网索引相对而言，优势在于：

l 原理简单，实现起来较为容易。

l 查询效率高，对那些数据量大，空间实体分布均匀的情况尤其明显。经过实验，在空间要素为300万左右的数据量下，查询1000个左右空间要素时，响应时间均在1秒以内。

l 索引维护相对比较简单。空间要素的添加、更新、删除操作，索引表均为固定的模式，没有R树分裂合并时的复杂情况。

但是，由于该索引方式是以网格编码索引为基础，所以该索引也继承了网格索引的缺陷：

l 最大的难点在于格网划分的精细程度的确定，格网划分的好坏将对索引数据量和检索效率产生直接影响。网格划分的精细程度在很大程度上取决于空间对象的分布以及建库人员的经验，所以，期望在任何情况下都能得到索引区域的一个最佳划分通常情况下是不容易的。

l 如果空间要素跨越多个网格区域，在多个索引表中将会保存此空间要素实体的信息，造成冗余，并使得索引数据量迅速增长。

l 建立多个索引表，本身也是额外的开销。

l 对于数据量比较小的GIS应用，建立多级索引反而会降低检索效率。

6.5.6. 索引技术比较¶

表6-3 索引综合性能对照表

空间索引的方法很多，但基本原理都类似，即采用分割原理，把查询空间划分为若干区域，通常为矩形或者是多边形，这些区域包含空间要素并且可唯一标识。目前，分割方法一般可归纳为两种：一种是规则分割法，另一种是对象分割法。规则分割法是将地理空间按照某种规则或半规则方式分割，分割单元间接地与空间要素相关联，空间要素的几何形状可能被分割到几个相邻的单元中，这时空间要素的描述保持完整，而空间索引单元只存储空间要素地址的参考信息。在对象分割法中，索引空间的分割直接由空间要素来确定，索引单元包括空间要素地址的参考信息和空间要素的外包络矩形。常见的空间索引方法一般都是自上而下、逐级划分地理空间，从而形成各种空间索引结构。比较有代表性的规则分割法包括网格系列索引。基于对象的分割法主要是包括R系列树索引。每一类空间索引方法都有其优越性和使用范围的局限。表6-3是在对各种类型索引研究的基础上归纳出来的索引综合性能对照表。