Skip to main content

Implement B + Tree

Here given code implementation process.

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