











B-Tree: Insertion
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.


- 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.


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.


- 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


- 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


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.


- Since Q is inserted at the leaf node which could accommodate more nodes.
- The final tree structure is shown as follows.

