B+ Tree Insertion ในโครงสร้างข้อมูล

ตัวอย่าง B+ Tree

การแทรก

คล้าย B-Tree แทรกที่ Leaf ถ้าอยู่ใน Internal Node จะมี Copy อยู่ที่ Leaf (Right Child ของตัวเอง)

ตัวอย่าง: แทรก 65 > 60 และ < 75 เข้า Middle Subtree แทรกหลัง 63 โหนดแยก 2 ส่วน 65 ขึ้นไป และ 65 อยู่ที่ Right Node ด้วย

อัลกอริทึม

BPlusTreeInsert(root, key)
Input: Root, Key to insert (assume not present)
Search to leaf. Path: x₁...xₕ. Insert key into xₕ.
i := h
while xᵢ overflows do
    divide xᵢ into 2 nodes, move larger half to new node p
    if xᵢ leaf: link p into leaf linked list
    identify key k to insert to parent with child pointer to p
    if xᵢ leaf: copy up (smallest key in p → k)
    else: push up (smallest key in p → k in parent)
    if i = 0: create new root with k, children xᵢ and p; return
    else: insert k and child pointer to p into xᵢ₋₁; i := i-1
    end if
done