吕闽晖 ，吕敏蓉

(1.海军工程大学 装备经济研究所，湖北 武汉 430033；2.湖南女子学院，湖南 长沙 410004)

常见的空间查询有点查询、窗口查询 (或称范围查询)、相交查询(或称区域查询)、被包围查询、毗连查询、最近邻查询、空间连接查询等，其中空间连接查询是最重要、最耗时的空间查询[1]。本文首先对Ingres原有空间连接方式进行研究。然后参照已有的相关研究论文，采用基于宽度优先的R树空间连接算法，并对其进行全面测试(包括功能和性能测试)，并与 Ingres原有空间连接进行性能对比。

1 Ingres空间连接算法

Ingres原有的空间连接执行时，如果两个表都建有R树索引，其QEP为TID Join。如有两个表RTreeJoin1和RTreeJoin2，对应的空间索引为 RTree1和 RTree2，如果执行 Select*from RTreeJoin1，RTreeJoin2 where RTreeJoin1.obj overlaps RTreeJoin2.obj，QEP如图 1所示。

图1 Ingres原有空间连接QEP

图中Spatial Join即Key Join，首先是将RTreeJoin1.obj的值作为键值查找索引RTree2，所得对应RTreeJoin2中的TID，然后再以此TID直接访问RTreeJoin2中的元组，即TID Join。此种方式没有利用两个基表都建有RTree的优势，因此在部分情况下不能获得最优的性能。这种方法称为“One-Rtree-Only”空间连接方法[2]。

2 Ingres空间连接算法改进

针对上述分析，希望能够在过滤阶段即利用两个R树索引。通过对两个索引进行按深度或按宽度的遍历，执行过滤运算，不可能满足连接条件的空间对象迅速排除[3-4]。本文将参考文献[5]使用广度优先遍历算法优化R树空间连接。

2.1 在遍历R树时剪枝

在R树中维护的一个重要信息就是它的层次性蕴含着它的包含性。即一个树结点的MBR总是包围着它的子孙结点的MBR。利用这一特点可知，一对结点nRir和nSjS需要进行连接仅当它们父结点的MBR相交，称为剪枝。……