0. 前言
動态查找樹主要有：二叉查找樹、平衡二叉樹、紅黑樹、B樹、B+樹。前面三種是典型的二叉查找樹，查找的時間複雜度是O(log2N)。涉及到磁盤的讀寫（比如每個節點都需要從磁盤擷取），讀寫的速度就與樹的深度有關系，那麼降低樹的深度也就可以提升查找效率。這時就提出了平衡多路查找樹，也就是B樹以及B+樹。
B樹和B+樹非常典型的場景就是用于關系型資料庫的索引(MySQL)
1. B類樹
B樹是一種平衡多路搜尋樹，B樹與紅黑樹最大的不同在于，B樹的結點可以有多個子女，從幾個到幾千個。那為什麼又說B樹與紅黑樹很相似呢?因為與紅黑樹一樣，一棵含n個結點的B樹的高度也為O（l ogn），但可能比一棵紅黑樹的高度小許多，因為它的分支因子比較大。是以，B樹可以在O（logn）時間内，實作各種如插入（insert），删除（delete）等動态集合操作。
B樹的定義如下：
根節點至少有兩個子節點
每個節點有M-1個key，并且以升序排列
位于M-1和M key的子節點的值位于M-1 和M key對應的Value之間
其它節點至少有M/2個子節點
所有葉子結點位于同一層；
下圖是一個M=4的4階的B樹：
4階 B 樹
B樹的搜尋：從根結點開始，對結點内的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為空，或已經是葉子結點；
B樹的特性：
關鍵字集合分布在整顆樹中；
任何一個關鍵字出現且隻出現在一個結點中；
搜尋有可能在非葉子結點結束(樹中所有結點都存儲資料，與B+樹這一點不同)；
其搜尋性能等價于在關鍵字全集内做一次二分查找；
B+樹是對B樹的一種變形，與B樹的差異在于：
有n棵子樹的結點中含有n個關鍵字，每個關鍵字不儲存資料，隻用來索引，所有資料都儲存在葉子節點。
所有的葉子結點中包含了全部關鍵字的資訊，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序連結。
所有的非終端結點可以看成是索引部分，結點中僅含其子樹（根結點）中的最大（或最小）關鍵字。
為所有葉子結點增加一個鍊指針，便于區間查找和周遊。
所有關鍵字都在葉子結點出現。
B+樹
B+樹的搜尋：與B-樹也基本相同，差別是B+樹隻有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
B+的特性：
非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）資料的資料層；
B+樹的葉子結點都是相鍊的，是以對整棵樹的周遊隻需要一次線性周遊葉子結點即可。而且由于資料順序排列并且相連，是以便于區間查找和搜尋。而B樹則需要進行每一層的遞歸周遊。相鄰的元素可能在記憶體中不相鄰，是以緩存命中性沒有B+樹好。
B+樹的分裂：
當一個結點滿時，配置設定一個新的結點，并将原結點中1/2的資料複制到新結點，最後在父結點中增加新結點的指針；
B+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，是以它不需要指向兄弟的指針。
B*樹是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
B*樹的分裂：
當一個結點滿時，如果它的下一個兄弟結點未滿，那麼将一部分資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字範圍改變了）；
如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各複制1/3的資料到新結點，最後在父結點增加新結點的指針。
B樹：多路搜尋樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字範圍的子結點；所有關鍵字在整顆樹中出現，且隻出現一次，非葉子結點可以命中；
B+樹：在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
B*樹：在B+樹基礎上，為非葉子結點也增加連結清單指針，将結點的最低使用率從1/2提高到2/3；
B+樹雖然優點很多，但是B樹也有優點，其優點在于，由于B樹的每一個節點都包含key和value，是以經常通路的元素可能離根節點更近，是以通路也更迅速。下面是B 樹和B+樹的差別圖：
B 樹和 B+樹對比
為什麼說B+tree比B樹更适合實際應用中作業系統的檔案索引和資料庫索引？
B+tree的磁盤讀寫代價更低
B+tree的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的内部結點需要2個盤快。而B+ 樹内部結點隻需要1個盤快。當需要把内部結點讀入記憶體中的時候，B 樹就比B+ 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
B+tree的查詢效率更加穩定
由于非葉子結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。
B樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹隻要周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的操作（或者說效率太低）。
2. LSM 樹
目前常見的主要的三種存儲引擎是：哈希、B+樹、LSM樹：
哈希存儲引擎：是哈希表的持久化實作，支援增、删、改以及随機讀取操作，但不支援順序掃描，對應的存儲系統為key-value存儲系統。對于key-value的插入以及查詢，哈希表的複雜度都是O(1)，明顯比樹的操作O(n)快,如果不需要有序的周遊資料，哈希表性能最好。
B+樹存儲引擎是B+樹的持久化實作，不僅支援單條記錄的增、删、讀、改操作，還支援順序掃描（B+樹的葉子節點之間的指針），對應的存儲系統就是關系資料庫（Mysql等）。
LSM樹（Log-Structured MergeTree）存儲引擎和B+樹存儲引擎一樣，同樣支援增、删、讀、改、順序掃描操作。而且通過批量存儲技術規避磁盤随機寫入問題。當然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
上面三種引擎中，LSM樹存儲引擎的代表資料庫就是HBase.
LSM樹核心思想的核心就是放棄部分讀能力，換取寫入的最大化能力。LSM Tree ，這個概念就是結構化合并樹的意思，它的核心思路其實非常簡單，就是假定記憶體足夠大，是以不需要每次有資料更新就必須将資料寫入到磁盤中，而可以先将最新的資料駐留在記憶體中，等到積累到足夠多之後，再使用歸并排序的方式将記憶體内的資料合并追加到磁盤隊尾(因為所有待排序的樹都是有序的，可以通過合并排序的方式快速合并到一起)。
日志結構的合并樹（LSM-tree）是一種基于硬碟的資料結構，與B+tree相比，能顯著地減少硬碟磁盤臂的開銷，并能在較長的時間提供對檔案的高速插入（删除）。然而LSM-tree在某些情況下，特别是在查詢需要快速響應時性能不佳。通常LSM-tree适用于索引插入比檢索更頻繁的應用系統。
LSM樹和B+樹的差異主要在于讀性能和寫性能進行權衡。在犧牲的同時尋找其餘補救方案：
LSM具有批量特性，存儲延遲。當寫讀比例很大的時候（寫比讀多），LSM樹相比于B樹有更好的性能。因為随着insert操作，為了維護B+樹結構，節點分裂。讀磁盤的随機讀寫機率會變大，性能會逐漸減弱。
B樹的寫入過程：對B樹的寫入過程是一次原位寫入的過程，主要分為兩個部分，首先是查找到對應的塊的位置，然後将新資料寫入到剛才查找到的資料塊中，然後再查找到塊所對應的磁盤實體位置，将資料寫入去。當然，在記憶體比較充足的時候，因為B樹的一部分可以被緩存在記憶體中，是以查找塊的過程有一定機率可以在記憶體内完成，不過為了表述清晰，我們就假定記憶體很小，隻夠存一個B樹塊大小的資料吧。可以看到，在上面的模式中，需要兩次随機尋道（一次查找，一次原位寫），才能夠完成一次資料的寫入，代價還是很高的。
LSM優化方式：
a. Bloom filter: 就是個帶随機機率的bitmap,可以快速的告訴你，某一個小的有序結構裡有沒有指定的那個資料的。于是就可以不用二分查找，而隻需簡單的計算幾次就能知道資料是否在某個小集合裡啦。效率得到了提升，但付出的是空間代價。
b. compact:小樹合并為大樹:因為小樹性能有問題，是以要有個程序不斷地将小樹合并到大樹上，這樣大部分的老資料查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了
B樹存儲引擎是B樹的持久化實作，不僅支援單條記錄的增、删、讀、改操作，還支援順序掃描（B+樹的葉子節點之間的指針），對應的存儲系統就是關系資料庫（Mysql等）。
LSM樹（Log-Structured Merge Tree）存儲引擎和B樹存儲引擎一樣，同樣支援增、删、讀、改、順序掃描操作。而且通過批量存儲技術規避磁盤随機寫入問題。當然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
LSM樹的設計思想非常樸素：将對資料的修改增量保持在記憶體中，達到指定的大小限制後将這些修改操作批量寫入磁盤，不過讀取的時候稍微麻煩，需要合并磁盤中曆史資料和記憶體中最近修改操作，是以寫入性能大大提升，讀取時可能需要先看是否命中記憶體，否則需要通路較多的磁盤檔案。極端的說，基于LSM樹實作的HBase的寫性能比Mysql高了一個數量級，讀性能低了一個數量級。
LSM樹原理把一顆大叔拆分成N顆小樹，它首先在記憶體中，它首先寫入記憶體中，随着小樹越來越大，記憶體中的小樹會flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成為一個大樹，用來優化讀性能。
以上就是hbase存儲設計的重要思想，這裡說明一下：
因為資料是先寫到記憶體中，是以為了防止記憶體資料丢失，會先把資料寫入hlog中，也符合了資料庫中标準，先寫日志，再寫資料
memstore上的樹達到一定大小之後，需要flush到磁盤中，然後再定期做合并，提高讀取的性能；
關于LSM Tree，對于最簡單的二層lsm而言。
lsm
tree，理論上，可以是記憶體中樹的一部分和磁盤中一層數做merge，對于磁盤中的樹直接做update操作有可能會破壞實體block的連續性，在實際場景中，一般lsm有多層，當磁盤中的小樹合并成為一個大樹的時候，可以重新排好順序，使block連續，優化讀性能。
hbase在視線中，是把整個記憶體在一定門檻值後，flush到disk中，形成一個hfile檔案。這個file的存儲也是一個小的b+樹，因為hbase是存儲在hdfs上，hdfs不支援更新操作，是以hbase的資料也是定期flush到磁盤中，而不是和檔案中的hfile做合并操作。
3. R 樹
R樹概括來說就是二維空間的B樹,因為空間擴充了,能表示的範圍就更廣闊了,但是暫時還沒應用實際用上它,還停留在學術概念,隻有某些公司從代碼層用它的概念來設計代碼.
1984年，加州大學伯克利分校的Guttman發表了一篇題為“R-trees:
a dynamic index structure for spatial
searching”的論文，向世人介紹了R樹這種處理高維空間存儲問題的資料結構。本文便是基于這篇論文寫作完成的，是以如果大家對R樹非常有興趣，我想最好還是參考一下原著：）。
R樹在資料庫等領域做出的功績是非常顯著的。它很好的解決了在高維空間搜尋等問題。舉個R樹在現實領域中能夠解決的例子：查找20英裡以内所有的餐廳。如果沒有R樹你會怎麼解決？一般情況下我們會把餐廳的坐标(x,y)分為兩個字段存放在資料庫中，一個字段記錄經度，另一個字段記錄緯度。這樣的話我們就需要周遊所有的餐廳擷取其位置資訊，然後計算是否滿足要求。如果一個地區有100家餐廳的話，我們就要進行100次位置計算操作了，如果應用到谷歌地圖這種超大資料庫中，這種方法便必定不可行了。
R樹就很好的解決了這種高維空間搜尋問題。它把B樹的思想很好的擴充到了多元空間，采用了B樹分割空間的思想，并在添加、删除操作時采用合并、分解結點的方法，保證樹的平衡性。是以，R樹就是一棵用來存儲高維資料的平衡樹。
OK，接下來，本文将詳細介紹R樹的資料結構以及R樹的操作。至于R樹的擴充與R樹的性能問題，可以查閱相關論文。
相信經過上面第一節的介紹，你已經對B樹或者B+樹有所了解。這種樹可以非常好的處理一維空間存儲的問題。B樹是一棵平衡樹，它是把一維直線分為若幹段線段，當我們查找滿足某個要求的點的時候，隻要去查找它所屬的線段即可。依我看來，這種思想其實就是先找一個大的空間，再逐漸縮小所要查找的空間，最終在一個自己設定的最小不可分空間内找出滿足要求的解。對應B樹的一個典型的查找如下：
要查找某一滿足條件的點，就要先去找到對應條件的線段，然後周遊所線上段上的點，即可找到答案。B樹是一種相對來說比較複雜的資料結構，尤其是在它的删除與插入操作過程中，因為它涉及到了葉子結點的分解與合并。由于本文第一節已經詳細介紹了B樹和B+樹，下面直接開始介紹我們的第二個主角：R樹。
R樹的資料結構
如上所述，R樹是B樹在高維空間的擴充，是一棵平衡樹。每個R樹的葉子結點包含了多個指向不同資料的指針，這些資料可以是存放在硬碟中的，也可以是存在記憶體中。根據R樹的這種資料結構，當我們需要進行一個高維空間查詢時，我們隻需要周遊少數幾個葉子結點所包含的指針，檢視這些指針指向的資料是否滿足要求即可。這種方式使我們不必周遊所有資料即可獲得答案，效率顯著提高。下圖1是R樹的一個簡單執行個體：
我們在上面說過，R樹運用了空間分割的理念，這種理念是如何實作的呢？R樹采用了一種稱為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結點開始用矩形（rectangle）将空間框起來，結點越往上，框住的空間就越大，以此對空間進行分割。有點不懂？沒關系，繼續往下看。在這裡我還想提一下，R樹中的R應該代表的是Rectangle（此處參考wikipedia上關于R樹的介紹），而不是大多數國内教材中所說的Region（很多書把R樹稱為區域樹，這是有誤的）。我們就拿二維空間來舉例。下圖是Guttman論文中的一幅圖：
我來詳細解釋一下這張圖。先來看圖（b）
首先我們假設所有資料都是二維空間下的點，圖中僅僅标志了R8區域中的資料，也就是那個shape of data object。别把那一塊不規則圖形看成一個資料，我們把它看作是多個資料圍成的一個區域。為了實作R樹結構，我們用一個最小邊界矩形恰好框住這個不規則區域，這樣，我們就構造出了一個區域：R8。R8的特點很明顯，就是正正好好框住所有在此區域中的資料。其他實線包圍住的區域，如R9，R10，R12等都是同樣的道理。這樣一來，我們一共得到了12個最最基本的最小矩形。這些矩形都将被存儲在子結點中。
下一步操作就是進行高一層次的處理。我們發現R8，R9，R10三個矩形距離最為靠近，是以就可以用一個更大的矩形R3恰好框住這3個矩形。
同樣道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之後，再次疊代，用更大的框去框住這些矩形。
我想大家都應該了解這個資料結構的特征了。用地圖的例子來解釋，就是所有的資料都是餐廳所對應的地點，先把相鄰的餐廳劃分到同一塊區域，劃分好所有餐廳之後，再把鄰近的區域劃分到更大的區域，劃分完畢後再次進行更高層次的劃分，直到劃分到隻剩下兩個最大的區域為止。要查找的時候就友善了。
下面就可以把這些大大小小的矩形存入我們的R樹中去了。根結點存放的是兩個最大的矩形，這兩個最大的矩形框住了所有的剩餘的矩形，當然也就框住了所有的資料。下一層的結點存放了次大的矩形，這些矩形縮小了範圍。每個葉子結點都是存放的最小的矩形，這些矩形中可能包含有n個資料。
在這裡，讀者先不要去糾結于如何劃分資料到最小區域矩形，也不要糾結怎樣用更大的矩形框住小矩形，這些都是下一節我們要讨論的。
講完了基本的資料結構，我們來講個執行個體，如何查詢特定的資料。又以餐廳為例，假設我要查詢廣州市天河區天河城附近一公裡的所有餐廳位址怎麼辦？
1.打開地圖（也就是整個R樹），先選擇國内還是國外（也就是根結點）。
2.然後選擇華南地區（對應第一層結點），選擇廣州市（對應第二層結點），
3.再選擇天河區（對應第三層結點），
4.最後選擇天河城所在的那個區域（對應葉子結點，存放有最小矩形），周遊所有在此區域内的結點，看是否滿足我們的要求即可。
怎麼樣，其實R樹的查找規則跟查地圖很像吧？對應下圖：
一棵R樹滿足如下的性質：
1. 除非它是根結點之外，所有葉子結點包含有m至M個記錄索引（條目）。作為根結點的葉子結點所具有的記錄個數可以少于m。通常，m=M/2。
2. 對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆寫這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴充到高維空間的）。
3. 每一個非葉子結點擁有m至M個孩子結點，除非它是根結點。
4. 對于在非葉子結點上的每一個條目，i是最小的可以在空間上完全覆寫這些條目所代表的店的矩形（同性質2）。
5. 所有葉子結點都位于同一層，是以R樹為平衡樹。
葉子結點的結構
先來探究一下葉子結點的結構。葉子結點所儲存的資料形式為：(I, tuple-identifier)。
其中，tuple-identifier表示的是一個存放于資料庫中的tuple，也就是一條記錄，它是n維的。I是一個n維空間的矩形，并可以恰好框住這個葉子結點中所有記錄代表的n維空間中的點。I=(I0,I1,…,In-1)。其結構如下圖所示：
下圖描述的就是在二維空間中的葉子結點所要存儲的資訊。
在這張圖中，I所代表的就是圖中的矩形，其範圍是a<=I0<=b，c<=I1<=d。有兩個tuple-identifier，在圖中即表示為那兩個點。這種形式完全可以推廣到高維空間。大家簡單想想三維空間中的樣子就可以了。這樣，葉子結點的結構就介紹完了。
非葉子結點
非葉子結點的結構其實與葉子結點非常類似。想象一下B樹就知道了，B樹的葉子結點存放的是真實存在的資料，而非葉子結點存放的是這些資料的“邊界”，或者說也算是一種索引（有疑問的讀者可以回顧一下上述第一節中講解B樹的部分）。
同樣道理，R樹的非葉子結點存放的資料結構為：(I, child-pointer)。
其中，child-pointer是指向孩子結點的指針，I是覆寫所有孩子結點對應矩形的矩形。這邊有點拗口，但我想不是很難懂？給張圖：
D,E,F,G為孩子結點所對應的矩形。A為能夠覆寫這些矩形的更大的矩形。這個A就是這個非葉子結點所對應的矩形。這時候你應該悟到了吧？無論是葉子結點還是非葉子結點，它們都對應着一個矩形。樹形結構上層的結點所對應的矩形能夠完全覆寫它的孩子結點所對應的矩形。根結點也唯一對應一個矩形，而這個矩形是可以覆寫所有我們擁有的資料資訊在空間中代表的點的。
我個人感覺這張圖畫的不那麼精确，應該是矩形A要恰好覆寫D,E,F,G，而不應該再留出這麼多沒用的空間了。但為尊重原圖的繪制者，特不作修改。
R樹的操作
這一部分也許是程式設計者最關注的問題了。這麼高效的資料結構該如何去實作呢？這便是這一節需要闡述的問題。
搜尋
R樹的搜尋操作很簡單，跟B樹上的搜尋十分相似。它傳回的結果是所有符合查找資訊的記錄條目。而輸入是什麼？就我個人的了解，輸入不僅僅是一個範圍了，它更可以看成是一個空間中的矩形。也就是說，我們輸入的是一個搜尋矩形。
先給出僞代碼：
Function：Search
描述：假設T為一棵R樹的根結點，查找所有搜尋矩形S覆寫的記錄條目。
S1:[查找子樹] 如果T是非葉子結點，如果T所對應的矩形與S有重合，那麼檢查所有T中存儲的條目，對于所有這些條目，使用Search操作作用在每一個條目所指向的子樹的根結點上（即T結點的孩子結點）。
S2:[查找葉子結點] 如果T是葉子結點，如果T所對應的矩形與S有重合，那麼直接檢查S所指向的所有記錄條目。傳回符合條件的記錄。
我們通過下圖來了解這個Search操作。
陰影部分所對應的矩形為搜尋矩形。它與根結點對應的最大的矩形（未畫出）有重疊。這樣将Search操作作用在其兩個子樹上。兩個子樹對應的矩形分别為R1與R2。搜尋R1，發現與R1中的R4矩形有重疊，繼續搜尋R4。最終在R4所包含的R11與R12兩個矩形中查找是否有符合條件的記錄。搜尋R2的過程同樣如此。很顯然，該算法進行的是一個疊代操作。
插入
R樹的插入操作也同B樹的插入操作類似。當新的資料記錄需要被添加入葉子結點時，若葉子結點溢出，那麼我們需要對葉子結點進行分裂操作。顯然，葉子結點的插入操作會比搜尋操作要複雜。插入操作需要一些輔助方法才能夠完成。
描述：将新的記錄條目E插入給定的R樹中。
I1：[為新記錄找到合适插入的葉子結點] 開始ChooseLeaf方法選擇葉子結點L以放置記錄E。
I2：[添加新記錄至葉子結點] 如果L有足夠的空間來放置新的記錄條目，則向L中添加E。如果沒有足夠的空間，則進行SplitNode方法以獲得兩個結點L與LL，這兩個結點包含了所有原來葉子結點L中的條目與新條目E。
I3：[将變換向上傳遞] 開始對結點L進行AdjustTree操作，如果進行了分裂操作，那麼同時需要對LL進行AdjustTree操作。
I4：[對樹進行增高操作] 如果結點分裂，且該分裂向上傳播導緻了根結點的分裂，那麼需要建立一個新的根結點，并且讓它的兩個孩子結點分别為原來那個根結點分裂後的兩個結點。
描述：選擇葉子結點以放置新條目E。
CL1：[Initialize] 設定N為根結點。
CL2：[葉子結點的檢查] 如果N為葉子結點，則直接傳回N。
CL3：[選擇子樹] 如果N不是葉子結點，則周遊N中的結點，找出添加E.I時擴張最小的結點，并把該結點定義為F。如果有多個這樣的結點，那麼選擇面積最小的結點。
CL4：[下降至葉子結點] 将N設為F，從CL2開始重複操作。
描述：葉子結點的改變向上傳遞至根結點以改變各個矩陣。在傳遞變換的過程中可能會産生結點的分裂。
AT1：[初始化] 将N設為L。
AT2：[檢驗是否完成] 如果N為根結點，則停止操作。
AT3：[調整父結點條目的最小邊界矩形] 設P為N的父節點，EN為指向在父節點P中指向N的條目。調整EN.I以保證所有在N中的矩形都被恰好包圍。
AT4：[向上傳遞結點分裂] 如果N有一個剛剛被分裂産生的結點NN，則建立一個指向NN的條目ENN。如果P有空間來存放ENN，則将ENN添加到P中。如果沒有，則對P進行SplitNode操作以得到P和PP。
AT5：[升高至下一級] 如果N等于L且發生了分裂，則把NN置為PP。從AT2開始重複操作。
同樣，我們用圖來更加直覺的了解這個插入操作。
我們來通過圖分析一下插入操作。現在我們需要插入R21這個矩形。開始時我們進行ChooseLeaf操作。在根結點中有兩個條目，分别為R1，R2。其實R1已經完全覆寫了R21，而若向R2中添加R21，則會使R2.I增大很多。顯然我們選擇R1插入。然後進行下一級的操作。相比于R4，向R3中添加R21會更合适，因為R3覆寫R21所需增大的面積相對較小。這樣就在R8，R9，R10所在的葉子結點中插入R21。由于葉子結點沒有足夠空間，則要進行分裂操作。
插入操作如下圖所示：
這個插入操作其實類似于第一節中B樹的插入操作，這裡不再具體介紹，不過想必看過上面的僞代碼大家應該也清楚了。
删除
R樹的删除操作與B樹的删除操作會有所不同，不過同B樹一樣，會涉及到壓縮等操作。相信讀者看完以下的僞代碼之後會有所體會。R樹的删除同樣是比較複雜的，需要用到一些輔助函數來完成整個操作。
描述：将一條記錄E從指定的R樹中删除。
D1：[找到含有記錄的葉子結點] 使用FindLeaf方法找到包含有記錄E的葉子結點L。如果搜尋失敗，則直接終止。
D2：[删除記錄] 将E從L中删除。
D3：[傳遞記錄] 對L使用CondenseTree操作
D4：[縮減樹] 當經過以上調整後，如果根結點隻包含有一個孩子結點，則将這個唯一的孩子結點設為根結點。
描述：根結點為T，期望找到包含有記錄E的葉子結點。
FL1：[搜尋子樹] 如果T不是葉子結點，則檢查每一條T中的條目F，找出與E所對應的矩形相重合的F（不必完全覆寫）。對于所有滿足條件的F，對其指向的孩子結點進行FindLeaf操作，直到尋找到E或者所有條目均以被檢查過。
FL2：[搜尋葉子結點以找到記錄] 如果T是葉子結點，那麼檢查每一個條目是否有E存在，如果有則傳回T。
描述：L為包含有被删除條目的葉子結點。如果L的條目數過少（小于要求的最小值m），則必須将該葉子結點L從樹中删除。經過這一删除操作，L中的剩餘條目必須重新插入樹中。此操作将一直重複直至到達根結點。同樣，調整在此修改樹的過程所經過的路徑上的所有結點對應的矩形大小。
CT1：[初始化] 令N為L。初始化一個用于存儲被删除結點包含的條目的連結清單Q。
CT2：[找到父條目] 如果N為根結點，那麼直接跳轉至CT6。否則令P為N 的父結點，令EN為P結點中存儲的指向N的條目。
CT3：[删除下溢結點] 如果N含有條目數少于m，則從P中删除EN，并把結點N中的條目添加傳入連結表Q中。
CT4：[調整覆寫矩形] 如果N沒有被删除，則調整EN.I使得其對應矩形能夠恰好覆寫N中的所有條目所對應的矩形。
CT5：[向上一層結點進行操作] 令N等于P，從CT2開始重複操作。
CT6：[重新插入孤立的條目] 所有在Q中的結點中的條目需要被重新插入。原來屬于葉子結點的條目可以使用Insert操作進行重新插入，而那些屬于非葉子結點的條目必須插入删除之前所在層的結點，以確定它們所指向的子樹還處于相同的層。
R樹删除記錄過程中的CondenseTree操作是不同于B樹的。我們知道，B樹删除過程中，如果出現結點的記錄數少于半滿（即下溢）的情況，則直接把這些記錄與其他葉子的記錄“融合”，也就是說兩個相鄰結點合并。然而R樹卻是直接重新插入。
同樣，我們用圖直覺的說明這個操作。
假設結點最大條目數為4，最小條目數為2。在這張圖中，我們的目标是删除記錄c。首先使用FindLeaf操作找到c所處在的葉子結點的位置——R11。當c從R11删除時，R11就隻有一條記錄了，少于最小條目數2，出現下溢，此時要調用CondenseTree操作。這樣，c被删除，R11剩餘的條目——指向記錄d的指針——被插傳入連結表Q。然後向更高一層的結點進行此操作。這樣R12會被插傳入連結表中。原理是一樣的，在這裡就不再贅述。
有一點需要解釋的是，我們發現這個删除操作向上傳遞之後，根結點的條目R1也被插入了Q中，這樣根結點隻剩下了R2。别着急，重新插入操作會有效的解決這個問題。我們插入R3，R12，d至它原來所處的層。這樣，我們發現根結點隻有一個條目了，此時根據Inert中的操作，我們把這個根結點删除，它的孩子結點，即R5，R6，R7，R3所在的結點被置為根結點。至此，删除操作結束。
結語
R樹是一種能夠有效進行高維空間搜尋的資料結構，它已經被廣泛應用在各種資料庫及其相關的應用中。但R樹的處理也具有局限性，它的最佳應用範圍是處理2至6維的資料，更高維的存儲會變得非常複雜，這樣就不适用了。近年來，R樹也出現了很多變體，R*樹就是其中的一種。這些變體提升了R樹的性能，感興趣的讀者可以參考相關文獻。文章有任何錯誤，還望各位讀者不吝賜教。本文完。
------------------------------------------------------------------------
引用連結：
https://www.jianshu.com/p/3fb899684392
https://blog.csdn.net/v_july_v/article/details/6530142