データ構造へのB+ツリーの挿入

ここでは、B+ツリーへの挿入を実行する方法を説明します。以下のようなB+ツリーがあるとします-

B+ツリーの例 −

要素を挿入するための考え方はBツリーと非常によく似ており、1つの要素が挿入されると、リーフノードに格納されます。それが内部ノードに存在する場合は、それ自体の右の子としてリーフにも存在します。

ツリーに65を挿入するとします。つまり、これは60より大きく、75未満です。次に、中央のサブツリーに挿入されます。これで、65が63の後にノードに挿入され、そのノードは2つの部分に分割され、65が上昇し、65もその右側のノードに配置されます。

65を挿入した後のB+ツリー。

アルゴリズム

BPlusTreeInsert（root、key） −

入力 −ツリーのルート、および挿入するキー

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