Ở đây chúng ta sẽ xem cách thực hiện chèn vào B-Tree. Giả sử chúng ta có B-Tree như bên dưới -
Ví dụ về B-Tree -
Để chèn một phần tử, ý tưởng rất giống với BST, nhưng chúng ta phải tuân theo một số quy tắc. Mỗi nút có m phần tử con và m-1 phần tử. Nếu chúng ta chèn một phần tử vào một nút, có hai trường hợp. Nếu nút có các phần tử nhỏ hơn m-1, thì phần tử mới sẽ được chèn trực tiếp vào nút. Nếu nó có m-1 phần tử, thì bằng cách lấy tất cả các phần tử và phần tử sẽ được chèn vào, sau đó lấy giá trị trung bình của chúng và giá trị trung vị được gửi đến gốc của nút đó bằng cách thực hiện cùng một tiêu chí, sau đó tạo hai tách danh sách khỏi nửa trái và nửa phải của nút
Giả sử chúng ta muốn chèn 79 vào cây. Lúc đầu, nó sẽ được kiểm tra với gốc, giá trị này lớn hơn 56. Sau đó, nó sẽ đến đúng cây con nhất. Bây giờ nó nhỏ hơn 81, vì vậy hãy chuyển sang cây phụ bên trái. Sau đó, nó sẽ được chèn vào gốc. Bây giờ có ba yếu tố [66, 78, 79]. Giá trị trung vị là 78, vì vậy 78 sẽ tăng lên, và nút gốc trở thành [79, 81], và các phần tử của nút sẽ được chia thành hai nút. Một sẽ giữ 66, và một sẽ giữ 79.
B-Tree sau khi chèn 79.
Thuật toán
BTreeInsert (root, key) -
Đầu vào - Gốc của cây và khóa để chèn Chúng tôi sẽ giả định rằng khóa không có trong danh sách
x := Read root if x is full, then y := new node z := new node Locate the middle object oi, stored in x, move the objects to the left of oi in to node y Move the object to the right of oi into node z. If x is an index node, then move the child pointers accordingly x->child[1] := address of y x->child[2] := address of z end if