데이터 구조에 B+ 트리 삽입

여기서 B+ 트리에 삽입을 수행하는 방법을 살펴보겠습니다. 아래와 같은 B+ 트리가 있다고 가정합니다. -

B+ 트리의 예 -

요소를 삽입하는 아이디어는 B-Tree와 매우 유사합니다. 하나의 요소가 삽입되면 리프 노드에 저장됩니다. 그것이 어떤 내부 노드에 존재한다면, 그것은 또한 자신의 오른쪽 자식으로 잎에 있을 것입니다.

트리에 65를 삽입한다고 가정합니다. 따라서 60보다 크고 75보다 작습니다. 그런 다음 중간 하위 트리에 삽입됩니다. 이제 65는 63 이후의 노드에 삽입되고 해당 노드는 두 부분으로 나뉘며 65는 위로 올라가고 65는 오른쪽 노드에도 있습니다.

65를 삽입한 후의 B+ 트리.

알고리즘

BPlusTreeInsert(루트, 키) -

입력 − 트리의 루트, 삽입할 키

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