地图索引 R-tree
http://blog.csdn.net/v_JULY_v/article/details/6530142
984年，加州大學伯克利分校的Guttman發(fā)表了一篇題為“R-trees: a dynamic index structure for spatial searching”的論文，向世人介紹了R樹這種處理高維空間存儲問題的數(shù)據(jù)結(jié)構(gòu)。本文便是基于這篇論文寫作完成的，因此如果大家對R樹非常有興趣，我想最好還是參考一下原著：）。為表示對這位牛人的尊重，給個引用先：
Guttman, A.;?“R-trees: a dynamic index structure for spatial searching,”?ACM,?1984, 14
R樹在數(shù)據(jù)庫等領(lǐng)域做出的功績是非常顯著的。它很好的解決了在高維空間搜索等問題。舉個R樹在現(xiàn)實領(lǐng)域中能夠解決的例子：查找20英里以內(nèi)所有的餐廳。如果沒有R樹你會怎么解決？一般情況下我們會把餐廳的坐標(x,y)分為兩個字段存放在數(shù)據(jù)庫中，一個字段記錄經(jīng)度，另一個字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計算是否滿足要求。如果一個地區(qū)有100家餐廳的話，我們就要進行100次位置計算操作了，如果應(yīng)用到谷歌地圖這種超大數(shù)據(jù)庫中，這種方法便必定不可行了。
R樹就很好的解決了這種高維空間搜索問題。它把B樹的思想很好的擴展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時采用合并、分解結(jié)點的方法，保證樹的平衡性。因此，R樹就是一棵用來存儲高維數(shù)據(jù)的平衡樹。
OK，接下來，本文將詳細介紹R樹的數(shù)據(jù)結(jié)構(gòu)以及R樹的操作。至于R樹的擴展與R樹的性能問題，可以查閱相關(guān)論文。
?
R樹的數(shù)據(jù)結(jié)構(gòu)
如上所述，R樹是B樹在高維空間的擴展，是一棵平衡樹。每個R樹的葉子結(jié)點包含了多個指向不同數(shù)據(jù)的指針，這些數(shù)據(jù)可以是存放在硬盤中的，也可以是存在內(nèi)存中。根據(jù)R樹的這種數(shù)據(jù)結(jié)構(gòu)，當我們需要進行一個高維空間查詢時，我們只需要遍歷少數(shù)幾個葉子結(jié)點所包含的指針，查看這些指針指向的數(shù)據(jù)是否滿足要求即可。這種方式使我們不必遍歷所有數(shù)據(jù)即可獲得答案，效率顯著提高。下圖1是R樹的一個簡單實例：
我們在上面說過，R樹運用了空間分割的理念，這種理念是如何實現(xiàn)的呢？R樹采用了一種稱為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結(jié)點開始用矩形（rectangle）將空間框起來，結(jié)點越往上，框住的空間就越大，以此對空間進行分割。有點不懂？沒關(guān)系，繼續(xù)往下看。在這里我還想提一下，R樹中的R應(yīng)該代表的是Rectangle（此處參考wikipedia上關(guān)于R樹的介紹），而不是大多數(shù)國內(nèi)教材中所說的Region（很多書把R樹稱為區(qū)域樹，這是有誤的）。我們就拿二維空間來舉例。下圖是Guttman論文中的一幅圖：
?
我來詳細解釋一下這張圖。先來看圖（b），首先我們假設(shè)所有數(shù)據(jù)都是二維空間下的點，圖中僅僅標志了R8區(qū)域中的數(shù)據(jù)，也就是那個shape of data object。別把那一塊不規(guī)則圖形看成一個數(shù)據(jù)，我們把它看作是多個數(shù)據(jù)圍成的一個區(qū)域。為了實現(xiàn)R樹結(jié)構(gòu)，我們用一個最小邊界矩形恰好框住這個不規(guī)則區(qū)域，這樣，我們就構(gòu)造出了一個區(qū)域：R8。R8的特點很明顯，就是正正好好框住所有在此區(qū)域中的數(shù)據(jù)。其他實線包圍住的區(qū)域，如R9，R10，R12等都是同樣的道理。這樣一來，我們一共得到了12個最最基本的最小矩形。這些矩形都將被存儲在子結(jié)點中。下一步操作就是進行高一層次的處理。我們發(fā)現(xiàn)R8，R9，R10三個矩形距離最為靠近，因此就可以用一個更大的矩形R3恰好框住這3個矩形。同樣道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形。我想大家都應(yīng)該理解這個數(shù)據(jù)結(jié)構(gòu)的特征了。用地圖的例子來解釋，就是所有的數(shù)據(jù)都是餐廳所對應(yīng)的地點，先把相鄰的餐廳劃分到同一塊區(qū)域，劃分好所有餐廳之后，再把鄰近的區(qū)域劃分到更大的區(qū)域，劃分完畢后再次進行更高層次的劃分，直到劃分到只剩下兩個最大的區(qū)域為止。要查找的時候就方便了。
下面就可以把這些大大小小的矩形存入我們的R樹中去了。根結(jié)點存放的是兩個最大的矩形，這兩個最大的矩形框住了所有的剩余的矩形，當然也就框住了所有的數(shù)據(jù)。下一層的結(jié)點存放了次大的矩形，這些矩形縮小了范圍。每個葉子結(jié)點都是存放的最小的矩形，這些矩形中可能包含有n個數(shù)據(jù)。
在這里，讀者先不要去糾結(jié)于如何劃分數(shù)據(jù)到最小區(qū)域矩形，也不要糾結(jié)怎樣用更大的矩形框住小矩形，這些都是下一節(jié)我們要討論的。
講完了基本的數(shù)據(jù)結(jié)構(gòu)，我們來講個實例，如何查詢特定的數(shù)據(jù)。又以餐廳為例，假設(shè)我要查詢廣州市天河區(qū)天河城附近一公里的所有餐廳地址怎么辦？打開地圖（也就是整個R樹），先選擇國內(nèi)還是國外（也就是根結(jié)點）。然后選擇華南地區(qū)（對應(yīng)第一層結(jié)點），選擇廣州市（對應(yīng)第二層結(jié)點），再選擇天河區(qū)（對應(yīng)第三層結(jié)點），最后選擇天河城所在的那個區(qū)域（對應(yīng)葉子結(jié)點，存放有最小矩形），遍歷所有在此區(qū)域內(nèi)的結(jié)點，看是否滿足我們的要求即可。怎么樣，其實R樹的查找規(guī)則跟查地圖很像吧？對應(yīng)下圖：
一棵R樹滿足如下的性質(zhì)：
1.?????除非它是根結(jié)點之外，所有葉子結(jié)點包含有m至M個記錄索引（條目）。作為根結(jié)點的葉子結(jié)點所具有的記錄個數(shù)可以少于m。通常，m=M/2。
2.?????對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴展到高維空間的）。
3.?????每一個飛葉子結(jié)點擁有m至M個孩子結(jié)點，除非它是根結(jié)點。
4.?????對于在非葉子結(jié)點上的每一個條目，i是最小的可以在空間上完全覆蓋這些條目所代表的店的矩形（同性質(zhì)2）。
5.?????所有葉子結(jié)點都位于同一層，因此R樹為平衡樹。
?
葉子結(jié)點的結(jié)構(gòu)
先來探究一下葉子結(jié)點的結(jié)構(gòu)。葉子結(jié)點所保存的數(shù)據(jù)形式為：(I, tuple-identifier)。
??????其中，tuple-identifier表示的是一個存放于數(shù)據(jù)庫中的tuple，也就是一條記錄，它是n維的。I是一個n維空間的矩形，并可以恰好框住這個葉子結(jié)點中所有記錄代表的n維空間中的點。I=(I0,I1,…,In-1)。其結(jié)構(gòu)如下圖所示：
下圖描述的就是在二維空間中的葉子結(jié)點所要存儲的信息。
?
在這張圖中，I所代表的就是圖中的矩形，其范圍是a<=I0<=b，c<=I1<=d。有兩個tuple-identifier，在圖中即表示為那兩個點。這種形式完全可以推廣到高維空間。大家簡單想想三維空間中的樣子就可以了。這樣，葉子結(jié)點的結(jié)構(gòu)就介紹完了。
?
非葉子結(jié)點
??????非葉子結(jié)點的結(jié)構(gòu)其實與葉子結(jié)點非常類似。想象一下B樹就知道了，B樹的葉子結(jié)點存放的是真實存在的數(shù)據(jù)，而非葉子結(jié)點存放的是這些數(shù)據(jù)的“邊界”，或者說也算是一種索引（有疑問的讀者可以回顧一下上述第一節(jié)中講解B樹的部分）。
??????同樣道理，R樹的非葉子結(jié)點存放的數(shù)據(jù)結(jié)構(gòu)為：(I, child-pointer)。
??????其中，child-pointer是指向孩子結(jié)點的指針，I是覆蓋所有孩子結(jié)點對應(yīng)矩形的矩形。這邊有點拗口，但我想不是很難懂？給張圖：
?
D,E,F,G為孩子結(jié)點所對應(yīng)的矩形。A為能夠覆蓋這些矩形的更大的矩形。這個A就是這個非葉子結(jié)點所對應(yīng)的矩形。這時候你應(yīng)該悟到了吧？無論是葉子結(jié)點還是非葉子結(jié)點，它們都對應(yīng)著一個矩形。樹形結(jié)構(gòu)上層的結(jié)點所對應(yīng)的矩形能夠完全覆蓋它的孩子結(jié)點所對應(yīng)的矩形。根結(jié)點也唯一對應(yīng)一個矩形，而這個矩形是可以覆蓋所有我們擁有的數(shù)據(jù)信息在空間中代表的點的。
我個人感覺這張圖畫的不那么精確，應(yīng)該是矩形A要恰好覆蓋D,E,F,G，而不應(yīng)該再留出這么多沒用的空間了。但為尊重原圖的繪制者，特不作修改。
?
R樹的操作
這一部分也許是編程者最關(guān)注的問題了。這么高效的數(shù)據(jù)結(jié)構(gòu)該如何去實現(xiàn)呢？這便是這一節(jié)需要闡述的問題。
?
搜索
R樹的搜索操作很簡單，跟B樹上的搜索十分相似。它返回的結(jié)果是所有符合查找信息的記錄條目。而輸入是什么？就我個人的理解，輸入不僅僅是一個范圍了，它更可以看成是一個空間中的矩形。也就是說，我們輸入的是一個搜索矩形。
先給出偽代碼：
Function：Search
描述：假設(shè)T為一棵R樹的根結(jié)點，查找所有搜索矩形S覆蓋的記錄條目。
S1:[查找子樹]?如果T是非葉子結(jié)點，如果T所對應(yīng)的矩形與S有重合，那么檢查所有T中存儲的條目，對于所有這些條目，使用Search操作作用在每一個條目所指向的子樹的根結(jié)點上（即T結(jié)點的孩子結(jié)點）。
S2:[查找葉子結(jié)點]?如果T是葉子結(jié)點，如果T所對應(yīng)的矩形與S有重合，那么直接檢查S所指向的所有記錄條目。返回符合條件的記錄。
我們通過下圖來理解這個Search操作。
?
?
陰影部分所對應(yīng)的矩形為搜索矩形。它與根結(jié)點對應(yīng)的最大的矩形（未畫出）有重疊。這樣將Search操作作用在其兩個子樹上。兩個子樹對應(yīng)的矩形分別為R1與R2。搜索R1，發(fā)現(xiàn)與R1中的R4矩形有重疊，繼續(xù)搜索R4。最終在R4所包含的R11與R12兩個矩形中查找是否有符合條件的記錄。搜索R2的過程同樣如此。很顯然，該算法進行的是一個迭代操作。
?
插入
??????R樹的插入操作也同B樹的插入操作類似。當新的數(shù)據(jù)記錄需要被添加入葉子結(jié)點時，若葉子結(jié)點溢出，那么我們需要對葉子結(jié)點進行分裂操作。顯然，葉子結(jié)點的插入操作會比搜索操作要復雜。插入操作需要一些輔助方法才能夠完成。
來看一下偽代碼：
Function：Insert
描述：將新的記錄條目E插入給定的R樹中。
I1：[為新記錄找到合適插入的葉子結(jié)點]?開始ChooseLeaf方法選擇葉子結(jié)點L以放置記錄E。
I2：[添加新記錄至葉子結(jié)點]?如果L有足夠的空間來放置新的記錄條目，則向L中添加E。如果沒有足夠的空間，則進行SplitNode方法以獲得兩個結(jié)點L與LL，這兩個結(jié)點包含了所有原來葉子結(jié)點L中的條目與新條目E。
I3：[將變換向上傳遞]?開始對結(jié)點L進行AdjustTree操作，如果進行了分裂操作，那么同時需要對LL進行AdjustTree操作。
I4：[對樹進行增高操作]?如果結(jié)點分裂，且該分裂向上傳播導致了根結(jié)點的分裂，那么需要創(chuàng)建一個新的根結(jié)點，并且讓它的兩個孩子結(jié)點分別為原來那個根結(jié)點分裂后的兩個結(jié)點。
?
Function：ChooseLeaf
描述：選擇葉子結(jié)點以放置新條目E。
CL1：[Initialize]?設(shè)置N為根結(jié)點。
CL2：[葉子結(jié)點的檢查]?如果N為葉子結(jié)點，則直接返回N。
CL3：[選擇子樹]?如果N不是葉子結(jié)點，則遍歷N中的結(jié)點，找出添加E.I時擴張最小的結(jié)點，并把該結(jié)點定義為F。如果有多個這樣的結(jié)點，那么選擇面積最小的結(jié)點。
CL4：[下降至葉子結(jié)點]?將N設(shè)為F，從CL2開始重復操作。
?
Function：AdjustTree
描述：葉子結(jié)點的改變向上傳遞至根結(jié)點以改變各個矩陣。在傳遞變換的過程中可能會產(chǎn)生結(jié)點的分裂。
AT1：[初始化]?將N設(shè)為L。
AT2：[檢驗是否完成]?如果N為根結(jié)點，則停止操作。
AT3：[調(diào)整父結(jié)點條目的最小邊界矩形]?設(shè)P為N的父節(jié)點，EN為指向在父節(jié)點P中指向N的條目。調(diào)整EN.I以保證所有在N中的矩形都被恰好包圍。
AT4：[向上傳遞結(jié)點分裂]?如果N有一個剛剛被分裂產(chǎn)生的結(jié)點NN，則創(chuàng)建一個指向NN的條目ENN。如果P有空間來存放ENN，則將ENN添加到P中。如果沒有，則對P進行SplitNode操作以得到P和PP。
AT5：[升高至下一級]?如果N等于L且發(fā)生了分裂，則把NN置為PP。從AT2開始重復操作。
?
同樣，我們用圖來更加直觀的理解這個插入操作。
?
?
????我們來通過圖分析一下插入操作。現(xiàn)在我們需要插入R21這個矩形。開始時我們進行ChooseLeaf操作。在根結(jié)點中有兩個條目，分別為R1，R2。其實R1已經(jīng)完全覆蓋了R21，而若向R2中添加R21，則會使R2.I增大很多。顯然我們選擇R1插入。然后進行下一級的操作。相比于R4，向R3中添加R21會更合適，因為R3覆蓋R21所需增大的面積相對較小。這樣就在B8，B9，B10所在的葉子結(jié)點中插入R21。由于葉子結(jié)點沒有足夠空間，則要進行分裂操作。
??? 插入操作如下圖所示：
?
這個插入操作其實類似于第一節(jié)中B樹的插入操作，這里不再具體介紹，不過想必看過上面的偽代碼大家應(yīng)該也清楚了。
?
刪除
R樹的刪除操作與B樹的刪除操作會有所不同，不過同B樹一樣，會涉及到壓縮等操作。相信讀者看完以下的偽代碼之后會有所體會。R樹的刪除同樣是比較復雜的，需要用到一些輔助函數(shù)來完成整個操作。
偽代碼如下：
Function：Delete
描述：將一條記錄E從指定的R樹中刪除。
D1：[找到含有記錄的葉子結(jié)點]?使用FindLeaf方法找到包含有記錄E的葉子結(jié)點L。如果搜索失敗，則直接終止。
D2：[刪除記錄]?將E從L中刪除。
D3：[傳遞記錄]?對L使用CondenseTree操作
D4：[縮減樹]?當經(jīng)過以上調(diào)整后，如果根結(jié)點只包含有一個孩子結(jié)點，則將這個唯一的孩子結(jié)點設(shè)為根結(jié)點。
?
Function：FindLeaf
描述：根結(jié)點為T，期望找到包含有記錄E的葉子結(jié)點。
FL1：[搜索子樹]?如果T不是葉子結(jié)點，則檢查每一條T中的條目F，找出與E所對應(yīng)的矩形相重合的F（不必完全覆蓋）。對于所有滿足條件的F，對其指向的孩子結(jié)點進行FindLeaf操作，直到尋找到E或者所有條目均以被檢查過。
FL2：[搜索葉子結(jié)點以找到記錄]?如果T是葉子結(jié)點，那么檢查每一個條目是否有E存在，如果有則返回T。
?
Function：CondenseTree
描述：L為包含有被刪除條目的葉子結(jié)點。如果L的條目數(shù)過少（小于要求的最小值m），則必須將該葉子結(jié)點L從樹中刪除。經(jīng)過這一刪除操作，L中的剩余條目必須重新插入樹中。此操作將一直重復直至到達根結(jié)點。同樣，調(diào)整在此修改樹的過程所經(jīng)過的路徑上的所有結(jié)點對應(yīng)的矩形大小。
CT1：[初始化]?令N為L。初始化一個用于存儲被刪除結(jié)點包含的條目的鏈表Q。
CT2：[找到父條目]?如果N為根結(jié)點，那么直接跳轉(zhuǎn)至CT6。否則令P為N?的父結(jié)點，令EN為P結(jié)點中存儲的指向N的條目。
CT3：[刪除下溢結(jié)點]?如果N含有條目數(shù)少于m，則從P中刪除EN，并把結(jié)點N中的條目添加入鏈表Q中。
CT4：[調(diào)整覆蓋矩形]?如果N沒有被刪除，則調(diào)整EN.I使得其對應(yīng)矩形能夠恰好覆蓋N中的所有條目所對應(yīng)的矩形。
CT5：[向上一層結(jié)點進行操作]?令N等于P，從CT2開始重復操作。
CT6：[重新插入孤立的條目]?所有在Q中的結(jié)點中的條目需要被重新插入。原來屬于葉子結(jié)點的條目可以使用Insert操作進行重新插入，而那些屬于非葉子結(jié)點的條目必須插入刪除之前所在層的結(jié)點，以確保它們所指向的子樹還處于相同的層。
?
??????R樹刪除記錄過程中的CondenseTree操作是不同于B樹的。我們知道，B樹刪除過程中，如果出現(xiàn)結(jié)點的記錄數(shù)少于半滿（即下溢）的情況，則直接把這些記錄與其他葉子的記錄“融合”，也就是說兩個相鄰結(jié)點合并。然而R樹卻是直接重新插入。
?
同樣，我們用圖直觀的說明這個操作。
?
假設(shè)結(jié)點最大條目數(shù)為4，最小條目數(shù)為2。在這張圖中，我們的目標是刪除記錄c。首先使用FindLeaf操作找到c所處在的葉子結(jié)點的位置——R11。當c從R11刪除時，R11就只有一條記錄了，少于最小條目數(shù)2，出現(xiàn)下溢，此時要調(diào)用CondenseTree操作。這樣，c被刪除，R11剩余的條目——指向記錄d的指針——被插入鏈表Q。然后向更高一層的結(jié)點進行此操作。這樣R12會被插入鏈表中。原理是一樣的，在這里就不再贅述。
有一點需要解釋的是，我們發(fā)現(xiàn)這個刪除操作向上傳遞之后，根結(jié)點的條目R1也被插入了Q中，這樣根結(jié)點只剩下了R2。別著急，重新插入操作會有效的解決這個問題。我們插入R3，R12，d至它原來所處的層。這樣，我們發(fā)現(xiàn)根結(jié)點只有一個條目了，此時根據(jù)Inert中的操作，我們把這個根結(jié)點刪除，它的孩子結(jié)點，即R5，R6，R7，R3所在的結(jié)點被置為根結(jié)點。至此，刪除操作結(jié)束。
總結(jié)
以上是生活随笔為你收集整理的地图索引 R-tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 给定key值，在Binary Searc
- 下一篇： 土地积水