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

ตัวอย่าง B+ Tree

กระบวนการลบ (2 ส่วน)

1. ค้นหาองค์ประกอบ (เหมือน Query)
2. ลบพร้อมรักษาเงื่อนไข: โหนดต้องมีอย่างน้อย m/2 องค์ประกอบ

ถ้าลบแล้วเหลือ < m-1 ให้ Adjust ถ้าลบโหนดทั้งโหนด ให้ Merge Children ถ้าขนาด = m ให้ Split กลับ 2 ส่วน Median ขึ้นไป

ตัวอย่าง: ลบ 78

มี Children 2 ตัว: [75, 77] และ [78, 85] ลบ 78 จาก Leaf ก่อน แล้วนำ 85 ขึ้น Copy Key 85 เป็น Root ของ Subtree

อัลกอริทึม

BPlusTreeDelete(x, key)
Input: Root, Key to delete
Assume key exists
Start from root, exact match till leaf. Path: x₁, x₂, ..., xₕ (x₁=root, xₕ=leaf)
Delete key from xₕ. If h=1 return.
i := h
while xᵢ underflows do
    if sibling s of xᵢ has ≥ m/2+1 elements then
        redistribute evenly between s and xᵢ
        update key k in parent xᵢ₋₁
        if xᵢ non-leaf: drag k down to xᵢ, push key from s up
        else: replace k with key from s
        return
    else
        merge xᵢ with sibling s. Delete child pointer in xᵢ₋₁
        if xᵢ internal: drag dividing key from xᵢ₋₁ into new node
        else: delete that key in xᵢ₋₁
        i := i - 1
    end if
done