昨天介紹了 m-way search tree，也提到了他的大問題：有可能斜曲的問題。今天我們要把它平衡化，也就是 B-tree

B-tree of order m (m > 2) 的定義

B-tree of order m 定義為：

1. root 的 degree: 2 <= degree <= m
2. **其他 root 的 degree: ceiling(m/2) <= degree <= m **
3. node 的 key 數為 degree - 1，且由小到大排序 ascending order

特殊的 B-tree

1. B-tree of order 3
   根據定義：
   root 的 degree: 2 <= degree <= 3
   其他 root 的 degree: ceiling(3/2) = 2 <= degree <= 3
   因此，整棵樹只有 degree 為 2 的點及 degree 為 3 的點，因此 B-tree of order 3 又叫做 2-3 tree
   
2. B-tree of order 4
   根據定義：
   root 的 degree: 2 <= degree <= 4
   其他 root 的 degree: ceiling(4/2) = 2 <= degree <= 4
   因此，整棵樹只有 degree 為 2 的點、degree 為 3 的點及 degree 為 3 的點，因此 B-tree of order 3 又叫做 2-3-4 tree
   

B-tree 節點數與鍵值（key）數

假設 B-tree 的高度為 h

1. 最大節點數與鍵值數：與 m-way search tree 相同，因上限皆為 m。
2. 最小節點數：因為 B-tree 有規定節點 degree 的下限，因此我們要來計算一下最少節點的情況。
   我們先假設 ceiling(m/2) = K，且 root level = 1
   root 最多 1 個節點
   level-2 最多 2 個節點，因為 root degree 最少為 2
   level-3 最多 2 * K 個節點，上層節點每個衍生出 K 個節點
   level-4 開始以此類推
   直到 level-h ，有 2 * (k^(h-2))
   因此，最小節點數有 1 + 2 * (k^(h-1) - 1 / (k - 1))，透過等比級數的公式可以得知
3. 最小鍵值數
   這就比較好想了：
   root 最少一個鍵值
   再來第二層開始，每個節點皆有 k - 1 個 key
   因此我們拿剛剛的節點數來計算：1 + (2 * (k^(h-1) - 1 / (k - 1)) * (k - 1))
   分母消掉後，最小鍵植數為 1 + 2 * (k^(h-1) - 1 / (k - 1))，可以將 2 乘進去，得到 (2k^(h-1) / (k - 1)) - 1，即為最小鍵值數。

明天來說 B-tree 的新增刪除，非常重要，與前面的 BST 所學操作不同喔