ตัวอย่าง B-Tree
การแทรก
คล้าย BST แต่มีกติกา: โหนดมี m Children, m-1 Elements แทรกแล้ว < m-1 → ใส่ตรง แทรกแล้ว = m-1 → หา Median ของทั้งหมด Median ขึ้น Root ทำซ้ำ แล้ว Split ซ้าย/ขวา
ตัวอย่าง: แทรก 79
Root 56 → Right Subtree < 81 → Left Subtree แทรกใน Root ได้ [66, 78, 79] Median = 78 ขึ้นไป Root กลายเป็น [79, 81] Split เป็น 2 โหนด: 66 และ 79
อัลกอริทึม
BTreeInsert(root, key)
Input: Root, Key (assume not present)
x := Read root
if x full:
y := new node, z := new node
locate middle object oᵢ in x
move left of oᵢ to y, right of oᵢ to z
if x index node: move child pointers
x→child[1] := y, x→child[2] := z
end if
