摘 要： 空間索引作為空間數(shù)據(jù)庫的關(guān)鍵技術(shù)，其性能的高低決定著整個空間數(shù)據(jù)庫的效率。通過對現(xiàn)有的多種空間索引結(jié)構(gòu)進行比較分析，基于開源數(shù)據(jù)庫Ingres實現(xiàn)了廣度優(yōu)先R樹連接算法(BFRJ)，并對其進行了局部優(yōu)化和全局優(yōu)化?；谡鎸崝?shù)據(jù)的實驗結(jié)果分析，證實了采用適當(dāng)?shù)娜謨?yōu)化方法的BFRJ優(yōu)于其他已知的空間連接算法方法。
關(guān)鍵詞： 空間索引；空間連接；Hilbert R樹；BFRJ
常見的空間查詢有點查詢、窗口查詢(或稱范圍查詢)、相交查詢(或稱區(qū)域查詢)、被包圍查詢、毗連查詢、最近鄰查詢、空間連接查詢等，其中空間連接查詢是最重要、最耗時的空間查詢[1]。本文首先對Ingres原有空間連接方式進行研究。然后參照已有的相關(guān)研究論文，采用基于寬度優(yōu)先的R樹空間連接算法，并對其進行全面測試(包括功能和性能測試)，并與Ingres原有空間連接進行性能對比。
1 Ingres空間連接算法
Ingres原有的空間連接執(zhí)行時，如果兩個表都建有R樹索引，其QEP為TID Join。如有兩個表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)]有利用兩個基表都建有RTree的優(yōu)勢，因此在部分情況下不能獲得最優(yōu)的性能。這種方法稱為“One-Rtree-Only”空間連接方法[2]。
2 Ingres空間連接算法改進
針對上述分析，希望能夠在過濾階段即利用兩個R樹索引。通過對兩個索引進行按深度或按寬度的遍歷，執(zhí)行過濾運算，不可能滿足連接條件的空間對象迅速排除[3-4]。本文將參考文獻[5]使用廣度優(yōu)先遍歷算法優(yōu)化R樹空間連接。
2.1 在遍歷R樹時剪枝
在R樹中維護的一個重要信息就是它的層次性蘊含著它的包含性。即一個樹結(jié)點的MBR總是包圍著它的子孫結(jié)點的MBR。利用這一特點可知，一對結(jié)點nRir和nSjS需要進行連接僅當(dāng)它們父結(jié)點的MBR相交，稱為剪枝。簡單的從頂至底的圖遍歷算法可以在任何層次上使用這種剪枝。參考文獻[5]中剪枝是在同時深度優(yōu)先遍歷兩棵輸入的R樹時進行的(DFRJ)，而參考文獻[6]則是在同時廣度優(yōu)先遍歷兩棵R樹時進行的(BFRJ)。在R樹的所有層次施行剪枝達到的效果是從頂層起，分別來自兩棵R樹的兩個結(jié)點被遍歷到僅當(dāng)它們父結(jié)點的MBR相交。這樣，相比簡單的嵌套循環(huán)的遍歷方式，剪枝將使得被遍歷的不相交的結(jié)點對數(shù)大大減少。
2.2 BFRJ算法
基于廣度優(yōu)先遍歷的R樹空間連接算法(BFRJ)步驟為：(1)對兩棵R樹的根結(jié)點(NR，NS)做一次結(jié)點連接。所謂結(jié)點連接，就是對輸入的兩個非葉子結(jié)點，返回其相交的元素項對。對根結(jié)點做結(jié)點連接的結(jié)果是一個二元組(oidR0，oidS0)的集合，稱為0階中間連接索引IJI0(intermediate join index at level 0)。因為本文主要著眼于對相交運算的空間連接，因此每一個二元組(oidR0，oidS0)意味著這兩個元素項的MBR相交。(2)對于IJI0的每一個二元組，BFRJ找出其在兩棵R樹中對應(yīng)的結(jié)點，進行結(jié)點連接。當(dāng)BFRJ從IJI0中讀入一個二元組進行計算時，它會以二元組(oidR1，oidS1)的形式保存結(jié)果，加入當(dāng)前的1階中間連接索引IJI1。當(dāng)BFRJ處理完IJI0中的所有二元組后，它會釋放IJI0并開始對IJI1進行相應(yīng)的連接操作。這個過程隨著BFRJ算法逐層遍歷R樹而繼續(xù)著。當(dāng)中間連接索引由兩棵R樹的葉子結(jié)點產(chǎn)生時，算法終止。如果兩棵R樹不等高，算法將在到達一棵樹的葉子結(jié)點(如R)時，枚舉葉子結(jié)點中的每一個元素項對另一棵樹S中對應(yīng)子樹做查詢操作。到此，空間連接過濾環(huán)節(jié)已經(jīng)結(jié)束，當(dāng)前的(葉子級的)IJI已經(jīng)不在空間連接的范疇之內(nèi)了。
2.3 局部優(yōu)化技術(shù)
局部優(yōu)化技術(shù)是在結(jié)點連接的過程中進行的。在參考文獻[6]中介紹了兩種局部優(yōu)化技術(shù)，分別為搜索空間限制(Search Space Restriction)和平面掃描(Plane Sweep)。
2.3.1 搜索空間限制
在一對結(jié)點nRir和nSjS進行連接時，它們的MBR的交叉區(qū)域仍然是MBR(稱為intersect-MBR)。如果nRir中的元素項(oidRir，mrbRir)x同nSjS中的元素項(oidSjS，mrbSjS)y相交，則mrbRir和mrbSjS必須同兩個結(jié)點的intersect-MBR相交。因此，可以首先對nRir和nSjS的元素項分別進行掃描，排除掉那些MBR同intersect-MBR不相交的元素項。在進行結(jié)點連接時，僅對剩余項進行連接。
2.3.2 平面掃描
這一優(yōu)化方式同合并兩個普通的數(shù)據(jù)集合時采用的排序-歸并技術(shù)類似。在一對結(jié)點nRir和nSjS進行連接的過程中，首先分別對兩個結(jié)點中的元素項依MBR進行排序。為了對多維數(shù)據(jù)進行排序，用MBR的最小x值作為關(guān)鍵字。在合并階段，依次對排序的MBR進行掃描。對于一棵樹中的MBR，僅對于其x坐標相交的MBR進行相交測試。
這兩種優(yōu)化技術(shù)各有側(cè)重，搜索空間限制技術(shù)可以對于結(jié)點容量較大但元素項分散的數(shù)據(jù)進行較大優(yōu)化，而平面掃描對于多維數(shù)據(jù)的優(yōu)勢更大。
2.4 全局優(yōu)化技術(shù)
在BFRJ算法框架下，i階中間連接索引(IJIi)在兩棵樹中所有的i層結(jié)點連接完畢后產(chǎn)生。而在i層進行結(jié)點連接的結(jié)點對來自于由更高的(i-1層)結(jié)點連接產(chǎn)生。因此可以在對一層結(jié)點進行結(jié)點連接之前，獲取該層所有結(jié)點訪問預(yù)計(包括它們可能的訪問順序和重復(fù)訪問次數(shù))的全局信息，可以利用一些技術(shù)來對中間連接索引進行高效的管理。
2.4.1 中間連接索引排序
設(shè)結(jié)點的MBR同R樹S的k個t級結(jié)點的MBR相交，則nRit的索引ID在IJIt-1中出現(xiàn)了k次。在計算t層的結(jié)點連接時，nRit將被恰好計算k次。對于一個固定大小的LRU系統(tǒng)緩沖，如果ID在IJIt-1中出現(xiàn)的比較分散，則結(jié)點nRit將從硬盤中被多次讀取(最多k次)。這是因為第一次和后面出現(xiàn)的對nRit的調(diào)用之間可能會比較遠，在需要被再次讀入時可能已經(jīng)從緩沖區(qū)中刪除。因此希望IJI能夠維護在一種有序的狀態(tài)下，使得多次出現(xiàn)的相同結(jié)點的ID在IJI中出現(xiàn)的位置不要分散得太過稀疏。
2.4.2 中間連接索引內(nèi)存管理
IJI可以被存儲在內(nèi)存中或是磁盤上。前者能提高IJI排序的效率并減少讀取IJI時多余的I/O操作；而后者能解放出更多的內(nèi)存資源用于連接計算。
2.4.3 中間連接索引緩沖管理
IJI排序技術(shù)傾向于維護索引的順序，使得任意兩個相同ID出現(xiàn)的位置不會相隔太遠。然而，對兩個項目都實現(xiàn)很好的聚類效果是不可能的，在連接運算中，對一個結(jié)點的多次磁盤讀取依然存在。如果緩沖管理可以預(yù)測哪個結(jié)點已經(jīng)連接完畢，而哪個結(jié)點將來還會參與運算，則這種多次讀取可以被進一步縮減。用這種方式，緩沖管理可以保留那些將來還會參與運算的結(jié)點頁面，而將已經(jīng)結(jié)束所有連接運算的結(jié)點頁面清理釋放。
3 實驗結(jié)果
采用實際數(shù)據(jù)進行實驗。實驗數(shù)據(jù)來自www.rtreeportal.org的兩個數(shù)據(jù)組：
(1)“Germany”數(shù)據(jù)組，包含四個數(shù)據(jù)包：
①“roads”：包含了德國的30 674條街道的MBR；
?、?ldquo;rrlines”：包含了36 334條鐵路線的MBR；
?、?ldquo;utility”：包含了17 790條公用網(wǎng)絡(luò)的MBR；
④“hypsogr”：地勢圖，由76 999個MBR組成。
(2)“Greece”數(shù)據(jù)組，包含兩個數(shù)據(jù)包：
?、?ldquo;roads”：包含了希臘的23 268條街道的MBR；
?、?ldquo;rivers”：包含了24 650條河流的MBR。
將這些數(shù)據(jù)包組成四個連接對進行實驗，即“Germany：roads，rrlines”，“Germany：roads，utility”，“Germany：roads，hypsogr”，“Greece：roads，rivers”。
在實驗中，固定了R樹的頁面大小，這樣，影響連接性能的主要參數(shù)除了使用的方法外即為緩沖大小。用緩沖區(qū)最多存放R樹頁面的個數(shù)作為衡量緩沖大小的參數(shù)，這樣在不失一般性的同時可以簡化緩沖管理操作在程序內(nèi)實現(xiàn)。
表1~表4給出了連接對“Germany：roads，rrlines”的實驗結(jié)果，其中的數(shù)據(jù)表示在給定的緩沖大小下給定空間連接方法在給定緩沖大小下對應(yīng)的頁面I/O次數(shù)m。
從實驗結(jié)果分析各連接方法，Buff size表示緩沖區(qū)大小，One-Rree-Only表示只對一個數(shù)據(jù)包建R樹；DFRJ表示使用DFRJ方法進行R樹連接；OrdOneStorDiskPinNo表示采用基于磁盤存儲的非特定排序優(yōu)化組合BFRJ方法進行空間連接；OrdOneStorMemPinYes表示采用基于主存存儲的對單棵樹排序優(yōu)化組合BFRJ方法進行空間連接，OrdSumStorMemPinYes表示采用基于主存存儲的對中值和排序的優(yōu)化組合BFRJ方法進行空間連接。由于StorMem意味著要將IJI保存在主存中，因此對緩沖大小有要求，當(dāng)緩沖較小時則不適用，對應(yīng)的表格項為N/A。
在真實數(shù)據(jù)的條件下，對于任意的緩沖大小，基于兩棵R樹的空間連接算法(DFRJ和BFRJ)的性能總是優(yōu)于基于一棵R樹的算法(One-Rree-Only)。而在R樹空間連接方法中，使用適當(dāng)全局優(yōu)化組合的BFRJ又明顯優(yōu)于DFRJ。在緩沖較小時，OrdOneStorDiskPinNo最適用；在適中的緩沖條件下，StorDisk的性能要比StorMem差，OrdOneStorMemPinYes相對更優(yōu)；而在較大的緩沖條件下，OrdSumStorMemPinYes能夠獲得最好的空間連接性能。
參考文獻
[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.