B樹

B樹的定義（為什么需要B樹）

B樹是一類樹，也稱為了 平衡的多路查找樹。包括B樹、B+樹、B*樹等，是一棵 自平衡的搜索樹，它類似普通的平衡二叉樹，不同的一點是B樹允許每個結點有更多的子結點。B樹是 專門為外部存儲器設計的，如磁盤，它對于讀取和寫入大塊數據有良好的性能，所以一般被用在 文件系統 及 數據庫 中。

傳統用來搜索的平衡二叉樹有很多，如 AVL 樹，紅黑樹等。這些樹在一般情況下查詢性能非常好，但當數據非常大的時候它們就無能為力了。

原因是 當數據量非常大時，內存不夠用，大部分數據只能存放在磁盤上，只有需要的數據才加載到內存中。一般而言內存訪問的時間約為 50 ns，而磁盤在 10 ms 左右。速度相差了近 5 個數量級，磁盤讀取時間遠遠超過了數據在內存中比較的時間。這說明程序大部分時間會阻塞在磁盤 IO 上。

那么我們如何提高程序性能？減少磁盤 IO 次數，像 AVL 樹，紅黑樹這類平衡二叉樹從設計上無法“迎合”磁盤。

B樹的特點

索引的效率依賴于磁盤 IO 的次數，快速索引需要有效的減少磁盤 IO 次數，如何快速索引呢？索引的原理 其實是不斷的縮小查找范圍，就如我們平時用字典查單詞一樣，先找首字母縮小范圍，再第二個字母等等。

平衡二叉樹是每次將范圍分割為兩個區間。為了更快，B樹每次將范圍分割為多個區間，區間越多，定位數據越快越精確。

那么如果結點為區間范圍，每個結點就較大了。所以新建結點時，直接申請頁大小的空間（磁盤是按頁分的，一般為 512 Byte（字節）。磁盤 IO 一次讀取若干個頁，具體大小和操作系統有關，一般為 4k，8k 或 16k），計算機內存分配是按頁對齊的，這樣就實現了一個結點只需要一次 IO。

具體來說，拿一棵m階B樹為例，滿足如下性質

書中每個結點最多有m棵子樹（即最多含有m-1個關鍵字）

解釋： m 階B樹，它結點的指針域最多有 m 個，每個指針域指向一棵子樹；兩個指針域之間必須由一個 key 值將兩個指針域隔開

若根結點不是葉子結點，則至少有兩棵樹，根結點關鍵字數量$[1,m?1]$，子樹數量$[2,m]$

解釋： 根結點如果不是葉子結點（在B樹中，葉子結點是沒有信息的，也就是null），那么根結點至少有兩個指針域（換句話說，至少有兩棵子樹）。如果沒有兩棵子樹怎么辦（比如，只有兩個key），那么，將這兩個key合并為一個結點（如果無法合并，比如m=2，那就無法構成B樹）。B樹的根結點至少有一個關鍵字，最多有m-1個關鍵字（也就是有m個指針域，m棵子樹）

除根結點外的所有非葉結點至少有 $\frac{m}{2}(向上取整)$ 棵子樹（即最少含有 $\frac{m}{2}(向上取整)?1$ 個關鍵字）,除根結點外的所有非葉結點關鍵字數量$[\frac{m}{2}(向上取整)?1,m?1]$，子樹數量 $[\frac{m}{2}(向上取整),m]$

解釋： 多有除了根結點的非葉子結點，子樹數量的下限是被控制的，不像根結點一樣，最少可以有2棵子樹，而是最少要有 $\frac{m}{2}(向上取整)$ 棵子樹

同一結點內有序，父子結點之間滿足二叉排序樹的排列規則

所有葉子結點出現在同一層次上，且不帶信息

圖示為一棵B樹。如果要尋找 30 的話，比較根結點 {20, 50, 70}，因為 $20\le 30\le 50$，走①號線；得到的子結點 {25, 30, 40}，找到了值為 30 的結點

綜合來說： B樹在提高效率就像二叉排序樹一樣，不同的是，面對不同階的樹，其結點上的值可能不止一個

那么，每棵B樹的結點多少個是如何決定的呢？

比如說，對于任意一棵包含n（n≥1）個關鍵字、高度為h、階數為m的B樹：

也就是說，這一棵B樹的結點中的值的個數在 $[1,m?1]$

一棵B樹的高的范圍為
$$h\in [lo{g}_m(n+1),lo{g}_{\frac{m}{2}}(\frac{n+1}{2})+1](\frac{m}{2}向上取整)$$
例如：一棵3階B樹，有8個結點，那么它的 h∈[2,3.17]

、

做一個思考，把100挪到90以下可以嗎？為什么？

（答案顯然是不可以的，首先，不滿足第3條，即非根結點需要的子樹是$[\frac{m}{2}(取上限),m]$，在本示例中為$[2,3]）$ ,把100挪到90以下,90只有一棵子樹了；其次不滿足第5條，即葉子結點在同一層)

B樹的查找

接下來讓我們來看看B樹的查找。

總的來說B樹的查找分為兩個基本操作：

在B樹中尋找結點

在結點內找關鍵字

下面，假設每個結點有 n 個 key值，被分割為 n+1 個區間，注意，每個 key 值緊跟著 data 域，這說明B樹的 key 和 data 是聚合在一起的。這里給出一棵B樹




一般而言，根結點都在內存中，B樹以每個結點為一次磁盤 IO，比如上圖中，若搜索 key 為 25 結點的 data，首先在根結點進行二分查找（因為 keys 有序，二分最快），判斷 key 25 小于 key 50，所以定位到最左側的結點，此時進行一次磁盤 IO，將該結點從磁盤讀入內存，接著繼續進行上述過程，直到找到該 key 為止。

參考代碼

Data* BTreeSearch(Root *node, Key key) {Data* data;if(root == NULL)return NULL;// 二分法查找目標keydata = BinarySearch(node);if(data->key == key){return data;}else{// 若沒有找到，對磁盤進行一次IO操作node = ReadDisk(data->next);BTreeSearch(node, key);} }

B樹的插入

與二叉查找樹相比，B樹的插入就復雜得多了。因為B樹的定義和限制就決定了這一點。

下面用圖片的方式，給大家介紹B樹插入過程中需要注意的問題

這是一棵3階B樹，給出一組關鍵字{20, 30, 50, 52, 60, 68, 70}，根據B樹的性質，根結點的關鍵字數量調整范圍為[1,2]，其他非葉結點關鍵字數量調整范圍為[1,2]

step1： B樹為空，20插入，作為根結點，此時，根結點僅1個關鍵字；然后30插入，由于比20大，所以插入20的右邊，此時，根結點關鍵字個數為2個，滿足B樹要求

step2： 50插入，作為根結點，此時，根結點有3關鍵字，不滿足B樹的定義要求，所以需要分裂；按B樹的分裂方法，應將中間的數提出，作為左右關鍵字的父結點，左右關鍵字作為其子結點，如下圖。

step3： 52插入，52比30大，來到右邊的子樹，52有比50大，所以插入到50右邊。此時這個結點的關鍵字數量為2，滿足B樹定義要求。

step4： 60插入，52比30大，來到右邊的子樹，60有比52大，所以插入到52右邊。但此時，這個結點的關鍵字數量為3，不滿足B樹定義要求。按照B樹分裂原則，將中間值52提出作為左右關鍵字的父結點，左右關鍵字作為52的子結點，如下圖。

step5： 68插入，68比52大，來到右邊的子樹，68有比60大，所以插入到60右邊。此時這個結點的關鍵字數量為2，滿足B樹定義要求。

step6： 最后，70插入，70比52大，來到右邊的子樹，70有比68大，所以插入到68右邊。此時這個結點的關鍵字數量為3，不滿足B樹定義要求。按照B樹分裂原則，將中間值68提出作為左右關鍵字的父結點，左右關鍵字作為68的子結點，如下圖2。但此時，他們的父結點，也是根結點的關鍵字數量為3，不滿足B樹定義要求。按照B樹分裂原則，將中間值52提出作為左右關鍵字的父結點，左右關鍵字作為52的子結點，如下圖3 。

最后濃縮提煉總結

檢查插入結點后，結點關鍵字是否大于B樹定義的結點關鍵字上限

如果超過上限，那就采用結點分裂，將中間的結點作為左右關鍵字的父結點

之后再次檢查，提出后結點進入父結點后，該結點關鍵字是否大于B樹定義的結點關鍵字上限

如果超過上限，那就采用結點分裂，將中間的結點作為左右關鍵字的父結點（1,2循環，加一個檢查）

B樹的刪除

相對來說，B樹的刪除較為復雜，不過原理都是類似的，就是滿足B樹的定義。也就是說，最基本的一點，要是刪除后的結點中的關鍵字個數≥ $\frac{m}{2}(向上取整)?1$ ，因此不可避免的，在刪除的過程中，涉及結點的合并問題。

根據刪除的關鍵字位置不同，可以分為關鍵字 在終端結點上 和 不在終端結點上

下面同樣結合圖片說明B樹的刪除是一個怎樣的過程（所舉的例子都是3階B樹，也就是說，B樹的根結點的關鍵字數量范圍為$[1,2]$，非根非葉子結點的關鍵字數量范圍為 $[1,2]$）。

1. 如果刪除的關鍵字在終端結點上

① 結點內關鍵字數 大于 $\frac{m}{2}(向上取整)?1$ ，這是刪除這個關鍵字不會被破壞B樹的定義要求，所以直接刪除。

如下圖，刪除9，直接刪除

② 結點內關鍵字數 等于 $\frac{m}{2}(向上取整)?1$ ，并且其左右兄弟結點存在關鍵字數大于 $\frac{m}{2}(向上取整)?1$ 的結點，則去兄弟結點中借關鍵字。

如下圖，刪除2，由于結點中的關鍵字數量 等于 $\frac{m}{2}(向上取整)?1=1$，恰好其兄弟結點{7,9}的關鍵字大于1，向兄弟結點借一個關鍵字，且在調整的時候需要按照大小順序進行排序。

③ 結點內關鍵字數 等于 $\frac{m}{2}(向上取整)?1$ ，并且其左右兄弟結點不存在關鍵字數大于 $\frac{m}{2}(向上取整)?1$ 的結點，則需要對結點進行合并。

如下圖，刪除16，由于結點中的關鍵字數量 等于 $\frac{m}{2}(向上取整)?1=1$，但是其兄弟結點的關鍵字均等于1，所以不存在像兄弟結點借一個關鍵字這樣的情況。所以需要進行結點合并。

合并：把上一層的結點取關鍵字與下一層結點合并。這種合并方式不唯一。

如方案①是把父結點的14與11合并；方案②是把父結點的20與22合并

2. 如果刪除的關鍵字不在終端結點上

需要先轉換成在終端結點上，在按照在終端結點上的情況來分別考慮對應的方法

這里介紹一個概念，就是相鄰關鍵字。

相鄰關鍵字就是對于不在終端結點上的關鍵字，它的相鄰關鍵字使其其 左子樹中最大的關鍵字 或者 右子樹中最小的關鍵字

第一種情況：存在關鍵字數量大于 $\frac{m}{2}(向上取整)?1$（這里等于1） 結點的左子樹和右子樹，在對應子樹上找到該關鍵字的相鄰關鍵字，然后將相鄰關鍵字替換待刪除關鍵字

Step1：找出這個待刪除關鍵字的相鄰關鍵字，比如下圖中10的相鄰關鍵字急救室9和11，其實就是這個大小序列中該關鍵字的 直接前驅或者是直接后繼關鍵字

Step2：將這個待刪除的關鍵字和這個相鄰關鍵字互換

Step3：這是就回到了刪除終端結點的操作

第二種情況：存在關鍵字數量均等于 $\frac{m}{2}(向上取整)?1$ （這里等于1），則將這兩個子樹結點合并，然后刪除待刪除關鍵字

Step1：首先觀察待刪除結點14，發現它的左右子樹中關鍵字均等于1

Step2：將14的左右子樹合并為{11,6}

Step3：刪除14，然后將{11,6}結點作為20的左結點

B+樹

B+樹的概念

B+樹是B樹的變種，它與B樹的不同之處在于：

• 在B+樹中，key 的副本存儲在 內部結點，真正的 key 和 data 存儲在葉子結點上 。
• n 個 key 值的結點指針域為 n 而不是 n+1。

因為內結點并不存儲 data，所以一般B+樹的葉結點和內結點大小不同，而B-樹的每個結點大小一般是相同的，為一頁。

為了增加 區間訪問性，一般會對B+樹做一些優化。

如下圖帶順序訪問的B+樹。

B+樹的特點

一棵m階的B+樹需滿足下列條件

每個分支結點最多有m棵子樹（子結點）（與B樹一樣）

非葉根結點至少有兩棵子樹，其他分支結點至少有$\frac{m}{2}(向上取整)$ 棵子樹（與B樹一樣）

結點的子樹個數與關鍵字個數相等（與B樹不一樣，B樹的子樹比關鍵字多1）

所有葉結點包含全部關鍵字以及指向相應記錄的指針業界點鐘將關鍵字按大小順序排序，并且相鄰葉結點按大小順序線連接起來

解釋：B+樹葉結點兩兩相連可大大增加區間訪問性，可使用在范圍查詢等，而B-樹每個結點 key 和 data 在一起，則無法區間查找。

根據空間局部性原理：如果一個存儲器的某個位置被訪問，那么將它附近的位置也會被訪問

B+樹可以很好的利用局部性原理，若我們訪問結點 key為 50，則 key 為 55、60、62 的結點將來也可能被訪問，我們可以利用磁盤預讀原理提前將這些數據讀入內存，減少了磁盤 IO 的次數。 （根本目的）

當然B+樹也能夠很好的完成范圍查詢。比如查詢 key 值在 50-70 之間的結點。

所有分支結點（可視為索引的索引）中僅包含它的各個子結點（即下一級的索引快）中關鍵字的最大值及指向其子結點的指針

解釋：B+非葉結點只做索引，沒有含該關鍵字對應的存儲信息

同樣的m階B樹與m階B+樹有什么區別

B樹B+樹

n個關鍵字的結點有n+1棵子樹	n個關鍵字的結點有n棵子樹
每個結點（非根、內部）的關鍵字個數范圍為$[\frac{m}{2}?1(向上取整),m?1]$ 根結點的關鍵字個數范圍為[1,m-1]	每個結點（非根、內部）的關鍵字個數范圍為$[\frac{m}{2}(向上取整),m]$ 根結點的關鍵字個數范圍為[1,m]
每個結點的關鍵字都是包含全部信息的，也就是說，每個結點既包含了該關鍵字的data域，又包含了關鍵字的指針域（key）	葉結點包含信息，所有非葉結點均起索引作用，非葉結點中的每個索引只含對應字數的最大關鍵字和指向該子樹的指針，并不含該關鍵字對應的存儲信息。
葉結點包含的關鍵字與其他結點包含的關鍵字是不重復的	葉結點包含了全部的關鍵字，也就是說，在非葉結點中出現的關鍵字也會出現在葉結點中
時間復雜度最好是O(1)	時間復雜度固定為$lo{g}_n$
每個結點 key 和 data 在一起，則無法區間查找	葉結點兩兩相連可大大增加區間訪問性，可使用在范圍查詢等
	更適合外部存儲，由于內結點無 data 域，每個結點能索引的范圍更大更精確
B樹為有序數組+平衡多叉樹	而B+樹為有序數組鏈表+平衡多叉樹

不同的數據庫使用不同的樹的原因在哪里

1. 為什么 MongoDB 使用B-樹

MongoDB 是一種 nosql，也存儲在磁盤上，被設計用在數據模型簡單，性能要求高的場合。性能要求高，看看B/B+樹的區別第一點：

B+樹內結點不存儲數據，所有 data 存儲在葉結點導致查詢時間復雜度固定為 log n。而B-樹查詢時間復雜度不固定，與 key 在樹中的位置有關，最好為O(1)

我們說過，盡可能少的磁盤 IO 是提高性能的有效手段。MongoDB 是聚合型數據庫，而 B-樹恰好 key 和 data 域聚合在一起。

2. 為什么 Mysql 使用B+樹

Mysql 是一種關系型數據庫，區間訪問是常見的一種情況，而 B-樹并不支持區間訪問（可參見上圖），而B+樹由于數據全部存儲在葉子結點，并且通過指針串在一起，這樣就很容易的進行區間遍歷甚至全部遍歷

B+樹葉結點兩兩相連可大大增加區間訪問性，可使用在范圍查詢等，而B-樹每個結點 key 和 data 在一起，則無法區間查找

B+樹的查詢效率更加穩定，數據全部存儲在葉子結點，查詢時間復雜度固定為 O(log n)

B+樹更適合外部存儲。由于內結點無 data 域，每個結點能索引的范圍更大更精確

B+樹更適合關系型數據庫

總結

以上是生活随笔為你收集整理的【数据结构-查找】4.五千字干活长文带你搞懂——B树和B+树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。