Xem chèn vào B+ Tree. Ví dụ B+ Tree:
Ví dụ B+ Tree
Chèn tương tự B-Tree: phần tử mới lưu ở lá. Nếu có ở nút nội, cũng xuất hiện ở lá như con phải của nó.
Ví dụ chèn 65. 65 > 60 và < 75 → vào cây con giữa. Chèn vào nút sau 63, nút tách 2, 65 lên cha, 65 cũng ở nút con phải.
B+ Tree sau chèn 65:
Thuật toán
BPlusTreeInsert(root, key)
Input: gốc, khóa chèn
Giả sử khóa chưa có trong cây
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.
Chèn đối tượng mới (key, value v) vào xh.
i := h
while xi overflow do
chia xi thành 2 nút, nửa lớn hơn chuyển sang nút mới p.
if xi là lá, nối p vào linked list các lá.
xác định khóa k chèn vào cấp cha cùng con trỏ p.
Chọn k tùy loại xi: nếu lá → copy up (khóa nhỏ nhất p copy lên cha).
nếu không phải lá → push up (khóa nhỏ nhất p push lên cha).
if i = 0 thì
tạo nút chỉ mục mới làm gốc mới. Lưu khóa k, 2 con xi và p.
return
else
chèn khóa k và con trỏ p vào xi-1.
i := i - 1
end if
done