B-Tree: Insertion

August 22, 2019

Insertion in B-Tree

In a B-Tree, the new element must be added to the leaf node only. The insertion operation can be performed as follows:

  • Initially we must check if the tree is empty or not.
  • If the tree is found to be empty, then a new node with new key value is created inserted as the root node.
  • If the tree is not empty, then using the BST logic the new node is inserted to it’s suitable location.
  • If there is some empty location at the leaf then, keeping in mind the increasing order of the key value, the node is inserted at the suitable position.
  • If the leaf node is filled completely, then split the node by moving the middle element upwards to the parent node.
  • If the node to be split is the root node, then the middle element that is moved becomes the new root node.
  • Let us understand this with the help of an example.

Assume we have a B-Tree as given in the image above.

  • As discussed in the properties above we , for instance, consider the B-tree of order = 5.
  • Hence to construct a B-tree by abiding by it’s properties we see,
  • The order of tree is 5. It means each node can have at most 4 keys.
b1
  • If we see the image, the node (5) violates the properties of the B-tree, since it contains 4 keys.
  • The node splits from the middle element ‘ U ‘ , which moves upwards to the parent node.
b2

Insert ‘ B ‘

  • Now, let us insert an element to the B-tree.
  • Let the element to be inserted is ‘ B ‘. 
  • Since ‘ B ‘ comes before ‘ G ‘ in alphabetical order, it is to be inserted in the node 2.
  • The node tree structure after insertion as follows.
b3
  • Now, since maximum keys a node can have = 4 ,the node 2 splits from the middle.
  • The middle element moves upward to the parent/root node.
  • The tree structure after alteration is shown as follows
b4
  • As discussed before, each node can have at most 4 keys, we can see here, the root node violates this property.
  • Hence, the root node is split from the middle.
  • The middle element ‘ M ‘ moves upward and becomes the new root to the tree structure.
  • The tree structure after alteration is shown as follows 
b5

Insert ‘ Q ‘

  • If we see the alphabetical order, the new node to be inserted Q lies after P.
  • Thus Q, will be inserted in the second last node before ‘ S ‘ and ‘ T ‘. 
  • The tree structure after new insertion is shown as follows.
b6
  • Since Q is inserted at the leaf node which could accommodate more nodes.
  • The final tree structure is shown as follows.
b7