Abstract: Spatial join is one of the most important and time-consuming operations.A new R-tree spatial join algorithm based on Breadth-First R-tree Join（BFRJ），named OBFRJ，is proposed.The OBFRJ algorithm scans the two R-tree involved in spatial join in breadth-first order.While the intermediate join index is being processed，the OBFRJ adopts a space filling curve to order it，hence reducing the chance of page faults during the join operation of the next layer.Compared with the DFRJ and BFRJ algorithms，this method reduces the frequency of disk access and the overhead of CPU.

Key words: spatial database, spatial join, R-tree, space-filling curve, plane sweeping

摘要： 空间数据库中空间连接操作是最重要、最耗时的操作之一，基于BFRJ算法研究了一种对中间连接索引优化排序的空间连接算法OBFRJ，该算法使用广度优先顺序对两棵R树进行同步遍历，对生成的中间连接索引采用了一种空间填充曲线进行排序，使得在下一层的连接时出现页错误的次数减少。实验结果表明，该算法在磁盘访问次数以及CPU代价上都要小于DFRJ和BFRJ算法。

关键词: 空间数据库, 空间连接, R树, 空间填充曲线, 平面扫描