前言

強烈建議進入本章節前，先閱讀前一篇介紹 m-way search tree 的文章，才能比較好的銜接本章節。此文會先點出 B Tree of order m 的定義，以及某些別稱，再來好好談此資料結構的操作

定義

簡單的說明一下，B tree of order m 就是 Balanced m-way search tree，Balanced 的意思就代表失敗的節點會在同一 Level 上
若 B tree of order m 不為空的話，先分為 2 個 case 來定義他

1. root's degree & key : 2 <= deg <= m , 1 <= key <= m-1
2. other node degree & key : (m/2)取上限 <= deg <= m , (m/2)取上限 <= key <= m-1

再加上我們前面提過的，失敗的節點會在同一 Level 上，就形成了 B Tree of order m 的定義啦～

某些特殊結構的別稱

B tree of order 3 (2 3 Tree)

我們將 m=3 代入定義內，可以發現

1. Root 2 <= deg <= 3
2. other node 2 <= deg <= 3

Root 與 other node 所受的限制是一樣的，deg 都只能是 2 和 3，因此也將 B tree of order 3 稱作 2 3 Tree

B tree of order 4 (2 3 4 Tree)

我們將 m=4 代入定義內，可以發現

1. Root 2 <= deg <= 4
2. other node 2 <= deg <= 4

Root 與 other node 所受的限制是一樣的，deg 都只能是 2 3 4，因此也將 B tree of order 4 稱作 2 3 4 Tree

操作

insert X

先將 X 放入 Search tree 中適當位置

1. 如果該 node 內 key 數量沒有超過限制，就可以直接置入
2. 如果該 node 內 key 數量超過限制即overflow，則要進行 Split 動作

split : 先將該 node 內第 (m/2)取上限的 key，往上拉到父節點，此 node 分為兩個 nodes
因為父節點會多出 1 個 key，因此要檢查父節點有沒有 overflow

delete X

先判斷刪除 x 是否是葉節點
如果是葉節點的話，將 x 刪除，判斷有沒有出現 underflow 的現象，如果兄弟節點可以借的話即作Rotation，若有則把父節點的 key 拉下來進行 combine

若不是葉節點，則將x刪除，以左子樹最大，或右子樹最小的key來取代(此key必定會是葉節點)，再針對葉節點檢查是否underflow，就跟原本的操作一樣囉