Algorithm
Insertion into a B-tree involves a series of steps to maintain the properties of the B-tree. B-trees are balanced search trees commonly used in databases and file systems for efficient data retrieval and insertion. Here is a high-level overview of the insertion process:
-
Search for the Node to Insert: Start at the root and traverse the tree to find the appropriate leaf node where the new key should be inserted. This is similar to searching for the key in a regular binary search tree.
-
Insertion in Leaf Node: Once the appropriate leaf node is found, insert the new key into that node. If the node overflows (i.e., exceeds the maximum allowed number of keys), it needs to be split.
-
Node Overflow and Split: If the leaf node overflows, split it into two nodes. The middle key of the overflowing node is moved up to its parent, and the remaining keys are divided between the two new nodes. If the parent also overflows, the process is repeated recursively until a node that does not overflow is found or a new root is created.
-
Update Parent Nodes: After a split, update the parent nodes by adding the middle key to the parent and linking the new nodes. If the parent node overflows, split it and update its parent, continuing the process until the root is reached.
-
Adjust Root if Necessary: If the root is split during the insertion process, create a new root with the middle key as its sole element.
-
Maintain B-tree Properties: Ensure that the B-tree properties are maintained after each insertion. These properties include a balanced tree structure and the maximum and minimum number of keys in each node.
-
Complexity: The time complexity of insertion in a B-tree is O(log n), where n is the number of keys in the tree. This is because the height of the B-tree remains balanced due to the splitting and merging of nodes.
Code Examples
#1 Insertion into a B-tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
class BTree:
def __init__(self, degree):
self.root = Node()
self.degree = degree
def insert(self, key):
root = self.root
if len(root.keys) == (2 * self.degree) - 1:
new_root = Node()
self.root = new_root
new_root.children.append(root)
self._split_child(new_root, 0)
self._insert_non_full(new_root, key)
else:
self._insert_non_full(root, key)
def _insert_non_full(self, x, key):
i = len(x.keys) - 1
if x.leaf:
x.keys.append(0)
while i >= 0 and key < x.keys[i]:
x.keys[i + 1] = x.keys[i]
i -= 1
x.keys[i + 1] = key
else:
while i >= 0 and key < x.keys[i]:
i -= 1
i += 1
if len(x.children[i].keys) == (2 * self.degree) - 1:
self._split_child(x, i)
if key > x.keys[i]:
i += 1
self._insert_non_full(x.children[i], key)
def _split_child(self, x, i):
t = self.degree
y = x.children[i]
z = Node(leaf=y.leaf)
x.children.insert(i + 1, z)
x.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t:]
y.keys = y.keys[:t - 1]
if not y.leaf:
z.children = y.children[t:]
y.children = y.children[:t]
# Example usage:
btree = BTree(degree=2)
keys = [3, 8, 12, 4, 1, 9, 6, 10, 11, 7, 5, 2]
for key in keys:
btree.insert(key)
# Print the B-tree structure
print("B-tree structure:")
print(btree.root.keys)
for child in btree.root.children:
print(child.keys)
#2 Insertion into a B-tree implement in Java
Code -
Java Programming
class BTreeNode {
int[] keys;
int t;
BTreeNode[] children;
int n; // Number of keys in the node
boolean leaf;
public BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}
}
public class BTree {
private BTreeNode root;
private int t; // Minimum degree
public BTree(int t) {
this.root = null;
this.t = t;
}
public void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) {
BTreeNode newRoot = new BTreeNode(t, false);
newRoot.children[0] = root;
splitChild(newRoot, 0);
root = newRoot;
}
insertNonFull(root, key);
}
}
private void insertNonFull(BTreeNode x, int key) {
int i = x.n - 1;
if (x.leaf) {
while (i >= 0 && key < x.keys[i]) {
x.keys[i + 1] = x.keys[i];
i--;
}
x.keys[i + 1] = key;
x.n++;
} else {
while (i >= 0 && key < x.keys[i]) {
i--;
}
i++;
if (x.children[i].n == 2 * t - 1) {
splitChild(x, i);
if (key > x.keys[i]) {
i++;
}
}
insertNonFull(x.children[i], key);
}
}
private void splitChild(BTreeNode x, int i) {
BTreeNode y = x.children[i];
BTreeNode z = new BTreeNode(t, y.leaf);
x.children[x.n + 1] = x.children[x.n];
for (int j = x.n - 1; j >= i; j--) {
x.children[j + 1] = x.children[j];
}
x.children[i + 1] = z;
for (int j = t - 1; j < 2 * t - 1; j++) {
z.keys[j - t + 1] = y.keys[j];
}
z.n = t - 1;
y.n = t - 1;
for (int j = t - 2; j >= 0; j--) {
y.keys[j] = 0; // Optional: Clear keys in the original node
}
x.keys[x.n] = y.keys[t - 1];
y.keys[t - 1] = 0;
x.n++;
}
// Other methods for searching, deleting, etc. can be added here.
}
#3 Insertion into a B-tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3
// Structure for a B-tree node
typedef struct BTreeNode {
int isLeaf; // 1 if the node is a leaf, 0 otherwise
int numKeys; // Number of keys in the node
int keys[MAX_KEYS]; // Array to store keys
struct BTreeNode* children[MAX_KEYS + 1]; // Array to store child pointers
} BTreeNode;
// Function to create a new B-tree node
BTreeNode* createNode() {
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
if (newNode == NULL) {
perror("Failed to create a new node");
exit(EXIT_FAILURE);
}
newNode->isLeaf = 1;
newNode->numKeys = 0;
for (int i = 0; i < MAX_KEYS + 1; i++) {
newNode->children[i] = NULL;
}
return newNode;
}
// Function to search for a key in the B-tree
BTreeNode* search(BTreeNode* root, int key) {
if (root == NULL) {
return NULL;
}
int i = 0;
while (i < root->numKeys && key > root->keys[i]) {
i++;
}
if (i < root->numKeys && key == root->keys[i]) {
return root; // Key found
}
if (root->isLeaf) {
return NULL; // Key not found in a leaf node
} else {
return search(root->children[i], key); // Recursively search in the appropriate child
}
}
// Function to insert a key into the B-tree
BTreeNode* insert(BTreeNode* root, int key) {
// Search for the key in the tree
BTreeNode* searchResult = search(root, key);
if (searchResult != NULL) {
printf("Key %d already exists in the B-tree.\n", key);
return root; // Key already exists
}
// If the root is full, split it and create a new root
if (root->numKeys == MAX_KEYS) {
BTreeNode* newRoot = createNode();
newRoot->isLeaf = 0;
newRoot->children[0] = root;
root = newRoot;
splitChild(newRoot, 0);
}
// Insert the key into the tree
insertNonFull(root, key);
return root;
}
// Function to insert a key into a non-full B-tree node
void insertNonFull(BTreeNode* node, int key) {
int i = node->numKeys - 1;
// If the node is a leaf, insert the key into the appropriate position
if (node->isLeaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->numKeys++;
} else {
// If the node is not a leaf, find the child to insert into
while (i >= 0 && key < node->keys[i]) {
i--;
}
i++;
// If the child is full, split it
if (node->children[i]->numKeys == MAX_KEYS) {
splitChild(node, i);
if (key > node->keys[i]) {
i++;
}
}
// Recursively insert into the appropriate child
insertNonFull(node->children[i], key);
}
}
// Function to split a full child of a B-tree node
void splitChild(BTreeNode* parentNode, int childIndex) {
BTreeNode* childNode = parentNode->children[childIndex];
BTreeNode* newChildNode = createNode();
newChildNode->isLeaf = childNode->isLeaf;
newChildNode->numKeys = MAX_KEYS / 2;
// Copy the second half of keys to the new child
for (int i = 0; i < newChildNode->numKeys; i++) {
newChildNode->keys[i] = childNode->keys[i + MAX_KEYS / 2];
}
// If the child is not a leaf, copy the second half of children pointers
if (!childNode->isLeaf) {
for (int i = 0; i < MAX_KEYS / 2 + 1; i++) {
newChildNode->children[i] = childNode->children[i + MAX_KEYS / 2];
}
}
// Update the number of keys in the child and the parent
childNode->numKeys = MAX_KEYS / 2;
parentNode->numKeys++;
// Shift the children pointers to make space for the new child
for (int i = parentNode->numKeys; i > childIndex + 1; i--) {
parentNode->children[i] = parentNode->children[i - 1];
}
// Insert the new child into the parent
parentNode->children[childIndex + 1] = newChildNode;
// Shift the keys to make space for the median key from the child
for (int i = parentNode->numKeys - 1; i > childIndex; i--) {
parentNode->keys[i] = parentNode->keys[i - 1];
}
// Move the median key from the child to the parent
parentNode->keys[childIndex] = childNode->keys[MAX_KEYS / 2];
}
// Function to print the B-tree in-order
void inOrderTraversal(BTreeNode* root) {
if (root != NULL) {
int i;
for (i = 0; i < root->numKeys; i++) {
inOrderTraversal(root->children[i]);
printf("%d ", root->keys[i]);
}
inOrderTraversal(root->children[i]);
}
}
// Function to free the memory allocated for the B-tree nodes
void freeBTree(BTreeNode* root) {
if (root != NULL) {
for (int i = 0; i < = root->numKeys; i++) {
freeBTree(root->children[i]);
}
free(root);
}
}
int main() {
BTreeNode* root = createNode();
// Insert keys into the B-tree
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 5);
root = insert(root, 6);
root = insert(root, 12);
// Print the B-tree in-order
printf("In-order traversal of the B-tree: ");
inOrderTraversal(root);
printf("\n");
// Free the memory allocated for the B-tree nodes
freeBTree(root);
return 0;
}
#4 Insertion into a B-tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
const int ORDER = 3;
// Node structure for the B-tree
struct BTreeNode {
bool is_leaf;
std::vector<int> keys;
std::vector < BTreeNode*> children;
BTreeNode() : is_leaf(true) {}
// Function to insert a key into the node
void insert(int key) {
auto it = std::upper_bound(keys.begin(), keys.end(), key);
keys.insert(it, key);
}
};
// Function to insert a key into the B-tree
BTreeNode* insert(BTreeNode* root, int key) {
// If the root is null, create a new root
if (!root) {
root = new BTreeNode;
root->insert(key);
return root;
}
// If the root is a leaf, insert the key into the root
if (root->is_leaf) {
root->insert(key);
} else {
// Find the child to insert into
int i = 0;
while (i < root->keys.size() && key > root->keys[i]) {
i++;
}
// Recursively insert into the child
root->children[i] = insert(root->children[i], key);
}
// If the root is full, split it
if (root->keys.size() >= ORDER) {
BTreeNode* new_root = new BTreeNode;
BTreeNode* new_child = new BTreeNode;
// Move the middle key to the new root
int mid_index = ORDER / 2;
new_root->insert(root->keys[mid_index]);
// Move keys and children to the new child
new_child->keys.assign(root->keys.begin() + mid_index + 1, root->keys.end());
new_child->children.assign(root->children.begin() + mid_index + 1, root->children.end());
// Update the original root
root->keys.resize(mid_index);
root->children.resize(mid_index + 1);
// Set the new child as the child of the new root
new_root->children[0] = root;
new_root->children[1] = new_child;
// Return the new root
return new_root;
}
return root;
}
// Function to print the B-tree (in-order traversal)
void printBTree(BTreeNode* root) {
if (root) {
for (int i = 0; i < root->keys.size(); ++i) {
printBTree(root->children[i]);
std::cout << root->keys[i] << " ";
}
printBTree(root->children.back());
}
}
int main() {
BTreeNode* root = nullptr;
// Insert keys into the B-tree
std::vector<int> keys_to_insert = {3, 7, 1, 9, 5, 12, 6, 8, 11, 10};
for (int key : keys_to_insert) {
root = insert(root, key);
}
// Print the B-tree
printBTree(root);
return 0;
}
Demonstration
Insertion into a B-tree-DevsEnv