# B-tree Insertion

Contents

## B-tree insertion

In this tutorial, you will learn how to insert a key into a btree. Additionally, you will discover working instances of inserting keys into a B-tree in C, C++, Java, and Python.

Inserting an element on a B-tree comprises of two occasions: searching the appropriate node to insert the element and splitting the node if required. Insertion activity consistently happens in the bottom-up approach.

## What is a B-Tree?

A B-Tree is a self-balancing m-way tree data structure that allows searches, accesses to, insertions, and deletions in logarithmic time. Every node in a B-Tree of order m can have, probably, m children and m-1 keys.

Consider B-Tree a generalization of a binary search tree (BST). Like a BST, the stored data is arranged in a B-Tree, however not at all like a BST, a B-Tree can have in excess of two child nodes.

Notwithstanding having different children, every node in a B-Tree can have more than one key, which keeps the height of the tree relatively little. Later on, we will perceive how keeping different keys in a single node assists with data locality.

In outline, a B-Tree of the order m has the accompanying properties:

• each node has at most m children

• a node with n children should have n-1 keys

• all leaf nodes are at a similar level

• every node, with the exception of the root, is in any event half full

• root has in any event two children on the off chance that it’s not a leaf

Let us understand these events below.

## Insertion Operation

1. If the tree is unfilled, apportion a root node and addition the key.
2. Update the allowed number of keys in the node.
3. Search the fitting node for addition.
4. If the node is full, follow the steps beneath.
5. Insert the elements in increasing order.
6. Now, there are elements greater than their limit. Along these lines, split at the middle.
7. Push the middle key upwards and make the left keys as a left child and the right keys as a right child.
8. If the node isn’t full, follow the steps beneath.
9. Insert the node in increasing order.

## Insertion Example

Let us understand the insertion operation with the illustrations below.

The elements to be inserted are 8, 9, 10, 11, 15, 16, 17, 18, 20, 23.

## Algorithm for Inserting an Element

```BreeInsertion(T, k)
r  root[T]
if n[r] = 2t - 1
s = AllocateNode()
root[T] = s
leaf[s] = FALSE
n[s] <- 0
c1[s] <- r
BtreeSplitChild(s, 1, r)
BtreeInsertNonFull(s, k)
else BtreeInsertNonFull(r, k)
BtreeInsertNonFull(x, k)
i = n[x]
if leaf[x]
while i ≥ 1 and k < keyi[x]
keyi+1 [x] = keyi[x]
i = i - 1
keyi+1[x] = k
n[x] = n[x] + 1
else while i ≥ 1 and k < keyi[x]
i = i - 1
i = i + 1
if n[ci[x]] == 2t - 1
BtreeSplitChild(x, i, ci[x])
if k &rt; keyi[x]
i = i + 1
BtreeInsertNonFull(ci[x], k)
BtreeSplitChild(x, i)
BtreeSplitChild(x, i, y)
z = AllocateNode()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
keyj[z] = keyj+t[y]
if not leaf [y]
for j = 1 to t
cj[z] = cj + t[y]
n[y] = t - 1
for j = n[x] + 1 to i + 1
cj+1[x] = cj[x]
ci+1[x] = z
for j = n[x] to i
keyj+1[x] = keyj[x]
keyi[x] = keyt[y]
n[x] = n[x] + 1```

## Python, Java, and C/C++ Examples

Python

```# Inserting a key on a B-tree in Python

# Create a node
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.child = []

# Tree
class BTree:
def __init__(self, t):
self.root = BTreeNode(True)
self.t = t

# Insert node
def insert(self, k):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
temp = BTreeNode()
self.root = temp
temp.child.insert(0, root)
self.split_child(temp, 0)
self.insert_non_full(temp, k)
else:
self.insert_non_full(root, k)

# Insert nonfull
def insert_non_full(self, x, k):
i = len(x.keys) - 1
if x.leaf:
x.keys.append((None, None))
while i >= 0 and k[0] < x.keys[i][0]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = k
else:
while i >= 0 and k[0] < x.keys[i][0]:
i -= 1
i += 1
if len(x.child[i].keys) == (2 * self.t) - 1:
self.split_child(x, i)
if k[0] > x.keys[i][0]:
i += 1
self.insert_non_full(x.child[i], k)

# Split the child
def split_child(self, x, i):
t = self.t
y = x.child[i]
z = BTreeNode(y.leaf)
x.child.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.child = y.child[t: 2 * t]
y.child = y.child[0: t - 1]

# Print the tree
def print_tree(self, x, l=0):
print("Level ", l, " ", len(x.keys), end=":")
for i in x.keys:
print(i, end=" ")
print()
l += 1
if len(x.child) > 0:
for i in x.child:
self.print_tree(i, l)

def main():
B = BTree(3)

for i in range(10):
B.insert((i, 2 * i))

B.print_tree(B.root)

if __name__ == '__main__':
main()```

Java

```// Inserting a key on a B-tree in Java

public class BTree {

private int T;

// Node Creation
public class Node {
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;

public int Find(int k) {
for (int i = 0; i < this.n; i++) {
if (this.key[i] == k) {
return i;
}
}
return -1;
};
}

public BTree(int t) {
T = t;
root = new Node();
root.n = 0;
root.leaf = true;
}

private Node root;

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

for (int j = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}

// insert key
public void insert(final int key) {
Node r = root;
if (r.n == 2 * T - 1) {
Node s = new Node();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
split(s, 0, r);
_insert(s, key);
} else {
_insert(r, key);
}
}

// insert node
final private void _insert(Node x, int k) {

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

}

public void display() {
display(root);
}

// Display the tree
private void display(Node x) {
assert (x == null);
for (int i = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
}
if (!x.leaf) {
for (int i = 0; i < x.n + 1; i++) {
display(x.child[i]);
}
}
}

public static void main(String[] args) {
BTree b = new BTree(3);
b.insert(8);
b.insert(9);
b.insert(10);
b.insert(11);
b.insert(15);
b.insert(20);
b.insert(17);

b.display();
}
}```

C

```// insertioning a key on a B-tree in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct btreeNode {
int item[MAX + 1], count;
};

struct btreeNode *root;

// Node creation
struct btreeNode *createNode(int item, struct btreeNode *child) {
struct btreeNode *newNode;
newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
newNode->item[1] = item;
newNode->count = 1;
return newNode;
}

// Insert
void insertValue(int item, int pos, struct btreeNode *node,
struct btreeNode *child) {
int j = node->count;
while (j > pos) {
node->item[j + 1] = node->item[j];
j--;
}
node->item[j + 1] = item;
node->count++;
}

// Split node
void splitNode(int item, int *pval, int pos, struct btreeNode *node,
struct btreeNode *child, struct btreeNode **newNode) {
int median, j;

if (pos > MIN)
median = MIN + 1;
else
median = MIN;

*newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->item[j - median] = node->item[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;

if (pos <= MIN) {
insertValue(item, pos, node, child);
} else {
insertValue(item, pos - median, *newNode, child);
}
*pval = node->item[node->count];
node->count--;
}

// Set the value of node
int setNodeValue(int item, int *pval,
struct btreeNode *node, struct btreeNode **child) {
int pos;
if (!node) {
*pval = item;
*child = NULL;
return 1;
}

if (item < node->item[1]) {
pos = 0;
} else {
for (pos = node->count;
(item < node->item[pos] && pos > 1); pos--)
;
if (item == node->item[pos]) {
printf("Duplicates not allowed\n");
return 0;
}
}
if (setNodeValue(item, pval, node->link[pos], child)) {
if (node->count < MAX) {
insertValue(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}

// Insert the value
void insertion(int item) {
int flag, i;
struct btreeNode *child;

flag = setNodeValue(item, &i, root, &child);
if (flag)
root = createNode(i, child);
}

// Copy the successor
void copySuccessor(struct btreeNode *myNode, int pos) {
struct btreeNode *dummy;

myNode->item[pos] = dummy->item[1];
}

// Do rightshift
void rightShift(struct btreeNode *myNode, int pos) {
int j = x->count;

while (j > 0) {
x->item[j + 1] = x->item[j];
}
x->item[1] = myNode->item[pos];
x->count++;

myNode->item[pos] = x->item[x->count];
x->count--;
return;
}

// Do leftshift
void leftShift(struct btreeNode *myNode, int pos) {
int j = 1;
struct btreeNode *x = myNode->link[pos - 1];

x->count++;
x->item[x->count] = myNode->item[pos];

myNode->item[pos] = x->item[1];
x->count--;

while (j <= x->count) {
x->item[j] = x->item[j + 1];
j++;
}
return;
}

// Merge the nodes
void mergeNodes(struct btreeNode *myNode, int pos) {
int j = 1;

x2->count++;
x2->item[x2->count] = myNode->item[pos];

while (j <= x1->count) {
x2->count++;
x2->item[x2->count] = x1->item[j];
j++;
}

j = pos;
while (j < myNode->count) {
myNode->item[j] = myNode->item[j + 1];
j++;
}
myNode->count--;
free(x1);
}

void adjustNode(struct btreeNode *myNode, int pos) {
if (!pos) {
leftShift(myNode, 1);
} else {
mergeNodes(myNode, 1);
}
} else {
if (myNode->count != pos) {
if (myNode->link[pos - 1]->count > MIN) {
rightShift(myNode, pos);
} else {
if (myNode->link[pos + 1]->count > MIN) {
leftShift(myNode, pos + 1);
} else {
mergeNodes(myNode, pos);
}
}
} else {
if (myNode->link[pos - 1]->count > MIN)
rightShift(myNode, pos);
else
mergeNodes(myNode, pos);
}
}
}

// Traverse the tree
void traversal(struct btreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
printf("%d ", myNode->item[i + 1]);
}
}
}

int main() {
int item, ch;

insertion(8);
insertion(9);
insertion(10);
insertion(11);
insertion(15);
insertion(16);
insertion(17);
insertion(18);
insertion(20);
insertion(23);

traversal(root);
}```

C++

```// Inserting a key on a B-tree in C++

#include <iostream>
using namespace std;

class Node {
int *keys;
int t;
Node **C;
int n;
bool leaf;

public:
Node(int _t, bool _leaf);

void insertNonFull(int k);
void splitChild(int i, Node *y);
void traverse();

friend class BTree;
};

class BTree {
Node *root;
int t;

public:
BTree(int _t) {
root = NULL;
t = _t;
}

void traverse() {
if (root != NULL)
root->traverse();
}

void insert(int k);
};

Node::Node(int t1, bool leaf1) {
t = t1;
leaf = leaf1;

keys = new int[2 * t - 1];
C = new Node *[2 * t];

n = 0;
}

// Traverse the nodes
void Node::traverse() {
int i;
for (i = 0; i < n; i++) {
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i];
}

if (leaf == false)
C[i]->traverse();
}

// Insert the node
void BTree::insert(int k) {
if (root == NULL) {
root = new Node(t, true);
root->keys[0] = k;
root->n = 1;
} else {
if (root->n == 2 * t - 1) {
Node *s = new Node(t, false);

s->C[0] = root;

s->splitChild(0, root);

int i = 0;
if (s->keys[0] < k)
i++;
s->C[i]->insertNonFull(k);

root = s;
} else
root->insertNonFull(k);
}
}

// Insert non full condition
void Node::insertNonFull(int k) {
int i = n - 1;

if (leaf == true) {
while (i >= 0 && keys[i] > k) {
keys[i + 1] = keys[i];
i--;
}

keys[i + 1] = k;
n = n + 1;
} else {
while (i >= 0 && keys[i] > k)
i--;

if (C[i + 1]->n == 2 * t - 1) {
splitChild(i + 1, C[i + 1]);

if (keys[i + 1] < k)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

// split the child
void Node::splitChild(int i, Node *y) {
Node *z = new Node(y->t, y->leaf);
z->n = t - 1;

for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

if (y->leaf == false) {
for (int j = 0; j < t; j++)
z->C[j] = y->C[j + t];
}

y->n = t - 1;
for (int j = n; j >= i + 1; j--)
C[j + 1] = C[j];

C[i + 1] = z;

for (int j = n - 1; j >= i; j--)
keys[j + 1] = keys[j];

keys[i] = y->keys[t - 1];
n = n + 1;
}

int main() {
BTree t(3);
t.insert(8);
t.insert(9);
t.insert(10);
t.insert(11);
t.insert(15);
t.insert(16);
t.insert(17);
t.insert(18);
t.insert(20);
t.insert(23);

cout << "The B-tree is: ";
t.traverse();
}```

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.