B Tree
[資料結構]B-tree - Chacha - Medium
【資料結構】平衡搜索樹 - 紅黑樹、B樹(2-3,2-3-4樹)、B+樹 | Z1N's house
Binary Search Tree 有個致命缺點，就是當這個樹狀資料結構不平衡時會使這個資料結構喪失其優勢
Use 平衡搜索樹（Balanced Search Tree）
- AVL Tree
- Red Black Tree 紅黑樹
- B Tree (Family)
For B Tree
- 每個 node 最多有
m個子樹 (最多m - 1個元素) (misorder) - 所有 leaf 在同一層上
- internal 內部節點
當插入資料會超過此節點所限制數量 m 時，B-tree 會進行分裂
左小右大
Insertion 插入
所有的插入都從根節點開始
如果節點擁有的元素數量小於最大值 m 插入到這一節點，且保持節點中元素有序
否則，這一節點已經滿了，平均地分裂成兩個節點：
- 從該節點的原有元素和新的元素中選擇出中位數
- 小於這一中位數的元素放入左邊節點，大於這一中位數的元素放入右邊節點，中位數作為分隔值
- 分隔值被插入到父節點中，這可能會造成父節點分裂，分裂父節點時可能又會使它的父節點分裂，以此類推
- 如果沒有父節點（這一節點是根節點），就建立一個新的根節點（增加了樹的高度）
Deletion 刪除
TODO