# 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 is inserted at the leaf node which could accommodate more nodes.
• The final tree structure is shown as follows. 