Chèn vào B-Tree trong cấu trúc dữ liệu

Xem chèn vào B-Tree. Ví dụ B-Tree:

Ví dụ B-Tree

Chèn tương tự BST nhưng có quy tắc. Nút có m con, m-1 khóa. Chèn vào nút: nếu khóa < m-1 → chèn trực tiếp. Nếu đã m-1 → lấy tất cả khóa + khóa mới, lấy trung vị, trung vị lên cha (đệ quy), tách 2 nửa thành 2 nút.

Ví dụ chèn 79. > 56 → cây con phải. < 81 → cây con trái. Chèn vào nút. Nay có 3 khóa [66,78,79]. Trung vị 78 → 78 lên cha. Nút gốc thành [79,81], tách 2 nút: 66 và 79.

B-Tree sau chèn 79:

Thuật toán

BTreeInsert(root, key)−

Input: gốc, khóa chèn. Giả sử khóa chưa có.

x := Read root
if x đầy thì
    y := nút mới
    z := nút mới
    Tìm đối tượng giữa oi trong x, chuyển bên trái oi vào y
    Chuyển bên phải oi vào z
    nếu x là nút chỉ mục thì
        chuyển con trỏ con cho phù hợp
        x->child[1] := địa chỉ y
        x->child[2] := địa chỉ z
    end if