Skip to main content

B Tree node insertion

In computer science, B-trees are self-balancing tree structures designed to maintain sorted data efficiently while allowing for insertions, deletions, and searches in logarithmic time. The B-tree is particularly useful for databases and file systems where data can be stored and retrieved in a sorted order. This article will explain B-tree node insertion, providing a detailed breakdown of the process, accompanied by a working C code example.

Problem Statement and Description

The problem we're addressing is the insertion of nodes into a B-tree. B-trees have certain properties that need to be maintained for efficient data access:

  1. Each node can have a variable number of keys, but it must be within a specified range (degree).
  2. The keys within a node are sorted in ascending order.
  3. Each node can have child pointers, and the number of child pointers is always one more than the number of keys.
  4. All leaves of the tree are at the same level.

Example

Let's consider inserting the following numbers into a B-tree with a degree of 3: 13, 5, 3, 6, 37, 23, 8, 9, 10, 26, 12, 7, and 11.

         (6, 9, 13)
        /   |  \   \
       /    |   \   (23,26,37)   
   (3,5) (7,8) (10,11,12)

Initially, the tree is empty. As we insert each number, the tree undergoes transformations to maintain the B-tree properties.

Idea to Solve the Problem

The insertion process involves traversing the tree to find the appropriate location for the new key. If the target node is full, it's split into two nodes, and the middle key is moved up to the parent node. This process is recursively applied until the tree is balanced.

Pseudocode

  1. Create a B-tree node structure and a B-tree structure with root pointer.
  2. Implement functions to create a B-tree node and initialize its values.
  3. Implement a function to split child nodes if needed.
  4. Implement a recursive function to insert a key into the B-tree.
  5. If the root is full, create a new root.
  6. Traverse the tree for insertion.

Algorithm Explanation

  1. Start with an empty B-tree.
  2. For each key insertion: a. If the root is empty, create a root node and add the key. b. If the root is full, split it and create a new root. c. If the root is not full, insert the key recursively.
  3. For recursive insertion: a. If the current node is a leaf, insert the key. b. If the current node is not a leaf: i. Find the child node where the key should be inserted. ii. If the child is full, split it. iii. Recurse into the appropriate child.

Code Solution

// C Program 
// B-Tree node insertion
#include <stdio.h>
#include <stdlib.h>

// Define tree node
struct TreeNode
{
	int *keys;
	struct TreeNode **child;
	int count;
	int leaf;
	int degree;
};
// Define structure of B Tree
struct BTree
{
	int degree;
	struct TreeNode *root;
};
// Returns the new b tree
struct BTree *createTree(int degree)
{
	struct BTree *tree = (struct BTree *) malloc(sizeof(struct BTree));
	if (tree != NULL)
	{
		tree->degree = degree;
		tree->root = NULL;
	}
	else
	{
		printf("\n Memory Overflow when create new Tree");
	}
}
// Creating and returning new node of b tree
struct TreeNode *createNode(int degree, int leaf)
{
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Create memory of node key
		node->keys = (int *) malloc((sizeof(int)) *(2 *degree - 1));
		// Allocate memory of node child
		node->child = (struct TreeNode **) malloc((2 *degree) *sizeof(struct TreeNode *));
		// Set initial child
		for (int i = 0; i < degree *2 - 1; ++i)
		{
			node->child[i] = NULL;
		}
		node->leaf = leaf;
		node->degree = degree;
		node->count = 0;
	}
}
// This function are split the child node
void splitChildNodes(struct TreeNode *x, struct TreeNode *y, int i)
{
	// Create new node z
	struct TreeNode *z = createNode(y->degree, y->leaf);
	z->count = x->degree - 1;
	int j = 0;
	// Get key
	for (j = 0; j < x->degree - 1; j++)
	{
		z->keys[j] = y->keys[j + x->degree];
		//reset slot value
		y->keys[j + x->degree] = 0;
	}
	if (y->leaf == 0)
	{
		// Get child value
		for (j = 0; j < x->degree; j++)
		{
			z->child[j] = y->child[j + x->degree];
			y->child[j + x->degree] = NULL;
		}
	}
	y->count = x->degree - 1;
	for (j = x->count; j >= i + 1; j--)
	{
		x->child[j + 1] = x->child[j];
	}
	x->child[i + 1] = z;
	for (j = x->count - 1; j >= i; j--)
	{
		x->keys[j + 1] = x->keys[j];
	}
	x->keys[i] = y->keys[x->degree - 1];
	y->keys[x->degree - 1] = 0;
	x->count = x->count + 1;
}
// Set key into the node
void setValue(struct TreeNode *node, int key)
{
	int i = node->count - 1;
	if (node->leaf == 1)
	{
		// When get leaf node
		// Find location to add new key
		while (i >= 0 && node->keys[i] > key)
		{
			node->keys[i + 1] = node->keys[i];
			i--;
		}
		// Add new key
		node->keys[i + 1] = key;
		// Update node key counter
		node->count = node->count + 1;
	}
	else
	{
		while (i >= 0 && node->keys[i] > key)
		{
			i--;
		}
		if (node->child[i + 1]->count == 2 *node->degree - 1)
		{
			// When need to split child nodes
			splitChildNodes(node, node->child[i + 1], i + 1);
			if (node->keys[i + 1] < key)
			{
				i++;
			}
		}
		setValue(node->child[i + 1], key);
	}
}
// Handles the request to add new node in B Tree
void insert(struct BTree *tree, int key)
{
	if (tree->root == NULL)
	{
		// When add first node of tree
		tree->root = createNode(tree->degree, 1);
		// set key value
		tree->root->keys[0] = key;
		tree->root->count++;
	}
	else
	{
		if (tree->root->count == 2 *tree->degree - 1)
		{
			struct TreeNode *node = createNode(tree->degree, 0);
			node->child[0] = tree->root;
			splitChildNodes(node, tree->root, 0);
			int i = 0;
			if (node->keys[0] < key)
			{
				i++;
			}
			setValue(node->child[i], key);
			// set new root
			tree->root = node;
		}
		else
		{
			setValue(tree->root, key);
		}
	}
}
// Display tree elements
void traversal(struct TreeNode *node)
{
	if (node != NULL)
	{
		int i = 0;
		while (i < node->count)
		{
			traversal(node->child[i]);
			printf("%d  ", node->keys[i]);
			i++;
		}
		traversal(node->child[i]);
	}
}
// Find that given element exists in b tree
int search(struct TreeNode *node, int key)
{
	if (node != NULL)
	{
		int i = 0;
		while (i < node->count)
		{
			if (search(node->child[i], key) == 1 || node->keys[i] == key)
			{
				return 1;
			}
			i++;
		}
		return search(node->child[i], key);
	}
	else
	{
		return 0;
	}
}
int main(int argc, char
	const *argv[])
{
	// Create b-tree with degree 3
	struct BTree *tree = createTree(3);
	insert(tree, 13);
	insert(tree, 5);
	insert(tree, 3);
	insert(tree, 6);
	insert(tree, 37);
	insert(tree, 23);
	insert(tree, 8);
	insert(tree, 9);
	insert(tree, 10);
	insert(tree, 26);
	insert(tree, 12);
	insert(tree, 7);
	insert(tree, 11);
	/*
	      (6,  9, 13)
	      /   |  \   \
	     /    |   \   (23,26,37)   
	  (3,5) (7,8) (10,11,12)

	  Constructed B Tree
	*/
	traversal(tree->root);
	return 0;
}

Output

3  5  6  7  8  9  10  11  12  13  23  26  37
// Java Program 
// B-Tree node insertion
// Define tree node
class TreeNode
{
	public int[] keys;
	public TreeNode[] child;
	public int count;
	public int leaf;
	public int degree;
	public TreeNode(int count, int leaf, int degree)
	{
		this.count = count;
		this.leaf = leaf;
		this.degree = degree;
	}
}
// Define structure of B Tree
public class BTree
{
	public int degree;
	public TreeNode root;
	public BTree(int degree)
	{
		this.root = null;
		this.degree = degree;
	}
	// Creating and returning new node of b tree
	public TreeNode createNode(int degree, int leaf)
	{
		TreeNode node = new TreeNode(0, leaf, degree);
		if (node != null)
		{
			// Create memory of node key
			node.keys = new int[2 * degree - 1];
			// Allocate memory of node child
			node.child = new TreeNode[2 * degree - 1];
			// Set initial child
			for (int i = 0; i < (degree * 2 - 1); ++i)
			{
				node.child[i] = null;
			}
		}
		return node;
	}
	// This function are split the child node
	public void splitChildNodes(TreeNode x, TreeNode y, int i)
	{
		// Create new node z
		TreeNode z = createNode(y.degree, y.leaf);
		z.count = x.degree - 1;
		int j = 0;
		// Get key
		for (j = 0; j < x.degree - 1; j++)
		{
			z.keys[j] = y.keys[j + x.degree];
			//reset slot value
			y.keys[j + x.degree] = 0;
		}
		if (y.leaf == 0)
		{
			// Get child value
			for (j = 0; j < x.degree; j++)
			{
				z.child[j] = y.child[j + x.degree];
				y.child[j + x.degree] = null;
			}
		}
		y.count = x.degree - 1;
		for (j = x.count; j >= i + 1; j--)
		{
			x.child[j + 1] = x.child[j];
		}
		x.child[i + 1] = z;
		for (j = x.count - 1; j >= i; j--)
		{
			x.keys[j + 1] = x.keys[j];
		}
		x.keys[i] = y.keys[x.degree - 1];
		y.keys[x.degree - 1] = 0;
		x.count = x.count + 1;
	}
	// Set key into the node
	public void setValue(TreeNode node, int key)
	{
		if (node == null)
		{
			System.out.print("Emty");
			return;
		}
		int i = node.count - 1;
		if (node.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node.keys[i] > key)
			{
				node.keys[i + 1] = node.keys[i];
				i--;
			}
			// Add new key
			node.keys[i + 1] = key;
			// Update node key counter
			node.count = node.count + 1;
		}
		else
		{
			while (i >= 0 && node.keys[i] > key)
			{
				i--;
			}
			if (node.child[i + 1].count == (2 * node.degree - 1))
			{
				// When need to split child nodes
				splitChildNodes(node, node.child[i + 1], i + 1);
				if (node.keys[i + 1] < key)
				{
					i++;
				}
			}
			setValue(node.child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	public void insert(int key)
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = createNode(this.degree, 1);
			// set key value
			this.root.keys[0] = key;
			this.root.count++;
		}
		else
		{
			if (this.root.count == 2 * this.degree - 1)
			{
				TreeNode node = createNode(this.degree, 0);
				node.child[0] = this.root;
				splitChildNodes(node, this.root, 0);
				int i = 0;
				if (node.keys[0] < key)
				{
					i++;
				}
				setValue(node.child[i], key);
				// set new root
				this.root = node;
			}
			else
			{
				setValue(this.root, key);
			}
		}
	}
	// Display tree elements
	public void traversal(TreeNode node)
	{
		if (node != null)
		{
			int i = 0;
			while (i < node.count)
			{
				traversal(node.child[i]);
				System.out.print("  " + node.keys[i]);
				i++;
			}
			traversal(node.child[i]);
		}
	}
	// Find that given element exists in b tree
	public int search(TreeNode node, int key)
	{
		if (node != null)
		{
			int i = 0;
			while (i < node.count)
			{
				if (search(node.child[i], key) == 1 || node.keys[i] == key)
				{
					return 1;
				}
				i++;
			}
			return search(node.child[i], key);
		}
		else
		{
			return 0;
		}
	}
	public static void main(String[] args)
	{
		// Create b-tree with degree 3
		BTree tree = new BTree(3);
		tree.insert(13);
		tree.insert(5);
		tree.insert(3);
		tree.insert(6);
		tree.insert(37);
		tree.insert(23);
		tree.insert(8);
		tree.insert(9);
		tree.insert(10);
		tree.insert(26);
		tree.insert(12);
		tree.insert(7);
		tree.insert(11);
		/*
		      (6,  9, 13)
		      /   |  \   \
		     /    |   \   (23,26,37)   
		  (3,5) (7,8) (10,11,12)

		  Constructed B Tree
		*/
		tree.traversal(tree.root);
	}
}

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
// Include header file
#include <iostream>

using namespace std;
// C++ Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
	public: 
    int *keys;
	TreeNode **child;
	int count;
	int leaf;
	int degree;
	TreeNode(int count, int leaf, int degree)
	{
		this->count = count;
		this->leaf = leaf;
		this->degree = degree;
	}
	TreeNode()
	{
        this->count = 0;
		
	}
};
// Define structure of B Tree
class BTree
{
	public: int degree;
	TreeNode *root;
	BTree(int degree)
	{
		this->root = NULL;
		this->degree = degree;
	}
	// Creating and returning new node of b tree
	TreeNode *createNode(int degree, int leaf)
	{
		TreeNode *node = new TreeNode(0, leaf, degree);
		if (node != NULL)
		{
			// Create memory of node key
			node->keys = new int[2 *degree - 1];
			// Allocate memory of node child
			node->child = new TreeNode*[2 *degree - 1];
			// Set initial child
			for (int i = 0; i < (degree *2 - 1); ++i)
			{
				node->child[i] = NULL;
			}
		}
		return node;
	}
	// This function are split the child node
	void splitChildNodes(TreeNode *x, TreeNode *y, int i)
	{
		// Create new node z
		TreeNode *z = this->createNode(y->degree, y->leaf);
		z->count = x->degree - 1;
		int j = 0;
		// Get key
		for (j = 0; j < x->degree - 1; j++)
		{
			z->keys[j] = y->keys[j + x->degree];
			//reset slot value
			y->keys[j + x->degree] = 0;
		}
		if (y->leaf == 0)
		{
			// Get child value
			for (j = 0; j < x->degree; j++)
			{
				z->child[j] = y->child[j + x->degree];
				y->child[j + x->degree] = NULL;
			}
		}
		y->count = x->degree - 1;
		for (j = x->count; j >= i + 1; j--)
		{
			x->child[j + 1] = x->child[j];
		}
		x->child[i + 1] = z;
		for (j = x->count - 1; j >= i; j--)
		{
			x->keys[j + 1] = x->keys[j];
		}
		x->keys[i] = y->keys[x->degree - 1];
		y->keys[x->degree - 1] = 0;
		x->count = x->count + 1;
	}
	// Set key into the node
	void setValue(TreeNode *node, int key)
	{
		if (node == NULL)
		{
			cout << "Emty";
			return;
		}
		int i = node->count - 1;
		if (node->leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node->keys[i] > key)
			{
				node->keys[i + 1] = node->keys[i];
				i--;
			}
			// Add new key
			node->keys[i + 1] = key;
			// Update node key counter
			node->count = node->count + 1;
		}
		else
		{
			while (i >= 0 && node->keys[i] > key)
			{
				i--;
			}
			if (node->child[i + 1]->count == (2 * node->degree - 1))
			{
				// When need to split child nodes
				this->splitChildNodes(node, node->child[i + 1], i + 1);
				if (node->keys[i + 1] < key)
				{
					i++;
				}
			}
			this->setValue(node->child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	void insert(int key)
	{
		if (this->root == NULL)
		{
			// When add first node of tree
			this->root = this->createNode(this->degree, 1);
			// set key value
			this->root->keys[0] = key;
			root->count++;
		}
		else
		{
			if (root->count == 2 *this->degree - 1)
			{
				TreeNode *node = this->createNode(this->degree, 0);
				node->child[0] = this->root;
				this->splitChildNodes(node, this->root, 0);
				int i = 0;
				if (node->keys[0] < key)
				{
					i++;
				}
				this->setValue(node->child[i], key);
				// set new root
				this->root = node;
			}
			else
			{
				this->setValue(this->root, key);
			}
		}
	}
	// Display tree elements
	void traversal(TreeNode *node)
	{
		if (node != NULL)
		{
			int i = 0;
			while (i < node->count)
			{
				this->traversal(node->child[i]);
				cout << "  " << node->keys[i];
				i++;
			}
			this->traversal(node->child[i]);
		}
	}
	// Find that given element exists in b tree
	int search(TreeNode *node, int key)
	{
		if (node != NULL)
		{
			int i = 0;
			while (i < node->count)
			{
				if (this->search(node->child[i], key) == 1 || 
                    node->keys[i] == key)
				{
					return 1;
				}
				i++;
			}
			return this->search(node->child[i], key);
		}
		else
		{
			return 0;
		}
	}
};
int main()
{
	// Create b-tree with degree 3
	BTree tree = BTree(3);
	tree.insert(13);
	tree.insert(5);
	tree.insert(3);
	tree.insert(6);
	tree.insert(37);
	tree.insert(23);
	tree.insert(8);
	tree.insert(9);
	tree.insert(10);
	tree.insert(26);
	tree.insert(12);
	tree.insert(7);
	tree.insert(11);
	/*
			(6,  9, 13)
			 /   |  \   \
			/    |   \   (23,26,37)   
		(3,5) (7,8) (10,11,12)

		 Constructed B Tree
	*/
	tree.traversal(tree.root);
	return 0;
}

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
// Include namespace system
using System;
// C# Program
// B-Tree node insertion
// Define tree node
public class TreeNode
{
	public int[] keys;
	public TreeNode[] child;
	public int count;
	public int leaf;
	public int degree;
	public TreeNode(int count, int leaf, int degree)
	{
		this.count = count;
		this.leaf = leaf;
		this.degree = degree;
	}
}
// Define structure of B Tree
public class BTree
{
	public int degree;
	public TreeNode root;
	public BTree(int degree)
	{
		this.root = null;
		this.degree = degree;
	}
	// Creating and returning new node of b tree
	public TreeNode createNode(int degree, int leaf)
	{
		TreeNode node = new TreeNode(0, leaf, degree);
		if (node != null)
		{
			// Create memory of node key
			node.keys = new int[2 * degree - 1];
			// Allocate memory of node child
			node.child = new TreeNode[2 * degree - 1];
			// Set initial child
			for (int i = 0; i < (degree * 2 - 1); ++i)
			{
				node.child[i] = null;
			}
		}
		return node;
	}
	// This function are split the child node
	public void splitChildNodes(TreeNode x, TreeNode y, int i)
	{
		// Create new node z
		TreeNode z = createNode(y.degree, y.leaf);
		z.count = x.degree - 1;
		int j = 0;
		// Get key
		for (j = 0; j < x.degree - 1; j++)
		{
			z.keys[j] = y.keys[j + x.degree];
			//reset slot value
			y.keys[j + x.degree] = 0;
		}
		if (y.leaf == 0)
		{
			// Get child value
			for (j = 0; j < x.degree; j++)
			{
				z.child[j] = y.child[j + x.degree];
				y.child[j + x.degree] = null;
			}
		}
		y.count = x.degree - 1;
		for (j = x.count; j >= i + 1; j--)
		{
			x.child[j + 1] = x.child[j];
		}
		x.child[i + 1] = z;
		for (j = x.count - 1; j >= i; j--)
		{
			x.keys[j + 1] = x.keys[j];
		}
		x.keys[i] = y.keys[x.degree - 1];
		y.keys[x.degree - 1] = 0;
		x.count = x.count + 1;
	}
	// Set key into the node
	public void setValue(TreeNode node, int key)
	{
		if (node == null)
		{
			Console.Write("Emty");
			return;
		}
		int i = node.count - 1;
		if (node.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node.keys[i] > key)
			{
				node.keys[i + 1] = node.keys[i];
				i--;
			}
			// Add new key
			node.keys[i + 1] = key;
			// Update node key counter
			node.count = node.count + 1;
		}
		else
		{
			while (i >= 0 && node.keys[i] > key)
			{
				i--;
			}
			if (node.child[i + 1].count == (2 * node.degree - 1))
			{
				// When need to split child nodes
				splitChildNodes(node, node.child[i + 1], i + 1);
				if (node.keys[i + 1] < key)
				{
					i++;
				}
			}
			setValue(node.child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	public void insert(int key)
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = createNode(this.degree, 1);
			// set key value
			this.root.keys[0] = key;
			this.root.count++;
		}
		else
		{
			if (this.root.count == 2 * this.degree - 1)
			{
				TreeNode node = createNode(this.degree, 0);
				node.child[0] = this.root;
				splitChildNodes(node, this.root, 0);
				int i = 0;
				if (node.keys[0] < key)
				{
					i++;
				}
				setValue(node.child[i], key);
				// set new root
				this.root = node;
			}
			else
			{
				setValue(this.root, key);
			}
		}
	}
	// Display tree elements
	public void traversal(TreeNode node)
	{
		if (node != null)
		{
			int i = 0;
			while (i < node.count)
			{
				traversal(node.child[i]);
				Console.Write("  " + node.keys[i]);
				i++;
			}
			traversal(node.child[i]);
		}
	}
	// Find that given element exists in b tree
	public int search(TreeNode node, int key)
	{
		if (node != null)
		{
			int i = 0;
			while (i < node.count)
			{
				if (search(node.child[i], key) == 1 || node.keys[i] == key)
				{
					return 1;
				}
				i++;
			}
			return search(node.child[i], key);
		}
		else
		{
			return 0;
		}
	}
	public static void Main(String[] args)
	{
		// Create b-tree with degree 3
		BTree tree = new BTree(3);
		tree.insert(13);
		tree.insert(5);
		tree.insert(3);
		tree.insert(6);
		tree.insert(37);
		tree.insert(23);
		tree.insert(8);
		tree.insert(9);
		tree.insert(10);
		tree.insert(26);
		tree.insert(12);
		tree.insert(7);
		tree.insert(11);
		/*
		      (6,  9, 13)
		      /   |  \   \
		     /    |   \   (23,26,37)   
		  (3,5) (7,8) (10,11,12)
		  Constructed B Tree
		*/
		tree.traversal(tree.root);
	}
}

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
<?php
// Php Program
// B-Tree node insertion

// Define tree node
class TreeNode
{
	public $keys;
	public $child;
	public $count;
	public $leaf;
	public $degree;

	function __construct($count, $leaf, $degree)
	{
		$this->count = $count;
		$this->leaf = $leaf;
		$this->degree = $degree;
	}
}
// Define structure of B Tree
class BTree
{
	public $degree;
	public $root;

	function __construct($degree)
	{
		$this->root = null;
		$this->degree = $degree;
	}
	// Creating and returning new node of b tree
	public	function createNode($degree, $leaf)
	{
		$node = new TreeNode(0, $leaf, $degree);
		if ($node != null)
		{
			// Create memory of node key
			$node->keys = array_fill(0, 2 * $degree - 1, 0);
			// Allocate memory of node child
			$node->child = array_fill(0, 2 * $degree - 1, null);
		}
		return $node;
	}
	// This function are split the child node
	public	function splitChildNodes($x, $y, $i)
	{
		// Create new node z
		$z = $this->createNode($y->degree, $y->leaf);
		$z->count = $x->degree - 1;
		$j = 0;
		// Get key
		for ($j = 0; $j < $x->degree - 1; $j++)
		{
			$z->keys[$j] = $y->keys[$j + $x->degree];
			//reset slot value
			$y->keys[$j + $x->degree] = 0;
		}
		if ($y->leaf == 0)
		{
			// Get child value
			for ($j = 0; $j < $x->degree; $j++)
			{
				$z->child[$j] = $y->child[$j + $x->degree];
				$y->child[$j + $x->degree] = null;
			}
		}
		$y->count = $x->degree - 1;
		for ($j = $x->count; $j >= $i + 1; $j--)
		{
			$x->child[$j + 1] = $x->child[$j];
		}
		$x->child[$i + 1] = $z;
		for ($j = $x->count - 1; $j >= $i; $j--)
		{
			$x->keys[$j + 1] = $x->keys[$j];
		}
		$x->keys[$i] = $y->keys[$x->degree - 1];
		$y->keys[$x->degree - 1] = 0;
		$x->count = $x->count + 1;
	}
	// Set key into the node
	public	function setValue($node, $key)
	{
		if ($node == null)
		{
			echo "Emty";
			return;
		}
		$i = $node->count - 1;
		if ($node->leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while ($i >= 0 && $node->keys[$i] > $key)
			{
				$node->keys[$i + 1] = $node->keys[$i];
				$i--;
			}
			// Add new key
			$node->keys[$i + 1] = $key;
			// Update node key counter
			$node->count = $node->count + 1;
		}
		else
		{
			while ($i >= 0 && $node->keys[$i] > $key)
			{
				$i--;
			}
			if ($node->child[$i + 1]->count == (2 * $node->degree - 1))
			{
				// When need to split child nodes
				$this->splitChildNodes($node, $node->child[$i + 1], $i + 1);
				if ($node->keys[$i + 1] < $key)
				{
					$i++;
				}
			}
			$this->setValue($node->child[$i + 1], $key);
		}
	}
	// Handles the request to add new node in B Tree
	public	function insert($key)
	{
		if ($this->root == null)
		{
			// When add first node of tree
			$this->root = $this->createNode($this->degree, 1);
			// set key value
			$this->root->keys[0] = $key;
			$this->root->count++;
		}
		else
		{
			if ($this->root->count == 2 * $this->degree - 1)
			{
				$node = $this->createNode($this->degree, 0);
				$node->child[0] = $this->root;
				$this->splitChildNodes($node, $this->root, 0);
				$i = 0;
				if ($node->keys[0] < $key)
				{
					$i++;
				}
				$this->setValue($node->child[$i], $key);
				// set new root
				$this->root = $node;
			}
			else
			{
				$this->setValue($this->root, $key);
			}
		}
	}
	// Display tree elements
	public	function traversal($node)
	{
		if ($node != null)
		{
			$i = 0;
			while ($i < $node->count)
			{
				$this->traversal($node->child[$i]);
				echo "  ". $node->keys[$i];
				$i++;
			}
			$this->traversal($node->child[$i]);
		}
	}
	// Find that given element exists in b tree
	public	function search($node, $key)
	{
		if ($node != null)
		{
			$i = 0;
			while ($i < $node->count)
			{
				if ($this->search($node->child[$i], $key) == 1 || $node->keys[$i] == $key)
				{
					return 1;
				}
				$i++;
			}
			return $this->search($node->child[$i], $key);
		}
		else
		{
			return 0;
		}
	}
}

function main()
{
	// Create b-tree with degree 3
	$tree = new BTree(3);
	$tree->insert(13);
	$tree->insert(5);
	$tree->insert(3);
	$tree->insert(6);
	$tree->insert(37);
	$tree->insert(23);
	$tree->insert(8);
	$tree->insert(9);
	$tree->insert(10);
	$tree->insert(26);
	$tree->insert(12);
	$tree->insert(7);
	$tree->insert(11);
    /*
        (6,  9, 13)
        /   |  \   \
       /    |   \   (23,26,37)   
    (3,5) (7,8) (10,11,12)
    Constructed B Tree
  */
	$tree->traversal($tree->root);
}
main();

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
// Node Js Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
	constructor(count, leaf, degree)
	{
		this.count = count;
		this.leaf = leaf;
		this.degree = degree;
	}
}
// Define structure of B Tree
class BTree
{
	constructor(degree)
	{
		this.root = null;
		this.degree = degree;
	}
	// Creating and returning new node of b tree
	createNode(degree, leaf)
	{
		var node = new TreeNode(0, leaf, degree);
		if (node != null)
		{
			// Create memory of node key
			node.keys = Array(2 * degree - 1).fill(0);
			// Allocate memory of node child
			node.child = Array(2 * degree - 1).fill(null);
		}
		return node;
	}
	// This function are split the child node
	splitChildNodes(x, y, i)
	{
		// Create new node z
		var z = this.createNode(y.degree, y.leaf);
		z.count = x.degree - 1;
		var j = 0;
		// Get key
		for (j = 0; j < x.degree - 1; j++)
		{
			z.keys[j] = y.keys[j + x.degree];
			//reset slot value
			y.keys[j + x.degree] = 0;
		}
		if (y.leaf == 0)
		{
			// Get child value
			for (j = 0; j < x.degree; j++)
			{
				z.child[j] = y.child[j + x.degree];
				y.child[j + x.degree] = null;
			}
		}
		y.count = x.degree - 1;
		for (j = x.count; j >= i + 1; j--)
		{
			x.child[j + 1] = x.child[j];
		}
		x.child[i + 1] = z;
		for (j = x.count - 1; j >= i; j--)
		{
			x.keys[j + 1] = x.keys[j];
		}
		x.keys[i] = y.keys[x.degree - 1];
		y.keys[x.degree - 1] = 0;
		x.count = x.count + 1;
	}
	// Set key into the node
	setValue(node, key)
	{
		if (node == null)
		{
			process.stdout.write("Emty");
			return;
		}
		var i = node.count - 1;
		if (node.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node.keys[i] > key)
			{
				node.keys[i + 1] = node.keys[i];
				i--;
			}
			// Add new key
			node.keys[i + 1] = key;
			// Update node key counter
			node.count = node.count + 1;
		}
		else
		{
			while (i >= 0 && node.keys[i] > key)
			{
				i--;
			}
			if (node.child[i + 1].count == (2 * node.degree - 1))
			{
				// When need to split child nodes
				this.splitChildNodes(node, node.child[i + 1], i + 1);
				if (node.keys[i + 1] < key)
				{
					i++;
				}
			}
			this.setValue(node.child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	insert(key)
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = this.createNode(this.degree, 1);
			// set key value
			this.root.keys[0] = key;
			this.root.count++;
		}
		else
		{
			if (this.root.count == 2 * this.degree - 1)
			{
				var node = this.createNode(this.degree, 0);
				node.child[0] = this.root;
				this.splitChildNodes(node, this.root, 0);
				var i = 0;
				if (node.keys[0] < key)
				{
					i++;
				}
				this.setValue(node.child[i], key);
				// set new root
				this.root = node;
			}
			else
			{
				this.setValue(this.root, key);
			}
		}
	}
	// Display tree elements
	traversal(node)
	{
		if (node != null)
		{
			var i = 0;
			while (i < node.count)
			{
				this.traversal(node.child[i]);
				process.stdout.write("  " + node.keys[i]);
				i++;
			}
			this.traversal(node.child[i]);
		}
	}
	// Find that given element exists in b tree
	search(node, key)
	{
		if (node != null)
		{
			var i = 0;
			while (i < node.count)
			{
				if (this.search(node.child[i], key) == 1 || node.keys[i] == key)
				{
					return 1;
				}
				i++;
			}
			return this.search(node.child[i], key);
		}
		else
		{
			return 0;
		}
	}
}

function main()
{
	// Create b-tree with degree 3
	var tree = new BTree(3);
	tree.insert(13);
	tree.insert(5);
	tree.insert(3);
	tree.insert(6);
	tree.insert(37);
	tree.insert(23);
	tree.insert(8);
	tree.insert(9);
	tree.insert(10);
	tree.insert(26);
	tree.insert(12);
	tree.insert(7);
	tree.insert(11);
	/*
	      (6,  9, 13)
	      /   |  \   \
	     /    |   \   (23,26,37)   
	  (3,5) (7,8) (10,11,12)
	  Constructed B Tree
	*/
	tree.traversal(tree.root);
}
main();

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
#  Python 3 Program
#  B-Tree node insertion

#  Define tree node
class TreeNode :
	
	def __init__(self, count, leaf, degree) :
		self.count = count
		self.leaf = leaf
		self.degree = degree
	

#  Define structure of B Tree
class BTree :
	
	def __init__(self, degree) :
		self.root = None
		self.degree = degree
	
	#  Creating and returning new node of b tree
	def createNode(self, degree, leaf) :
		node = TreeNode(0, leaf, degree)
		if (node != None) :
			#  Create memory of node key
			node.keys = [0] * (2 * degree - 1)
			#  Allocate memory of node child
			node.child = [None] * (2 * degree - 1)
		return node
	
	#  This function are split the child node
	def splitChildNodes(self, x, y, i) :
		#  Create new node z
		z = self.createNode(y.degree, y.leaf)
		z.count = x.degree - 1
		j = 0
		#  Get key
		while (j < x.degree - 1) :
			z.keys[j] = y.keys[j + x.degree]
			# reset slot value
			y.keys[j + x.degree] = 0
			j += 1
		
		if (y.leaf == 0) :
			#  Get child value
			j = 0
			while (j < x.degree) :
				z.child[j] = y.child[j + x.degree]
				y.child[j + x.degree] = None
				j += 1
			
		
		y.count = x.degree - 1
		j = x.count
		while (j >= i + 1) :
			x.child[j + 1] = x.child[j]
			j -= 1
		
		x.child[i + 1] = z
		j = x.count - 1
		while (j >= i) :
			x.keys[j + 1] = x.keys[j]
			j -= 1
		
		x.keys[i] = y.keys[x.degree - 1]
		y.keys[x.degree - 1] = 0
		x.count = x.count + 1
	
	#  Set key into the node
	def setValue(self, node, key) :
		if (node == None) :
			print("Emty", end = "")
			return
		
		i = node.count - 1
		if (node.leaf == 1) :
			#  When get leaf node
			#  Find location to add new key
			while (i >= 0 and node.keys[i] > key) :
				node.keys[i + 1] = node.keys[i]
				i -= 1
			
			#  Add new key
			node.keys[i + 1] = key
			#  Update node key counter
			node.count = node.count + 1
		else :
			while (i >= 0 and node.keys[i] > key) :
				i -= 1
			
			if (node.child[i + 1].count == (2 * node.degree - 1)) :
				#  When need to split child nodes
				self.splitChildNodes(node, node.child[i + 1], i + 1)
				if (node.keys[i + 1] < key) :
					i += 1
				
			
			self.setValue(node.child[i + 1], key)
		
	
	#  Handles the request to add new node in B Tree
	def insert(self, key) :
		if (self.root == None) :
			#  When add first node of tree
			self.root = self.createNode(self.degree, 1)
			#  set key value
			self.root.keys[0] = key
			self.root.count += 1
		else :
			if (self.root.count == 2 * self.degree - 1) :
				node = self.createNode(self.degree, 0)
				node.child[0] = self.root
				self.splitChildNodes(node, self.root, 0)
				i = 0
				if (node.keys[0] < key) :
					i += 1
				
				self.setValue(node.child[i], key)
				#  set new root
				self.root = node
			else :
				self.setValue(self.root, key)
			
		
	
	#  Display tree elements
	def traversal(self, node) :
		if (node != None) :
			i = 0
			while (i < node.count) :
				self.traversal(node.child[i])
				print(" ", node.keys[i], end = "")
				i += 1
			
			self.traversal(node.child[i])
		
	
	#  Find that given element exists in b tree
	def search(self, node, key) :
		if (node != None) :
			i = 0
			while (i < node.count) :
				if (self.search(node.child[i], key) == 1 or 
                    node.keys[i] == key) :
					return 1
				
				i += 1
			
			return self.search(node.child[i], key)
		else :
			return 0
		
	

def main() :
	#  Create b-tree with degree 3
	tree = BTree(3)
	tree.insert(13)
	tree.insert(5)
	tree.insert(3)
	tree.insert(6)
	tree.insert(37)
	tree.insert(23)
	tree.insert(8)
	tree.insert(9)
	tree.insert(10)
	tree.insert(26)
	tree.insert(12)
	tree.insert(7)
	tree.insert(11)
	# 
	#       (6,  9, 13)
	#       /   |  \   \
	#      /    |   \   (23,26,37)   
	#   (3,5) (7,8) (10,11,12)
	#   Constructed B Tree
	
	tree.traversal(tree.root)

if __name__ == "__main__": main()

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
#  Ruby Program
#  B-Tree node insertion

#  Define tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :keys, :child, :count, :leaf, :degree
	attr_accessor :keys, :child, :count, :leaf, :degree
 
	
	def initialize(count, leaf, degree) 
		self.count = count
		self.leaf = leaf
		self.degree = degree
	end

end

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

	#  Creating and returning new node of b tree
	def createNode(degree, leaf) 
		node = TreeNode.new(0, leaf, degree)
		if (node != nil) 
			#  Create memory of node key
			node.keys = Array.new(2 * degree - 1) {0}
			#  Allocate memory of node child
			node.child = Array.new(2 * degree - 1) {nil}
		end

		return node
	end

	#  This function are split the child node
	def splitChildNodes(x, y, i) 
		#  Create new node z
		z = self.createNode(y.degree, y.leaf)
		z.count = x.degree - 1
		j = 0
		#  Get key
		while (j < x.degree - 1) 
			z.keys[j] = y.keys[j + x.degree]
			# reset slot value
			y.keys[j + x.degree] = 0
			j += 1
		end

		if (y.leaf == 0) 
			#  Get child value
			j = 0
			while (j < x.degree) 
				z.child[j] = y.child[j + x.degree]
				y.child[j + x.degree] = nil
				j += 1
			end

		end

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

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

		x.keys[i] = y.keys[x.degree - 1]
		y.keys[x.degree - 1] = 0
		x.count = x.count + 1
	end

	#  Set key into the node
	def setValue(node, key) 
		if (node == nil) 
			print("Emty")
			return
		end

		i = node.count - 1
		if (node.leaf == 1) 
			#  When get leaf node
			#  Find location to add new key
			while (i >= 0 && node.keys[i] > key) 
				node.keys[i + 1] = node.keys[i]
				i -= 1
			end

			#  Add new key
			node.keys[i + 1] = key
			#  Update node key counter
			node.count = node.count + 1
		else 
			while (i >= 0 && node.keys[i] > key) 
				i -= 1
			end

			if (node.child[i + 1].count == (2 * node.degree - 1)) 
				#  When need to split child nodes
				self.splitChildNodes(node, node.child[i + 1], i + 1)
				if (node.keys[i + 1] < key) 
					i += 1
				end

			end

			self.setValue(node.child[i + 1], key)
		end

	end

	#  Handles the request to add new node in B Tree
	def insert(key) 
		if (self.root == nil) 
			#  When add first node of tree
			self.root = self.createNode(self.degree, 1)
			#  set key value
			self.root.keys[0] = key
			self.root.count += 1
		else 
			if (self.root.count == 2 * self.degree - 1) 
				node = self.createNode(self.degree, 0)
				node.child[0] = self.root
				self.splitChildNodes(node, self.root, 0)
				i = 0
				if (node.keys[0] < key) 
					i += 1
				end

				self.setValue(node.child[i], key)
				#  set new root
				self.root = node
			else 
				self.setValue(self.root, key)
			end

		end

	end

	#  Display tree elements
	def traversal(node) 
		if (node != nil) 
			i = 0
			while (i < node.count) 
				self.traversal(node.child[i])
				print("  ", node.keys[i])
				i += 1
			end

			self.traversal(node.child[i])
		end

	end

	#  Find that given element exists in b tree
	def search(node, key) 
		if (node != nil) 
			i = 0
			while (i < node.count) 
				if (self.search(node.child[i], key) == 1 || node.keys[i] == key) 
					return 1
				end

				i += 1
			end

			return self.search(node.child[i], key)
		else 
			return 0
		end

	end

end

def main() 
	#  Create b-tree with degree 3
	tree = BTree.new(3)
	tree.insert(13)
	tree.insert(5)
	tree.insert(3)
	tree.insert(6)
	tree.insert(37)
	tree.insert(23)
	tree.insert(8)
	tree.insert(9)
	tree.insert(10)
	tree.insert(26)
	tree.insert(12)
	tree.insert(7)
	tree.insert(11)
	# 
	#       (6,  9, 13)
	#       /   |  \   \
	#      /    |   \   (23,26,37)   
	#   (3,5) (7,8) (10,11,12)
	#   Constructed B Tree
	
	tree.traversal(tree.root)
end

main()

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
// Scala Program
// B-Tree node insertion
// Define tree node
class TreeNode(var keys: Array[Int] , 
  var child: Array[TreeNode] , 
    var count: Int , 
      var leaf: Int , 
        var degree: Int)
{
	def this(count: Int, leaf: Int, degree: Int)
	{
		this(Array.fill[Int](2 * degree - 1)(0), 
             Array.fill[TreeNode](2 * degree - 1)(null), 
             count, leaf, degree);
	}
}
// Define structure of B Tree
class BTree(var degree: Int , var root: TreeNode)
{
	def this(degree : Int)
	{
		this(degree, null);
	}
	// Creating and returning new node of b tree
	def createNode(degree: Int, leaf: Int): TreeNode = {
		var node: TreeNode = new TreeNode(0, leaf, degree);
	
		return node;
	}
	// This function are split the child node
	def splitChildNodes(x: TreeNode, y: TreeNode, i: Int): Unit = {
		// Create new node z
		var z: TreeNode = this.createNode(y.degree, y.leaf);
		z.count = x.degree - 1;
		var j: Int = 0;
		// Get key
		while (j < x.degree - 1)
		{
			z.keys(j) = y.keys(j + x.degree);
			//reset slot value
			y.keys(j + x.degree) = 0;
			j += 1;
		}
		if (y.leaf == 0)
		{
			// Get child value
			j = 0;
			while (j < x.degree)
			{
				z.child(j) = y.child(j + x.degree);
				y.child(j + x.degree) = null;
				j += 1;
			}
		}
		y.count = x.degree - 1;
		j = x.count;
		while (j >= i + 1)
		{
			x.child(j + 1) = x.child(j);
			j -= 1;
		}
		x.child(i + 1) = z;
		j = x.count - 1;
		while (j >= i)
		{
			x.keys(j + 1) = x.keys(j);
			j -= 1;
		}
		x.keys(i) = y.keys(x.degree - 1);
		y.keys(x.degree - 1) = 0;
		x.count = x.count + 1;
	}
	// Set key into the node
	def setValue(node: TreeNode, key: Int): Unit = {
		if (node == null)
		{
			print("Emty");
			return;
		}
		var i: Int = node.count - 1;
		if (node.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node.keys(i) > key)
			{
				node.keys(i + 1) = node.keys(i);
				i -= 1;
			}
			// Add new key
			node.keys(i + 1) = key;
			// Update node key counter
			node.count = node.count + 1;
		}
		else
		{
			while (i >= 0 && node.keys(i) > key)
			{
				i -= 1;
			}
			if (node.child(i + 1).count == (2 * node.degree - 1))
			{
				// When need to split child nodes
				this.splitChildNodes(node, node.child(i + 1), i + 1);
				if (node.keys(i + 1) < key)
				{
					i += 1;
				}
			}
			this.setValue(node.child(i + 1), key);
		}
	}
	// Handles the request to add new node in B Tree
	def insert(key: Int): Unit = {
		if (this.root == null)
		{
			// When add first node of tree
			this.root = this.createNode(this.degree, 1);
			// set key value
			this.root.keys(0) = key;
			this.root.count += 1;
		}
		else
		{
			if (this.root.count == 2 * this.degree - 1)
			{
				var node: TreeNode = this.createNode(this.degree, 0);
				node.child(0) = this.root;
				this.splitChildNodes(node, this.root, 0);
				var i: Int = 0;
				if (node.keys(0) < key)
				{
					i += 1;
				}
				this.setValue(node.child(i), key);
				// set new root
				this.root = node;
			}
			else
			{
				this.setValue(this.root, key);
			}
		}
	}
	// Display tree elements
	def traversal(node: TreeNode): Unit = {
		if (node != null)
		{
			var i: Int = 0;
			while (i < node.count)
			{
				this.traversal(node.child(i));
				print("  " + node.keys(i));
				i += 1;
			}
			this.traversal(node.child(i));
		}
	}
	// Find that given element exists in b tree
	def search(node: TreeNode, key: Int): Int = {
		if (node != null)
		{
			var i: Int = 0;
			while (i < node.count)
			{
				if (this.search(node.child(i), key) == 1 || node.keys(i) == key)
				{
					return 1;
				}
				i += 1;
			}
			return this.search(node.child(i), key);
		}
		else
		{
			return 0;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		// Create b-tree with degree 3
		var tree: BTree = new BTree(3);
		tree.insert(13);
		tree.insert(5);
		tree.insert(3);
		tree.insert(6);
		tree.insert(37);
		tree.insert(23);
		tree.insert(8);
		tree.insert(9);
		tree.insert(10);
		tree.insert(26);
		tree.insert(12);
		tree.insert(7);
		tree.insert(11);
		/*
		      (6,  9, 13)
		      /   |  \   \
		     /    |   \   (23,26,37)   
		  (3,5) (7,8) (10,11,12)
		  Constructed B Tree
		*/
		tree.traversal(tree.root);
	}
}

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37
// Swift 4 Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
	var keys: [Int];
	var child: [TreeNode?];
	var count: Int;
	var leaf: Int;
	var degree: Int;
	init(_ count: Int, _ leaf: Int, _ degree: Int)
	{
		self.count = count;
		self.leaf = leaf;
		self.degree = degree;
      	self.keys = Array(repeating: 0, count: 2 * degree - 1);
      	self.child = Array(repeating: nil, count: 2 * degree - 1);
	}
}
// Define structure of B Tree
class BTree
{
	var degree: Int;
	var root: TreeNode? ;
	init(_ degree: Int)
	{
		self.root = nil;
		self.degree = degree;
	}
	// Creating and returning new node of b tree
	func createNode(_ degree: Int, _ leaf: Int)->TreeNode?
	{
		let node: TreeNode? = TreeNode(0, leaf, degree);
		return node;
	}
	// This function are split the child node
	func splitChildNodes(_ x: TreeNode? , _ y : TreeNode? , _ i : Int)
	{
		// Create new node z
		let z: TreeNode? = self.createNode(y!.degree, y!.leaf);
		z!.count = x!.degree - 1;
		var j: Int = 0;
		// Get key
		while (j < x!.degree - 1)
		{
			z!.keys[j] = y!.keys[j + x!.degree];
			//reset slot value
			y!.keys[j + x!.degree] = 0;
			j += 1;
		}
		if (y!.leaf == 0)
		{
			// Get child value
			j = 0;
			while (j < x!.degree)
			{
				z!.child[j] = y!.child[j + x!.degree];
				y!.child[j + x!.degree] = nil;
				j += 1;
			}
		}
		y!.count = x!.degree - 1;
		j = x!.count;
		while (j >= i + 1)
		{
			x!.child[j + 1] = x!.child[j];
			j -= 1;
		}
		x!.child[i + 1] = z;
		j = x!.count - 1;
		while (j >= i)
		{
			x!.keys[j + 1] = x!.keys[j];
			j -= 1;
		}
		x!.keys[i] = y!.keys[x!.degree - 1];
		y!.keys[x!.degree - 1] = 0;
		x!.count = x!.count + 1;
	}
	// Set key into the node
	func setValue(_ node: TreeNode? , _ key : Int)
	{
		if (node == nil)
		{
			print("Emty", terminator: "");
			return;
		}
		var i: Int = node!.count - 1;
		if (node!.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node!.keys[i] > key)
			{
				node!.keys[i + 1] = node!.keys[i];
				i -= 1;
			}
			// Add new key
			node!.keys[i + 1] = key;
			// Update node key counter
			node!.count = node!.count + 1;
		}
		else
		{
			while (i >= 0 && node!.keys[i] > key)
			{
				i -= 1;
			}
			if (node!.child[i + 1]!.count == (2 * node!.degree - 1))
			{
				// When need to split child nodes
				self.splitChildNodes(node, node!.child[i + 1], i + 1);
				if (node!.keys[i + 1] < key)
				{
					i += 1;
				}
			}
			self.setValue(node!.child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	func insert(_ key: Int)
	{
		if (self.root == nil)
		{
			// When add first node of tree
			self.root = self.createNode(self.degree, 1);
			// set key value
			self.root!.keys[0] = key;
			self.root!.count += 1;
		}
		else
		{
			if (self.root!.count == 2 * self.degree - 1)
			{
				let node: TreeNode? = self.createNode(self.degree, 0);
				node!.child[0] = self.root;
				self.splitChildNodes(node, self.root, 0);
				var i: Int = 0;
				if (node!.keys[0] < key)
				{
					i += 1;
				}
				self.setValue(node!.child[i], key);
				// set new root
				self.root = node;
			}
			else
			{
				self.setValue(self.root, key);
			}
		}
	}
	// Display tree elements
	func traversal(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			var i: Int = 0;
			while (i < node!.count)
			{
				self.traversal(node!.child[i]);
				print("  ", node!.keys[i], terminator: "");
				i += 1;
			}
			self.traversal(node!.child[i]);
		}
	}
	// Find that given element exists in b tree
	func search(_ node: TreeNode? , _ key : Int)->Int
	{
		if (node  != nil)
		{
			var i: Int = 0;
			while (i < node!.count)
			{
				if (self.search(node!.child[i], key) == 1 || node!.keys[i] == key)
				{
					return 1;
				}
				i += 1;
			}
			return self.search(node!.child[i], key);
		}
		else
		{
			return 0;
		}
	}
}
func main()
{
	// Create b-tree with degree 3
	let tree: BTree = BTree(3);
	tree.insert(13);
	tree.insert(5);
	tree.insert(3);
	tree.insert(6);
	tree.insert(37);
	tree.insert(23);
	tree.insert(8);
	tree.insert(9);
	tree.insert(10);
	tree.insert(26);
	tree.insert(12);
	tree.insert(7);
	tree.insert(11);
	/*
	      (6,  9, 13)
	      /   |  \   \
	     /    |   \   (23,26,37)   
	  (3,5) (7,8) (10,11,12)
	  Constructed B Tree
	*/
	tree.traversal(tree.root);
}
main();

Output

   3   5   6   7   8   9   10   11   12   13   23   26   37
// Kotlin Program
// B-Tree node insertion
// Define tree node
class TreeNode
{
	var keys: Array <Int> ;
	var child: Array <TreeNode?> ;
	var count: Int;
	var leaf: Int;
	var degree: Int;
	constructor(count: Int, leaf: Int, degree: Int)
	{
		this.count = count;
		this.leaf = leaf;
		this.degree = degree;
		// Create memory of node key
		this.keys = Array(2 * degree - 1)
		{
			0
		};
		// Allocate memory of node child
		this.child = Array(2 * degree - 1)
		{
			null
		};
	}
}
// Define structure of B Tree
class BTree
{
	var degree: Int;
	var root: TreeNode ? ;
	constructor(degree: Int)
	{
		this.root = null;
		this.degree = degree;
	}
	// Creating and returning new node of b tree
	fun createNode(degree: Int, leaf: Int): TreeNode
	{
		var node: TreeNode = TreeNode(0, leaf, degree);
		return node;
	}
	// This function are split the child node
	fun splitChildNodes(x: TreeNode? , y : TreeNode? , i : Int): Unit
	{
		// Create new node z
		var z: TreeNode = this.createNode(y!!.degree, y.leaf);
		z.count = x!!.degree - 1;
		var j: Int = 0;
		// Get key
		while (j < x.degree - 1)
		{
			z.keys[j] = y.keys[j + x.degree];
			//reset slot value
			y.keys[j + x.degree] = 0;
			j += 1;
		}
		if (y.leaf == 0)
		{
			// Get child value
			j = 0;
			while (j < x.degree)
			{
				z.child[j] = y.child[j + x.degree];
				y.child[j + x.degree] = null;
				j += 1;
			}
		}
		y.count = x.degree - 1;
		j = x.count;
		while (j >= i + 1)
		{
			x.child[j + 1] = x.child[j];
			j -= 1;
		}
		x.child[i + 1] = z;
		j = x.count - 1;
		while (j >= i)
		{
			x.keys[j + 1] = x.keys[j];
			j -= 1;
		}
		x.keys[i] = y.keys[x.degree - 1];
		y.keys[x.degree - 1] = 0;
		x.count = x.count + 1;
	}
	// Set key into the node
	fun setValue(node: TreeNode ? , key : Int): Unit
	{
	
		var i: Int = node!!.count - 1;
		if (node.leaf == 1)
		{
			// When get leaf node
			// Find location to add new key
			while (i >= 0 && node.keys[i] > key)
			{
				node.keys[i + 1] = node.keys[i];
				i -= 1;
			}
			// Add new key
			node.keys[i + 1] = key;
			// Update node key counter
			node.count = node.count + 1;
		}
		else
		{
			while (i >= 0 && node.keys[i] > key)
			{
				i -= 1;
			}
			if (node.child[i + 1]!!.count == (2 * node.degree - 1))
			{
				// When need to split child nodes
				this.splitChildNodes(node, node.child[i + 1], i + 1);
				if (node.keys[i + 1] < key)
				{
					i += 1;
				}
			}
			this.setValue(node.child[i + 1], key);
		}
	}
	// Handles the request to add new node in B Tree
	fun insert(key: Int): Unit
	{
		if (this.root == null)
		{
			// When add first node of tree
			this.root = this.createNode(this.degree, 1);
			// set key value
			this.root!!.keys[0] = key;
			this.root!!.count += 1;
		}
		else
		{
			if (this.root!!.count == 2 * this.degree - 1)
			{
				var node: TreeNode = this.createNode(this.degree, 0);
				node.child[0] = this.root;
				this.splitChildNodes(node, this.root, 0);
				var i: Int = 0;
				if (node.keys[0] < key)
				{
					i += 1;
				}
				this.setValue(node.child[i], key);
				// set new root
				this.root = node;
			}
			else
			{
				this.setValue(this.root, key);
			}
		}
	}
	// Display tree elements
	fun traversal(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			var i: Int = 0;
			while (i < node.count)
			{
				this.traversal(node.child[i]);
				print("  " + node.keys[i]);
				i += 1;
			}
			this.traversal(node.child[i]);
		}
	}
	// Find that given element exists in b tree
	fun search(node: TreeNode ? , key : Int): Int
	{
		if (node != null)
		{
			var i: Int = 0;
			while (i < node.count)
			{
				if (this.search(node.child[i], key) == 1 || node.keys[i] == key)
				{
					return 1;
				}
				i += 1;
			}
			return this.search(node.child[i], key);
		}
		else
		{
			return 0;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create b-tree with degree 3
	var tree: BTree = BTree(3);
	tree.insert(13);
	tree.insert(5);
	tree.insert(3);
	tree.insert(6);
	tree.insert(37);
	tree.insert(23);
	tree.insert(8);
	tree.insert(9);
	tree.insert(10);
	tree.insert(26);
	tree.insert(12);
	tree.insert(7);
	tree.insert(11);
	/*
	      (6,  9, 13)
	      /   |  \   \
	     /    |   \   (23,26,37)   
	  (3,5) (7,8) (10,11,12)
	  Constructed B Tree
	*/
	tree.traversal(tree.root);
}

Output

  3  5  6  7  8  9  10  11  12  13  23  26  37

Time Complexity

The time complexity for inserting a key into a B-tree is O(log n), where n is the number of keys in the tree. This is because each insertion or split operation involves traversing the height of the tree, which is logarithmic in relation to the number of keys.

Java Code Work

Internal representation of B Tree in c




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