數據結構: B-Tree 簡介及插入

02-15

在之前的文章中我們介紹過AVL樹，紅黑樹，它們都屬於二叉樹，即每個節點最多只能擁有2個子節點，而B-tree（B樹）的每個節點可以擁有2個以上的子節點，所以我們簡單概括一下：B-tree就是一顆多路平衡查找樹，它廣泛應用於資料庫索引和文件系統中。

首先我們介紹一下一顆 m 階B-tree的特性，那麼這個 m 階是怎麼定義的呢？這裡我們以一個節點能擁有的最大子節點數來表示這顆樹的階數。舉個例子，如果一個節點最多有 n 個key，那麼這個節點最多就會有 n+1 個子節點，這棵樹就叫做 n+1（m=n+1）階樹。一顆 m 階B-tree包括以下5條特性：

每個節點最多有 m 個子節點
除根節點和葉子節點，其它每個節點至少有 [m/2] （向上取整的意思）個子節點
若根節點不是葉子節點，則其至少有2個子節點
所有NULL節點到根節點的高度都一樣
除根節點外，其它節點都包含 n 個key，其中 [m/2] -1 <= n <= m-1

這些特性可能看著不太好理解，下面我們會介紹B-tree的插入，在插入節點的過程中我們就會慢慢理解這些特性了。B-tree的插入比較簡單，就是一個節點至下而上的分裂過程。下面我們具體以一顆4階樹來展示B-tree的插入過程。

首先我們插入 200，300，400，沒有什麼問題，直接插入就好。

| 200 | 300 | 400 |

現在我們接著插入500，這個時候我們發現有點問題，根據定義及特性1我們知道一顆4階B-tree的每個節點最多只能有3個key，插入500後這個節點就有4個key了。

| 200 | 300 | 400 | 500 |

這個時候我們就需要分裂，將中間的key上移到父節點，左邊的作為左節點，右邊的作為右節點，如下圖所示：

這個時候我們是不是就明白特性3了，如果根節點不是葉子節點，那麼它肯定發生了分裂，所以至少會有2個子節點。同樣我們接著插入600，700，800，900插入過程如下圖所示：

現在根節點也已經滿了，如果我們繼續插入910，920，會怎樣呢？根節點就會繼續分裂，樹繼續向上生長。看下圖：

通過整個的插入過程我們也會發現，B-tree和二叉樹的一個顯著的區別就是，B-tree是從下往上生長，而二叉樹是從上往下生長的。現在我們想想特性2和特性5是為什麼？首先我們知道子節點的個數是等於key的數目+1，然後一個節點達到m個key後就會分裂，所以分裂後的節點最少能得到 m/2 - 1個key 。為啥還要減一呢？因為還要拿一個作為父節點。所以這個節點最少回擁有 m/2 - 1 + 1 = m/2 個子節點。同樣得到特性5，因為最少有m/2個子節點，所以最少就含有m/2-1個key，m 階樹，每個節點存到了m個key就會分裂，所以最多就有 m-1個key。

根據以上特性我們能推出一棵含有N個總關鍵字數的m階的B-tree樹的最大高度h的值,

樹的高度h: 1， 2， 3 ， 4 ，.......... ， h

節點個數s: 1， 2， 2*(m/2)， 2*(m/2)(m/2)， ........ ，2*(m/2)的h-2次方

s = 1 + 2(1 - $(m/2)^{h-1}$ )/(1- (m/2))

N = 1 + s * ((m/2) - 1) = 2 * ( $(m/2)^{h-1}$ ) - 1

h = log┌m/2┐((N+1)/2 )+1

好就到這吧，下次我們在介紹 B-tree的應用及刪除。