Skip to main content

Implement B + Tree

In the realm of data structures, the B+ tree stands as a remarkable solution for indexing and managing large datasets efficiently. This article takes a deep dive into the implementation of a B+ tree in C. With clear explanations, illustrative code, and an example, we'll uncover the intricacies of B+ tree creation, insertion, and traversal.

Problem Statement and Description

This article aims to implement a B+ tree from scratch using C programming. We'll cover tree node creation, insertion of elements, and a method to print the elements in order. The code will be explained step by step, allowing readers to understand how a B+ tree functions and how elements are organized within it.

Example

We'll create a B+ tree with a degree of 4 and insert the following elements: 10, 7, 15, 2, -3, 12, 35, and 14. The tree will then be printed in order, showcasing the arrangement of elements.

Idea to Solve

To solve this problem, we'll follow these key steps:

  1. Define the structures for the tree nodes and the B+ tree itself.
  2. Implement functions to create new nodes and the tree itself.
  3. Develop insertion functions to add elements to the tree while maintaining the B+ tree properties.
  4. Design a function to print the elements of the B+ tree in order.

Standard Pseudocode

struct TreeNode:
	int isLeaf
	int *keys
	int count
	TreeNode **child

struct BPTree:
	TreeNode *root
	int degree

createTree(degree):
	tree = allocate memory for BPTree
	if tree is not NULL:
		tree.degree = degree
		tree.root = NULL

createNode(degree):
	node = allocate memory for TreeNode
	if node is not NULL:
		node.keys = allocate memory for keys array
		node.child = allocate memory for child array
		node.isLeaf = 0
		node.count = 0
	return node

findParent(cursor, child):
	parent = NULL
	if cursor.isLeaf == 1 or cursor.child[0].isLeaf == 1:
		return NULL
	for i in range(cursor.count + 1):
		if cursor.child[i] == child:
			parent = cursor
			return parent
		else:
			parent = findParent(cursor.child[i], child)
			if parent is not NULL:
				return parent

insertInternal(tree, x, cursor, child):
	// Implementation details follow

insert(tree, x):
	// Implementation details follow

printNode(node):
	// Implementation details follow

Algorithm Explanation

  • The createTree function initializes a new B+ tree with the given degree.
  • The createNode function creates a new tree node with allocated memory for keys and child arrays.
  • The findParent function identifies the parent of a given child node in the B+ tree.
  • The insertInternal function handles the insertion of elements into internal nodes while maintaining properties.
  • The insert function manages the insertion process, including splitting nodes and potential root updates.
  • The printNode function traverses the B+ tree in order and prints the elements.

Code Solution

// C program
// Implement B + Tree
#include <stdio.h>
#include <stdlib.h>

// Define tree node
struct TreeNode
{
    int isLeaf;
    int *keys;
    int count;
    struct TreeNode **child;
};

// Define tree structure
struct BPTree
{
    struct TreeNode *root;
    int degree;
};
// Returns the new B+ tree
struct BPTree *createTree(int degree)
{

    // Allocate memory of new tree
    struct BPTree *tree = (struct BPTree *) malloc(sizeof(struct BPTree));

    if (tree != NULL)
    {
        // Set degree and root value
        tree->degree = degree;
        tree->root = NULL;
    }
    else
    {
        printf("\n Memory Overflow when create new Tree");
    }
}
// Returns new B+ tree node
struct TreeNode *createNode(int degree)
{
    // Create new tree node
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    
    if (node != NULL)
    {
        // Create memory of node key
        node->keys = (int *) malloc((sizeof(int)) *(degree));
        // Allocate memory of node child
        node->child = (struct TreeNode **) malloc((degree + 1) *sizeof(struct TreeNode *));
        // Set initial child
        for (int i = 0; i <= degree ; ++i)
        {
            node->child[i] = NULL;
        }
        node->isLeaf = 0;
        node->count = 0;
    }
}

struct TreeNode *findParent(struct TreeNode *cursor, struct TreeNode *child)
{
    struct TreeNode *parent = NULL;

    if (cursor->isLeaf == 1 || (cursor->child[0])->isLeaf == 1)
    {
        return NULL;
    }
    for (int i = 0; i < cursor->count + 1; i++)
    {
       
        if (cursor->child[i] == child)
        {
            parent = cursor;
            return parent;
        }
        else
        {
        
            parent = findParent(cursor->child[i], child);

            if (parent != NULL)
            {
                return parent;
            }
        }
    }
  
    return parent;
}

void insertInternal(struct BPTree *tree, int x, struct TreeNode *cursor, struct TreeNode *child)
{
      
    int i = 0;
    int j = 0;
    if (cursor->count < tree->degree)
    {
     
        while (x > cursor->keys[i] && i < cursor->count)
        {
            i++;
        }
     
        for (j = cursor->count; j > i; j--)
        {
            cursor->keys[j] = cursor->keys[j - 1];
        }
 
        for (j = cursor->count + 1; j > i + 1; j--)
        {
            cursor->child[j] = cursor->child[j - 1];
        }
        cursor->keys[i] = x;
        cursor->count++;
        cursor->child[i + 1] = child;
    }
    else
    {


        struct TreeNode *newInternal = createNode(tree->degree);
        int virtualKey[tree->degree + 1];
        struct TreeNode *virtualPtr[tree->degree + 2];
      
        for (i = 0; i < tree->degree; i++)
        {
            virtualKey[i] = cursor->keys[i];
        }
        
        for (i = 0; i < tree->degree + 1; i++)
        {
            virtualPtr[i] = cursor->child[i];
        }
 
        i = 0;

        while (x > virtualKey[i] && i < tree->degree)
        {
            i++;
        }
        
        for (j = tree->degree + 1; j > i; j--)
        {
            virtualKey[j] = virtualKey[j - 1];
        }
        virtualKey[i] = x;
    
        for ( j = tree->degree + 2; j > i + 1; j--)
        {
            virtualPtr[j] = virtualPtr[j - 1];
        }
        virtualPtr[i + 1] = child;
        newInternal->isLeaf = 0;
        cursor->count = (tree->degree + 1) / 2;
        newInternal->count = tree->degree - (tree->degree + 1) / 2;
        for (i = 0, j = cursor->count + 1; i < newInternal->count; i++, j++)
        {
            newInternal->keys[i] = virtualKey[j];
        }
        for (i = 0, j = cursor->count + 1; i < newInternal->count + 1; i++, j++)
        {
            newInternal->child[i] = virtualPtr[j];
        }
     
        if (cursor == tree->root)
        {
           
            tree->root = createNode(tree->degree);

            tree->root->keys[0] = cursor->keys[cursor->count];

            tree->root->child[0] = cursor;

            tree->root->child[1] = newInternal;

            tree->root->isLeaf = 0;

            tree->root->count = 1;

        }
        else
        {
            insertInternal(tree, cursor->keys[cursor->count], findParent(tree->root, cursor), newInternal);
        }
    }
}
// Handles the request to add new node in B+ tree
void insert(struct BPTree *tree, int x)
{
    if (tree->root == NULL)
    {
        // Add first node of tree
        tree->root = createNode(tree->degree);
        tree->root->isLeaf  = 1;
        tree->root->count   = 1;
        tree->root->keys[0] = x;

    }
    else
    {
        // Loop controlling variables
        int i = 0;
        int j = 0;

        struct TreeNode *cursor = tree->root;

        struct TreeNode *parent = NULL;

        // Executes the loop until when cursor node is not leaf node
        while (cursor->isLeaf == 0)
        {
            // Get the current node
            parent = cursor;

            for (i = 0; i < cursor->count; i++)
            {
                if (x < cursor->keys[i])
                {
                    cursor = cursor->child[i];
                    break;
                }
                if (i == cursor->count - 1)
                {
                    cursor = cursor->child[i + 1];
                    break;
                }
            }
        }
        if (cursor->count < tree->degree)
        {
            i = 0;
            while (x > cursor->keys[i] && i < cursor->count)
            {
                i++;
            }
            for (j = cursor->count; j > i; j--)
            {
                cursor->keys[j] = cursor->keys[j - 1];
            }
            cursor->keys[i] = x;
            cursor->count++;
            cursor->child[cursor->count] = cursor->child[cursor->count - 1];
            cursor->child[cursor->count - 1] = NULL;
        }
        else
        {
    
            struct TreeNode *newLeaf = createNode(tree->degree);

            int virtualNode[tree->degree + 2];
 
            for (i = 0; i < tree->degree; i++)
            {
                virtualNode[i] = cursor->keys[i];
            }
            i = 0;
            while (x > virtualNode[i] && i < tree->degree)
            {
                i++;
            }
 
            for (j = tree->degree + 1; j > i; j--)
            {
                virtualNode[j] = virtualNode[j - 1];
            }
            virtualNode[i] = x;
            newLeaf->isLeaf = 1;
            cursor->count = (tree->degree + 1) / 2;
            newLeaf->count = tree->degree + 1 - (tree->degree + 1) / 2;
            cursor->child[cursor->count] = newLeaf;
            newLeaf->child[newLeaf->count] = cursor->child[tree->degree];
            cursor->child[tree->degree] = NULL;

            for (i = 0; i < cursor->count; i++)
            {
                cursor->keys[i] = virtualNode[i];
            }
            for (i = 0, j = cursor->count; i < newLeaf->count; i++, j++)
            {
                newLeaf->keys[i] = virtualNode[j];
            }
            if (cursor == tree->root)
            {
                struct TreeNode *newRoot = createNode(tree->degree);
             
                newRoot->keys[0] = newLeaf->keys[0];
                newRoot->child[0] = cursor;
                newRoot->child[1] = newLeaf;
                newRoot->isLeaf = 0;
                newRoot->count = 1;
                tree->root = newRoot;
            }
            else
            {
                insertInternal(tree, newLeaf->keys[0], parent, newLeaf);
            }
        }
    }
}

// Print the elements of B+ tree elements
void printNode(struct TreeNode *node) 
{
    if(node == NULL)
    {
        // When node is empty
        return;
    }
    else
    {
        int i  = 0;

        // iterate the node element
        while(i < node->count)
        {
            if(node->isLeaf==0)
            {
                // When node is not leaf
                printNode(node->child[i]);
            }
            else
            {
                // Print the left node value
                printf("  %d",node->keys[i]); 
            }
            i++;
        }
        if(node->isLeaf == 0)
        {
            printNode(node->child[i]);
        }
    }
}

int main(int argc, char const *argv[])
{
    // Create a new b+ tree with degree 4
    struct BPTree *tree = createTree(4);

    // Add node
    insert(tree,10);
    insert(tree,7);
    insert(tree,15);
    insert(tree,2);
    insert(tree,-3);
    insert(tree,12);
    insert(tree,35);
    insert(tree,14);

    // Print Tree elements
    printNode(tree->root);

    return 0;
}

input

  -3  2  7  10  12  14  15  35
/*
  Java Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	public boolean isLeaf;
	public int[] keys;
	public int count;
	public TreeNode[] child;
	public TreeNode(int degree)
	{
		this.isLeaf = false;
		this.count = 0;
		this.keys = new int[degree];
		this.child = new TreeNode[degree + 1];
		// Set initial child
		for (int i = 0; i <= degree; ++i)
		{
			this.child[i] = null;
		}
	}
}
// Define tree structure
public class BPTree
{
	public TreeNode root;
	public int degree;
	public BPTree(int degree)
	{
		this.degree = degree;
		this.root = null;
	}
	public TreeNode findParent(TreeNode cursor, TreeNode child)
	{
		TreeNode parent = null;
		if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
		{
			return null;
		}
		for (int i = 0; i < cursor.count + 1; i++)
		{
			if (cursor.child[i] == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = findParent(cursor.child[i], child);
				if (parent != null)
				{
					return parent;
				}
			}
		}
		return parent;
	}
	public void insertInternal(int x, TreeNode cursor, TreeNode child)
	{
		int i = 0;
		int j = 0;
		if (cursor.count < this.degree)
		{
			while (x > cursor.keys[i] && i < cursor.count)
			{
				i++;
			}
			for (j = cursor.count; j > i; j--)
			{
				cursor.keys[j] = cursor.keys[j - 1];
			}
			for (j = cursor.count + 1; j > i + 1; j--)
			{
				cursor.child[j] = cursor.child[j - 1];
			}
			cursor.keys[i] = x;
			cursor.count++;
			cursor.child[i + 1] = child;
		}
		else
		{
			TreeNode newInternal = new TreeNode(this.degree);
			int[] virtualKey = new int[this.degree + 1];
			TreeNode[] virtualPtr = new TreeNode[this.degree + 2];
			for (i = 0; i < this.degree; i++)
			{
				virtualKey[i] = cursor.keys[i];
			}
			for (i = 0; i < this.degree + 1; i++)
			{
				virtualPtr[i] = cursor.child[i];
			}
			i = 0;
			while (x > virtualKey[i] && i < this.degree)
			{
				i++;
			}
			for (j = this.degree + 1; j > i; j--)
			{
				virtualKey[j] = virtualKey[j - 1];
			}
			virtualKey[i] = x;
			for (j = this.degree + 2; j > i + 1; j--)
			{
				virtualPtr[j] = virtualPtr[j - 1];
			}
			virtualPtr[i + 1] = child;
			newInternal.isLeaf = false;
			cursor.count = (this.degree + 1) / 2;
			newInternal.count = this.degree - (this.degree + 1) / 2;
			for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
			{
				newInternal.keys[i] = virtualKey[j];
			}
			for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
			{
				newInternal.child[i] = virtualPtr[j];
			}
			if (cursor == this.root)
			{
				this.root = new TreeNode(this.degree);
				this.root.keys[0] = cursor.keys[cursor.count];
				this.root.child[0] = cursor;
				this.root.child[1] = newInternal;
				this.root.isLeaf = false;
				this.root.count = 1;
			}
			else
			{
				insertInternal(cursor.keys[cursor.count], findParent(this.root, cursor), newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	public void insert(int x)
	{
		if (this.root == null)
		{
			// Add first node of tree
			this.root = new TreeNode(this.degree);
			this.root.isLeaf = true;
			this.root.count = 1;
			this.root.keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			int i = 0;
			int j = 0;
			TreeNode cursor = this.root;
			TreeNode parent = null;
			// Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				for (i = 0; i < cursor.count; i++)
				{
					if (x < cursor.keys[i])
					{
						cursor = cursor.child[i];
						break;
					}
					if (i == cursor.count - 1)
					{
						cursor = cursor.child[i + 1];
						break;
					}
				}
			}
			if (cursor.count < this.degree)
			{
				i = 0;
				while (x > cursor.keys[i] && i < cursor.count)
				{
					i++;
				}
				for (j = cursor.count; j > i; j--)
				{
					cursor.keys[j] = cursor.keys[j - 1];
				}
				cursor.keys[i] = x;
				cursor.count++;
				cursor.child[cursor.count] = cursor.child[cursor.count - 1];
				cursor.child[cursor.count - 1] = null;
			}
			else
			{
				TreeNode newLeaf = new TreeNode(this.degree);
				int[] virtualNode = new int[this.degree + 2];
				for (i = 0; i < this.degree; i++)
				{
					virtualNode[i] = cursor.keys[i];
				}
				i = 0;
				while (x > virtualNode[i] && i < this.degree)
				{
					i++;
				}
				for (j = this.degree + 1; j > i; j--)
				{
					virtualNode[j] = virtualNode[j - 1];
				}
				virtualNode[i] = x;
				newLeaf.isLeaf = true;
				cursor.count = (this.degree + 1) / 2;
				newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
				cursor.child[cursor.count] = newLeaf;
				newLeaf.child[newLeaf.count] = cursor.child[this.degree];
				cursor.child[this.degree] = null;
				for (i = 0; i < cursor.count; i++)
				{
					cursor.keys[i] = virtualNode[i];
				}
				for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
				{
					newLeaf.keys[i] = virtualNode[j];
				}
				if (cursor == this.root)
				{
					TreeNode newRoot = new TreeNode(this.degree);
					newRoot.keys[0] = newLeaf.keys[0];
					newRoot.child[0] = cursor;
					newRoot.child[1] = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					this.root = newRoot;
				}
				else
				{
					insertInternal(newLeaf.keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	public void printNode(TreeNode node)
	{
		if (node == null)
		{
			// When node is empty
			return;
		}
		else
		{
			int i = 0;
			// iterate the node element
			while (i < node.count)
			{
				if (node.isLeaf == false)
				{
					// When node is not leaf
					printNode(node.child[i]);
				}
				else
				{
					// Print the left node value
					System.out.print("  " + node.keys[i]);
				}
				i++;
			}
			if (node.isLeaf == false)
			{
				printNode(node.child[i]);
			}
		}
	}
	public static void main(String[] args)
	{
		// Create a new b+ tree with degree 4
		BPTree tree = new BPTree(4);
		// Add node
		tree.insert(10);
		tree.insert(7);
		tree.insert(15);
		tree.insert(2);
		tree.insert(-3);
		tree.insert(12);
		tree.insert(35);
		tree.insert(14);
		// Print Tree elements
		tree.printNode(tree.root);
	}
}

input

  -3  2  7  10  12  14  15  35
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	public: 
    bool isLeaf;
	int *keys;
	int count;
	TreeNode **child;
	TreeNode(int degree)
	{
		this->isLeaf = false;
		this->count = 0;
		this->keys = new int[degree];
		this->child = new TreeNode *[degree + 1];
		// Set initial child
		for (int i = 0; i <= degree; ++i)
		{
			this->child[i] = NULL;
		}
	}
	TreeNode()
	{
		this->count = 0;
	}
};
// Define tree structure
class BPTree
{
	public: TreeNode *root;
	int degree;
	BPTree(int degree)
	{
		this->degree = degree;
		this->root = NULL;
	}
	TreeNode *findParent(TreeNode *cursor, TreeNode *child)
	{
		TreeNode *parent = NULL;
		if (cursor->isLeaf == true || (cursor->child[0])->isLeaf == true)
		{
			return NULL;
		}
		for (int i = 0; i < cursor->count + 1; i++)
		{
			if (cursor->child[i] == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = this->findParent(cursor->child[i], child);
				if (parent != NULL)
				{
					return parent;
				}
			}
		}
		return parent;
	}
	void insertInternal(int x, TreeNode *cursor, TreeNode *child)
	{
		int i = 0;
		int j = 0;
		if (cursor->count < this->degree)
		{
			while (x > cursor->keys[i] && i < cursor->count)
			{
				i++;
			}
			for (j = cursor->count; j > i; j--)
			{
				cursor->keys[j] = cursor->keys[j - 1];
			}
			for (j = cursor->count + 1; j > i + 1; j--)
			{
				cursor->child[j] = cursor->child[j - 1];
			}
			cursor->keys[i] = x;
			cursor->count++;
			cursor->child[i + 1] = child;
		}
		else
		{
			TreeNode *newInternal = new TreeNode(this->degree);
			int *virtualKey = new int[this->degree + 1];
			TreeNode **virtualPtr = new TreeNode *[this->degree + 2];
			for (i = 0; i < this->degree; i++)
			{
				virtualKey[i] = cursor->keys[i];
			}
			for (i = 0; i < this->degree + 1; i++)
			{
				virtualPtr[i] = cursor->child[i];
			}
			i = 0;
			while (x > virtualKey[i] && i < this->degree)
			{
				i++;
			}
			for (j = this->degree + 1; j > i; j--)
			{
				virtualKey[j] = virtualKey[j - 1];
			}
			virtualKey[i] = x;
			for (j = this->degree + 2; j > i + 1; j--)
			{
				virtualPtr[j] = virtualPtr[j - 1];
			}
			virtualPtr[i + 1] = child;
			newInternal->isLeaf = false;
			cursor->count = (this->degree + 1) / 2;
			newInternal->count = this->degree - (this->degree + 1) / 2;
			for (i = 0, j = cursor->count + 1; i < newInternal->count; 
                 i++, j++)
			{
				newInternal->keys[i] = virtualKey[j];
			}
			for (i = 0, j = cursor->count + 1; i < newInternal->count + 1; 
                 i++, j++)
			{
				newInternal->child[i] = virtualPtr[j];
			}
			if (cursor == this->root)
			{
				this->root = new TreeNode(this->degree);
				this->root->keys[0] = cursor->keys[cursor->count];
				this->root->child[0] = cursor;
				this->root->child[1] = newInternal;
				this->root->isLeaf = false;
				this->root->count = 1;
			}
			else
			{
				this->insertInternal(cursor->keys[cursor->count], 
                                     this->findParent(this->root, cursor),
                                     newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	void insert(int x)
	{
		if (this->root == NULL)
		{
			// Add first node of tree
			this->root = new TreeNode(this->degree);
			this->root->isLeaf = true;
			this->root->count = 1;
			this->root->keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			int i = 0;
			int j = 0;
			TreeNode *cursor = this->root;
			TreeNode *parent = NULL;
			// Executes the loop until when cursor node is not leaf node
			while (cursor->isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				for (i = 0; i < cursor->count; i++)
				{
					if (x < cursor->keys[i])
					{
						cursor = cursor->child[i];
						break;
					}
					if (i == cursor->count - 1)
					{
						cursor = cursor->child[i + 1];
						break;
					}
				}
			}
			if (cursor->count < this->degree)
			{
				i = 0;
				while (x > cursor->keys[i] && i < cursor->count)
				{
					i++;
				}
				for (j = cursor->count; j > i; j--)
				{
					cursor->keys[j] = cursor->keys[j - 1];
				}
				cursor->keys[i] = x;
				cursor->count++;
				cursor->child[cursor->count] = cursor->child[cursor->count - 1];
				cursor->child[cursor->count - 1] = NULL;
			}
			else
			{
				TreeNode *newLeaf = new TreeNode(this->degree);
				int *virtualNode = new int[this->degree + 2];
				for (i = 0; i < this->degree; i++)
				{
					virtualNode[i] = cursor->keys[i];
				}
				i = 0;
				while (x > virtualNode[i] && i < this->degree)
				{
					i++;
				}
				for (j = this->degree + 1; j > i; j--)
				{
					virtualNode[j] = virtualNode[j - 1];
				}
				virtualNode[i] = x;
				newLeaf->isLeaf = true;
				cursor->count = (this->degree + 1) / 2;
				newLeaf->count = this->degree + 1 - (this->degree + 1) / 2;
				cursor->child[cursor->count] = newLeaf;
				newLeaf->child[newLeaf->count] = cursor->child[this->degree];
				cursor->child[this->degree] = NULL;
				for (i = 0; i < cursor->count; i++)
				{
					cursor->keys[i] = virtualNode[i];
				}
				for (i = 0, j = cursor->count; i < newLeaf->count; i++, j++)
				{
					newLeaf->keys[i] = virtualNode[j];
				}
				if (cursor == this->root)
				{
					TreeNode *newRoot = new TreeNode(this->degree);
					newRoot->keys[0] = newLeaf->keys[0];
					newRoot->child[0] = cursor;
					newRoot->child[1] = newLeaf;
					newRoot->isLeaf = false;
					newRoot->count = 1;
					this->root = newRoot;
				}
				else
				{
					this->insertInternal(newLeaf->keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	void printNode(TreeNode *node)
	{
		if (node == NULL)
		{
			// When node is empty
			return;
		}
		else
		{
			int i = 0;
			// iterate the node element
			while (i < node->count)
			{
				if (node->isLeaf == false)
				{
					// When node is not leaf
					this->printNode(node->child[i]);
				}
				else
				{
					// Print the left node value
					cout << "  " << node->keys[i];
				}
				i++;
			}
			if (node->isLeaf == false)
			{
				this->printNode(node->child[i]);
			}
		}
	}
};
int main()
{
	// Create a new b+ tree with degree 4
	BPTree *tree = new BPTree(4);
	// Add node
	tree->insert(10);
	tree->insert(7);
	tree->insert(15);
	tree->insert(2);
	tree->insert(-3);
	tree->insert(12);
	tree->insert(35);
	tree->insert(14);
	// Print Tree elements
	tree->printNode(tree->root);
	return 0;
}

input

  -3  2  7  10  12  14  15  35
// Include namespace system
using System;
/*
  Csharp Program 
  Implement B Plus Tree Implement
*/
// Define tree node
public class TreeNode
{
	public Boolean isLeaf;
	public int[] keys;
	public int count;
	public TreeNode[] child;
	public TreeNode(int degree)
	{
		this.isLeaf = false;
		this.count = 0;
		this.keys = new int[degree];
		this.child = new TreeNode[degree + 1];
		// Set initial child
		for (int i = 0; i <= degree; ++i)
		{
			this.child[i] = null;
		}
	}
}
// Define tree structure
public class BPTree
{
	public TreeNode root;
	public int degree;
	public BPTree(int degree)
	{
		this.degree = degree;
		this.root = null;
	}
	public TreeNode findParent(TreeNode cursor, TreeNode child)
	{
		TreeNode parent = null;
		if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
		{
			return null;
		}
		for (int i = 0; i < cursor.count + 1; i++)
		{
			if (cursor.child[i] == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = this.findParent(cursor.child[i], child);
				if (parent != null)
				{
					return parent;
				}
			}
		}
		return parent;
	}
	public void insertInternal(int x, TreeNode cursor, TreeNode child)
	{
		int i = 0;
		int j = 0;
		if (cursor.count < this.degree)
		{
			while (x > cursor.keys[i] && i < cursor.count)
			{
				i++;
			}
			for (j = cursor.count; j > i; j--)
			{
				cursor.keys[j] = cursor.keys[j - 1];
			}
			for (j = cursor.count + 1; j > i + 1; j--)
			{
				cursor.child[j] = cursor.child[j - 1];
			}
			cursor.keys[i] = x;
			cursor.count++;
			cursor.child[i + 1] = child;
		}
		else
		{
			TreeNode newInternal = new TreeNode(this.degree);
			int[] virtualKey = new int[this.degree + 1];
			TreeNode[] virtualPtr = new TreeNode[this.degree + 2];
			for (i = 0; i < this.degree; i++)
			{
				virtualKey[i] = cursor.keys[i];
			}
			for (i = 0; i < this.degree + 1; i++)
			{
				virtualPtr[i] = cursor.child[i];
			}
			i = 0;
			while (x > virtualKey[i] && i < this.degree)
			{
				i++;
			}
			for (j = this.degree + 1; j > i; j--)
			{
				virtualKey[j] = virtualKey[j - 1];
			}
			virtualKey[i] = x;
			for (j = this.degree + 2; j > i + 1; j--)
			{
				virtualPtr[j] = virtualPtr[j - 1];
			}
			virtualPtr[i + 1] = child;
			newInternal.isLeaf = false;
			cursor.count = (this.degree + 1) / 2;
			newInternal.count = this.degree - (this.degree + 1) / 2;
			for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
			{
				newInternal.keys[i] = virtualKey[j];
			}
			for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
			{
				newInternal.child[i] = virtualPtr[j];
			}
			if (cursor == this.root)
			{
				this.root = new TreeNode(this.degree);
				this.root.keys[0] = cursor.keys[cursor.count];
				this.root.child[0] = cursor;
				this.root.child[1] = newInternal;
				this.root.isLeaf = false;
				this.root.count = 1;
			}
			else
			{
				this.insertInternal(cursor.keys[cursor.count], 
                                    this.findParent(this.root, cursor),
                                    newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	public void insert(int x)
	{
		if (this.root == null)
		{
			// Add first node of tree
			this.root = new TreeNode(this.degree);
			this.root.isLeaf = true;
			this.root.count = 1;
			this.root.keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			int i = 0;
			int j = 0;
			TreeNode cursor = this.root;
			TreeNode parent = null;
			// Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				for (i = 0; i < cursor.count; i++)
				{
					if (x < cursor.keys[i])
					{
						cursor = cursor.child[i];
						break;
					}
					if (i == cursor.count - 1)
					{
						cursor = cursor.child[i + 1];
						break;
					}
				}
			}
			if (cursor.count < this.degree)
			{
				i = 0;
				while (x > cursor.keys[i] && i < cursor.count)
				{
					i++;
				}
				for (j = cursor.count; j > i; j--)
				{
					cursor.keys[j] = cursor.keys[j - 1];
				}
				cursor.keys[i] = x;
				cursor.count++;
				cursor.child[cursor.count] = cursor.child[cursor.count - 1];
				cursor.child[cursor.count - 1] = null;
			}
			else
			{
				TreeNode newLeaf = new TreeNode(this.degree);
				int[] virtualNode = new int[this.degree + 2];
				for (i = 0; i < this.degree; i++)
				{
					virtualNode[i] = cursor.keys[i];
				}
				i = 0;
				while (x > virtualNode[i] && i < this.degree)
				{
					i++;
				}
				for (j = this.degree + 1; j > i; j--)
				{
					virtualNode[j] = virtualNode[j - 1];
				}
				virtualNode[i] = x;
				newLeaf.isLeaf = true;
				cursor.count = (this.degree + 1) / 2;
				newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
				cursor.child[cursor.count] = newLeaf;
				newLeaf.child[newLeaf.count] = cursor.child[this.degree];
				cursor.child[this.degree] = null;
				for (i = 0; i < cursor.count; i++)
				{
					cursor.keys[i] = virtualNode[i];
				}
				for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
				{
					newLeaf.keys[i] = virtualNode[j];
				}
				if (cursor == this.root)
				{
					TreeNode newRoot = new TreeNode(this.degree);
					newRoot.keys[0] = newLeaf.keys[0];
					newRoot.child[0] = cursor;
					newRoot.child[1] = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					this.root = newRoot;
				}
				else
				{
					this.insertInternal(newLeaf.keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	public void printNode(TreeNode node)
	{
		if (node == null)
		{
			// When node is empty
			return;
		}
		else
		{
			int i = 0;
			// iterate the node element
			while (i < node.count)
			{
				if (node.isLeaf == false)
				{
					// When node is not leaf
					this.printNode(node.child[i]);
				}
				else
				{
					// Print the left node value
					Console.Write("  " + node.keys[i]);
				}
				i++;
			}
			if (node.isLeaf == false)
			{
				this.printNode(node.child[i]);
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create a new b+ tree with degree 4
		BPTree tree = new BPTree(4);
		// Add node
		tree.insert(10);
		tree.insert(7);
		tree.insert(15);
		tree.insert(2);
		tree.insert(-3);
		tree.insert(12);
		tree.insert(35);
		tree.insert(14);
		// Print Tree elements
		tree.printNode(tree.root);
	}
}

input

  -3  2  7  10  12  14  15  35
<?php
/*
  Php Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	public $isLeaf;
	public $keys;
	public $count;
	public $child;
	public function __construct($degree)
	{
		$this->isLeaf = false;
		$this->count = 0;
		$this->keys = array_fill(0, $degree, 0);
		$this->child = array_fill(0, $degree + 1, NULL);
		// Set initial child
		for ($i = 0; $i <= $degree; ++$i)
		{
			$this->child[$i] = NULL;
		}
	}
}
// Define tree structure
class BPTree
{
	public $root;
	public $degree;
	public function __construct($degree)
	{
		$this->degree = $degree;
		$this->root = NULL;
	}
	public function findParent($cursor, $child)
	{
		$parent = NULL;
		if ($cursor->isLeaf == true || ($cursor->child[0]).isLeaf == true)
		{
			return NULL;
		}
		for ($i = 0; $i < $cursor->count + 1; $i++)
		{
			if ($cursor->child[$i] == $child)
			{
				$parent = $cursor;
				return $parent;
			}
			else
			{
				$parent = $this->findParent($cursor->child[$i], $child);
				if ($parent != NULL)
				{
					return $parent;
				}
			}
		}
		return $parent;
	}
	public function insertInternal($x, $cursor, $child)
	{
		$i = 0;
		$j = 0;
		if ($cursor->count < $this->degree)
		{
			while ($x > $cursor->keys[$i] && $i < $cursor->count)
			{
				$i++;
			}
			for ($j = $cursor->count; $j > $i; $j--)
			{
				$cursor->keys[$j] = $cursor->keys[$j - 1];
			}
			for ($j = $cursor->count + 1; $j > $i + 1; $j--)
			{
				$cursor->child[$j] = $cursor->child[$j - 1];
			}
			$cursor->keys[$i] = $x;
			$cursor->count++;
			$cursor->child[$i + 1] = $child;
		}
		else
		{
			$newInternal = new TreeNode($this->degree);
			$virtualKey = array_fill(0, $this->degree + 1, 0);
			$virtualPtr = array_fill(0, $this->degree + 2, NULL);
			for ($i = 0; $i < $this->degree; $i++)
			{
				$virtualKey[$i] = $cursor->keys[$i];
			}
			for ($i = 0; $i < $this->degree + 1; $i++)
			{
				$virtualPtr[$i] = $cursor->child[$i];
			}
			$i = 0;
			while ($x > $virtualKey[$i] && $i < $this->degree)
			{
				$i++;
			}
			for ($j = $this->degree + 1; $j > $i; $j--)
			{
				$virtualKey[$j] = $virtualKey[$j - 1];
			}
			$virtualKey[$i] = $x;
			for ($j = $this->degree + 2; $j > $i + 1; $j--)
			{
				$virtualPtr[$j] = $virtualPtr[$j - 1];
			}
			$virtualPtr[$i + 1] = $child;
			$newInternal->isLeaf = false;
			$cursor->count = (int)(($this->degree + 1) / 2);
			$newInternal->count = $this->degree - (int)(($this->degree + 1) / 2);
			for ($i = 0, $j = $cursor->count + 1; $i < $newInternal->count;
                 $i++, $j++)
			{
				$newInternal->keys[$i] = $virtualKey[$j];
			}
			for ($i = 0, $j = $cursor->count + 1; $i < $newInternal->count + 1;
                 $i++, $j++)
			{
				$newInternal->child[$i] = $virtualPtr[$j];
			}
			if ($cursor == $this->root)
			{
				$this->root = new TreeNode($this->degree);
				$this->root->keys[0] = $cursor->keys[$cursor->count];
				$this->root->child[0] = $cursor;
				$this->root->child[1] = $newInternal;
				$this->root->isLeaf = false;
				$this->root->count = 1;
			}
			else
			{
				$this->insertInternal($cursor->keys[$cursor->count], 
                                      $this->findParent($this->root, $cursor),
                                      $newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	public function insert($x)
	{
		if ($this->root == NULL)
		{
			// Add first node of tree
			$this->root = new TreeNode($this->degree);
			$this->root->isLeaf = true;
			$this->root->count = 1;
			$this->root->keys[0] = $x;
		}
		else
		{
			// Loop controlling variables
			$i = 0;
			$j = 0;
			$cursor = $this->root;
			$parent = NULL;
			// Executes the loop until when cursor node is not leaf node
			while ($cursor->isLeaf == false)
			{
				// Get the current node
				$parent = $cursor;
				for ($i = 0; $i < $cursor->count; $i++)
				{
					if ($x < $cursor->keys[$i])
					{
						$cursor = $cursor->child[$i];
						break;
					}
					if ($i == $cursor->count - 1)
					{
						$cursor = $cursor->child[$i + 1];
						break;
					}
				}
			}
			if ($cursor->count < $this->degree)
			{
				$i = 0;
				while ($x > $cursor->keys[$i] && $i < $cursor->count)
				{
					$i++;
				}
				for ($j = $cursor->count; $j > $i; $j--)
				{
					$cursor->keys[$j] = $cursor->keys[$j - 1];
				}
				$cursor->keys[$i] = $x;
				$cursor->count++;
				$cursor->child[$cursor->count] = $cursor->child[$cursor->count - 1];
				$cursor->child[$cursor->count - 1] = NULL;
			}
			else
			{
				$newLeaf = new TreeNode($this->degree);
				$virtualNode = array_fill(0, $this->degree + 2, 0);
				for ($i = 0; $i < $this->degree; $i++)
				{
					$virtualNode[$i] = $cursor->keys[$i];
				}
				$i = 0;
				while ($x > $virtualNode[$i] && $i < $this->degree)
				{
					$i++;
				}
				for ($j = $this->degree + 1; $j > $i; $j--)
				{
					$virtualNode[$j] = $virtualNode[$j - 1];
				}
				$virtualNode[$i] = $x;
				$newLeaf->isLeaf = true;
				$cursor->count = (int)(($this->degree + 1) / 2);
				$newLeaf->count = $this->degree + 1 - (int)(($this->degree + 1) / 2);
				$cursor->child[$cursor->count] = $newLeaf;
				$newLeaf->child[$newLeaf->count] = $cursor->child[$this->degree];
				$cursor->child[$this->degree] = NULL;
				for ($i = 0; $i < $cursor->count; $i++)
				{
					$cursor->keys[$i] = $virtualNode[$i];
				}
				for ($i = 0, $j = $cursor->count; $i < $newLeaf->count; 
                     $i++, $j++)
				{
					$newLeaf->keys[$i] = $virtualNode[$j];
				}
				if ($cursor == $this->root)
				{
					$newRoot = new TreeNode($this->degree);
					$newRoot->keys[0] = $newLeaf->keys[0];
					$newRoot->child[0] = $cursor;
					$newRoot->child[1] = $newLeaf;
					$newRoot->isLeaf = false;
					$newRoot->count = 1;
					$this->root = $newRoot;
				}
				else
				{
					$this->insertInternal($newLeaf->keys[0], $parent, $newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	public function printNode($node)
	{
		if ($node == NULL)
		{
			// When node is empty
			return;
		}
		else
		{
			$i = 0;
			// iterate the node element
			while ($i < $node->count)
			{
				if ($node->isLeaf == false)
				{
					// When node is not leaf
					$this->printNode($node->child[$i]);
				}
				else
				{
					// Print the left node value
					echo "  ". $node->keys[$i];
				}
				$i++;
			}
			if ($node->isLeaf == false)
			{
				$this->printNode($node->child[$i]);
			}
		}
	}
}

function main()
{
	// Create a new b+ tree with degree 4
	$tree = new BPTree(4);
	// Add node
	$tree->insert(10);
	$tree->insert(7);
	$tree->insert(15);
	$tree->insert(2);
	$tree->insert(-3);
	$tree->insert(12);
	$tree->insert(35);
	$tree->insert(14);
	// Print Tree elements
	$tree->printNode($tree->root);
}
main();

input

  -3  2  7  10  12  14  15  35
/*
  Node JS Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	constructor(degree)
	{
		this.isLeaf = false;
		this.count = 0;
		this.keys = Array(degree).fill(0);
		this.child = Array(degree + 1).fill(null);
		// Set initial child
		for (var i = 0; i <= degree; ++i)
		{
			this.child[i] = null;
		}
	}
}
// Define tree structure
class BPTree
{
	constructor(degree)
	{
		this.degree = degree;
		this.root = null;
	}
	findParent(cursor, child)
	{
		var parent = null;
		if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true)
		{
			return null;
		}
		for (var i = 0; i < cursor.count + 1; i++)
		{
			if (cursor.child[i] == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = this.findParent(cursor.child[i], child);
				if (parent != null)
				{
					return parent;
				}
			}
		}
		return parent;
	}
	insertInternal(x, cursor, child)
	{
		var i = 0;
		var j = 0;
		if (cursor.count < this.degree)
		{
			while (x > cursor.keys[i] && i < cursor.count)
			{
				i++;
			}
			for (j = cursor.count; j > i; j--)
			{
				cursor.keys[j] = cursor.keys[j - 1];
			}
			for (j = cursor.count + 1; j > i + 1; j--)
			{
				cursor.child[j] = cursor.child[j - 1];
			}
			cursor.keys[i] = x;
			cursor.count++;
			cursor.child[i + 1] = child;
		}
		else
		{
			var newInternal = new TreeNode(this.degree);
			var virtualKey = Array(this.degree + 1).fill(0);
			var virtualPtr = Array(this.degree + 2).fill(null);
			for (i = 0; i < this.degree; i++)
			{
				virtualKey[i] = cursor.keys[i];
			}
			for (i = 0; i < this.degree + 1; i++)
			{
				virtualPtr[i] = cursor.child[i];
			}
			i = 0;
			while (x > virtualKey[i] && i < this.degree)
			{
				i++;
			}
			for (j = this.degree + 1; j > i; j--)
			{
				virtualKey[j] = virtualKey[j - 1];
			}
			virtualKey[i] = x;
			for (j = this.degree + 2; j > i + 1; j--)
			{
				virtualPtr[j] = virtualPtr[j - 1];
			}
			virtualPtr[i + 1] = child;
			newInternal.isLeaf = false;
			cursor.count = parseInt((this.degree + 1) / 2);
			newInternal.count = this.degree - parseInt((this.degree + 1) / 2);
			for (i = 0, j = cursor.count + 1; i < newInternal.count; i++, j++)
			{
				newInternal.keys[i] = virtualKey[j];
			}
			for (i = 0, j = cursor.count + 1; i < newInternal.count + 1; i++, j++)
			{
				newInternal.child[i] = virtualPtr[j];
			}
			if (cursor == this.root)
			{
				this.root = new TreeNode(this.degree);
				this.root.keys[0] = cursor.keys[cursor.count];
				this.root.child[0] = cursor;
				this.root.child[1] = newInternal;
				this.root.isLeaf = false;
				this.root.count = 1;
			}
			else
			{
				this.insertInternal(cursor.keys[cursor.count], this.findParent(this.root, cursor), newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	insert(x)
	{
		if (this.root == null)
		{
			// Add first node of tree
			this.root = new TreeNode(this.degree);
			this.root.isLeaf = true;
			this.root.count = 1;
			this.root.keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			var i = 0;
			var j = 0;
			var cursor = this.root;
			var parent = null;
			// Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				for (i = 0; i < cursor.count; i++)
				{
					if (x < cursor.keys[i])
					{
						cursor = cursor.child[i];
						break;
					}
					if (i == cursor.count - 1)
					{
						cursor = cursor.child[i + 1];
						break;
					}
				}
			}
			if (cursor.count < this.degree)
			{
				i = 0;
				while (x > cursor.keys[i] && i < cursor.count)
				{
					i++;
				}
				for (j = cursor.count; j > i; j--)
				{
					cursor.keys[j] = cursor.keys[j - 1];
				}
				cursor.keys[i] = x;
				cursor.count++;
				cursor.child[cursor.count] = cursor.child[cursor.count - 1];
				cursor.child[cursor.count - 1] = null;
			}
			else
			{
				var newLeaf = new TreeNode(this.degree);
				var virtualNode = Array(this.degree + 2).fill(0);
				for (i = 0; i < this.degree; i++)
				{
					virtualNode[i] = cursor.keys[i];
				}
				i = 0;
				while (x > virtualNode[i] && i < this.degree)
				{
					i++;
				}
				for (j = this.degree + 1; j > i; j--)
				{
					virtualNode[j] = virtualNode[j - 1];
				}
				virtualNode[i] = x;
				newLeaf.isLeaf = true;
				cursor.count = parseInt((this.degree + 1) / 2);
				newLeaf.count = this.degree + 1 - parseInt((this.degree + 1) / 2);
				cursor.child[cursor.count] = newLeaf;
				newLeaf.child[newLeaf.count] = cursor.child[this.degree];
				cursor.child[this.degree] = null;
				for (i = 0; i < cursor.count; i++)
				{
					cursor.keys[i] = virtualNode[i];
				}
				for (i = 0, j = cursor.count; i < newLeaf.count; i++, j++)
				{
					newLeaf.keys[i] = virtualNode[j];
				}
				if (cursor == this.root)
				{
					var newRoot = new TreeNode(this.degree);
					newRoot.keys[0] = newLeaf.keys[0];
					newRoot.child[0] = cursor;
					newRoot.child[1] = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					this.root = newRoot;
				}
				else
				{
					this.insertInternal(newLeaf.keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	printNode(node)
	{
		if (node == null)
		{
			// When node is empty
			return;
		}
		else
		{
			var i = 0;
			// iterate the node element
			while (i < node.count)
			{
				if (node.isLeaf == false)
				{
					// When node is not leaf
					this.printNode(node.child[i]);
				}
				else
				{
					// Print the left node value
					process.stdout.write("  " + node.keys[i]);
				}
				i++;
			}
			if (node.isLeaf == false)
			{
				this.printNode(node.child[i]);
			}
		}
	}
}

function main()
{
	// Create a new b+ tree with degree 4
	var tree = new BPTree(4);
	// Add node
	tree.insert(10);
	tree.insert(7);
	tree.insert(15);
	tree.insert(2);
	tree.insert(-3);
	tree.insert(12);
	tree.insert(35);
	tree.insert(14);
	// Print Tree elements
	tree.printNode(tree.root);
}
main();

input

  -3  2  7  10  12  14  15  35
# Python 3 Program
# Check if two numbers are co - prime or not
# Define tree node
class TreeNode :
	def __init__(self, degree) :
		self.isLeaf = False
		self.count = 0
		self.keys = [0] * (degree)
		self.child = [None] * (degree + 1)
		# Set initial child
		i = 0
		while (i <= degree) :
			self.child[i] = None
			i += 1
		
	

# Define tree structure
class BPTree :
	def __init__(self, degree) :
		self.degree = degree
		self.root = None
	
	def findParent(self, cursor, child) :
		parent = None
		if (cursor.isLeaf == True or (cursor.child[0]).isLeaf == True) :
			return None
		
		i = 0
		while (i < cursor.count + 1) :
			if (cursor.child[i] == child) :
				parent = cursor
				return parent
			else :
				parent = self.findParent(cursor.child[i], child)
				if (parent != None) :
					return parent
				
			
			i += 1
		
		return parent
	
	def insertInternal(self, x, cursor, child) :
		i = 0
		j = 0
		if (cursor.count < self.degree) :
			while (x > cursor.keys[i] and i < cursor.count) :
				i += 1
			
			j = cursor.count
			while (j > i) :
				cursor.keys[j] = cursor.keys[j - 1]
				j -= 1
			
			j = cursor.count + 1
			while (j > i + 1) :
				cursor.child[j] = cursor.child[j - 1]
				j -= 1
			
			cursor.keys[i] = x
			cursor.count += 1
			cursor.child[i + 1] = child
		else :
			newInternal = TreeNode(self.degree)
			virtualKey = [0] * (self.degree + 1)
			virtualPtr = [None] * (self.degree + 2)
			i = 0
			while (i < self.degree) :
				virtualKey[i] = cursor.keys[i]
				i += 1
			
			i = 0
			while (i < self.degree + 1) :
				virtualPtr[i] = cursor.child[i]
				i += 1
			
			i = 0
			while (x > virtualKey[i] and i < self.degree) :
				i += 1
			
			j = self.degree + 1
			while (j > i) :
				virtualKey[j] = virtualKey[j - 1]
				j -= 1
			
			virtualKey[i] = x
			j = self.degree + 2
			while (j > i + 1) :
				virtualPtr[j] = virtualPtr[j - 1]
				j -= 1
			
			virtualPtr[i + 1] = child
			newInternal.isLeaf = False
			cursor.count = int((self.degree + 1) / 2)
			newInternal.count = self.degree - int((self.degree + 1) / 2)
			i = 0
			j = cursor.count + 1
			while (i < newInternal.count) :
				newInternal.keys[i] = virtualKey[j]
				i += 1
				j += 1
			
			i = 0
			j = cursor.count + 1
			while (i < newInternal.count + 1) :
				newInternal.child[i] = virtualPtr[j]
				i += 1
				j += 1
			
			if (cursor == self.root) :
				self.root = TreeNode(self.degree)
				self.root.keys[0] = cursor.keys[cursor.count]
				self.root.child[0] = cursor
				self.root.child[1] = newInternal
				self.root.isLeaf = False
				self.root.count = 1
			else :
				self.insertInternal(cursor.keys[cursor.count], 
                                    self.findParent(self.root, cursor),
                                    newInternal)
			
		
	
	# Handles the request to add new node in B + tree
	def insert(self, x) :
		if (self.root == None) :
			# Add first node of tree
			self.root = TreeNode(self.degree)
			self.root.isLeaf = True
			self.root.count = 1
			self.root.keys[0] = x
		else :
			i = 0
			j = 0
			cursor = self.root
			parent = None
			# Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == False) :
				# Get the current node
				parent = cursor
				i = 0
				while (i < cursor.count) :
					if (x < cursor.keys[i]) :
						cursor = cursor.child[i]
						break
					
					if (i == cursor.count - 1) :
						cursor = cursor.child[i + 1]
						break
					
					i += 1
				
			
			if (cursor.count < self.degree) :
				i = 0
				while (x > cursor.keys[i] and i < cursor.count) :
					i += 1
				
				j = cursor.count
				while (j > i) :
					cursor.keys[j] = cursor.keys[j - 1]
					j -= 1
				
				cursor.keys[i] = x
				cursor.count += 1
				cursor.child[cursor.count] = cursor.child[cursor.count - 1]
				cursor.child[cursor.count - 1] = None
			else :
				newLeaf = TreeNode(self.degree)
				virtualNode = [0] * (self.degree + 2)
				i = 0
				while (i < self.degree) :
					virtualNode[i] = cursor.keys[i]
					i += 1
				
				i = 0
				while (x > virtualNode[i] and i < self.degree) :
					i += 1
				
				j = self.degree + 1
				while (j > i) :
					virtualNode[j] = virtualNode[j - 1]
					j -= 1
				
				virtualNode[i] = x
				newLeaf.isLeaf = True
				cursor.count = int((self.degree + 1) / 2)
				newLeaf.count = self.degree + 1 - int((self.degree + 1) / 2)
				cursor.child[cursor.count] = newLeaf
				newLeaf.child[newLeaf.count] = cursor.child[self.degree]
				cursor.child[self.degree] = None
				i = 0
				while (i < cursor.count) :
					cursor.keys[i] = virtualNode[i]
					i += 1
				
				i = 0
				j = cursor.count
				while (i < newLeaf.count) :
					newLeaf.keys[i] = virtualNode[j]
					i += 1
					j += 1
				
				if (cursor == self.root) :
					newRoot = TreeNode(self.degree)
					newRoot.keys[0] = newLeaf.keys[0]
					newRoot.child[0] = cursor
					newRoot.child[1] = newLeaf
					newRoot.isLeaf = False
					newRoot.count = 1
					self.root = newRoot
				else :
					self.insertInternal(newLeaf.keys[0], parent, newLeaf)
				
			
		
	
	# Print the elements of B + tree elements
	def printNode(self, node) :
		if (node == None) :
			# When node is empty
			return
		else :
			i = 0
			# iterate the node element
			while (i < node.count) :
				if (node.isLeaf == False) :
					# When node is not leaf
					self.printNode(node.child[i])
				else :
					# Print the left node value
					print("  ", node.keys[i], end = "")
				
				i += 1
			
			if (node.isLeaf == False) :
				self.printNode(node.child[i])
			
		
	

def main() :
	tree = BPTree(4)
	# Add node
	tree.insert(10)
	tree.insert(7)
	tree.insert(15)
	tree.insert(2)
	tree.insert(-3)
	tree.insert(12)
	tree.insert(35)
	tree.insert(14)
	# Print Tree elements
	tree.printNode(tree.root)

if __name__ == "__main__": main()

input

   -3   2   7   10   12   14   15   35
# Ruby Program
# Check if two numbers are co - prime or not
# Define tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :isLeaf, :keys, :count, :child
	attr_accessor :isLeaf, :keys, :count, :child
	def initialize(degree) 
		self.isLeaf = false
		self.count = 0
		self.keys = Array.new(degree) {0}
		self.child = Array.new(degree + 1) {nil}
		# Set initial child
		i = 0
		while (i <= degree) 
			self.child[i] = nil
			i += 1
		end

	end

end

# Define tree structure
class BPTree 
	# Define the accessor and reader of class BPTree
	attr_reader :root, :degree
	attr_accessor :root, :degree
	def initialize(degree) 
		self.degree = degree
		self.root = nil
	end

	def findParent(cursor, child) 
		parent = nil
		if (cursor.isLeaf == true || (cursor.child[0]).isLeaf == true) 
			return nil
		end

		i = 0
		while (i < cursor.count + 1) 
			if (cursor.child[i] == child) 
				parent = cursor
				return parent
			else 
				parent = self.findParent(cursor.child[i], child)
				if (parent != nil) 
					return parent
				end

			end

			i += 1
		end

		return parent
	end

	def insertInternal(x, cursor, child) 
		i = 0
		j = 0
		if (cursor.count < self.degree) 
			while (x > cursor.keys[i] && i < cursor.count) 
				i += 1
			end

			j = cursor.count
			while (j > i) 
				cursor.keys[j] = cursor.keys[j - 1]
				j -= 1
			end

			j = cursor.count + 1
			while (j > i + 1) 
				cursor.child[j] = cursor.child[j - 1]
				j -= 1
			end

			cursor.keys[i] = x
			cursor.count += 1
			cursor.child[i + 1] = child
		else 
			newInternal = TreeNode.new(self.degree)
			virtualKey = Array.new(self.degree + 1) {0}
			virtualPtr = Array.new(self.degree + 2) {nil}
			i = 0
			while (i < self.degree) 
				virtualKey[i] = cursor.keys[i]
				i += 1
			end

			i = 0
			while (i < self.degree + 1) 
				virtualPtr[i] = cursor.child[i]
				i += 1
			end

			i = 0
			while (x > virtualKey[i] && i < self.degree) 
				i += 1
			end

			j = self.degree + 1
			while (j > i) 
				virtualKey[j] = virtualKey[j - 1]
				j -= 1
			end

			virtualKey[i] = x
			j = self.degree + 2
			while (j > i + 1) 
				virtualPtr[j] = virtualPtr[j - 1]
				j -= 1
			end

			virtualPtr[i + 1] = child
			newInternal.isLeaf = false
			cursor.count = (self.degree + 1) / 2
			newInternal.count = self.degree - (self.degree + 1) / 2
			i = 0, j = cursor.count + 1
			while (i < newInternal.count) 
				newInternal.keys[i] = virtualKey[j]
				i += 1
				j += 1
			end

			i = 0
			j = cursor.count + 1
			while (i < newInternal.count + 1) 
				newInternal.child[i] = virtualPtr[j]
				i += 1
				j += 1
			end

			if (cursor == self.root) 
				self.root = TreeNode.new(self.degree)
				self.root.keys[0] = cursor.keys[cursor.count]
				self.root.child[0] = cursor
				self.root.child[1] = newInternal
				self.root.isLeaf = false
				self.root.count = 1
			else 
				self.insertInternal(cursor.keys[cursor.count],
                                    self.findParent(self.root, cursor), 
                                    newInternal)
			end

		end

	end

	# Handles the request to add new node in B + tree
	def insert(x) 
		if (self.root == nil) 
			# Add first node of tree
			self.root = TreeNode.new(self.degree)
			self.root.isLeaf = true
			self.root.count = 1
			self.root.keys[0] = x
		else 
			# Loop controlling variables
			i = 0
			j = 0
			cursor = self.root
			parent = nil
			# Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == false) 
				# Get the current node
				parent = cursor
				i = 0
				while (i < cursor.count) 
					if (x < cursor.keys[i]) 
						cursor = cursor.child[i]
						break
					end

					if (i == cursor.count - 1) 
						cursor = cursor.child[i + 1]
						break
					end

					i += 1
				end

			end

			if (cursor.count < self.degree) 
				i = 0
				while (x > cursor.keys[i] && i < cursor.count) 
					i += 1
				end

				j = cursor.count
				while (j > i) 
					cursor.keys[j] = cursor.keys[j - 1]
					j -= 1
				end

				cursor.keys[i] = x
				cursor.count += 1
				cursor.child[cursor.count] = cursor.child[cursor.count - 1]
				cursor.child[cursor.count - 1] = nil
			else 
				newLeaf = TreeNode.new(self.degree)
				virtualNode = Array.new(self.degree + 2) {0}
				i = 0
				while (i < self.degree) 
					virtualNode[i] = cursor.keys[i]
					i += 1
				end

				i = 0
				while (x > virtualNode[i] && i < self.degree) 
					i += 1
				end

				j = self.degree + 1
				while (j > i) 
					virtualNode[j] = virtualNode[j - 1]
					j -= 1
				end

				virtualNode[i] = x
				newLeaf.isLeaf = true
				cursor.count = (self.degree + 1) / 2
				newLeaf.count = self.degree + 1 - (self.degree + 1) / 2
				cursor.child[cursor.count] = newLeaf
				newLeaf.child[newLeaf.count] = cursor.child[self.degree]
				cursor.child[self.degree] = nil
				i = 0
				while (i < cursor.count) 
					cursor.keys[i] = virtualNode[i]
					i += 1
				end

				i = 0
				j = cursor.count
				while (i < newLeaf.count) 
					newLeaf.keys[i] = virtualNode[j]
					i += 1
					j += 1
				end

				if (cursor == self.root) 
					newRoot = TreeNode.new(self.degree)
					newRoot.keys[0] = newLeaf.keys[0]
					newRoot.child[0] = cursor
					newRoot.child[1] = newLeaf
					newRoot.isLeaf = false
					newRoot.count = 1
					self.root = newRoot
				else 
					self.insertInternal(newLeaf.keys[0], parent, newLeaf)
				end

			end

		end

	end

	# Print the elements of B + tree elements
	def printNode(node) 
		if (node == nil) 
			# When node is empty
			return
		else 
			i = 0
			# iterate the node element
			while (i < node.count) 
				if (node.isLeaf == false) 
					# When node is not leaf
					self.printNode(node.child[i])
				else 
					# Print the left node value
					print("  ", node.keys[i])
				end

				i += 1
			end

			if (node.isLeaf == false) 
				self.printNode(node.child[i])
			end

		end

	end

end

def main() 
	# Create a new b + tree with degree 4
	tree = BPTree.new(4)
	# Add node
	tree.insert(10)
	tree.insert(7)
	tree.insert(15)
	tree.insert(2)
	tree.insert(-3)
	tree.insert(12)
	tree.insert(35)
	tree.insert(14)
	# Print Tree elements
	tree.printNode(tree.root)
end

main()

input

  -3  2  7  10  12  14  15  35
/*
  Scala Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode(var isLeaf: Boolean , var keys: Array[Int] , var count: Int , var child: Array[TreeNode])
{
	def this(degree: Int)
	{
      	this(false,
             Array.fill[Int](degree)(0),
             0,
             Array.fill[TreeNode](degree + 1)(null)
        );
	}
}
// Define tree structure
class BPTree(var root: TreeNode , var degree: Int)
{
	def this(degree: Int)
	{
		this(null,degree)
	}
	def findParent(cursor: TreeNode, child: TreeNode): TreeNode = {
		var parent: TreeNode = null;
		if (cursor.isLeaf == true || (cursor.child(0)).isLeaf == true)
		{
			return null;
		}
		var i: Int = 0;
		while (i < cursor.count + 1)
		{
			if (cursor.child(i) == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = findParent(cursor.child(i), child);
				if (parent != null)
				{
					return parent;
				}
			}
			i += 1;
		}
		return parent;
	}
	def insertInternal(x: Int, cursor: TreeNode, child: TreeNode): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		if (cursor.count < this.degree)
		{
			while (x > cursor.keys(i) && i < cursor.count)
			{
				i += 1;
			}
			j = cursor.count;
			while (j > i)
			{
				cursor.keys(j) = cursor.keys(j - 1);
				j -= 1
			}
			j = cursor.count + 1;
			while (j > i + 1)
			{
				cursor.child(j) = cursor.child(j - 1);
				j -= 1
			}
			cursor.keys(i) = x;
			cursor.count += 1;
			cursor.child(i + 1) = child;
		}
		else
		{
			var newInternal: TreeNode = new TreeNode(this.degree);
			var virtualKey: Array[Int] = Array.fill[Int](this.degree + 1)(0);
			var virtualPtr: Array[TreeNode] = Array.fill[TreeNode](this.degree + 2)(null);
			i = 0;
			while (i < this.degree)
			{
				virtualKey(i) = cursor.keys(i);
				i += 1
			}
			i = 0;
			while (i < this.degree + 1)
			{
				virtualPtr(i) = cursor.child(i);
				i += 1
			}
			i = 0;
			while (x > virtualKey(i) && i < this.degree)
			{
				i += 1;
			}
			j = this.degree + 1;
			while (j > i)
			{
				virtualKey(j) = virtualKey(j - 1);
				j -= 1
			}
			virtualKey(i) = x;
			j = this.degree + 2;
			while (j > i + 1)
			{
				virtualPtr(j) = virtualPtr(j - 1);
				j -= 1;
			}
			virtualPtr(i + 1) = child;
			newInternal.isLeaf = false;
			cursor.count = ((this.degree + 1) / 2).toInt;
			newInternal.count = this.degree - ((this.degree + 1) / 2).toInt;
			i = 0;
          	j = cursor.count + 1;
			while (i < newInternal.count)
			{
				newInternal.keys(i) = virtualKey(j);
				i += 1; 
              	j += 1;
			}
			i = 0;
          	j = cursor.count + 1;
			while (i < newInternal.count + 1)
			{
				newInternal.child(i) = virtualPtr(j);
				i += 1;
                j += 1;
			}
			if (cursor == this.root)
			{
				this.root = new TreeNode(this.degree);
				this.root.keys(0) = cursor.keys(cursor.count);
				this.root.child(0) = cursor;
				this.root.child(1) = newInternal;
				this.root.isLeaf = false;
				this.root.count = 1;
			}
			else
			{
				insertInternal(cursor.keys(cursor.count), findParent(this.root, cursor), newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	def insert(x: Int): Unit = {
		if (this.root == null)
		{
			// Add first node of tree
			this.root = new TreeNode(this.degree);
			this.root.isLeaf = true;
			this.root.count = 1;
			this.root.keys(0) = x;
		}
		else
		{
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 0;
			var cursor: TreeNode = this.root;
			var parent: TreeNode = null;
			// Executes the loop until when cursor node is not leaf node
			while (cursor.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				i = 0;
				while (i < cursor.count)
				{
					if (x < cursor.keys(i))
					{
						cursor = cursor.child(i);
                      	// break
						i = cursor.count;
					}
					if (i == cursor.count - 1)
					{
						cursor = cursor.child(i + 1);
                      	// break
						i = cursor.count;
					}
					i += 1
				}
			}
			i = 0;
			if (cursor.count < this.degree)
			{
				
				while (x > cursor.keys(i) && i < cursor.count)
				{
					i += 1;
				}
				j = cursor.count;
				while (j > i)
				{
					cursor.keys(j) = cursor.keys(j - 1);
					j -= 1
				}
				cursor.keys(i) = x;
				cursor.count += 1;
				cursor.child(cursor.count) = cursor.child(cursor.count - 1);
				cursor.child(cursor.count - 1) = null;
			}
			else
			{
				var newLeaf: TreeNode = new TreeNode(this.degree);
				var virtualNode: Array[Int] = Array.fill[Int](this.degree + 2)(0);
				i = 0;
				while (i < this.degree)
				{
					virtualNode(i) = cursor.keys(i);
					i += 1
				}
				i = 0;
				while (x > virtualNode(i) && i < this.degree)
				{
					i += 1;
				}
				j = this.degree + 1;
				while (j > i)
				{
					virtualNode(j) = virtualNode(j - 1);
					j -= 1
				}
				virtualNode(i) = x;
				newLeaf.isLeaf = true;
				cursor.count = ((this.degree + 1) / 2).toInt;
				newLeaf.count = this.degree + 1 - ((this.degree + 1) / 2).toInt;
				cursor.child(cursor.count) = newLeaf;
				newLeaf.child(newLeaf.count) = cursor.child(this.degree);
				cursor.child(this.degree) = null;
				i = 0;
				while (i < cursor.count)
				{
					cursor.keys(i) = virtualNode(i);
					i += 1
				}
				i = 0;
              	j = cursor.count;
				while (i < newLeaf.count)
				{
					newLeaf.keys(i) = virtualNode(j);
					i += 1;
                    j += 1
				}
				if (cursor == this.root)
				{
					var newRoot: TreeNode = new TreeNode(this.degree);
					newRoot.keys(0) = newLeaf.keys(0);
					newRoot.child(0) = cursor;
					newRoot.child(1) = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					this.root = newRoot;
				}
				else
				{
					insertInternal(newLeaf.keys(0), parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	def printNode(node: TreeNode): Unit = {
		if (node == null)
		{
			// When node is empty
			return;
		}
		else
		{
			var i: Int = 0;
			// iterate the node element
			while (i < node.count)
			{
				if (node.isLeaf == false)
				{
					// When node is not leaf
					printNode(node.child(i));
				}
				else
				{
					// Print the left node value
					print("  " + node.keys(i));
				}
				i += 1;
			}
			if (node.isLeaf == false)
			{
				printNode(node.child(i));
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create a new b+ tree with degree 4
		var tree: BPTree = new BPTree(4);
		// Add node
		tree.insert(10);
		tree.insert(7);
		tree.insert(15);
		tree.insert(2);
		tree.insert(-3);
		tree.insert(12);
		tree.insert(35);
		tree.insert(14);
		// Print Tree elements
		tree.printNode(tree.root);
	}
}

input

  -3  2  7  10  12  14  15  35
/*
  Swift 4 Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	var isLeaf: Bool;
	var keys: [Int];
	var count: Int;
	var child: [TreeNode?];
	init(_ degree: Int)
	{
		self.isLeaf = false;
		self.count = 0;
		self.keys = Array(repeating: 0, count: degree);
		self.child = Array(repeating: nil, count: degree + 1);
		// Set initial child
		var i: Int = 0;
		while (i <= degree)
		{
			self.child[i] = nil;
			i += 1;
		}
	}
}
// Define tree structure
class BPTree
{
	var root: TreeNode? ;
	var degree: Int;
	init(_ degree: Int)
	{
		self.degree = degree;
		self.root = nil;
	}
	func findParent(_ cursor: TreeNode? , _ child : TreeNode? )->TreeNode?
	{
		var parent: TreeNode? = nil;
		if (cursor!.isLeaf == true || (cursor!.child[0])!.isLeaf == true)
		{
			return nil;
		}
		var i: Int = 0;
		while (i < cursor!.count + 1)
		{
			if (cursor!.child[i] === child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = self.findParent(cursor!.child[i], child);
				if (parent  != nil)
				{
					return parent;
				}
			}
			i += 1;
		}
		return parent;
	}
	func insertInternal(_ x: Int, _ cursor: TreeNode? , _ child : TreeNode? )
	{
		var i: Int = 0;
		var j: Int = 0;
		if (cursor!.count < self.degree)
		{
			while (x > cursor!.keys[i] && i < cursor!.count)
			{
				i += 1;
			}
			j = cursor!.count;
			while (j > i)
			{
				cursor!.keys[j] = cursor!.keys[j - 1];
				j -= 1;
			}
			j = cursor!.count + 1;
			while (j > i + 1)
			{
				cursor!.child[j] = cursor!.child[j - 1];
				j -= 1;
			}
			cursor!.keys[i] = x;
			cursor!.count += 1;
			cursor!.child[i + 1] = child;
		}
		else
		{
			let newInternal: TreeNode = TreeNode(self.degree);
			var virtualKey: [Int] = Array(repeating: 0, count: self.degree + 1);
			var virtualPtr: [TreeNode?] = Array(repeating: nil, count: self.degree + 2);
			i = 0;
			while (i < self.degree)
			{
				virtualKey[i] = cursor!.keys[i];
				i += 1;
			}
			i = 0;
			while (i < self.degree + 1)
			{
				virtualPtr[i] = cursor!.child[i];
				i += 1;
			}
			i = 0;
			while (x > virtualKey[i] && i < self.degree)
			{
				i += 1;
			}
			j = self.degree + 1;
			while (j > i)
			{
				virtualKey[j] = virtualKey[j - 1];
				j -= 1;
			}
			virtualKey[i] = x;
			j = self.degree + 2;
			while (j > i + 1)
			{
				virtualPtr[j] = virtualPtr[j - 1];
				j -= 1;
			}
			virtualPtr[i + 1] = child;
			newInternal.isLeaf = false;
			cursor!.count = (self.degree + 1) / 2;
			newInternal.count = self.degree - (self.degree + 1) / 2;
			i = 0;
			j = cursor!.count + 1;
			while (i < newInternal.count)
			{
				newInternal.keys[i] = virtualKey[j];
				i += 1;
				j += 1;
			}
			i = 0;
			j = cursor!.count + 1;
			while (i < newInternal.count + 1)
			{
				newInternal.child[i] = virtualPtr[j];
				i += 1;
				j += 1;
			}
			if (cursor === self.root)
			{
				self.root = TreeNode(self.degree);
				self.root!.keys[0] = cursor!.keys[cursor!.count];
				self.root!.child[0] = cursor;
				self.root!.child[1] = newInternal;
				self.root!.isLeaf = false;
				self.root!.count = 1;
			}
			else
			{
				self.insertInternal(cursor!.keys[cursor!.count], self.findParent(self.root, cursor), newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	func insert(_ x: Int)
	{
		if (self.root == nil)
		{
			// Add first node of tree
			self.root = TreeNode(self.degree);
			self.root!.isLeaf = true;
			self.root!.count = 1;
			self.root!.keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 0;
			var cursor: TreeNode? = self.root;
			var parent: TreeNode? = nil;
			// Executes the loop until when cursor node is not leaf node
			while (cursor!.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				i = 0;
				while (i < cursor!.count)
				{
					if (x < cursor!.keys[i])
					{
						cursor = cursor!.child[i];
						break;
					}
					if (i == cursor!.count - 1)
					{
						cursor = cursor!.child[i + 1];
						break;
					}
					i += 1;
				}
			}
			if (cursor!.count < self.degree)
			{
				i = 0;
				while (x > cursor!.keys[i] && i < cursor!.count)
				{
					i += 1;
				}
				j = cursor!.count;
				while (j > i)
				{
					cursor!.keys[j] = cursor!.keys[j - 1];
					j -= 1;
				}
				cursor!.keys[i] = x;
				cursor!.count += 1;
				cursor!.child[cursor!.count] = cursor!.child[cursor!.count - 1];
				cursor!.child[cursor!.count - 1] = nil;
			}
			else
			{
				let newLeaf: TreeNode = TreeNode(self.degree);
				var virtualNode: [Int] = Array(repeating: 0, count: self.degree + 2);
				i = 0;
				while (i < self.degree)
				{
					virtualNode[i] = cursor!.keys[i];
					i += 1;
				}
				i = 0;
				while (x > virtualNode[i] && i < self.degree)
				{
					i += 1;
				}
				j = self.degree + 1;
				while (j > i)
				{
					virtualNode[j] = virtualNode[j - 1];
					j -= 1;
				}
				virtualNode[i] = x;
				newLeaf.isLeaf = true;
				cursor!.count = (self.degree + 1) / 2;
				newLeaf.count = self.degree + 1 - (self.degree + 1) / 2;
				cursor!.child[cursor!.count] = newLeaf;
				newLeaf.child[newLeaf.count] = cursor!.child[self.degree];
				cursor!.child[self.degree] = nil;
				i = 0;
				while (i < cursor!.count)
				{
					cursor!.keys[i] = virtualNode[i];
					i += 1;
				}
				i = 0;
				j = cursor!.count;
				while (i < newLeaf.count)
				{
					newLeaf.keys[i] = virtualNode[j];
					i += 1;
					j += 1;
				}
				if (cursor === self.root)
				{
					let newRoot: TreeNode = TreeNode(self.degree);
					newRoot.keys[0] = newLeaf.keys[0];
					newRoot.child[0] = cursor;
					newRoot.child[1] = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					self.root = newRoot;
				}
				else
				{
					self.insertInternal(newLeaf.keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	func printNode(_ node: TreeNode? )
	{
		if (node == nil)
		{
			// When node is empty
			return;
		}
		else
		{
			var i: Int = 0;
			// iterate the node element
			while (i < node!.count)
			{
				if (node!.isLeaf == false)
				{
					// When node is not leaf
					self.printNode(node!.child[i]);
				}
				else
				{
					// Print the left node value
					print("  ", node!.keys[i], terminator: "");
				}
				i += 1;
			}
			if (node!.isLeaf == false)
			{
				self.printNode(node!.child[i]);
			}
		}
	}
}
func main()
{
	// Create a new b+ tree with degree 4
	let tree: BPTree = BPTree(4);
	// Add node
	tree.insert(10);
	tree.insert(7);
	tree.insert(15);
	tree.insert(2);
	tree.insert(-3);
	tree.insert(12);
	tree.insert(35);
	tree.insert(14);
	// Print Tree elements
	tree.printNode(tree.root);
}
main();

input

   -3   2   7   10   12   14   15   35
/*
  Kotlin Program 
  Implement B Plus Tree Implement
*/
// Define tree node
class TreeNode
{
	var isLeaf: Boolean;
	var keys: Array < Int > ;
	var count: Int;
	var child: Array < TreeNode? > ;
	constructor(degree: Int)
	{
		this.isLeaf = false;
		this.count = 0;
		this.keys = Array(degree)
		{
			0
		};
		this.child = Array(degree + 1)
		{
			null
		};
		var i: Int = 0;
		while (i <= degree)
		{
			this.child[i] = null;
			i += 1;
		}
	}
}
// Define tree structure
class BPTree
{
	var root: TreeNode ? ;
	var degree: Int;
	constructor(degree: Int)
	{
		this.degree = degree;
		this.root = null;
	}
	fun findParent(cursor: TreeNode ? , child : TreeNode ? ): TreeNode?
	{
		var parent: TreeNode ? = null;
		if (cursor!!.isLeaf == true || (cursor.child[0])!!.isLeaf == true)
		{
			return null;
		}
		var i: Int = 0;
		while (i < cursor.count + 1)
		{
			if (cursor.child[i] == child)
			{
				parent = cursor;
				return parent;
			}
			else
			{
				parent = this.findParent(cursor.child[i], child);
				if (parent != null)
				{
					return parent;
				}
			}
			i += 1;
		}
		return parent;
	}
	fun insertInternal(x: Int, cursor: TreeNode ? , child : TreeNode ? ): Unit
	{
		var i: Int = 0;
		var j: Int ;
		if (cursor!!.count < this.degree)
		{
			while (x > cursor.keys[i] && i < cursor.count)
			{
				i += 1;
			}
			j = cursor.count;
			while (j > i)
			{
				cursor.keys[j] = cursor.keys[j - 1];
				j -= 1;
			}
			j = cursor.count + 1;
			while (j > i + 1)
			{
				cursor.child[j] = cursor.child[j - 1];
				j -= 1;
			}
			cursor.keys[i] = x;
			cursor.count += 1;
			cursor.child[i + 1] = child;
		}
		else
		{
			val newInternal: TreeNode = TreeNode(this.degree);
			val virtualKey: Array < Int > = Array(this.degree + 1)
			{
				0
			};
			val virtualPtr: Array < TreeNode? > = Array(this.degree + 2)
			{
				null
			};
			i = 0;
			while (i < this.degree)
			{
				virtualKey[i] = cursor.keys[i];
				i += 1;
			}
			i = 0;
			while (i < this.degree + 1)
			{
				virtualPtr[i] = cursor.child[i];
				i += 1;
			}
			i = 0;
			while (x > virtualKey[i] && i < this.degree)
			{
				i += 1;
			}
			j = this.degree + 1;
			while (j > i)
			{
				virtualKey[j] = virtualKey[j - 1];
				j -= 1;
			}
			virtualKey[i] = x;
			j = this.degree + 2;
			while (j > i + 1)
			{
				virtualPtr[j] = virtualPtr[j - 1];
				j -= 1;
			}
			virtualPtr[i + 1] = child;
			newInternal.isLeaf = false;
			cursor.count = (this.degree + 1) / 2;
			newInternal.count = this.degree - (this.degree + 1) / 2;
			i = 0;
			j = cursor.count + 1;
			while (i < newInternal.count)
			{
				newInternal.keys[i] = virtualKey[j];
				i += 1;
				j += 1;
			}
			i = 0;
			j = cursor.count + 1;
			while (i < newInternal.count + 1)
			{
				newInternal.child[i] = virtualPtr[j];
				i += 1;
				j += 1;
			}
			if (cursor == this.root)
			{
				this.root = TreeNode(this.degree);
				this.root!!.keys[0] = cursor.keys[cursor.count];
				this.root!!.child[0] = cursor;
				this.root!!.child[1] = newInternal;
				this.root!!.isLeaf = false;
				this.root!!.count = 1;
			}
			else
			{
				this.insertInternal(cursor.keys[cursor.count], this.findParent(this.root, cursor), newInternal);
			}
		}
	}
	// Handles the request to add new node in B+ tree
	fun insert(x: Int): Unit
	{
		if (this.root == null)
		{
			// Add first node of tree
			this.root = TreeNode(this.degree);
			this.root!!.isLeaf = true;
			this.root!!.count = 1;
			this.root!!.keys[0] = x;
		}
		else
		{
			// Loop controlling variables
			var i: Int ;
			var j: Int ;
			var cursor: TreeNode ? = this.root;
			var parent: TreeNode ? = null;
			while (cursor!!.isLeaf == false)
			{
				// Get the current node
				parent = cursor;
				i = 0;
				while (i < cursor!!.count)
				{
					if (x < cursor.keys[i])
					{
						cursor = cursor.child[i];
						break;
					}
					if (i == cursor.count - 1)
					{
						cursor = cursor.child[i + 1];
						break;
					}
					i += 1;
				}
			}
			if (cursor.count < this.degree)
			{
				i = 0;
				while (x > cursor.keys[i] && i < cursor.count)
				{
					i += 1;
				}
				j = cursor.count;
				while (j > i)
				{
					cursor.keys[j] = cursor.keys[j - 1];
					j -= 1;
				}
				cursor.keys[i] = x;
				cursor.count += 1;
				cursor.child[cursor.count] = cursor.child[cursor.count - 1];
				cursor.child[cursor.count - 1] = null;
			}
			else
			{
				val newLeaf: TreeNode = TreeNode(this.degree);
				val virtualNode: Array < Int > = Array(this.degree + 2)
				{
					0
				};
				i = 0;
				while (i < this.degree)
				{
					virtualNode[i] = cursor.keys[i];
					i += 1;
				}
				i = 0;
				while (x > virtualNode[i] && i < this.degree)
				{
					i += 1;
				}
				j = this.degree + 1;
				while (j > i)
				{
					virtualNode[j] = virtualNode[j - 1];
					j -= 1;
				}
				virtualNode[i] = x;
				newLeaf.isLeaf = true;
				cursor.count = (this.degree + 1) / 2;
				newLeaf.count = this.degree + 1 - (this.degree + 1) / 2;
				cursor.child[cursor.count] = newLeaf;
				newLeaf.child[newLeaf.count] = cursor.child[this.degree];
				cursor.child[this.degree] = null;
				i = 0;
				while (i < cursor.count)
				{
					cursor.keys[i] = virtualNode[i];
					i += 1;
				}
				i = 0;
				j = cursor.count;
				while (i < newLeaf.count)
				{
					newLeaf.keys[i] = virtualNode[j];
					i += 1;
					j += 1;
				}
				if (cursor == this.root)
				{
					val newRoot: TreeNode = TreeNode(this.degree);
					newRoot.keys[0] = newLeaf.keys[0];
					newRoot.child[0] = cursor;
					newRoot.child[1] = newLeaf;
					newRoot.isLeaf = false;
					newRoot.count = 1;
					this.root = newRoot;
				}
				else
				{
					this.insertInternal(newLeaf.keys[0], parent, newLeaf);
				}
			}
		}
	}
	// Print the elements of B+ tree elements
	fun printNode(node: TreeNode ? ): Unit
	{
		if (node == null)
		{
			// When node is empty
			return;
		}
		else
		{
			var i: Int = 0;
			while (i < node.count)
			{
				if (node.isLeaf == false)
				{
					// When node is not leaf
					this.printNode(node.child[i]);
				}
				else
				{
					// Print the left node value
					print("  " + node.keys[i]);
				}
				i += 1;
			}
			if (node.isLeaf == false)
			{
				this.printNode(node.child[i]);
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create a new b+ tree with degree 4
	val tree: BPTree = BPTree(4);
	// Add node
	tree.insert(10);
	tree.insert(7);
	tree.insert(15);
	tree.insert(2);
	tree.insert(-3);
	tree.insert(12);
	tree.insert(35);
	tree.insert(14);
	// Print Tree elements
	tree.printNode(tree.root);
}

input

  -3  2  7  10  12  14  15  35

Time Complexity

The average time complexity for insertion and searching in a B+ tree is O(log n), making it an efficient data structure for managing large datasets.

Java Code Work

B + Tree Implementation Java Example
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment