圖論演算法ch18 — B-Trees

為什麼要有B-tree？

他是可以控制高度的搜尋樹
會配合磁碟的特性做最佳化

什麼是B-tree？（B-tree的性質）

B-tree

1. 每個點，t≤child的個數≤2t
2. root：1≤key的個數≤2t-1
   非root：t-1≤key的個數≤2t-1
3. 有n[x]個keys，就會有n[x]+1個children
4. 所有leaves都有相同的深度
5. t，題目會給

B-tree的高度

6. B-tree的高度為 logt n（以t為底）

Search搜尋

跟binary tree很像，只是在每個節點都要比n[x]個keys
在節點內，由左往右，一個一個比

search 的 code & run time

Insert插入

從root開始往下找
只要遇到滿了的節點(有2t-1個keys)
就要split(把中間的key往上放，剩下的key分成兩邊)
最後再放到leaf
insert的比較都是，由右往左比

split的概念

insert多個keys

insert的所有code

Delete刪除

從root開始往下走，確保經過的節點都有t個key

case1. 節點x是leaf 而且 k在節點x

case 1

case2. 節點x是internal node(中間的節點) 而且 k在節點x

case 2a
雖然有t個，但不可以直接刪
左子有t個，找左子最大來取代k
將左子最大刪除

case 2a

case 2b
雖然有t個，但不可以直接刪
右子有t個，找右子最小來取代k
將右子最小刪除

case 2b

case 2c
雖然有t個，但不可以直接刪
左子、右子都只有t-1個keys
左子、右子、k合併

case 2c

case3. 節點x是internal node(中間的節點) 而且 k在節點x的子樹中

case 3a
x的child 有t個keys
直接用遞迴去刪

case 3b
x的child 只有t-1個keys
若兄有t個，跟兄借
若弟有t個，跟弟借

case 3b

case 3c
x(P)的child(C L) 只有t-1個keys
且兄＆弟有t個，合併

case 3c