摘  要： 空間索引作為空間數(shù)據(jù)庫的關(guān)鍵技術(shù)，其性能的高低決定著整個(gè)空間數(shù)據(jù)庫的效率。通過對現(xiàn)有的多種空間索引結(jié)構(gòu)進(jìn)行比較分析，基于開源數(shù)據(jù)庫Ingres實(shí)現(xiàn)了廣度優(yōu)先R樹連接算法(BFRJ)，并對其進(jìn)行了局部優(yōu)化和全局優(yōu)化?；谡鎸?shí)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果分析，證實(shí)了采用適當(dāng)?shù)娜謨?yōu)化方法的BFRJ優(yōu)于其他已知的空間連接算法方法。
關(guān)鍵詞： 空間索引；空間連接；Hilbert R樹；BFRJ

　常見的空間查詢有點(diǎn)查詢、窗口查詢(或稱范圍查詢)、相交查詢(或稱區(qū)域查詢)、被包圍查詢、毗連查詢、最近鄰查詢、空間連接查詢等，其中空間連接查詢是最重要、最耗時(shí)的空間查詢[1]。本文首先對Ingres原有空間連接方式進(jìn)行研究。然后參照已有的相關(guān)研究論文，采用基于寬度優(yōu)先的R樹空間連接算法，并對其進(jìn)行全面測試(包括功能和性能測試)，并與Ingres原有空間連接進(jìn)行性能對比。
1 Ingres空間連接算法
　Ingres原有的空間連接執(zhí)行時(shí)，如果兩個(gè)表都建有R樹索引，其QEP為TID Join。如有兩個(gè)表RTreeJoin1和RTreeJoin2，對應(yīng)的空間索引為RTree1和RTree2，如果執(zhí)行Select*from RTreeJoin1，RTreeJoin2 where RTreeJoin1.obj overlaps RTreeJoin2.obj，QEP如圖1所示。

　圖中Spatial Join即Key Join，首先是將RTreeJoin1.obj的值作為鍵值查找索引RTree2，所得對應(yīng)RTreeJoin2中的TID，然后再以此TID直接訪問RTreeJoin2中的元組，即TID Join。此種方式?jīng)]有利用兩個(gè)基表都建有RTree的優(yōu)勢，因此在部分情況下不能獲得最優(yōu)的性能。這種方法稱為“One-Rtree-Only”空間連接方法[2]。
2 Ingres空間連接算法改進(jìn)
　針對上述分析，希望能夠在過濾階段即利用兩個(gè)R樹索引。通過對兩個(gè)索引進(jìn)行按深度或按寬度的遍歷，執(zhí)行過濾運(yùn)算，不可能滿足連接條件的空間對象迅速排除[3-4]。本文將參考文獻(xiàn)[5]使用廣度優(yōu)先遍歷算法優(yōu)化R樹空間連接。
2.1 在遍歷R樹時(shí)剪枝
　在R樹中維護(hù)的一個(gè)重要信息就是它的層次性蘊(yùn)含著它的包含性。即一個(gè)樹結(jié)點(diǎn)的MBR總是包圍著它的子孫結(jié)點(diǎn)的MBR。利用這一特點(diǎn)可知，一對結(jié)點(diǎn)nRir和nSjS需要進(jìn)行連接僅當(dāng)它們父結(jié)點(diǎn)的MBR相交，稱為剪枝。簡單的從頂至底的圖遍歷算法可以在任何層次上使用這種剪枝。參考文獻(xiàn)[5]中剪枝是在同時(shí)深度優(yōu)先遍歷兩棵輸入的R樹時(shí)進(jìn)行的(DFRJ)，而參考文獻(xiàn)[6]則是在同時(shí)廣度優(yōu)先遍歷兩棵R樹時(shí)進(jìn)行的(BFRJ)。在R樹的所有層次施行剪枝達(dá)到的效果是從頂層起，分別來自兩棵R樹的兩個(gè)結(jié)點(diǎn)被遍歷到僅當(dāng)它們父結(jié)點(diǎn)的MBR相交。這樣，相比簡單的嵌套循環(huán)的遍歷方式，剪枝將使得被遍歷的不相交的結(jié)點(diǎn)對數(shù)大大減少。
2.2 BFRJ算法
　基于廣度優(yōu)先遍歷的R樹空間連接算法(BFRJ)步驟為：(1)對兩棵R樹的根結(jié)點(diǎn)(NR，NS)做一次結(jié)點(diǎn)連接。所謂結(jié)點(diǎn)連接，就是對輸入的兩個(gè)非葉子結(jié)點(diǎn)，返回其相交的元素項(xiàng)對。對根結(jié)點(diǎn)做結(jié)點(diǎn)連接的結(jié)果是一個(gè)二元組(oidR0，oidS0)的集合，稱為0階中間連接索引IJI0(intermediate join index at level 0)。因?yàn)楸疚闹饕塾趯ο嘟贿\(yùn)算的空間連接，因此每一個(gè)二元組(oidR0，oidS0)意味著這兩個(gè)元素項(xiàng)的MBR相交。(2)對于IJI0的每一個(gè)二元組，BFRJ找出其在兩棵R樹中對應(yīng)的結(jié)點(diǎn)，進(jìn)行結(jié)點(diǎn)連接。當(dāng)BFRJ從IJI0中讀入一個(gè)二元組進(jìn)行計(jì)算時(shí)，它會(huì)以二元組(oidR1，oidS1)的形式保存結(jié)果，加入當(dāng)前的1階中間連接索引IJI1。當(dāng)BFRJ處理完IJI0中的所有二元組后，它會(huì)釋放IJI0并開始對IJI1進(jìn)行相應(yīng)的連接操作。這個(gè)過程隨著BFRJ算法逐層遍歷R樹而繼續(xù)著。當(dāng)中間連接索引由兩棵R樹的葉子結(jié)點(diǎn)產(chǎn)生時(shí)，算法終止。如果兩棵R樹不等高，算法將在到達(dá)一棵樹的葉子結(jié)點(diǎn)(如R)時(shí)，枚舉葉子結(jié)點(diǎn)中的每一個(gè)元素項(xiàng)對另一棵樹S中對應(yīng)子樹做查詢操作。到此，空間連接過濾環(huán)節(jié)已經(jīng)結(jié)束，當(dāng)前的(葉子級(jí)的)IJI已經(jīng)不在空間連接的范疇之內(nèi)了。

2.3 局部優(yōu)化技術(shù)
　局部優(yōu)化技術(shù)是在結(jié)點(diǎn)連接的過程中進(jìn)行的。在參考文獻(xiàn)[6]中介紹了兩種局部優(yōu)化技術(shù)，分別為搜索空間限制(Search Space Restriction)和平面掃描(Plane Sweep)。
2.3.1 搜索空間限制
　在一對結(jié)點(diǎn)nRir和nSjS進(jìn)行連接時(shí)，它們的MBR的交叉區(qū)域仍然是MBR(稱為intersect-MBR)。如果nRir中的元素項(xiàng)(oidRir，mrbRir)x同nSjS中的元素項(xiàng)(oidSjS，mrbSjS)y相交，則mrbRir和mrbSjS必須同兩個(gè)結(jié)點(diǎn)的intersect-MBR相交。因此，可以首先對nRir和nSjS的元素項(xiàng)分別進(jìn)行掃描，排除掉那些MBR同intersect-MBR不相交的元素項(xiàng)。在進(jìn)行結(jié)點(diǎn)連接時(shí)，僅對剩余項(xiàng)進(jìn)行連接。
2.3.2 平面掃描
　這一優(yōu)化方式同合并兩個(gè)普通的數(shù)據(jù)集合時(shí)采用的排序-歸并技術(shù)類似。在一對結(jié)點(diǎn)nRir和nSjS進(jìn)行連接的過程中，首先分別對兩個(gè)結(jié)點(diǎn)中的元素項(xiàng)依MBR進(jìn)行排序。為了對多維數(shù)據(jù)進(jìn)行排序，用MBR的最小x值作為關(guān)鍵字。在合并階段，依次對排序的MBR進(jìn)行掃描。對于一棵樹中的MBR，僅對于其x坐標(biāo)相交的MBR進(jìn)行相交測試。
　這兩種優(yōu)化技術(shù)各有側(cè)重，搜索空間限制技術(shù)可以對于結(jié)點(diǎn)容量較大但元素項(xiàng)分散的數(shù)據(jù)進(jìn)行較大優(yōu)化，而平面掃描對于多維數(shù)據(jù)的優(yōu)勢更大。
2.4 全局優(yōu)化技術(shù)
　在BFRJ算法框架下，i階中間連接索引(IJIi)在兩棵樹中所有的i層結(jié)點(diǎn)連接完畢后產(chǎn)生。而在i層進(jìn)行結(jié)點(diǎn)連接的結(jié)點(diǎn)對來自于由更高的(i-1層)結(jié)點(diǎn)連接產(chǎn)生。因此可以在對一層結(jié)點(diǎn)進(jìn)行結(jié)點(diǎn)連接之前，獲取該層所有結(jié)點(diǎn)訪問預(yù)計(jì)(包括它們可能的訪問順序和重復(fù)訪問次數(shù))的全局信息，可以利用一些技術(shù)來對中間連接索引進(jìn)行高效的管理。
2.4.1 中間連接索引排序
　設(shè)結(jié)點(diǎn)的MBR同R樹S的k個(gè)t級(jí)結(jié)點(diǎn)的MBR相交，則nRit的索引ID在IJIt-1中出現(xiàn)了k次。在計(jì)算t層的結(jié)點(diǎn)連接時(shí)，nRit將被恰好計(jì)算k次。對于一個(gè)固定大小的LRU系統(tǒng)緩沖，如果ID在IJIt-1中出現(xiàn)的比較分散，則結(jié)點(diǎn)nRit將從硬盤中被多次讀取(最多k次)。這是因?yàn)榈谝淮魏秃竺娉霈F(xiàn)的對nRit的調(diào)用之間可能會(huì)比較遠(yuǎn)，在需要被再次讀入時(shí)可能已經(jīng)從緩沖區(qū)中刪除。因此希望IJI能夠維護(hù)在一種有序的狀態(tài)下，使得多次出現(xiàn)的相同結(jié)點(diǎn)的ID在IJI中出現(xiàn)的位置不要分散得太過稀疏。
2.4.2 中間連接索引內(nèi)存管理
　IJI可以被存儲(chǔ)在內(nèi)存中或是磁盤上。前者能提高IJI排序的效率并減少讀取IJI時(shí)多余的I/O操作；而后者能解放出更多的內(nèi)存資源用于連接計(jì)算。
2.4.3 中間連接索引緩沖管理
　IJI排序技術(shù)傾向于維護(hù)索引的順序，使得任意兩個(gè)相同ID出現(xiàn)的位置不會(huì)相隔太遠(yuǎn)。然而，對兩個(gè)項(xiàng)目都實(shí)現(xiàn)很好的聚類效果是不可能的，在連接運(yùn)算中，對一個(gè)結(jié)點(diǎn)的多次磁盤讀取依然存在。如果緩沖管理可以預(yù)測哪個(gè)結(jié)點(diǎn)已經(jīng)連接完畢，而哪個(gè)結(jié)點(diǎn)將來還會(huì)參與運(yùn)算，則這種多次讀取可以被進(jìn)一步縮減。用這種方式，緩沖管理可以保留那些將來還會(huì)參與運(yùn)算的結(jié)點(diǎn)頁面，而將已經(jīng)結(jié)束所有連接運(yùn)算的結(jié)點(diǎn)頁面清理釋放。
3 實(shí)驗(yàn)結(jié)果
　采用實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)來自www.rtreeportal.org的兩個(gè)數(shù)據(jù)組：
　(1)“Germany”數(shù)據(jù)組，包含四個(gè)數(shù)據(jù)包：
?、?ldquo;roads”：包含了德國的30 674條街道的MBR；
?、?ldquo;rrlines”：包含了36 334條鐵路線的MBR；
　③“utility”：包含了17 790條公用網(wǎng)絡(luò)的MBR；
?、?ldquo;hypsogr”：地勢圖，由76 999個(gè)MBR組成。
　(2)“Greece”數(shù)據(jù)組，包含兩個(gè)數(shù)據(jù)包：
?、?ldquo;roads”：包含了希臘的23 268條街道的MBR；
?、?ldquo;rivers”：包含了24 650條河流的MBR。
　將這些數(shù)據(jù)包組成四個(gè)連接對進(jìn)行實(shí)驗(yàn)，即“Germany：roads，rrlines”，“Germany：roads，utility”，“Germany：roads，hypsogr”，“Greece：roads，rivers”。
在實(shí)驗(yàn)中，固定了R樹的頁面大小，這樣，影響連接性能的主要參數(shù)除了使用的方法外即為緩沖大小。用緩沖區(qū)最多存放R樹頁面的個(gè)數(shù)作為衡量緩沖大小的參數(shù)，這樣在不失一般性的同時(shí)可以簡化緩沖管理操作在程序內(nèi)實(shí)現(xiàn)。
　表1~表4給出了連接對“Germany：roads，rrlines”的實(shí)驗(yàn)結(jié)果，其中的數(shù)據(jù)表示在給定的緩沖大小下給定空間連接方法在給定緩沖大小下對應(yīng)的頁面I/O次數(shù)m。

　從實(shí)驗(yàn)結(jié)果分析各連接方法，Buff size表示緩沖區(qū)大小，One-Rree-Only表示只對一個(gè)數(shù)據(jù)包建R樹；DFRJ表示使用DFRJ方法進(jìn)行R樹連接；OrdOneStorDiskPinNo表示采用基于磁盤存儲(chǔ)的非特定排序優(yōu)化組合BFRJ方法進(jìn)行空間連接；OrdOneStorMemPinYes表示采用基于主存存儲(chǔ)的對單棵樹排序優(yōu)化組合BFRJ方法進(jìn)行空間連接，OrdSumStorMemPinYes表示采用基于主存存儲(chǔ)的對中值和排序的優(yōu)化組合BFRJ方法進(jìn)行空間連接。由于StorMem意味著要將IJI保存在主存中，因此對緩沖大小有要求，當(dāng)緩沖較小時(shí)則不適用，對應(yīng)的表格項(xiàng)為N/A。
　在真實(shí)數(shù)據(jù)的條件下，對于任意的緩沖大小，基于兩棵R樹的空間連接算法(DFRJ和BFRJ)的性能總是優(yōu)于基于一棵R樹的算法(One-Rree-Only)。而在R樹空間連接方法中，使用適當(dāng)全局優(yōu)化組合的BFRJ又明顯優(yōu)于DFRJ。在緩沖較小時(shí)，OrdOneStorDiskPinNo最適用；在適中的緩沖條件下，StorDisk的性能要比StorMem差，OrdOneStorMemPinYes相對更優(yōu)；而在較大的緩沖條件下，OrdSumStorMemPinYes能夠獲得最好的空間連接性能。
參考文獻(xiàn)
[1] KAMEL I， FALOUTSOS C. Hilbert R-tree： An improved R-tree using fractals[M]. In： Proceedings of the 20th VLDB， Santiago， Chile， 1994，500-509.
[2] HUANG P W， LIN P L， LIN H Y. Optimizing storage utilization in R-tree dynamic index structure for spatial databases[J]. Journal of Systems and Software， 2001，55(3)：291-299.
[3] BRAKATSOULAS S， PFOSER D， THEODORIDIS Y. Revisiting R-tree construction principles[M]. In： Proceedings of the 6th ADBIS， Bratislava， Slovakia， 2002，149-162.
[4] BRINKHOFF T， KRIEGEL H. P， SEEGER B. Efficient processing of spatial joins using R-trees[M]. In： Proceedings of ACM SIGMOD， Washington DC， 1993，237-246.
[5] MARTYNOV M. Spatial joins and R-trees. In： Proceedings of the 3rd ADBIS[M]， Moscow， Russia， 1995，295-304.
[6] HUANG Y W， JING N， RUNDENSTEINER E. Spatial joins using R-trees： Breadth First traversal with global optimizations. In： Proceedings of the 23rd VLDB， At hens， Greece， 1997，396-405.