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

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

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