資料結構-（2-3樹，2-3-4樹，B-樹，B+樹）

目錄

1，二叉樹存在問題分析

2，多叉樹B樹的介紹

2.1，2-3樹和2-3-4樹的介紹

2.2，B樹的查找

2.3，B樹的建立和插入

2.4，B樹的删除

3，B+樹

3.1，m 階的B+樹與m階的B樹的主要差異

1，二叉樹存在問題分析

雖然我們說二叉排序樹，平衡二叉樹的查找操作效率較高，但是也存在問題, 請看下面的二叉樹。

• 二叉樹需要加載到記憶體的，如果二叉樹的節點少，沒有什麼問題，但是如果二叉樹的節點很多(比如1億)， 就存在如下問題:
  • 問題1：在建構二叉樹時，需要多次進行i/o操作(海量資料存在資料庫或檔案中)，節點海量，建構二叉樹時，速度有影響。
  • 問題2：節點海量，也會造成二叉樹的高度很大，會降低操作速度。
• 二叉樹每一個節點隻有兩個子樹，存儲的資料量也有限，那我們就像，能否通過提高每一個節點的分支數量來提高我們資訊的存儲量，這個就是我們今天要講解的多叉樹。

2，多叉樹B樹的介紹

B樹，又叫做多路平衡查找樹，B樹中所有節點的孩子個數的最大值稱為B樹的階數，通常我們使用m标示，一棵m階的B樹為空樹，或者為滿足如下特性的m階B數：

• 樹中每一個節點最多有m棵子樹，也就是最多有m-1個關鍵字。
• 如果根節點不是終端節點，那麼根節點至少有兩棵子樹。
• 除了根節點之外所有的非葉子節點至少有

  

  棵子樹。（符号表示向上取整），也就是至少含有

  

  -1個關鍵字。
• 所有的非葉子節點的結構如下：

其中

表示的是關鍵字，并且滿足

，

為指向子樹根節點的指針，并且指針

所指向的子樹中所有節點中的關鍵字均小于關鍵字

，

所指的子樹中所有的關鍵字均大于關鍵字

，

為節點中關鍵字的個數。

• 所有的葉節點均出現在同一層次上面，并且不帶資訊（可以認為是外部節點或者是類似于折半查找判定樹中查找失敗的節點，實際上這些節點是不存在的，指向這些節點的指針是空的）。
• B樹是所有節點的平衡因子均為0的多路平衡查找樹。

定義看起來很枯燥，下面我們就來看看真實的B樹長的什麼樣子

下面我們根據性質來分析一下這一棵3階B樹：

• 孩子節點的個數等于該節點中關鍵字的個數+1。
• 如果根節點中沒有關鍵字就沒有子樹，此時B樹是空樹，如果根節點中有關鍵字，那麼其子樹必然大于等于兩棵，本樹中有3個子樹，也就是子樹個數等于關鍵字個數+1。
• 除了根節點之外所有非終端節點至少有

  

  =2棵子樹，也就是說至少有2-1個關鍵字，最多有3棵子樹，也就是最多有2個關鍵字。
• 節點中關鍵字從左到右依次遞增有序，關鍵字兩側均有指向子樹的指針，左邊的指針所指的子樹中所有關鍵字均小于該關鍵字，右邊指針所指的子樹中所有關鍵字均大于該關鍵字。
• 所有葉子節點均在第4層，也就是查找失敗的位置。

這裡需要注意的是，我們下面要講解的2-3樹和2-3-4樹都是B樹的一種特殊的形式，2-3 樹是 3 階 B 樹，2-3-4 樹是 4 階 B 樹，不同的是，2-3樹中每一個節點中要麼有一個值包含兩個孩子或者沒有孩子，或者一個節點中包含兩個數值，三個孩子或者是沒有孩子，不能隻有一個或者兩個孩子，這是與普通B樹不同的地方，2-3-4樹也是同樣的道理。

2.1，2-3樹和2-3-4樹的介紹

好了，上面了解了B樹，下面看2-3樹和2-3-4樹就很好了解了。

我們先來看看2-3樹的定義：

• 2-3樹是這樣的一棵多路查找樹：其中的每一個節點都具有兩個孩子(我們稱它為 2 節點)或三個孩子(我們稱它為 3 節點)。
• 一個 2 節點包含一個元素和兩個孩子(或沒有孩子)，且與二叉排序樹類似，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。不過，與二叉排序樹不同的是，這個 2 節點要麼沒有孩子，要麼就有兩個，不能隻有一個孩子。與普通B樹的差別。
• 一個 3 節點包含一大一小兩個元素和三個孩子(或沒有孩子)，一個 3 節點要麼沒有孩子，要麼具有 3 個孩子。如果某個 3 節點有孩子的話，左子樹包含小于較小元素的元素，右子樹包含大于較大元素的元素，中間子樹包含介于兩元素之間的元素。
• 并且 2-3 樹種所有的葉子都在同一層次上。如下圖所示就是一顆有效的 2-3 樹。
• 下面是一棵2-3樹，注意：每個節點中要麼有2個孩子或者是3個孩子（兩個孩子的節點對應有一個元素值，三個孩子節點的對應有2個元素值），裡面是不存在隻有一個孩子的節點的。

• 事實上，2-3 樹複雜的地方就在于新節點的插入和已有節點的删除。畢竟每個節點可能是 2 節點也可能是 3 節點，要保證所有葉子都在同一層次，是需要一番複雜操作的。

接下來我們再來看看2-3-4樹的定義：

• 有了 2-3 樹的講解，2-3-4 樹就很好了解了，它其實就是 2-3 樹的概念擴充，包括了 4 節點的使用（也即是節點中有3個元素的那種情況）。
• 一個 4 節點包含小中大三個元素和四個孩子(或沒有孩子)，一個 4 節點要麼沒有孩子，要麼具有 4 個孩子。
• 如果某個 4 節點有孩子的話，左子樹包含小于最小元素的元素；第二子樹包含大于最小元素，小于第二進制素的元素；第三子樹包含大于第二進制素，小于最大元素的元素；右子樹包含大于最大元素的元素

2.2，B樹的查找

在B 樹上進行查找與二叉查找樹很相似，隻是每個結點都是多個關鍵字的有序表，在每個結點上所做的不是兩路分支決定，而是根據該結點的子樹所做的多路分支決定。

• B 樹的查找包含兩個基本操作：
  • 在B 樹中找結點，
  • 在結點内找關鍵字，
  • 由于B 樹常存存儲在磁盤上，是以前一個查找操作是在磁盤上進行的，而後一個查找操作是在記憶體中進行的， 即在找到目标結點後，先将結點資訊讀入記憶體，然後在結點内采用順序查找法或折半查找法。
• 在B 樹上查找到某個結點後， 先在有序表中進行查找，若找到則查找成功，否則按照對應的指針資訊到所指的子樹中去查找。
  • 例如我們在上面的3階樹中查找元素90，先和根節點中的元素比較，90>50，是以就找到節點50的右孩子，也就是節點80，但是90>80，于是就接着和80節點的右子樹比較，80的右子樹上面有兩個節點，90和這兩個元素逐個比較，發現查找到90就傳回。

2.3，B樹的建立和插入

與二叉查找樹的插入操作相比， B 樹的插入操作要複雜得多。在二又查找樹中，僅需查找到需插入的終端結點的位置。但是，在B 樹中找到插入的位置後，并不能簡單地将其添加到終端結點中，因為此時可能會導緻整棵樹不再滿足B 樹定義中的要求。将關鍵字key 插入B 樹的過程如下:

• 定位。利用前述的B 樹查找算法，找出插入該關鍵字的最低層中的某個非葉結點(在B樹中查找key 時，會找到表示查找失敗的葉結點，這樣就确定了最底層非日f結點的插入位置。注意:插入位置一定是最低層中的某個非葉結點)。
• 插入。在B 樹中每個非失敗結點的關鍵字個數都在區間[m/2l -1, m - 1 ] 内。插入後的結點關鍵于個數小于m ， 可以直接插入，插入後檢查被插入結點内關鍵宇的個數。當插入後的結點關鍵字個數大于m-1 時，必須對結點進行分裂。
  • 分裂的方法是：取一個新結點，在插入key 後的原結點，從中間位置(

    

    ) 将其中的關鍵宇分為兩部分，左部分包含的關鍵字放在原結點中， 右部分包含的關鍵字放到新結點中，中間位置(

    

    ) 的結點插入原結點的父結點。若此時導緻其父結點的關鍵宇個數也超過了上限，則繼續進行這種分裂操作，直至這個過程傳到根結點為止，進而導緻B 樹高度增1。

下面我們來建立一棵B樹并逐個插入節點：以（20,30,50，52,60，68,70）序列來建立一顆3階B樹。因為M=3，是以除了根節點外，非葉節點中元素個數是1-2。

• 第一步：首先插入20.30 ，結點内關鍵字個數不超過Im/2l= 2 ，不會引起分裂。

• 第二步：插入50，由于在插入元素50之後，節點内元素超過2個，是以需要進行分裂操作，把

  

  處的元素作為父節點分裂出去。

• 第三步：插入元素52

• 第四步：插入60 ，插入50， 52 所在的結點， 引起分裂，但上升到父結點中，不會引起父結點的分裂。

• 第五步：插入68 ， 插入60 所在的結點，不會引起分裂

• 第六步：插入70 ，插入60 ， 68 所在的結點， 引起分裂， 68 上升為新的父結點， 68 上升到30 . 52 所在的結點後，會繼續引起該結點的分裂，故52 上升為新的根結點。最後得到的B 樹如下圖所示。

可以看到，B樹在建立和插入元素的過程中，是不斷向上長高的，

2.4，B樹的删除

B 樹中的删除操作與插入操作類似，但要稍微複雜一些，即要使得删除後的結點中的關鍵字個數>=

-1，是以将涉及結點的"合并"問題。

• 當被删關鍵子k 不在終端結點(最低層非葉結點) 中時可用k 的前驅(或後繼) k'來替 代k ,然後在相應的結點中删除k'，關鍵字k 必定落在某個終端結點中， 則轉換成被删除的關鍵字在終端節點中的情況，
• 下面的4 階B 樹中， 删除關鍵宇80 ，用其前驅78 替代，然後在終端結點中删除78， 是以隻需讨論删除終端結點中關鍵字的情形。

• 當被删關鍵字在終端結點(最低層非葉結點)中時，有下列三種情況：
  • 直接删除關鍵字。若被删除關鍵字所在結點的關鍵宇個數=

    

    -1， 表明删除該關鍵字後仍滿足B 樹的定義，則直接删去該關鍵字。
  • 兄弟夠借。若被删除關鍵字所在結點删除前的關鍵宇個數=

    

    - 1，且與此結點相鄰的右(或左)兄弟結點的關鍵宇個數>

    

    ， 則需要調整該結點、右(或左)兄弟結點

    及其雙親結點(父子換位法)，以達到新的平衡。下圖中删除4 階B 樹的關鍵字65 ，右兄弟關鍵字個數>=

    

    =2 ，将71 取代原65 的位置，将74 調整到71 的位置。

• 兄弟不夠借。若被删除關鍵字所在結點删除前的關鍵宇個數=

  

  - 1，且此時與該結點相鄰的左、右兄弟結點的關鍵字個數均=

  

  -1，則将關鍵宇删除後與左(或右)兄弟結點及雙親結點中的關鍵字進行合并。下圖中删除4 階B 樹的關鍵宇5 ，它及其右兄弟結點的關鍵字個數=

  

  - 1 = 1，故在5 删除後将60 合并到65 結點中。

在合并過程中，雙親結點中的關鍵宇個數會減1 。若其雙親結點是根結點且關鍵宇個數減少至o (根結點關鍵宇個數為1 時， 有2 棵子樹)，則直接将根結點删除，合并後的新結點成為根;若雙親結點不是根結點，且關鍵宇個數減少到

- 2 ， 則又要與它自己的兄弟結點進行調整或合并操作，并重複上述步驟，直至符合B 樹的要求為止。

下面我們對一棵三階B樹進行插入和删除操作，三階B樹如下：

第一步：插入90，90插入100所在的節點，不會引起分裂。

• 第二步：插入25，25插入8,20所在的節點，元素個數大于2，是以會引起分裂，把中間位置節點上升到父節點位置。

•  第三步：插入45，将45 插入35， 40 所在的結點，引起分裂， 中間元素40 上升到父結點(20， 30 所在的結點)中，引起父結點分裂，中間元素30 上升到父結點(50 所在的結點)中，兩次分裂後的B 樹如下圖所示。

• 第四步：删除60，删除60 後，其所在的結點元素為空，進而導緻借用右兄弟結點的元素，調整後的B 樹如下圖所示。（這種情況是其兄弟夠借的情況）

• 第五步：删除80，删除80 後，導緻80 所在結點的父結點與其右兄弟結點合井，這時父結點元素個數為0 ，再次對父結點進行調整。将50 與40 合并成一個新結點， 則90，100 所在結點為這個結點的子結點。進而構造的B 樹如下圖所示。注意，這次調整的過程實際上包含多次調整過程， 希望讀者對照考點講解中的删除過程仔細思考。

至此，我們的删除操作也基本說完了。

3，B+樹

B+樹是應資料庫所需而出現的一種B 樹的變形樹。一棵m 階的B十樹需滿足下列條件:

• 每個分支結點最多有m 棵子樹(孩子結點)。
• 非葉根結點至少有兩棵子樹，其他每個分支結點至少有

  

  棵子樹。
• 結點的子樹個數與關鍵宇個數相等。
• 所有葉結點包含全部關鍵字及指向相應記錄的指針，葉結點中将關鍵宇按大小順序排列，并且相鄰葉結點按大小順序互相連結起來。
• 所有分支結點(可視為索引的索引)中僅包含它的各個子結點( 即下一級的索引塊)中關鍵字的最大值及指向其子結點的指針。

下圖為一棵4 階B十樹。可以看出，分支結點的某個關鍵字是其子樹中最大關鍵字的副本。通常在B+樹中有兩個頭指針:一個指向根結點，另一個指向關鍵子最小的葉結點。是以，可以對B+樹進行兩種查找運算:一種是從最小關鍵字開始的順序查找，另一種是從根結點開始的多路查找。

• B+樹的查找、插入和删除操作和B 樹的基本類似。隻是在查找過程中， 非葉結點上的關鍵宇值等于給定值時并不終止，而是繼續向下查找， 直到葉結點上的該關鍵字為止。是以，在B+樹中查找時，無論查找成功與否，每次查找都是一條從根結點到葉結點的路徑。 

3.1，m 階的B+樹與m階的B樹的主要差異

• 在B+樹中， 具有n 個關鍵字的結點隻含有n 棵子樹，即每個關鍵于對應一棵子樹;而在B 樹中，具有n 個關鍵字的結點含有n 十l 棵子樹。
• 在B+樹中，每個結點(非根内部結點)的關鍵宇個數n 的範圍是

  

   <=n <=m (根結點:1<=n <=m) ; 在B 樹中，每個結點(非根内部結點〉的關鍵字個數n 的範圍是

  

  -1<=n<=m - 1 (根結點: 1 <=n<=m 一1)。
• 在B+樹中， 葉結點包含資訊，所有非葉結點f夾起索引作用，非葉結點中的每個索引項隻含有對應子樹的最大關鍵字和指向該子樹的指針，不含有該關鍵字對應記錄的存儲位址。
• 在B+樹中， 葉結點包含了全部關鍵字， 即在非葉結點中出現的關鍵字也會出現在葉結于是中;而在B樹中，葉結點包含的灰飛建字和其他結點包含的關鍵宇是不重複的。

參考資料：

[1] https://www.jianshu.com/p/174a815b1495