0.2 Lưu trữ và cấu trúc tập tin  (Page 18/26)

Procedure Insert(value V, pointer P)

Tìm nút lá L sẽ chứa giá trị V

Insert_entry(L, V, P)

end procedure

Procedure Insert_entry(node L, value V, pointer P)

If (L có không gian cho (V, P) then

Xen (V, P) vào L

elsebegin/* tách L */

Tạo nút L'

If ( L là nút lá) then begin

V' là giá trị sao cho m/2 giá trị trong các giá trị L.K1, L.K2, ..., L.Km-1, V nhỏ hơn V'

n là chỉ số nhỏ nhất sao cho L.Kn  V'

Di chuyển L.Pn, L.Kn, ..., L.Pm-1, L.Kn-1 sang L'

If (V<V') then xen (V, P) vào trong L else xen (P, V) vào trong L'

end else begin

V' là giá trị sao cho m/2 giá trị trong các giá trị L.K1, L.K2, ..., L.Km-1, V lớn hơn hoặc bằng V'

n là chỉ số nhỏ nhất sao cho L.Kn  V'

Thêm Nil, L.Kn, L.Pn+1, L.Kn+1, ..., L.Pm-1, L.Km-1, L.Pm vào L'

Xoá L.Kn, L.Pn+1, L.Kn+1, ..., L.Pm-1, L.Km-1, L.Pm khỏi L

If (V<V') then xen (P, V) vào trong L else xen (P, V) vào trong L'

xoá (Nil, V') khỏi L'

end

If (L không là nút gốc) then Insert_entry(parent(L), V', L')

else begin

Tạo ra nút mới R với các nút con là L và L' với giá trị duy nhất trong nó là V'

Tạo R là gốc của cây

end

If (L) là một nút lá then begin

đặt L'.Pm = L.Pm

đặt L.Pm = L'

end

end

end procedure

• Xoá. Sử dụng kỹ thuật tìm kiếm tìm mẩu tin cần xoá, xoá nó khỏi file, xoá giá trị khoá tìm kiếm khỏi nút lá trong B+-cây nếu không có bucket kết hợp với giá trị khoá tìm kiếm hoặc bucket trở nên rỗng sau khi xoá con trỏ tương ứng trong nó. Việc xoá một giá trị khoá khỏi một nút của B+-cây có thể dẫn đến nút lá trở nên rỗng, phải trả lại, từ đó nút cha của nó có thể có số con nhỏ hơn ngưỡng cho phép, trong trường hợp đó hoặc phải chuyển một con từ nút anh em của nút cha đó sang nút cha nếu điều đó có thể (nút anh em của nút cha này còn số con  m/2 sau khi chuyển đi một con). Nếu không, phải gom nút cha này với một nút anh em của nó, điều này dẫn tới xoá một nút trong khỏi cây, rồi xoá khỏi nút cha của nó một hạng, ... quá trình này có thể dẫn đến tận gốc. Trong trường hợp nút gốc chỉ còn một con sau xoá, cây phải thay nút gốc cũ bởi nút con của nó, nút gốc cũ phải trả lại cho hệ thống, chiều cao cây giảm đi một.

Procedure delete(value V, pointer P)

Tìm nút lá chứa (V, P)

delete_entry(L, V, P)

end procedure

Procedure delete_entry(node L, value V, pointer P)

xoá (V, P) khỏi L

If (L là nút gốc and L chỉ còn lại một con) then

Lấy con của L làm nút gốc mới của cây, xoá L

else If (L có quá ít giá trị/ con trỏ) then begin

L' là anh em kề trái hoặc phải của L

V' là giá trị ở giữa hai con trỏ L, L' (trong nút parent(L))

If (các đầu vào của L và L' có thể lấp đầy trong một khối) then begin

If (L là nút trước của L') then wsap_variables(L, L')

If (L không là lá) then nối V' và tất cả con trỏ, giá trị trong L với L'

else begin nối tất cả các cặp (K, P) trong L với L'; L'.Pp = L.Pp end

delete_entry(parent(L), V', L); xoá nút L

end

else begin

If (L' là nút trước của L) then begin

If (L không là nút lá) then begin

p là chỉ số sao cho L'.Pp là con trỏ cuối trong L'

xoá (L'.Kp-1, L'.Pp) khỏi L'

xen (L'.Pp, V') như phần tử đầu tiên trong L (right_shift tất cả các phần tử của L)

thay thế V' trong parent(L) bởi L'.Kp-1