Xóa trong B+ Tree trong cấu trúc dữ liệu

Xem xóa nút khỏi B+ Tree. Ví dụ B+ Tree:

Ví dụ B+ Tree

Xóa có 2 phần: tìm phần tử (giống query). Quy tắc: nút phải có ít nhất m/2 phần tử. Nếu xóa để lại < m-1, tự điều chỉnh. Nếu xóa hết nút, gộp con, nếu size = m thì tách 2, giá trị trung vị lên cha.

Ví dụ xóa 78. Hai con [75,77] và [78,85]. Xóa 78 ở lá, lấy 85, copy khóa 85 làm gốc cây con.

Thuật toán

BPlusTreeDelete(x, key)

Input: gốc cây, khóa xóa

Giả sử khóa có trong cây
Bắt đầu từ gốc, khớp chính xác 'key' đến lá.
Đường tìm: x1, x2, ..., xh (x1=gốc, xh=lá). xi cha của xi+1.
Xóa đối tượng khóa 'key' từ xh.
if h = 1 thì return (chỉ có gốc).
i := h
while xi underflow do
    if anh chị em liền kề s của xi có ≥ m/2+1 phần tử thì
        phân phối lại đều giữa s và xi.
        khóa k trong cha xi-1 thay đổi.
        if xi không phải lá thì
            k kéo xuống xi, khóa từ s đẩy lên chỗ k
        else
            k thay bằng khóa trong s
        return
    else
        gộp xi với s. Xóa con trỏ con trong xi-1.
        if xi là nút nội thì
            kéo khóa trong xi-1 (trước đây chia xi và s) vào nút mới
            xi và s gộp thành nút mới xi
        else
            xóa khóa đó trong xi-1
        i := i - 1
    end if
done