Ở đâ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 B-Tree, nếu một phần tử được chèn vào, phần tử đó sẽ được lưu trữ tại nút lá. Nếu nó hiện diện trong một số nút bên trong, thì nó cũng sẽ ở đó, ở lá như con bên phải của chính nó.
Giả sử chúng ta muốn chèn 65 vào cây. Vì vậy, giá trị đó lớn hơn 60 và nhỏ hơn 75. Sau đó, nó sẽ được chèn vào cây con ở giữa. Bây giờ, 65, sẽ được chèn vào nút sau 63, sau đó nút đó sẽ được chia thành hai phần, 65 sẽ đi lên và 65 cũng sẽ ở đó ở nút bên phải của nó.
B + Cây sau khi chèn 65.
Thuật toán
BPlusTreeInsert (root, key) -
Đầu vào - Gốc của cây và chìa khóa để chèn
We will assume, that the key is not present into the list Start from root node, perform exact match for key as ‘key’ till a leaf node. Let the search path be x1, x2, … , xh. The x1 is first node so root, then xh is leaf node. Each node xi is parent of xi+1 Insert the new object where key is ‘key’, and value is v into xh. i := h while xi overflows, do divide xi into two nodes, by moving the larger half of the keys into a new node p. if xi is leaf node, link p into the linked list among leaf nodes. identify a key k, to be inserted into the parent level along with child pointer pointing p. The choice of k depends on the type of the node xi. If xi is leaf node, we will perform copy up. So smallest key in p, is copied as k to the parent level. On the other hand, if xi is non-leaf node, then we will perform push up. So smallest key in p, will be copied into k, in the parent node. if i = 0, then create a new index node as the new root. In the new root store node with key k, and two child xi and p. return else insert a key k and a child pointer pointing to p, into node xi-1. i := i – 1 end if done