第3章多維索引

1、第二部分 數(shù)據(jù)存儲管理第3章 多維索引 關系 account(branch-name, loan-number, balance)，在branch-name和balance屬性上分別都有索引。 考慮針對該關系的一個多維查詢： SELECT loan-number FROM account WHERE branch-name=Perryridge and balance=1000 有三種策略可處理這個查詢： 用基于branch-name的索引來找出所有branch-name=Perryridge的記錄。然后，再檢查這些記錄，進一步挑選出balance=1000的記錄。 用基于balance的索引

2、來找出所有balance=1000的記錄。然后，再檢查這些記錄，進一步挑選出branch-name=Perryridge的記錄。 先根據(jù)兩個索引，分別找出滿足branch-name=Perryridge和balance=1000的記錄指針，然后，在內(nèi)存中求這兩組指針交集，再通過屬于交集中的指針找出所有目標記錄。利用位圖索引可以加快這種方法的交集操作。3.1 需要多維索引的應用簡介 3.1.1 數(shù)據(jù)倉庫的數(shù)據(jù)立方體 在數(shù)據(jù)倉庫中，通常需要建立一種稱為“數(shù)據(jù)立方體”的多維數(shù)據(jù)結(jié)構(gòu)，以更好支持決策分析。例如，一個全國連鎖店，可能記錄每一筆銷售，包括銷售時間、銷售地區(qū)和商品的種類等。 可以把銷售量、銷

3、售金額等數(shù)據(jù)作為希望觀察的事實數(shù)據(jù)，而把可能影響這些銷售事實數(shù)據(jù)的各因子，如時間、地區(qū)和商品類型等屬性，作為不同的觀察維度。 每個元組是該空間的一個點。然后，分析人員可按某些維對數(shù)據(jù)進行分組，并通過聚集匯總這些分組。 設銷售事實表為 Sales(dt_id, area_id, product_id, sales_count) 它通過dt_id、area_id、product_id三個屬性分別關聯(lián)到時間維表dt_dim、地區(qū)維表area_dim和產(chǎn)品維表prod_dim。 我們可通過發(fā)出如下的SQL語句，來獲得與示圖等效的數(shù)據(jù)立方體。 SELECT dt_dim.season,area_dim.

4、city,prod_dtype,sum(sales_count)FROM sales INNER JOIN dt_dim ON sales.dt_id=dt_dim.dt_id INNER JOIN area_dim ON sales.area_id=area_dim.area_id INNER JOIN prod_dim ON d_id=prod_d_idWHERE dt_dim.year=2009GROUP BY dt_dim.serson,area_dim.city,prod_dtype3.1.2 空間數(shù)據(jù)與地理信息系統(tǒng) 有兩種

5、類型的空間數(shù)據(jù)特別重要。 計算機輔助設計(CAD)數(shù)據(jù)：包括如何構(gòu)造物體的一些空間信息、集成電路設計信息等。 地理數(shù)據(jù)：例如道路地圖、行政區(qū)域地圖。地理信息系統(tǒng)(GIS)是適用于存儲地理數(shù)據(jù)的專用數(shù)據(jù)庫系統(tǒng). 許多數(shù)據(jù)庫系統(tǒng)都添加了對地理數(shù)據(jù)的支持，如IBM DB2 Spatial Extender, Informix Spatial Datablade和Oracle Spatial。地理數(shù)據(jù)庫的用途 地理數(shù)據(jù)庫有多種用途，包括聯(lián)機地圖服務、交通導航系統(tǒng)、公共服務設施分布網(wǎng)絡信息等。 當前，基于Web的道路地圖及相關設施服務，已成為廣受人們青睞的WEB應用程序。 交通導航系統(tǒng)是裝載在車輛上的、

6、提供道路地圖和旅行計劃服務的移動地理信息系統(tǒng)。GPS是移動GIS的一個有效附件，能利用GPS衛(wèi)星，以幾十米的精度確定當前位置。 幾何信息表示方法 在DB中，各種幾何結(jié)構(gòu)有很多規(guī)范化的表示形式。 可采用順序列出多邊形頂點來表示多邊形，也可用三角形剖分多邊形的方法表示多邊形。復雜多邊形被賦予一個標識符。 地理數(shù)據(jù) 地理數(shù)據(jù)實際上就是空間數(shù)據(jù)。 地圖和衛(wèi)星圖像就是典型的例子。地圖不僅可以提供位置信息，如邊界、河流和道路等，而且還可提供很多與位置區(qū)域相關的信息，如海拔、年降水量等。 地理數(shù)據(jù)可分為兩類 ： 矢量數(shù)據(jù)(vector data) 由基本幾何對象構(gòu)成，如點、線段、三角形和二維多邊形，以及圓柱

7、體、球體、立方體和其它多維幾何體。 光柵數(shù)據(jù)(raster data)。這種數(shù)據(jù)由二維或更高維的位圖或象素圖組成。二維光柵圖的典型例子是衛(wèi)星云圖，其中每個象素存儲了特定地區(qū)的云層可見度。這種數(shù)據(jù)也可以是三維的，例如，同樣在衛(wèi)星的幫助下測得的不同地區(qū)在不同高度下的溫度分布。時間可以形成另一個維度。設計數(shù)據(jù)庫通常不存儲光柵本身數(shù)據(jù)。 相應地理數(shù)據(jù)表示也有兩種： 地理特征可表示成復雜多邊形。某些特征（如河流）可以表示成復雜曲線或復雜多邊形。我們可用多邊形表示區(qū)域，每個多邊形表示一個區(qū)域，區(qū)域內(nèi)部的數(shù)組值是相同的。 關于地區(qū)的地理信息（如年降水量），可以表示成一個數(shù)組，也就是光柵的形式。 空間查詢的三

8、種主要類型 臨近查詢：要求找出指定位置的對象。最近鄰查詢(nearest-neighbor query)則要求找出離指定點最近的對象。 部分查詢：只指定部分維的值，查找維上匹配這些值的所有點或形狀； 區(qū)域查詢：查找全部或部分位于指定區(qū)域內(nèi)的對象。查詢還可能要計算區(qū)域的交和并。例如，查詢年降水查詢還可能要計算區(qū)域的交和并。例如，查詢年降水量低和人口密度高的區(qū)域。計算區(qū)域交的查詢可被看量低和人口密度高的區(qū)域。計算區(qū)域交的查詢可被看作計算空間連接作計算空間連接。 3.2 空間數(shù)據(jù)索引結(jié)構(gòu) 3.2.1 用傳統(tǒng)索引執(zhí)行范圍查詢 可采用的處理方案： 為每一維(x和y)各建立一個輔助索引(不妨設索引結(jié)構(gòu)是B

9、樹)； 通過x的B樹索引，找出x在范圍內(nèi)的所有指針； 通過y的B樹索引，找出y在范圍內(nèi)的所有指針； 如主存能存放下x, y 在查詢范圍內(nèi)的所有指針，可直接在主存中求指針交集。 執(zhí)行查詢所需的I/O數(shù)估算公式： B-樹查找的少量樹查找的少量I/OB-樹需被檢查的葉結(jié)點數(shù)樹需被檢查的葉結(jié)點數(shù) 讀數(shù)據(jù)記錄塊的讀數(shù)據(jù)記錄塊的I/O數(shù)數(shù) 示例問題 考慮一個含100萬個記錄點的關系(x,y)，隨機分布在(0,0)(1000, 1000) 矩形區(qū)域內(nèi)。設： 每個塊可存放100個記錄點的數(shù)據(jù)，B-樹的1個葉結(jié)點約有200個鍵值指針對； x值落在450,550范圍內(nèi)的記錄點數(shù)約有10萬個， y也是如此，而x和y

10、同時落在450,550范圍內(nèi)的記錄點數(shù)約有1萬個。試估算執(zhí)行范圍試估算執(zhí)行范圍450 x, y 550內(nèi)的記錄點內(nèi)的記錄點查詢所需的查詢所需的I/O次數(shù)。次數(shù)。I/O數(shù)估算 每塊可存放100記錄點，100萬記錄點，共需1萬個塊存儲數(shù)據(jù)。 每個葉節(jié)點可存200記錄指針，x落在450,550內(nèi)約有10萬記錄個點，共需500個葉節(jié)點。如果B-樹根節(jié)點駐留主存，則我們檢索關于x的B-樹，找出x在450,550內(nèi)的所有指針，需要501次的I/O 同樣，找出y在450,550內(nèi)的所有指針，也需501次I/O。合計1002次I/O。 最后對已找到的1萬個交集指針，還需進行實際記錄數(shù)據(jù)的讀取。由于記錄隨機存放

11、，可能需要檢索包含1萬個記錄點的所有塊。 多維索引結(jié)構(gòu) 網(wǎng)格索引結(jié)構(gòu) （類散列結(jié)構(gòu)） kd樹 （類樹結(jié)構(gòu)） 四叉樹 （類樹結(jié)構(gòu)） R樹 （類樹結(jié)構(gòu)）3.2.1 網(wǎng)格索引結(jié)構(gòu) 本章后面介紹常使用的一個例子： 有一個存放顧客購買金首飾記錄的 關系表(age, salary, ) 表中有12個顧客，他們的記錄表示成下列的年齡-薪水對： (26, 0.6) (45, 0.60) (51, 0.75) (51, 1.0) (51, 1.28) (70, 1.30) (85, 1.4) (30, 2.60) (26, 4.0) (45, 3.5) (51, 2.75) (60, 2.6) 基于年齡和月薪這

12、兩搜索鍵建立的網(wǎng)格索引結(jié)構(gòu) 0 1 2 3 4432100 1 2 3 4 80* 一個網(wǎng)格文件有一個網(wǎng)格數(shù)組(grid array)和兩個與搜索鍵對應的線性標度(linear scale) 。 網(wǎng)格數(shù)組的每個單元(Cell)含有一個指向桶的指針，每個桶可以是一個塊或物理相鄰的塊組，桶中直接存放記錄。為了節(jié)省空間，網(wǎng)格數(shù)組的多個單元可以指向同一個桶。 插入一個搜索鍵為(70, 3.5K)的記錄： 首先，我們用顧客月薪的線性標度，來定位新Cell的行，按順序它應位于第3行。如果搜索鍵所有現(xiàn)有標度元素，則取最后一行。 其次，我們用顧客年齡的線性標度定位新Cell的列。本例中，應定位到第3列。存儲包

13、含搜索鍵值(70, 3.5K)的記錄到桶j中。 必須選擇線性標度，使得記錄能盡可能均勻分布在各Cell上。當需要往一個已經(jīng)滿的桶中插入記錄時，系統(tǒng)必須為該桶添加掛接溢出塊。但如果一個桶掛接的溢出塊過多，會影響系統(tǒng)的性能。 為改善這種情況的性能， 如果指向有溢出塊桶(令為A)的Cell數(shù)超過1，可先分裂A桶，即增加1個桶(令為B)，并調(diào)原先指向A桶的部分Cell指針，使其指向B桶。 如果指向有溢出塊桶的Cell數(shù)只有1個，這是，我們只有重新組織網(wǎng)格文件，擴展網(wǎng)格數(shù)組和擴展某個搜索鍵的線性標度，這一過程很類似可擴展散列中擴展桶地址表。 網(wǎng)格文件對多維查詢支持： 對指定點的查找，若無溢出塊，僅需1次

14、I/O； 部分匹配：可能需要查找桶矩陣的某行或某列的所有桶，I/O數(shù)可能很大； 范圍查詢：檢查與范圍區(qū)域有相交的所有桶；要回答簡單范圍查詢：Age20 and salary1K 滿足這個條件的所有單元第0行的14列上。找出這些單元所指向的桶(本查詢，有兩個桶)，并有在桶中查找相應的記錄。 由于桶中可能包含其它一些不滿足查詢條件的記錄，因此，需要對桶中記錄的搜索鍵進行逐個檢查。但為了回答這個查詢，我們只需要檢查很少的幾個桶。 網(wǎng)格文件存在主要問題 概念上，將二維網(wǎng)格擴展到n維網(wǎng)格數(shù)組，也是很簡單的；但實際很少使用。 對于多鍵查詢，網(wǎng)格文件有效減少查詢處理時間。然而，它也帶來了： 額外的空間負荷(

15、存放含桶指針的網(wǎng)格數(shù)組、各搜索鍵的線性標度信息）； 額外的性能負荷(進行記錄插入和刪除時)。此外，為搜索鍵選擇合適的標度劃分，使得記錄能盡可能均勻分布，也往往是很困難的一件事。 若插入到網(wǎng)格很頻繁，還必須定期執(zhí)行重新組織，這往往也需要付出很高的代價的。 3.2.2 K-d樹樹(k維搜索樹維搜索樹) 早期建立多維空間索引的一種簡單樹形結(jié)構(gòu)。早期建立多維空間索引的一種簡單樹形結(jié)構(gòu)。 每個節(jié)點將一個空間劃分為兩個子空間。劃分首每個節(jié)點將一個空間劃分為兩個子空間。劃分首先通過樹頂層節(jié)點的一個維進行，然后在緊接的先通過樹頂層節(jié)點的一個維進行，然后在緊接的下一個層節(jié)點上用另一個維進行劃分，以此類推。下一個

16、層節(jié)點上用另一個維進行劃分，以此類推。 K-d樹的數(shù)據(jù)結(jié)構(gòu)特點樹的數(shù)據(jù)結(jié)構(gòu)特點 是二叉樹的變種或推廣； 每個內(nèi)結(jié)點關聯(lián)1個屬性及其屬性值，將數(shù)據(jù)記錄點在該屬性維上劃分為兩部分； 不同層結(jié)點關聯(lián)不同屬性； 所有屬性在層間循環(huán)； 葉結(jié)點是存儲塊，存儲盡可能多的記錄。k-d樹及其所隱含的空間劃分 薪 水 1 .5 K年 齡 6 0年 齡 4 7薪 水 0 .8 K薪 水 3 .0 K7 0 , 1 .3 k8 5 , 1 .4 k5 1 , 2 .7 5 k6 0 , 2 .6 k年 齡 3 85 1 , 1 .0 k5 1 , 1 .2 8 k2 6 , 0 .6 k4 5 , 0 .6 k5 1

17、 , 0 .7 5 k3 0 , 2 .6 k2 6 , 4 .0 k4 5 , 3 .5 k0 2 0 4 0 6 0 8 0 1 0 05 K*4 K3 K2 K1 K0 KK - d 樹K - d 樹 所 隱 含 的空 間 劃 分k-d樹的性能及對多維查詢支持 部分匹配查詢 當給定某些屬性值，屬性在屬性值已知的層的結(jié)點上時，只需考察一個方向的子結(jié)點；當處于屬性值未知的結(jié)點上時，必須考察它的兩個方向的子結(jié)點； 例：年齡為51的所有點 范圍查詢 有時一個范圍允許移動到結(jié)點的唯一的一個子結(jié)點 如范圍跨越結(jié)點劃分值時，需考察兩個方向的子結(jié)點樹 例：年齡 35-55 薪水 1K-2K 最鄰近查詢

18、可通過多次的范圍查詢實現(xiàn)； k-d樹應用的主要問題 每結(jié)點占用1個塊,空間利用率低； 查詢路徑可能會很長； 解決方案聚集多個內(nèi)結(jié)點到一個塊 。3.2.3 四叉樹(quadtrees) 四叉樹的每個節(jié)點關聯(lián)到空間的一個矩形區(qū)。頂層節(jié)點關聯(lián)整個目標空間。 每個節(jié)點有四個子節(jié)點關聯(lián)到節(jié)點所代表矩形區(qū)的四個象限。 葉節(jié)點有0個或多個不超過最大數(shù)的數(shù)據(jù)點數(shù)。如果超過了指定的最大數(shù)據(jù)點數(shù)，葉節(jié)點轉(zhuǎn)為節(jié)點，并進行四等分的象限劃分。 3.2.3 四叉樹(quadtrees)在一個四叉樹中，每個結(jié)點對應于二維空間中的一個矩形區(qū)域如果一個矩形中的點數(shù)不比一個塊中能存放的數(shù)多，則這個矩形看作樹的葉結(jié)點如果矩形中有太

19、多點一個塊存放不下，把它看作內(nèi)部結(jié)點，它的子結(jié)點對應它的四個象限對于象限和結(jié)點的子結(jié)點使用指南針標示法 NW西北 NE東北 SW西南 SE東南四叉樹及其所隱含的空間劃分 50, 2 . 5 K75, 1 . 2525, 3 . 7545, 0 . 6 k50, 2 . 75k60, 2 . 6 k50, 1 . 0 k50, 1 .28k50, 0 . 75k30, 2 . 6 k25, 4 . 0 k45, 3 . 5 k0 20 40 60 80 1005 K*4 K3 K2 K1 K0 K四叉樹四叉樹所隱含的空間劃分26, 0 . 6 kIIIIVIIIIV70, 1 . 3 k85,

20、1 . 4 kIIIV3.2.4 R樹 GUTTMAN在1984年提出了R樹索引。R樹索引是最早支持擴展對象存取方法之一，R樹是一個高度平衡樹，它是B樹在k維上的自然擴展。R樹中用最小外包矩形(MBR)來表示對象范圍，它開辟了空間索引研究的新方向。3.2.4 R樹 SELLIS(1987)，GREENE(1989)，BECKMANN(1990)，KAMEL(1994)和GARCFA(1998)等人在其基礎上不斷地進行改進，提出了R樹的多種變形，形成了由R樹、R+樹、R*樹、Hilbert R樹、SR樹等組成的R樹系列空間索引。R樹及其眾多變形都是一種平衡樹，結(jié)構(gòu)非常類似于B樹，也具有類似于B樹

21、的一些性質(zhì)，從而形成了一個R樹索引體系。 R樹是一種利用B樹的某些本質(zhì)特征來處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。R樹表示由二維或更高維區(qū)域組成的數(shù)據(jù)，稱之為數(shù)據(jù)區(qū)。一個R樹的內(nèi)結(jié)點對應于某個內(nèi)部區(qū)域，原則上，區(qū)域可以是任何形狀。R樹運用了空間分割的理念，采用了一種稱為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結(jié)點開始用矩形（rectangle）將空間框起來，結(jié)點越往上，框住的空間就越大，以此對空間進行分割。 圖（b），首先我們假設所有數(shù)據(jù)都是二維空間下的點，圖中僅僅標志了R8區(qū)域中的數(shù)據(jù)，也就是那個shape of data object。

22、我們把不規(guī)則圖形看作是多個數(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恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后

23、，再次迭代，用更大的框去框住這些矩形我們來講個實例，如何查詢特定的數(shù)據(jù)吧。假設我要查詢廣州市天河區(qū)天河城附近一公里的所有餐廳地址怎么辦？打開地圖（也就是整個R樹），先選擇國內(nèi)還是國外（也就是根結(jié)點）。然后選擇華南地區(qū)（對應第一層結(jié)點），選擇廣州市（對應第二層結(jié)點），再選擇天河區(qū)（對應第三層結(jié)點），最后選擇天河城所在的那個區(qū)域（對應葉子結(jié)點，存放有最小矩形），遍歷所有在此區(qū)域內(nèi)的結(jié)點，看是否滿足我們的要求即可。 一棵一棵R樹滿足如下的性質(zhì)：樹滿足如下的性質(zhì)：1.除非它是根結(jié)點之外，所有葉子結(jié)點包含有除非它是根結(jié)點之外，所有葉子結(jié)點包含有m至至M個記錄索引（條個記錄索引（條目）。作為根結(jié)點的葉子結(jié)

24、點所具有的記錄個數(shù)可以少于目）。作為根結(jié)點的葉子結(jié)點所具有的記錄個數(shù)可以少于m。通常，。通常，m=M/2。2.對于所有在葉子中存儲的記錄（條目），對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的“矩形矩形”是是可以擴展到高維空間的）。可以擴展到高維空間的）。3.每一個非葉子結(jié)點擁有每一個非葉子結(jié)點擁有m至至M個孩子結(jié)點，除非它是根結(jié)點。個孩子結(jié)點，除非它是根結(jié)點。4.對于在非葉子結(jié)點上的每一個條目，對于在非葉子結(jié)點上的每一個條目，i是最小的可以在空間上完全是最小的可

25、以在空間上完全覆蓋這些條目所代表的點的矩形（同性質(zhì)覆蓋這些條目所代表的點的矩形（同性質(zhì)2）。）。5.所有葉子結(jié)點都位于同一層，因此所有葉子結(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é)點所要存儲的信息。在這張圖中，I所代表的就是圖中的矩形，其范

26、圍是a=I0=b，c=I1=d。有兩個tuple-identifier，在圖中即表示為那兩個點。非葉子結(jié)點結(jié)構(gòu)非葉子結(jié)點結(jié)構(gòu)非葉子結(jié)點存放的數(shù)據(jù)結(jié)構(gòu)為：(I, child-pointer)。 其中，child-pointer是指向孩子結(jié)點的指針，I是覆蓋所有孩子結(jié)點對應矩形的矩形。D,E,F,G為孩子結(jié)點所對應的矩形。A為能夠覆蓋這些矩形的更大的矩形。這個A就是這個非葉子結(jié)點所對應的矩形。樹形結(jié)構(gòu)上層的結(jié)點所對應的矩形能夠完全覆蓋它的孩子結(jié)點所對應的矩形。根結(jié)點也唯一對應一個矩形，而這個矩形是可以覆蓋所有我們擁有的數(shù)據(jù)信息在空間中代表的點的。R樹的操作樹的操作搜索搜索R樹的搜索操作很簡單，它返

27、回的結(jié)果是所有符合查找信息的記錄條目。輸入不僅僅是一個范圍了，它更可以看成是一個空間中的矩形。也就是說，我們輸入的是一個搜索矩形。先給出偽代碼：Function：Search描述：假設T為一棵R樹的根結(jié)點，查找所有搜索矩形S覆蓋的記錄條目。S1:查找子樹 如果T是非葉子結(jié)點，如果T所對應的矩形與S有重合，那么檢查所有T中存儲的條目，對于所有這些條目，使用Search操作作用在每一個條目所指向的子樹的根結(jié)點上（即T結(jié)點的孩子結(jié)點）。S2:查找葉子結(jié)點 如果T是葉子結(jié)點，如果T所對應的矩形與S有重合，那么直接檢查S所指向的所有記錄條目。返回符合條件的記錄。我們通過下圖來理解這個我們通過下圖來理解這

28、個Search操作。操作。陰影部分所對應的矩形為搜索矩形。它與根結(jié)點對應的最大的矩形（未畫出）有重疊。這樣將Search操作作用在其兩個子樹上。兩個子樹對應的矩形分別為R1與R2。搜索R1，發(fā)現(xiàn)與R1中的R4矩形有重疊，繼續(xù)搜索R4。最終在R4所包含的R11與R12兩個矩形中查找是否有符合條件的記錄。搜索R2的過程同樣如此。很顯然，該算法進行的是一個迭代操作。插入插入當新的數(shù)據(jù)記錄需要被添加入葉子結(jié)點時，若葉子結(jié)點溢出，那么我們需要對葉子結(jié)點進行分裂操作。顯然，葉子結(jié)點的插入操作會比搜索操作要復雜。插入操作需要一些輔助方法才能夠完成。來看一下偽代碼：Function：Insert描述：將新的記

29、錄條目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é)點分別為原來那個根

30、結(jié)點分裂后的兩個結(jié)點。 Function：ChooseLeaf描述：選擇葉子結(jié)點以放置新條目E。CL1：Initialize 設置N為根結(jié)點。CL2：葉子結(jié)點的檢查 如果N為葉子結(jié)點，則直接返回N。CL3：選擇子樹 如果N不是葉子結(jié)點，則遍歷N中的結(jié)點，找出添加E.I時擴張最小的結(jié)點，并把該結(jié)點定義為F。如果有多個這樣的結(jié)點，那么選擇面積最小的結(jié)點。CL4：下降至葉子結(jié)點 將N設為F，從CL2開始重復操作。Function：AdjustTree描述：葉子結(jié)點的改變向上傳遞至根結(jié)點以改變各個矩陣。在傳遞變換的過程中可能會產(chǎn)生結(jié)點的分裂。AT1：初始化 將N設為L。AT2：檢驗是否完成 如果N為根

31、結(jié)點，則停止操作。AT3：調(diào)整父結(jié)點條目的最小邊界矩形 設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這個矩形。開始時我們進行ChooseLea

32、f操作。在根結(jié)點中有兩個條目，分別為R1，R2。其實R1已經(jīng)完全覆蓋了R21，而若向R2中添加R21，則會使R2.I增大很多。顯然我們選擇R1插入。然后進行下一級的操作。相比于R4，向R3中添加R21會更合適，因為R3覆蓋R21所需增大的面積相對較小。這樣就在R8，R9，R10所在的葉子結(jié)點中插入R21。由于葉子結(jié)點沒有足夠空間，則要進行分裂操作。插入操作如下圖所示：插入操作如下圖所示：刪除刪除R樹的刪除同樣是比較復雜的，需要用到一些輔助函數(shù)來完成整個操作。偽代碼如下：Function：Delete描述：將一條記錄E從指定的R樹中刪除。D1：找到含有記錄的葉子結(jié)點 使用FindLeaf方法找到

33、包含有記錄E的葉子結(jié)點L。如果搜索失敗，則直接終止。D2：刪除記錄 將E從L中刪除。D3：傳遞記錄 對L使用CondenseTree操作D4：縮減樹 當經(jīng)過以上調(diào)整后，如果根結(jié)點只包含有一個孩子結(jié)點，則將這個唯一的孩子結(jié)點設為根結(jié)點。Function：FindLeaf描述：根結(jié)點為T，期望找到包含有記錄E的葉子結(jié)點。FL1：搜索子樹 如果T不是葉子結(jié)點，則檢查每一條T中的條目F，找出與E所對應的矩形相重合的F（不必完全覆蓋）。對于所有滿足條件的F，對其指向的孩子結(jié)點進行FindLeaf操作，直到尋找到E或者所有條目均以被檢查過。FL2：搜索葉子結(jié)點以找到記錄 如果T是葉子結(jié)點，那么檢查每一個條目是否有E存在，如