空間數(shù)據(jù)庫(kù)中r樹變體的研究與應(yīng)用

空間數(shù)據(jù)庫(kù)中r樹變體的研究與應(yīng)用

1u3000結(jié)u3000論空間數(shù)據(jù)庫(kù)是一個(gè)磁盤數(shù)據(jù)庫(kù)，可以快速有效地訪問空間數(shù)據(jù)。為了快速有效地訪問大量的空間數(shù)據(jù)，專家和科學(xué)家提出了許多空間索引方法。從空間數(shù)據(jù)庫(kù)的角度來(lái)看，空間索引結(jié)構(gòu)可分為三種空間提取方法（pam）和空間擴(kuò)展對(duì)象（包括點(diǎn)、線、面、體）。pam包括gri文件、budye樹、k-d-b樹、hb樹、lsd樹和其他空間對(duì)象。sam使用空間對(duì)象的近似來(lái)索引空間對(duì)象，例如將最小空間對(duì)象剖面為高維空間的點(diǎn)，并使用點(diǎn)標(biāo)記法將高維空間中的空間對(duì)象分類到一維模型。例如，空間填充曲線的一般方法將高維空間中的空間對(duì)象分類到一個(gè)空間，然后使用點(diǎn)標(biāo)記法在三維空間中提取數(shù)據(jù)集，例如，gray碼、morton代碼、hilber代碼、granula碼等。對(duì)象分類復(fù)制是將空間中的數(shù)據(jù)對(duì)象劃分為幾個(gè)對(duì)象，并將它們存儲(chǔ)在相互重疊的空間中。對(duì)于r-u型木材，可以創(chuàng)建z型木材，布局樹和r-u型木材等。R樹是一種采用對(duì)象界定技術(shù)的高度平衡樹,是B樹在k維空間上的自然擴(kuò)展.作為目前最流行的動(dòng)態(tài)空間索引結(jié)構(gòu)之一,R樹廣泛應(yīng)用于原型研究和商用空間數(shù)據(jù)庫(kù)系統(tǒng)中.R樹最初由Guttman于1984年提出,其后,人們?cè)诖嘶A(chǔ)上針對(duì)不同的空間操作需求提出了各種改進(jìn)方案.經(jīng)過20年的發(fā)展,不斷產(chǎn)生的R樹變體逐漸形成了一個(gè)枝繁葉茂的空間索引R樹家族.從其覆蓋的廣度和深度來(lái)看,多維空間索引R樹就像一維線性索引B樹一樣,是無(wú)處不在的1.本文回顧了國(guó)內(nèi)外20年來(lái)空間索引R樹研究的重要成果,討論了R樹及其主要變體的結(jié)構(gòu)特點(diǎn),描述了R樹構(gòu)造過程中的批量操作方法,分析了基于R樹的空間查詢處理過程及基于R樹的查詢代價(jià)模型及查詢優(yōu)化過程,介紹了R樹并行處理與并發(fā)控制的研究進(jìn)展;并結(jié)合作者在該領(lǐng)域的研究工作和實(shí)驗(yàn)過程對(duì)這些研究成果進(jìn)行了分析與評(píng)述,進(jìn)而對(duì)當(dāng)前R樹的研究熱點(diǎn)問題進(jìn)行了討論和展望.2r+樹多路徑搜索問題的解決技術(shù)經(jīng)過搜集與整理20年來(lái)國(guó)際計(jì)算機(jī)與GIS領(lǐng)域?qū)樹的研究文獻(xiàn),我們得出如圖1所示的R樹家族進(jìn)化圖,描述了R樹家族自1984年提出以來(lái)的演變和發(fā)展歷程.R樹是一種層次數(shù)據(jù)結(jié)構(gòu),它是B樹在k維空間上的自然擴(kuò)展,因此和B樹一樣,R樹是一種高度平衡樹,在葉結(jié)點(diǎn)中包含指向?qū)嶋H數(shù)據(jù)對(duì)象的指針,并能保證至少50%的有效空間存儲(chǔ)利用率.R樹是一種完全動(dòng)態(tài)的空間索引數(shù)據(jù)結(jié)構(gòu),插入、刪除和查詢可以同時(shí)進(jìn)行,并且不需要周期性的索引重組.R樹由中間結(jié)點(diǎn)和葉結(jié)點(diǎn)組成,葉結(jié)點(diǎn)存儲(chǔ)的是實(shí)際空間對(duì)象的最小邊界矩形(MBR),而不是實(shí)際的空間對(duì)象.R樹的其它特性可見文獻(xiàn).R樹允許兄弟結(jié)點(diǎn)之間的相互重疊.因此對(duì)于精確匹配查詢,R樹不能保證唯一的搜索路徑.圖2是一個(gè)二維2層R樹的實(shí)例,左邊是空間數(shù)據(jù)對(duì)象,右邊是對(duì)應(yīng)R樹,其中M=3(M是結(jié)點(diǎn)最大容量).為了避免R樹由于兄弟結(jié)點(diǎn)的重疊而產(chǎn)生的多路徑查詢問題,1987年,Sellis等設(shè)計(jì)了R+樹,以提高其檢索性能.R+樹采用對(duì)象分割技術(shù),避免了兄弟結(jié)點(diǎn)的重疊,要求跨越子空間的對(duì)象必須分割成兩個(gè)或多個(gè)MBR,即一個(gè)特定的對(duì)象可能包含于多個(gè)結(jié)點(diǎn)之中.R+樹解決了R樹點(diǎn)查詢中的多路徑搜索問題,但同時(shí)也帶來(lái)了其它問題,如冗余存儲(chǔ)增加了樹的高度,降低了域查詢的性能;在構(gòu)造R+樹的過程中,結(jié)點(diǎn)MBR的增大會(huì)引起向上和向下的分裂,導(dǎo)致一系列復(fù)雜的連鎖更新操作;在不利的情況下可能會(huì)造成死鎖.1990年,Beckmann等設(shè)計(jì)了R*樹,指出區(qū)域重疊技術(shù)并不意味著更壞的平均檢索性能,而插入過程才是提高檢索性能的關(guān)鍵階段;并且通過大量對(duì)不同分布數(shù)據(jù)的實(shí)驗(yàn)研究,找到了一系列相互影響的決定檢索性能的參數(shù),提出了一系列結(jié)點(diǎn)分裂優(yōu)化準(zhǔn)則,設(shè)計(jì)了結(jié)點(diǎn)強(qiáng)制重插技術(shù).這些研究成果提高了R樹的空間利用率,減少了結(jié)點(diǎn)分裂次數(shù),使得目錄矩形(某一路徑所有矩形的最小邊界矩形)更近似于正方形,從而極大地改善了樹結(jié)構(gòu),顯著提高了樹的查詢性能,但同時(shí)也增加了CPU計(jì)算代價(jià).1994年,Kamel和Faloutsos提出了HilbertR樹,以提高結(jié)點(diǎn)存儲(chǔ)利用率,優(yōu)化R樹結(jié)構(gòu).其主要思想是利用Hilbert分形曲線對(duì)k維空間數(shù)據(jù)進(jìn)行一維線性排序,進(jìn)而對(duì)樹結(jié)點(diǎn)進(jìn)行排序,借以獲得面積、周長(zhǎng)最小化的樹結(jié)點(diǎn).此外,對(duì)于通過排序后得到的組織良好的兄弟結(jié)點(diǎn)集,實(shí)施類似于B*樹的滯后分裂算法,從而獲得較高的結(jié)點(diǎn)存儲(chǔ)利用率.2001年,Huang等提出了CompactR樹.由于其特殊的分裂算法,該變體可以達(dá)到幾乎100%的存儲(chǔ)利用率,并導(dǎo)致結(jié)點(diǎn)分裂的次數(shù)明顯減少,構(gòu)建開銷低于R樹,易于實(shí)現(xiàn)和維護(hù).但其檢索性能僅與R樹相仿,不及R+樹、R*樹等變體優(yōu)良.2002年,Brakatsoulas等通過深入研究R樹構(gòu)建原理,提出了cR樹,認(rèn)為動(dòng)態(tài)R樹的創(chuàng)建本質(zhì)上是一個(gè)典型的聚類問題,可以利用現(xiàn)有的成熟聚類算法來(lái)解決.他們采用通用的“k-means”聚類算法,把傳統(tǒng)的兩路分裂改進(jìn)為由聚類技術(shù)支持的多路分裂.cR樹插入代價(jià)與R樹相仿,而查詢性能與R*樹相近,更適合于數(shù)據(jù)密集型環(huán)境且實(shí)現(xiàn)算法簡(jiǎn)單,不需要強(qiáng)制重插等復(fù)雜技術(shù),易于維護(hù).有關(guān)R樹的數(shù)據(jù)結(jié)構(gòu)和分裂算法方面的改進(jìn)和變體還有還多,如在空間對(duì)象的近似表達(dá)方面,有利用最小邊界球的球樹(Spheretrees),最小邊界凸多邊形的CP樹,最小邊界多邊形的Cell樹、P樹;在結(jié)點(diǎn)分裂方面,文獻(xiàn)提出了不同的分裂算法;DR樹是適合主存索引的變體;而位圖R樹借鑒了位圖索引的思想;其它的R樹變體在文獻(xiàn)中有詳細(xì)介紹.3基于o方法的r樹批量操作技術(shù)傳統(tǒng)的R樹的構(gòu)建是從空樹開始,利用傳統(tǒng)的插入算法逐個(gè)插入記錄,直至生成整個(gè)R樹,稱為OBO方法(one-by-one).由于要?jiǎng)討B(tài)維護(hù)空間索引結(jié)構(gòu),該方法的插入代價(jià)非常高,特別對(duì)于海量空間數(shù)據(jù)而言,索引的創(chuàng)建過程將耗時(shí)巨大.因此,面向應(yīng)用需求,專家學(xué)者開始尋求高效的R樹批量操作技術(shù),在維持和提高查詢性能的前提下,盡可能提高R樹的靜態(tài)加載和動(dòng)態(tài)更新速度.3.1靜態(tài)結(jié)構(gòu)的預(yù)處理R樹批量加載技術(shù)又稱壓縮技術(shù).在數(shù)據(jù)為已知且相對(duì)靜態(tài)的情況下,對(duì)已知數(shù)據(jù)進(jìn)行有效的預(yù)處理,提高數(shù)據(jù)加載速度,建立結(jié)構(gòu)優(yōu)化的R樹,改善空間存儲(chǔ)利用率,從而獲得優(yōu)良的檢索性能,是壓縮技術(shù)的初衷.3.1.1各節(jié)點(diǎn)點(diǎn)的點(diǎn)旨?xì)w算法第一個(gè)基于R樹的壓縮算法由Roussopoulos等在1985年提出,用以建立能夠達(dá)到100%空間利用率的壓縮R樹.其基本思想是根據(jù)空間對(duì)象的最小邊界矩形的一個(gè)角點(diǎn)的x坐標(biāo)或y坐標(biāo)對(duì)空間對(duì)象進(jìn)行排序,然后用這些有序的空間對(duì)象逐個(gè)壓滿樹的葉結(jié)點(diǎn),自下而上,一次一層,遞歸生成最終的壓縮R樹.由算法可知,在壓縮R樹中的每一層中,除了最后一個(gè)結(jié)點(diǎn)可能不滿外,其它所有結(jié)點(diǎn)都是滿的,因此,可以獲得幾乎100%的空間利用率.但是,該算法僅在點(diǎn)數(shù)據(jù)的點(diǎn)查詢方面優(yōu)于線性分裂或平方分裂的R樹和R*樹,而對(duì)于域查詢和空間擴(kuò)展數(shù)據(jù)(如矩形等)性能較差.3.1.2ert2d-c算法設(shè)計(jì)Kamel和Faloutsos在1993年提出了一種基于分形曲線構(gòu)建靜態(tài)R樹的壓縮算法,更確切地講,是利用分形Hilbert曲線對(duì)已知空間數(shù)據(jù)對(duì)象進(jìn)行更好的一維排序,以獲得優(yōu)良的壓縮效果.他們?cè)O(shè)計(jì)了不同的變體進(jìn)行了大量的實(shí)驗(yàn),最終“2D-C”(利用空間對(duì)象MBR中心點(diǎn)的Hilbert碼進(jìn)行排序)變體性能最優(yōu).該變體在查詢性能上不僅優(yōu)于Roussopoulos等的packedR樹,而且優(yōu)于當(dāng)時(shí)R樹的所有動(dòng)態(tài)版本,如R+樹、R*樹等,且特別適合實(shí)際的、不規(guī)則分布的數(shù)據(jù).3.1.3基于種子樹的空間索引結(jié)構(gòu)的技術(shù)與基于排序的批量加載方法不同,Bercken在1997年提出的批量加載方法是一種基于緩沖的技術(shù),也可以認(rèn)為是基于種子樹方法的推廣,它并不局限于R樹,而是適用于所有基于樹的空間索引結(jié)構(gòu).該方法借鑒了buffer樹的思想,通過Lazybuffer技術(shù),利用一個(gè)有效的臨時(shí)數(shù)據(jù)結(jié)構(gòu),一次一層地建立整個(gè)索引結(jié)構(gòu),避免了數(shù)據(jù)排序預(yù)處理過程.Bercken通過性能分析得出該算法的R樹插入代價(jià)達(dá)到了外排序的下界,但是并沒有進(jìn)行實(shí)驗(yàn)證明和性能比較.3.1.4切線片面內(nèi)最大可達(dá)性1997年,Leutenegger等提出了一種STR(Sort-Tile-Recursive)壓縮算法,可稱為遞歸網(wǎng)格排序算法.該算法易于實(shí)現(xiàn),比前幾種壓縮算法的數(shù)據(jù)適用范圍更廣,且可以適應(yīng)不同的緩沖區(qū)大小.其基本思想如下:假設(shè)在2維空間中有N個(gè)矩形,M是R樹結(jié)點(diǎn)的最大容量,用矩形中心點(diǎn)的x坐標(biāo)對(duì)數(shù)據(jù)矩形排序,用S=√Ν/ΜS=N/M?????√個(gè)垂直切片切割數(shù)據(jù)空間,使得每個(gè)切片包含S個(gè)結(jié)點(diǎn)和S·M個(gè)矩形(最后一個(gè)切片會(huì)少于S·M個(gè)矩形);然后在每一個(gè)垂直切片中,用矩形中心點(diǎn)的y坐標(biāo)對(duì)數(shù)據(jù)矩形排序,每M個(gè)矩形一組依次壓入結(jié)點(diǎn).自下而上,一次一層,遞歸生成整個(gè)R樹.該算法可以很容易地推廣到高維空間.Leutenegger等的實(shí)驗(yàn)結(jié)果表明:沒有一種最優(yōu)算法適合于所有的數(shù)據(jù)類型.總體來(lái)講,與以前提出的最好的算法(HilbertpackedR樹)相比,對(duì)于均勻分布的數(shù)據(jù)或者中等程度畸變的點(diǎn)數(shù)據(jù)和區(qū)域數(shù)據(jù),該算法在點(diǎn)查詢和區(qū)域查詢上會(huì)減少50%的磁盤獲取,然而對(duì)于高度畸變的點(diǎn)數(shù)據(jù)和區(qū)域數(shù)據(jù)性能大致相同.Leutenegger等的另一貢獻(xiàn)是在STR實(shí)現(xiàn)中加入了LRU(最近最少使用算法)緩沖管理,并提出一個(gè)分析模型來(lái)預(yù)測(cè)緩沖管理下的磁盤存取次數(shù),用以評(píng)價(jià)壓縮算法的質(zhì)量.3.1.5tgs的所有數(shù)據(jù)垂直分割1998年,Garcia等提出了TGS(Top-downGreedy-Split)算法,稱為自上而下地貪婪分裂算法,其特點(diǎn)為自上而下地遞歸構(gòu)建R樹.TGS遞歸應(yīng)用如下基本分裂過程:對(duì)于數(shù)據(jù)空間中的N個(gè)矩形,TGS沿著某一坐標(biāo)軸把所有數(shù)據(jù)垂直分割為兩個(gè)子集.該分割要求滿足以下兩個(gè)條件:(1)使得用戶自定義代價(jià)函數(shù)f(r1,r2)的值最小,其中r1,r2分別是兩個(gè)子集的MBR;(2)每個(gè)子集有i·S個(gè)矩形,其中S是該層每個(gè)子樹的最大矩形個(gè)數(shù),i小于該層結(jié)點(diǎn)的個(gè)數(shù).該過程遞歸應(yīng)用于兩個(gè)子集,直至生成整個(gè)R樹.作者實(shí)驗(yàn)結(jié)果表明,TGS算法的檢索性能要優(yōu)于前述的STR和Hilbert算法,且特別適合于區(qū)域數(shù)據(jù)和不規(guī)則分布的數(shù)據(jù)集.但是由于其自適應(yīng)預(yù)處理過程需要多次對(duì)數(shù)據(jù)對(duì)象進(jìn)行重新組織,導(dǎo)致數(shù)據(jù)加載時(shí)間遠(yuǎn)大于其它方法.3.1.6動(dòng)態(tài)批量加載Arge等提出了不同于Bercken的buffer技術(shù).兩者的共同之處在于都借鑒了buffer樹的思想和Lazybuffer技術(shù),都充分利用了操作系統(tǒng)的可用主存和頁(yè)面大小.不同的是,Arge等的方法不僅可以進(jìn)行靜態(tài)批量加載,而且可以進(jìn)行動(dòng)態(tài)批量更新,是一種在線處理的有效方法.另外,與所有其它的批量操作方法相比,它能夠支持并發(fā)的批量操作.但是,在數(shù)據(jù)批量加載方面,該文僅僅進(jìn)行了理論分析,并沒有進(jìn)行實(shí)驗(yàn)性能比較.3.1.7omt的計(jì)算OMT(OverlapMinimizingTop-downBulkLoading)批量加載技術(shù)可以看作STR方法的一個(gè)倒裝,與STR不同的是,OMT首先通過簡(jiǎn)單的計(jì)算獲得目標(biāo)R樹的拓?fù)潢P(guān)系;然后自上而下地分割空間,聚簇?cái)?shù)據(jù),創(chuàng)建整個(gè)R樹.其主要思想是盡可能減少上層結(jié)點(diǎn)間的重疊區(qū)域,從而減少查詢遍歷路徑,提高查詢性能.但是,該文沒有提供針對(duì)OMT的理論分析和實(shí)驗(yàn)性能比較.直觀看來(lái),該技術(shù)構(gòu)建R樹的代價(jià)相當(dāng)大,而且由于沒有提出解決上層結(jié)點(diǎn)間重疊區(qū)域問題的更為有效的方法,與STR算法相比,查詢性能的提高也值得懷疑.3.2動(dòng)態(tài)批量插入技術(shù)對(duì)于動(dòng)態(tài)R樹來(lái)講,利用OBO生成的R樹結(jié)構(gòu)應(yīng)該是最好的,檢索性能也應(yīng)該是最高的,因?yàn)樗赗樹構(gòu)建過程中利用結(jié)點(diǎn)分裂算法實(shí)現(xiàn)了樹結(jié)構(gòu)的局部重組.因此,動(dòng)態(tài)批量插入要解決的問題是如何把新數(shù)據(jù)集批量插入到現(xiàn)有的空間索引結(jié)構(gòu)中,目的在于提高插入效率,而不是提高查詢性能.R樹動(dòng)態(tài)批量插入技術(shù)的研究起步較晚.3.2.1si和sn算法下的葉控制和加載算法1996年,Kamel等基于新數(shù)據(jù)通?？偸且詳?shù)據(jù)集的形式出現(xiàn)的事實(shí),首次提出了動(dòng)態(tài)R樹的批量加載問題.作者設(shè)計(jì)了SI(排序插入)和SN(排序結(jié)點(diǎn)插入)兩種插入算法,SI首先利用空間對(duì)象MBR中心點(diǎn)的Hilbert碼對(duì)新數(shù)據(jù)集進(jìn)行一維排序,然后借助于結(jié)點(diǎn)緩沖區(qū)的幫助,依次把數(shù)據(jù)對(duì)象逐個(gè)插入到現(xiàn)有的R樹中.而SN首先利用空間對(duì)象MBR中心點(diǎn)的Hilbert碼對(duì)新數(shù)據(jù)集進(jìn)行一維排序,然后將其依次分組構(gòu)建成為新的70%滿的葉結(jié)點(diǎn),最后把構(gòu)建好的葉結(jié)點(diǎn)逐個(gè)插入到現(xiàn)有R樹中的葉子層.實(shí)驗(yàn)結(jié)果表明,SI和SN算法在維持R樹索引查詢性能基本不變的情況下,極大地減小了插入代價(jià),其中以SN更為顯著.然而,SN更適合大數(shù)據(jù)集的批量加載,因?yàn)閷?duì)于新的小數(shù)據(jù)集,經(jīng)過多次的插入之后,R樹的查詢性能將顯著下降.因此,SI和SN方法應(yīng)該根據(jù)新數(shù)據(jù)集的大小交替使用.3.2.2stlt技術(shù)1998年,Chen等針對(duì)新的不規(guī)則分布的數(shù)據(jù)集的動(dòng)態(tài)插入問題進(jìn)行了研究,提出了STLT(Small-Tree-Large-Tree)技術(shù),后來(lái)將應(yīng)用該技術(shù)的R樹稱為歸并R樹(MergingR-tree).STLT首先把新數(shù)據(jù)集獨(dú)立構(gòu)建為一顆小R樹,然后在原有的大R樹中為其定位,最后把小R樹插入到大R樹中.實(shí)驗(yàn)結(jié)果表明,STLT技術(shù)特別適合于不規(guī)則分布數(shù)據(jù)和大R樹與小R樹數(shù)據(jù)量比率較大的情況,此時(shí)的插入代價(jià)遠(yuǎn)小于OBO的傳統(tǒng)插入技術(shù),且查詢性能也在多數(shù)情況下優(yōu)于用OBO技術(shù)形成的R樹.但STLT存在數(shù)據(jù)分布的局限.3.2.3基于聚類分析的新數(shù)據(jù)集STLT的作者為了擺脫僅適合不規(guī)則分布數(shù)據(jù)集的局限性,對(duì)該技術(shù)進(jìn)行了改進(jìn),提出一種通用動(dòng)態(tài)R樹批量插入策略——GBI(GeneralizedBulk-Insertion),使其能適合任意分布的數(shù)據(jù)集.GBI首先利用聚類算法將新數(shù)據(jù)集分割為一系列的組群和離群值,然后為每一個(gè)組群構(gòu)建一顆小R樹,并為其在原有大R樹中定位插入位置;最后批量插入所有的小R樹和離群值.實(shí)驗(yàn)結(jié)果表明,GBI適合各種分布的數(shù)據(jù)集,尤其是隨機(jī)分布數(shù)據(jù)和包含少數(shù)自然組群的實(shí)際數(shù)據(jù)集,其插入代價(jià)要比已有批量插入技術(shù)低200%,且性能優(yōu)良.3.2.4動(dòng)態(tài)批量插入、刪除/查詢?cè)揜樹變體已在靜態(tài)批量插入部分做過介紹.該變體不僅適合做靜態(tài)批量加載,還可以進(jìn)行動(dòng)態(tài)批量插入、刪除和查詢,而且支持并發(fā).但是,從概念上來(lái)講,其動(dòng)態(tài)批量插入算法等同于重復(fù)插入算法;而且在批量更新方面,作者僅僅與SN方法進(jìn)行了性能比較,認(rèn)為該R樹變體具有更快的更新時(shí)間和更好的查詢性能.3.2.5scb和傳統(tǒng)obo研究的比較2003年,Lee等充分考慮了已有的目標(biāo)R樹結(jié)構(gòu)對(duì)于待輸入數(shù)據(jù)集的空間聚簇分類的影響,提出了一種SCB(BulkInsertionbySeededClustering)方法.SCB利用種子聚簇(SeededClustering)技術(shù),減少目標(biāo)R樹和輸入R樹之間的結(jié)點(diǎn)重疊面積,優(yōu)化樹結(jié)構(gòu),提高查詢性能.該方法首先通過復(fù)制目標(biāo)R樹的最上面的k層索引結(jié)構(gòu)以構(gòu)建種子樹(seedtree),然后利用種子樹來(lái)指導(dǎo)輸入數(shù)據(jù)集的聚簇分類,再為每一個(gè)組群構(gòu)建相應(yīng)的小R樹,最后批量插入所有的新構(gòu)建的小R樹和離群值.另外,作者還提出了一種再壓縮(repacking)技術(shù),該技術(shù)在插入過程中用來(lái)最小化目標(biāo)R樹和輸入R樹的重疊面積.實(shí)驗(yàn)結(jié)果表明,SCB方法在插入和查詢代價(jià)上都優(yōu)于傳統(tǒng)的OBO方法和GBI方法,而且其查詢性能不會(huì)隨著不斷的數(shù)據(jù)插入而惡化.SCB是唯一一種在查詢性能上優(yōu)于傳統(tǒng)OBO方法的技術(shù),之前的STLT方法雖也聲稱如此,但它僅針對(duì)不規(guī)則分布的數(shù)據(jù)集.4基于r樹的空間查詢算法由于空間對(duì)象和空間操作的復(fù)雜性,使得空間數(shù)據(jù)庫(kù)中的空間操作既是I/O密集型又是CPU密集型的.因此,充分利用空間索引有效地進(jìn)行空間檢索,是空間數(shù)據(jù)庫(kù)的一項(xiàng)關(guān)鍵技術(shù).空間索引R樹流行的一個(gè)重要原因就是能夠有效支持多種空間操作.近年來(lái),許多專家學(xué)者針對(duì)基于R樹的空間查詢算法進(jìn)行了大量的研究.空間查詢主要包括精確匹配查詢、點(diǎn)查詢、窗口查詢、域查詢、拓?fù)洳樵?、方位查詢、最近鄰查詢和空間連接等.空間查詢處理通常采用如圖3所示的兩步查詢處理過程.基于R樹的空間查詢算法基本集中在過濾步驟.由于點(diǎn)可以看作退化的矩形,而窗口查詢也可以看作域查詢的一個(gè)特例,因此點(diǎn)查詢和窗口查詢都可以歸入域查詢.基于R樹的域查詢算法在文獻(xiàn)中有詳細(xì)論述,且少有改進(jìn),僅在文獻(xiàn)中提出了同時(shí)處理多個(gè)域查詢以提高性能的方法;拓?fù)洳樵兒头轿徊樵兎謩e在文獻(xiàn)和文獻(xiàn)中有所論述;大部分基于R樹的空間查詢處理研究集中在空間連接和最近鄰查詢.4.1基于r樹的空間連接查詢算法在空間數(shù)據(jù)庫(kù)中,空間連接是非常重要的運(yùn)算符.當(dāng)兩個(gè)關(guān)系(表)R和S基于一個(gè)空間謂詞θ進(jìn)行連接時(shí),稱該連接為空間連接.空間連接主要用來(lái)根據(jù)空間屬性合并兩個(gè)或多個(gè)數(shù)據(jù)集的空間對(duì)象.GIS中的重要的運(yùn)算符‘地圖疊加’(mapoverlay)是空間連接的一個(gè)變體.空間謂詞θ主要有intersect(相交)、contains(包含)、is_enclosed_by(被包圍)、distance(距離)、adjacent(鄰接)、meets(接觸)、overlap(交疊)等.空間連接查詢與域查詢和最近鄰查詢等單向掃描查詢不同,它是雙向掃描(兩路空間連接)或多向掃描(多路空間連接)的.基于R樹的空間連接算法研究通常都假設(shè)參與連接的關(guān)系(表)事先已建立R樹索引,且往往針對(duì)兩步空間查詢處理中的過濾步驟.4.1.1限制搜索空間的算法1993年,Brinkhoff等提出了基于R樹的空間連接算法.該算法是一種深度優(yōu)先遍歷過程,其出發(fā)點(diǎn)是非葉結(jié)點(diǎn)的矩形能夠容納所有子結(jié)點(diǎn)中矩形的MBR.因此,若兩個(gè)目錄矩形不相交,則其子樹中所有數(shù)據(jù)矩形必然也不相交;如果目錄矩形相交,則其子樹中某些數(shù)據(jù)矩形有可能相交.為了減少CPU計(jì)算代價(jià),作者提出了限制搜索空間及其空間排序和平面搜索的優(yōu)化措施;為了減少I/O代價(jià),作者提出了基于空間臨近性的局部?jī)?yōu)化策略,包括鎖定局部平面搜索排序和局部Z排序,用以控制結(jié)點(diǎn)讀入內(nèi)存緩沖區(qū)的次序.1995年,Martynov對(duì)該算法進(jìn)行了改進(jìn),用基于網(wǎng)格的啟發(fā)式優(yōu)化代替平面搜索,提高了空間連接的執(zhí)行效率.4.1.2深度優(yōu)先遍歷算法針對(duì)深度優(yōu)先遍歷算法只能進(jìn)行局部?jī)?yōu)化的缺陷,Huang等在1997年提出了一種基于全局優(yōu)化的廣度優(yōu)先遍歷算法.該方法以廣度優(yōu)先的方式同時(shí)遍歷兩棵R樹,同時(shí)逐層處理連接計(jì)算.在每一層,創(chuàng)建中間連接索引并實(shí)施全局優(yōu)化策略,如排序、內(nèi)存管理和緩沖區(qū)管理等,用以提高下一層的空間連接計(jì)算性能.該算法與深度優(yōu)先遍歷算法的實(shí)驗(yàn)比較表明,在正確選擇全局優(yōu)化選項(xiàng)的前提下,該算法性能提高了50%.基于R樹的空間連接仍是一個(gè)活躍的研究領(lǐng)域,其它研究成果包括多路空間連接、增量距離連接和半連接以及最近鄰對(duì)查詢等.4.2悲觀主義定義基于R樹的最近鄰查詢算法最早由Roussopoulos等于1995年提出.作者使用分枝界定的R樹遍歷算法,提出了兩個(gè)度量標(biāo)準(zhǔn)用于R樹的排序和剪枝,一個(gè)是MINDIST,稱為樂觀距離;另一個(gè)是MINMAXDIST,稱為悲觀距離;分別作為查詢點(diǎn)到樹結(jié)點(diǎn)MBR中最近鄰對(duì)象的距離下界和上界.基于這兩個(gè)度量標(biāo)準(zhǔn),作者提出了三個(gè)啟發(fā)式規(guī)則來(lái)過濾不包含最近鄰居的結(jié)點(diǎn),從而減少結(jié)點(diǎn)訪問個(gè)數(shù),減少磁盤I/O,進(jìn)而有效地提高查詢性能.1998年,Cheung等進(jìn)一步改進(jìn)該算法,移除前兩個(gè)既不能增強(qiáng)剪枝效果又具有高計(jì)算復(fù)雜度的剪枝規(guī)則,減少了CPU計(jì)算代價(jià).其它基于R樹的最近鄰算法有增量最近鄰查詢(INN)、逆最近鄰查詢、條件最近鄰查詢等.5基于r樹的域查詢代價(jià)模型如前所述,R樹變體眾多,因此如何評(píng)價(jià)或預(yù)測(cè)它們的性能就顯得至關(guān)重要.除了通過實(shí)驗(yàn)來(lái)比較R樹及其變體的性能之外,還需要從理論上研究其代價(jià)模型,包括插入、刪除和查詢代價(jià)模型.代價(jià)模型的重要性體現(xiàn)在:(1)能夠更好地理解在不同類型和大小的輸入數(shù)據(jù)集下的空間索引行為;(2)能夠?qū)Ω鞣N空間索引的性能進(jìn)行客觀比較;(3)在空間數(shù)據(jù)庫(kù)中,基于代價(jià)的查詢優(yōu)化需要利用代價(jià)模型來(lái)評(píng)估復(fù)雜空間查詢的代價(jià),以選擇最優(yōu)查詢計(jì)劃.鑒于空間查詢的重要性和通用性,且空間索引的性能通常通過域查詢的能力來(lái)反映,因此關(guān)于R樹及其變體的代價(jià)模型的研究大部分集中在域查詢方面.Faloutsos等最先嘗試分析R樹域查詢性能.他們提出的模型假設(shè)數(shù)據(jù)是一致分布的,并且樹的每個(gè)結(jié)點(diǎn)都被填滿(packed樹).雖然該模型有其局限性,但是以后幾乎所有的代價(jià)模型都是以此為基礎(chǔ)發(fā)展起來(lái)的.式(1)是最著名的計(jì)算R樹高度的公式:h=logfΝC(1)h=logfNC(1)其中,N是數(shù)據(jù)記錄總數(shù),C是葉節(jié)點(diǎn)容量,f(fanout)是結(jié)點(diǎn)平均容量.1993年,Kamel和Pagel分別獨(dú)立地對(duì)式(1)進(jìn)行了擴(kuò)展,提出了式(2).假設(shè)n維空間中有一n維的R樹,該R樹有k個(gè)結(jié)點(diǎn),結(jié)點(diǎn)sj的邊(sj1,sj2,…,sjn)為已知,則對(duì)于任一查詢窗口q=(q1,q2,…,qn),可以得到查詢的平均磁盤訪問次數(shù)DA(q).DA(q)=k∑j=1{n∏i=1(sj,i+qi)}(2)該模型的貢獻(xiàn)之一是揭示了除面積之外R樹結(jié)點(diǎn)周長(zhǎng)最小化的重要性,有助于更好地理解R*樹.但該模型要求R樹必須預(yù)先建立,且假設(shè)數(shù)據(jù)和查詢窗口是均勻分布.1995年,Faloutsos和Kamel對(duì)文獻(xiàn)進(jìn)行了擴(kuò)展,利用點(diǎn)數(shù)據(jù)集的分形維屬性d,使代價(jià)模型能夠預(yù)測(cè)磁盤訪問次數(shù).該模型是第一個(gè)能夠處理非均勻分布數(shù)據(jù)的代價(jià)模型,但僅針對(duì)點(diǎn)數(shù)據(jù)集.同樣,Bleussi和Faloutsos也利用分形維作出了選擇性評(píng)估.幾乎同時(shí),Pagel等也對(duì)文獻(xiàn)進(jìn)行了擴(kuò)展,作者提出了一個(gè)優(yōu)化算法用來(lái)計(jì)算靜態(tài)R樹性能的下界,從而能夠在不同空間索引結(jié)構(gòu)之間進(jìn)行絕對(duì)性能比較.利用該算法,作者計(jì)算出當(dāng)時(shí)最好的靜態(tài)R樹和動(dòng)態(tài)R樹分別是HilbertpackedR樹和R*樹.一年之后,作者又對(duì)結(jié)點(diǎn)矩形的面積、周長(zhǎng)和數(shù)量三要素進(jìn)行了進(jìn)一步研究,推導(dǎo)出了各種域查詢的查詢代價(jià)模型,并且得出一個(gè)重要結(jié)論:窗口查詢性能在一般情況下可以代表其它各種域查詢的性能.1996年,Theodoridis和Sellis提出了一個(gè)新的代價(jià)模型,該模型僅利用了數(shù)據(jù)集本身的特性,即數(shù)據(jù)的個(gè)數(shù)和數(shù)據(jù)密度,因此,該模型可以在R樹創(chuàng)建之前就可以評(píng)估其查詢性能.根據(jù)實(shí)驗(yàn)結(jié)果,對(duì)于均勻分布和非均勻分布的數(shù)據(jù)集,該模型的相對(duì)誤差在10%～15%之間.2000年,Jin等采用與文獻(xiàn)類似的數(shù)據(jù)密度的思想,提出了自己的選擇性評(píng)估和查詢代價(jià)模型.不同之處在于,Jin等維護(hù)的是一個(gè)作為輔助數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)密度文件,基于數(shù)據(jù)密度文件來(lái)實(shí)施累積密度方案.根據(jù)作者的實(shí)驗(yàn)結(jié)果,該模型的選擇性評(píng)估和域查詢代價(jià)評(píng)估的相對(duì)誤差不超過5%.有別于數(shù)據(jù)密度的思想,1999年,Proietti等研究了R樹結(jié)點(diǎn)中MBR的分布,發(fā)現(xiàn)它們遵循所依賴數(shù)據(jù)的分布.因此,作者利用MBR的分布,得出了不同以往的域查詢代價(jià)模型,實(shí)驗(yàn)結(jié)果表明其域查詢I/O次數(shù)的最大平均相對(duì)誤差小于30%.至此,所有上述代價(jià)模型都是以結(jié)點(diǎn)訪問次數(shù)作為查詢性能的基準(zhǔn),都忽略了緩沖區(qū)對(duì)于查詢代價(jià)評(píng)估的影響.直至2000年,Leutenegger等才將基于LRU算法的緩沖區(qū)尺寸引入到R樹查詢代價(jià)模型中.通過研究三種著名的R樹變體的加載性能,作者得出一個(gè)重要結(jié)論:如果忽略緩沖區(qū)的影響,只把節(jié)點(diǎn)訪問次數(shù)作為性能評(píng)價(jià)基準(zhǔn),將會(huì)得出錯(cuò)誤的結(jié)果.因此,在R樹的性能研究中,應(yīng)該把基于緩沖區(qū)的磁盤訪問次數(shù)作為主要衡量基準(zhǔn).綜上所述,基于R樹的域查詢代價(jià)模型研究已經(jīng)相當(dāng)深入,而最近鄰查詢和空間連接的代價(jià)模型和選擇性評(píng)估也取得了一定的發(fā)展;由于大多數(shù)的代價(jià)模型和選擇性評(píng)估采用的是參數(shù)化技術(shù),即事先對(duì)數(shù)據(jù)集的特性進(jìn)行假設(shè),如假設(shè)數(shù)據(jù)集遵循均勻分布等,然后用近似公式對(duì)其進(jìn)行評(píng)估,因此受到較大的限制.目前,部分學(xué)者提出利用采樣技術(shù)和直方圖技術(shù),從給定的數(shù)據(jù)集中提取充分的信息對(duì)數(shù)據(jù)集進(jìn)行選擇性評(píng)估的方法.該方法限制性小、更有針對(duì)性且更為精確,一經(jīng)提出就得到了廣泛的關(guān)注.6基于r樹的并行和并行控制6.1多系統(tǒng)并行查詢技術(shù)并行是數(shù)據(jù)庫(kù)的主要發(fā)展趨勢(shì)之一,而且由于空間操作既是CPU密集型又是I/O密集型的,擴(kuò)展空間查詢語(yǔ)言又比傳統(tǒng)的SQL有更多的基本操作,使得空間數(shù)據(jù)庫(kù)系統(tǒng)在并行方面的需求與傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)有所不同.針對(duì)傳統(tǒng)串行R樹算法的并行改進(jìn)主要基于多磁盤系統(tǒng)和多處理器系統(tǒng).在多磁盤系統(tǒng)下,主要是利用I/O并行提高系統(tǒng)吞吐量,而難點(diǎn)在于如何在多個(gè)可用磁盤上合理分解R樹結(jié)構(gòu),以期在查詢處理過程中,在多個(gè)磁盤間盡可能平均分配工作量.在多處理器系統(tǒng)下,需同時(shí)利用I/O并行和CPU并行來(lái)提高系統(tǒng)性能,其難點(diǎn)在于如何更好地分解查詢以便在多個(gè)處理器之間實(shí)現(xiàn)負(fù)載平衡.早在1992年,Kamel等就針對(duì)單處理器、多磁盤的硬件結(jié)構(gòu)研究了基于R樹的并行查詢機(jī)制.作者采取多元R樹(MultiplexedR樹)軟件結(jié)構(gòu),應(yīng)用鄰近指數(shù)(proximityindex)準(zhǔn)則進(jìn)行優(yōu)化,對(duì)于均勻分布數(shù)據(jù)獲得了優(yōu)于其它方法的并行域查詢性能.隨后,專家學(xué)者們研究了多磁盤環(huán)境下的R樹最近鄰并行查詢算法、多計(jì)算機(jī)系統(tǒng)下的R樹并行算法、共享虛擬內(nèi)存結(jié)構(gòu)下的并行空間連接算法、多磁盤環(huán)境下的R樹最近鄰并行查詢算法;出現(xiàn)了GPR樹、Master-clientR樹、UpgradedParallelR樹等并行R樹變體.6.2基于動(dòng)態(tài)粒度鎖的質(zhì)控技術(shù)在多用戶環(huán)境中,并發(fā)控制技術(shù)是必不可少的.在空間數(shù)據(jù)庫(kù)環(huán)境下基于R樹的并發(fā)機(jī)制仍是一個(gè)尚待研究的領(lǐng)域.當(dāng)多個(gè)用戶同時(shí)對(duì)一個(gè)索引結(jié)構(gòu)進(jìn)行查詢、插入、刪除等操作時(shí),并發(fā)機(jī)制必須保證數(shù)據(jù)一致性和各個(gè)操作的正確性.成熟的B樹并發(fā)控制技術(shù)并不完全適用于R樹,主要原因是R樹的鍵值是多維的MBR,其上沒有線性順序,而且兄弟結(jié)點(diǎn)間的MBR可能交疊.1993年,Ng等首次對(duì)R樹的并發(fā)訪問機(jī)制進(jìn)行了研究,提出了三種不同的鎖定方法用于并發(fā)控制,分別為單一鎖、修改鎖和耦合鎖.實(shí)驗(yàn)結(jié)果表明,耦合鎖具有最好的檢索性能.但是,該方法修改了原始R樹的結(jié)構(gòu),限制了它的通用性.一個(gè)提高B樹并發(fā)度的策略是確保在給定時(shí)間內(nèi)只有一個(gè)結(jié)點(diǎn)被鎖定,該策略隨后在1994年被Ng和Kornacker等修改用于R樹,并且分別提出了R-link方法.兩者不同的是,Kornacker應(yīng)用了更為高級(jí)的邏輯序列碼技術(shù)(LogicalSequenceNumbers,LSN)來(lái)對(duì)兄弟結(jié)點(diǎn)排序.實(shí)驗(yàn)結(jié)果顯示,R-link方法比耦合鎖機(jī)制有更好的吞吐量和更快的響應(yīng)速度.1997年,Chen等提出