Insertion in B-Tree in Java

Insertion in B-Tree 

 

Here, in this section we will discuss Insertion in B-tree in Java. Inserting an element on  a B-tree consists of two events : searching the appropriate node to insert the element and splitting the node if required. Insertion operation always takes place in  the bottom-up approach. In this article, you will learn how to insert a key into a B-Tree.

 

Insertion in B-Tree in Java

B-Tree

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reason of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.

  1. Every node in a B-Tree contains at most m children.
  2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
  3. The root nodes must have at least 2 nodes.
  4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes.

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.

A B-tree of order 2 is shown in the following Example:

Example For Insertion in B-Tree

Example for Insertion in B-Tree in java

Code in Java

public class BTree
{   
    private int T;  

    public class Node
    {          
        int n;
        int key[] = new int[2 * T - 1];
        Node child[] = new Node[2 * T];
        boolean leaf = true;
 
        public int Find (int k)
        {                        
            for (int i = 0; i < this.n; i++)
	        {	             
                if (this.key[i] == k)
	            {            
                    return i;
                }	        
            }                        
            return -1;
        };       
    }
 
    public BTree(int t)
    {             
        T = t;
        root = new Node ();
        root.n = 0;
        root.leaf = true;
    } 

    private Node root;
     
    // split
    private void split (Node x, int pos, Node y)
    {             
        Node z = new Node ();
        z.leaf = y.leaf;
        z.n = T - 1;

        for (int j = 0; j < T - 1; j++)
        {	        
            z.key[j] = y.key[j + T];
        } 
        if (!y.leaf)
        {	        
            for (int j = 0; j < T; j++)
	        {	            
                z.child[j] = y.child[j + T];
            } 
        }          
        y.n = T - 1;
    
        for (int j = x.n; j >= pos + 1; j--)
        {	        
            x.child[j + 1] = x.child[j];
        } 
        x.child[pos + 1] = z;   

        for (int j = x.n - 1; j >= pos; j--)
        {	        
            x.key[j + 1] = x.key[j];
        } 
        x.key[pos] = y.key[T - 1];
        x.n = x.n + 1;
    } 
 
     // insert key
    public void insert (final int key)
    {             
        Node r = root;

        if (r.n == 2 * T - 1)
        {	    
            Node s = new Node ();
            root = s;
            s.leaf = false;
            s.n = 0;
            s.child[0] = r;
            split (s, 0, r);
            _insert (s, key);
        }
        else
        {	        
            _insert (r, key);
        }       
    } 
    // insert node
    final private void _insert (Node x, int k)
    {    
 
        if (x.leaf)
        {	        
            int i = 0;
	
	        for (i = x.n - 1; i >= 0 && k < x.key[i]; i--)
	        {	            
                x.key[i + 1] = x.key[i];
            }	    
            x.key[i + 1] = k;
            x.n = x.n + 1;
        }
        else
        {	    
            int i = 0;

            for (i = x.n - 1; i >= 0 && k < x.key[i]; i--)
	        {	      
            };
            i++;
            
            Node tmp = x.child[i];
            if (tmp.n == 2 * T - 1)
	        {
                split (x, i, tmp);
                if (k > x.key[i])
	            {	        	
                    i++;
                }	      
            }	    
            _insert (x.child[i], k);
        }   
    }   
    
    public void display ()
    {
        display (root);
    }  

    // Display the tree
    private void display (Node x)
    {      
        assert (x == null);
        for (int i = 0; i < x.n; i++)
        {	    
            System.out.print (x.key[i] + " ");
        } 
        
        if (!x.leaf)
        {	
            for (int i = 0; i < x.n + 1; i++)
	        {	    
                display (x.child[i]);
            } 
        }   
    } 
    public static void main (String[]args)
    {         
        BTree b = new BTree(1);
        b.insert(5);
        b.insert (6);
        b.insert (7);
        b.insert (8);
        b.insert (12);
        b.insert (13);
        b.insert (14);
        b.display ();
    } 
}

Output

5 6 7 8 12 13 14