B樹和B+樹

本文轉載自 部落格

，因為題主寫的已經很詳細了。

還有，必須要強調一點，樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導緻查詢效率低下，隻有減少樹的深度，讓樹從“高瘦”變成“矮胖”就可以減少I/O次數，進而提高查詢效率（查找樹的每一個結點都要進行一次I/O）

B樹是為實作高效的磁盤存取而設計的多叉平衡搜尋樹。這個概念在檔案系統，資料庫系統中非常重要。當然，有關于B樹的産生，發展，結構等等方面的介紹已經非常詳細，是以本文隻是介紹有關于B樹和B+樹最核心的知識點，也算是我本人的學習筆記。至于詳細的資料，因為畢竟有着太多，是以不再贅述。可以向大家推薦一篇部落格：

從B樹、B+樹、B*樹談到R 樹

，這篇文章中，作者對于B樹系列資料結構的講解非常詳細，我的這篇部落格，也是大量參考了人家的很多例子和描述。

B樹

一、基本原理

首先，簡單說一下B樹産生的原因。B樹是一種查找樹，我們知道，這一類樹（比如二叉查找樹，紅黑樹等等）最初生成的目的都是為了解決某種系統中，查找效率低的問題。B樹也是如此，它最初啟發于二叉查找樹，二叉查找樹的特點是每個非葉節點都隻有兩個孩子節點。然而這種做法會導緻當資料量非常大時，二叉查找樹的深度過深，搜尋算法自根節點向下搜尋時，需要通路的節點也就變的相當多。如果這些節點存儲在外存儲器中，每通路一個節點，相當于就是進行了一次I/O操作，随着樹高度的增加，頻繁的I/O操作一定會降低查詢的效率。

這裡有一個基本的概念，就是說我們從外存儲器中讀取資訊的步驟，簡單來分，大緻有兩步：

1. 找到存儲這個資料所對應的磁盤頁面，這個過程是機械化的過程，需要依靠磁臂的轉動，找到對應磁道，是以耗時長。
2. 讀取資料進記憶體，并實施運算，這是電子化的過程，相當快。

綜上，對于外存儲器的資訊讀取最大的時間消耗在于尋找磁盤頁面。那麼一個基本的想法就是能不能減少這種讀取的次數，在一個磁盤頁面上，多存儲一些索引資訊。B樹的基本邏輯就是這個思路，它要改二叉為多叉，每個節點存儲更多的指針資訊，以降低I/O操作數。

二、基本結構

1. B樹的定義

有關于B樹概念的定義，不同的資料在表述上有所差别。我在這裡采用《算導》中的定義，用最小度

來定義B樹。一棵最小度為

的B樹是滿足如下四個條件的平衡多叉樹：

1. 每個節點最多包含

   

   個關鍵字；除根節點外的每個節點至少有

   

   個關鍵字（

   

   ），根節點至少有一個關鍵字；
2. 一個節點

   

   中的關鍵字按非降序排列：

   

   ；
3. 每個節點的關鍵字對其子樹的範圍分割。設節點

   

   有

   

   個指針，指向其

   

   棵子樹，指針為

   

   ，關鍵字

   

   為

   

   所指的子樹中的關鍵字，有

   

   成立；
4. 所有葉子節點具有相同的深度，即樹的高度

   

   。這表明B樹是平衡的。平衡性其實正是B樹名字的來源，B表示的正是單詞Balanced；

一個标準的B樹如下圖：

2. B樹的高度

我直接給出結論了：對于一個包含

個關鍵字(

)，最小度數

的B樹T，其高度

滿足如下規律：

在搜尋B樹時，很明顯，通路節點（即讀取磁盤）的次數與樹的高度呈正比，而B樹與紅黑樹和普通的二叉查找樹相比，雖然高度都是對數數量級，但是顯然B樹中

函數的底可以比2更大，是以，和二叉樹相比，極大地減少了磁盤讀取的次數。

三、搜尋算法

這裡，我直接用部落格

中的例子（因為這個例子非常好，也有現成的圖示，就直接拿來用，不再自己班門弄斧了），一棵已經建立好的B樹如下圖所示，我們的目的是查找關鍵字為29的檔案：

先簡單對上圖說明一下：

1. 圖中的小紅方塊表示對應關鍵字所代表的檔案的存儲位置，實際上可以看做是一個位址，比如根節點中17旁邊的小紅塊表示的就是關鍵字17所對應的檔案在硬碟中的存儲位址。
2. P是指針，不用多說了，需要注意的是：指針，關鍵字，以及關鍵字所代表的檔案位址這三樣東西合起來構成了B樹的一個節點，這個節點存儲在一個磁盤塊上

下面，看看搜尋關鍵字的29的檔案的過程：

1. 從根節點開始，讀取根節點資訊，根節點有2個關鍵字：17和35。因為17 < 29 < 35，是以找到指針P2指向的子樹，也就是磁盤塊3（1次I/0操作）
2. 讀取目前節點資訊，目前節點有2個關鍵字：26和30。26 < 29 < 30，找到指針P2指向的子樹，也就是磁盤塊8（2次I/0操作）
3. 讀取目前節點資訊，目前節點有2個關鍵字：28和29。找到了！（3次I/0操作）

由上面的過程可見，同樣的操作，如果使用平衡二叉樹，那麼需要至少4次I/O操作，B樹比之二叉樹的這種優勢，還會随着節點數的增加而增加。另外，因為B樹節點中的關鍵字都是排序好的，是以，在節點中的資訊被讀入記憶體之後，可以采用二分查找這種快速的查找方式，更進一步減少了讀入記憶體之後的計算時間，由此更能說明對于外存資料結構來說，I/O次數是其查找資訊中最大的時間消耗，而我們要做的所有努力就是盡量在搜尋過程中減少I/O操作的次數。

四、向B樹插入關鍵字

向B樹種插入關鍵字的過程與向二叉查找樹中插入關鍵字的過程類似，但是要稍微複雜一點，因為根據上面B樹的定義，我們可以看出，B樹每個節點中關鍵字的個數是有範圍要求的，同時，B樹是平衡的，是以，如果像二叉查找樹那樣，直接找到相關的葉子，插入關鍵字，有可能會導緻B樹的結構發生變化而這種變化會使得B樹不再是B樹。

是以，我們這樣來設計B樹種對新關鍵字的插入：首先找到要插入的關鍵字應該插入的葉子節點（為友善描述，設這個葉子節點為

），如果

是滿的（恰好有

個關鍵字），那麼由于不能将一個關鍵字插入滿的節點，我們需要對

按其目前排在中間關鍵字

進行分裂，分裂成兩個節點

；同時，作為分裂标準的關鍵字

​會被上移到

的父節點中，在

​插入前，如果

的父節點未滿，則直接插入即可；如果

的父節點已滿，則按照上面的方法對

的父節點分裂，這個過程如果一直不停止的話，最終會導緻B樹的根節點分裂，B樹的高度增加一層。

我用《算導》中的一個題目展示一下這種插入關鍵字的過程：

現在我們要将關鍵字序列：F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y依次插入一棵最小度為2的B樹中。也就是說，這棵樹的節點中，最多有3個關鍵字，最少有1個關鍵字。

第1步 ，F, S, Q可以被插入一個節點（也就是根節點）

第2步 ，插入關鍵字K，因為節點已滿，是以在插入前，發生分裂，中間關鍵字Q上移，建立了一個新的根節點：

第3步 ，插入關鍵字C:

第4步 ，插入關鍵字L，L應該被插入到根節點的左側的孩子中，因為此時該節點已滿，是以在插入前，發生分裂：

第5步 ，插入關鍵字H, T, V，這個過程沒有發生節點的分裂：

第6步 ，插入關鍵字W，W應該被插入到根節點的最右側的孩子中，因為此時該節點已滿，是以在插入前，關鍵字T上移，最右端的葉子節點發生分裂：

第7步 ，插入關鍵字M，M應該被插入到根節點的左起第2個孩子中，因為此時該節點已滿，是以在插入前，發生分裂，分裂之後，中間關鍵字K上移，導緻根節點發生分裂，樹高增加1：

第8步，同樣的道理，插入關鍵字R, N, P, A, B, X, Y：最終得到的B樹如下：

五、從B樹删除關鍵字

删除操作的基本思想和插入操作是一樣的，都是不能因為關鍵字的改變而改變B樹的結構。插入操作主要防止的是某個節點中關鍵字的個數太多，是以采用了分裂；删除則是要防止某個節點中，因删除了關鍵字而導緻這個節點的關鍵字個數太少，是以采用了合并操作。

下面分三種情況來讨論下删除操作是如何工作的，這個過程的順序是自根節點起向下周遊B樹

**Case - 1：**如果要删除的關鍵字

在節點

中，而且

是葉子節點，那麼直接删除

**Case - 2：**如果要删除的關鍵字

是内部節點，那麼分以下3種情況讨論：

(1) 如果

中前于

的子節點

中至少含有

個關鍵字，則找出

在以

​為根的子樹中的前驅

（前驅的意思是

​中比

小的關鍵字中最大的），然後在以

​為根的子樹中删除

，并在

中以

替代

(2) 如果上面的條件(1)不成立，也就是說，前于

的子節點中關鍵字的個數小于

了，那麼就去找後于

的子節點，記為

​。若

​中至少含有

​為根的子樹中的後繼

(大于

的關鍵字中最小的)，然後在以

。可以看出（2）是（1）的一個對稱過程

(3) 如果

​中的關鍵字個數都是

，則将

和

​合并後并入

，這樣

就失去了

和指向

​的指針，最後遞歸地從

中删除

**Case - 3：**如果要删除的關鍵字

不在目前節點

是内部節點（如果自上而下掃描到葉子都沒有這個關鍵字的話，那就說明要删除的關鍵字根本就不存在，是以此處隻考慮

是内部節點的情況），則首先确定包含

的

的子樹，我們這裡設為

​。如果

個關鍵字，那麼繼續掃描，尋找下一個要被掃描的子樹；如果

​中隻含有

個關鍵字，則需要分下面兩種情況進行操作：

至少有一個相鄰的兄弟比較"豐滿"（即這個兄弟至少有

個關鍵字）。則将

中的一個關鍵字降至

​，同時令

的最"豐滿"的兄弟中升一個關鍵至

。然後繼續掃描B樹，尋找

(2) 如果

​的兩個相鄰的兄弟都不"豐滿"（都隻有

個關鍵字）。則令

​和其一個兄弟合并，再将

的一個關鍵字降至新合并的節點。使之成為該節點的中間關鍵字。

舉個例子，就可以清晰看到上面說的這幾種删除的情況。拿下圖所示的最小度為3的B樹為例（即樹中除根和葉子之外的節點隻能有2，3，4，5四種情況的關鍵字個數）：

Step 1: 删除上圖中的關鍵字F，過程如下：先掃描根節點（含P），再掃描其左孩子（含CGM），發現豐滿，繼續掃描到左起第二個葉子，然後就是符合 Case - 1 的情況了。結果如下圖所示：

Step 2: 再删除M，此時遇到**Case - 2(1)**的情況，結果如下圖所示：

Step 3: 再删除G，G的前驅、後驅都是不豐滿的。也就是**Case - 2(3)**的情況，結果如下圖所示：

Step 4: 再删除D，掃描至含CL的節點後，發現它不豐滿，且他的兄弟也不豐滿。則将節點CL和TX合并，并降關鍵字P至新合并的節點。也就是**Case - 3(2)**的情況，結果如下圖所示，此時，樹高減1：

Step 5: 再删除B，也就是**Case - 3(1)**的情況，結果如下圖所示：

下面總結一下B樹的删除原理：

1. 基本原則是不能破壞關鍵字個數的限制；
2. 如果在目前節點中，找到了要删的關鍵字，且目前節點為内部節點。那麼，如果有比較豐滿的前驅或後繼，借一個上來，再把要删的關鍵字降下去，在子樹中遞歸删除；如果沒有比較豐滿的前驅或後繼，則令前驅與後繼合并，把要删的關鍵字降下去，遞歸删除；
3. 如果在目前節點中，還未找到要删的關鍵字，且目前節點為内部節點。那麼去找下一步應該掃描的孩子，并判斷這個孩子是否豐滿，如果豐滿，繼續掃描；如果不豐滿，則看其有無豐滿的兄弟，有的話，從父親那裡接一個，父親再找其最豐滿的兄弟借一個；如果沒有豐滿的兄弟，則合并，再令父親下降，以保證B樹的結構。

B+樹

B+樹的定義

B+樹是B樹的一種變形，它更适合實際應用中作業系統的檔案索引和資料庫索引。定義如下：（為和大多資料保持一緻，這裡使用階數

來定義B+樹，而不像之前的B樹中，使用的是最小度

來定義）

1. 除根節點外的内部節點，每個節點最多有

   

   個關鍵字，最少有

   

   個關鍵字。其中每個關鍵字對應一個子樹（也就是最多有

   

   棵子樹，最少有

   

   棵子樹）；
2. 根節點要麼沒有子樹，要麼至少有2棵子樹；
3. 所有的葉子節點包含了全部的關鍵字以及這些關鍵字指向檔案的指針，并且：

• 所有葉子節點中的關鍵字按大小順序排列
• 相鄰的葉子節點順序連結（相當于是構成了一個順序連結清單）
• 所有葉子節點在同一層

1. 所有分支節點的關鍵字都是對應子樹中關鍵字的最大值

比如，下圖就是一個非常典型的B+樹的例子。

B+樹和B樹相比，主要的不同點在以下3項：

1. 内部節點中，關鍵字的個數與其子樹的個數相同，不像B樹種，子樹的個數總比關鍵字個數多1個
2. 所有指向檔案的關鍵字及其指針都在葉子節點中，不像B樹，有的指向檔案的關鍵字是在内部節點中。換句話說，B+樹中，内部節點僅僅起到索引的作用，
3. 在搜尋過程中，如果查詢和内部節點的關鍵字一緻，那麼搜尋過程不停止，而是繼續向下搜尋這個分支。

根據B+樹的結構，我們可以發現B+樹相比于B樹，在檔案系統，資料庫系統當中，更有優勢，原因如下：

1. B+樹的磁盤讀寫代價更低

B+樹的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說I/O讀寫次數也就降低了。

1. B+樹的查詢效率更加穩定

由于内部結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。

1. B+樹更有利于對資料庫的掃描

B樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題，而B+樹隻需要周遊葉子節點就可以解決對全部關鍵字資訊的掃描，是以對于資料庫中頻繁使用的range query，B+樹有着更高的性能。

聚集索引和非聚集索引

聚集索引：

該索引中鍵值的邏輯順序決定了表中相應行的實體順序。

聚集索引确定表中資料的實體順序。聚集索引類似于電話簿，後者按姓氏排列資料。由于聚集索引規定資料在表中的實體存儲順序，是以一個表隻能包含一個聚集索引。但該索引可以包含多個列（組合索引），就像電話簿按姓氏和名字進行組織一樣。

非聚集索引：

該索引中索引的邏輯順序與磁盤上行的實體存儲順序不同。

索引是通過二叉樹的資料結構來描述的，我們可以這麼了解聚簇索引：索引的葉節點就是資料節點。而非聚簇索引的葉節點仍然是索引節點，隻不過有一個指針指向對應的資料塊。