Algorithm
Insertion in a B+ tree involves a series of steps to maintain the balance and properties of the tree. Here's a high-level overview of the insertion process:
-
Search for the Correct Leaf Node: Start by traversing the tree from the root to a leaf node, following the path that would be taken during a search operation. This step is identical to the search operation and is done to find the appropriate leaf node for the new key.
-
Insertion in the Leaf Node: Once the leaf node is found, insert the new key and its associated value into the leaf node. If the leaf node overflows due to the insertion, it needs to be split.
-
Leaf Node Overflow Handling: If the leaf node overflows, split it into two nodes. Distribute the keys evenly between the two nodes and promote the middle key to the parent node. Update the parent node to include the new key and the pointer to the right node resulting from the split.
-
Update Ancestors: If the parent node overflows after the insertion, the process is repeated. The overflow is resolved by splitting the parent node, promoting the middle key, and updating the ancestors accordingly. This process continues until the root node is reached or a node that does not overflow is found.
-
Adjust Root: If the root node overflows during the insertion, it needs to be split, and a new root is created with the middle key as the only key, pointing to the two new children.
-
Update Tree Properties: After the insertion, make sure to update any necessary metadata, such as maintaining the ordering of keys in nodes and updating the pointers correctly.
The splitting process is what maintains the balance of the B+ tree and ensures that it remains a valid search tree. The splitting and updating of nodes may propagate up the tree until it either reaches the root or creates a new root.
Code Examples
#1 Insertion on a B+ Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
class BPlusTree:
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(leaf=False)
new_root.children.append(self.root)
self._split(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _insert_non_full(self, x, key):
i = len(x.keys) - 1
if x.leaf:
x.keys.append(None)
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(x, i)
if key > x.keys[i]:
i += 1
self._insert_non_full(x.children[i], key)
def _split(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:
bptree = BPlusTree(degree=2)
keys = [3, 7, 1, 9, 5, 2, 8, 4, 6]
for key in keys:
bptree.insert(key)
#2 Insertion on a B+ Tree implement in Java
Code -
Java Programming
public class BPlusTree {
// Define the degree of the B+ tree
private int degree;
// Root of the B+ tree
private Node root;
// Constructor
public BPlusTree(int degree) {
this.degree = degree;
this.root = new LeafNode();
}
// Insert a key into the B+ tree
public void insert(int key) {
root = root.insert(key);
}
// Node class representing both internal and leaf nodes
private abstract class Node {
// Common methods and properties for nodes
// Insert a key into the node
abstract Node insert(int key);
}
// LeafNode class representing leaf nodes of the B+ tree
private class LeafNode extends Node {
// List to store keys in a leaf node
private List < Integer> keys;
// Reference to the next leaf node
private LeafNode next;
// Constructor
private LeafNode() {
this.keys = new ArrayList < >();
}
@Override
Node insert(int key) {
// Insert the key into the sorted list of keys
int index = 0;
while (index < keys.size() && key > keys.get(index)) {
index++;
}
keys.add(index, key);
// Check if a split is needed
if (keys.size() > degree) {
return split();
} else {
return BPlusTree.this;
}
}
// Split the leaf node into two leaf nodes
private Node split() {
LeafNode newLeafNode = new LeafNode();
int midIndex = keys.size() / 2;
// Move half of the keys to the new leaf node
newLeafNode.keys.addAll(keys.subList(midIndex, keys.size()));
keys.subList(midIndex, keys.size()).clear();
// Update the next reference
newLeafNode.next = this.next;
this.next = newLeafNode;
// Return the new leaf node
return newLeafNode;
}
}
}
#3 Insertion on a B+ Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for the B+ tree
typedef struct Node {
int *keys;
struct Node **children;
int num_keys;
int is_leaf;
struct Node *next; // Pointer to the next node (used for leaf nodes)
} Node;
// B+ tree structure
typedef struct BPlusTree {
Node *root;
int order; // Order of the B+ tree
} BPlusTree;
// Function to create a new node
Node *createNode(int is_leaf) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->keys = (int *)malloc(sizeof(int) * (2 * t - 1));
newNode->children = (Node **)malloc(sizeof(Node *) * (2 * t));
newNode->num_keys = 0;
newNode->is_leaf = is_leaf;
newNode->next = NULL;
return newNode;
}
// Function to create a new B+ tree
BPlusTree *createBPlusTree(int order) {
BPlusTree *tree = (BPlusTree *)malloc(sizeof(BPlusTree));
tree->root = createNode(1); // Root is initially a leaf node
tree->order = order;
return tree;
}
// Function to search for the correct position to insert the key
int searchKey(Node *node, int key) {
int index = 0;
while (index < node->num_keys && key > node->keys[index]) {
index++;
}
return index;
}
// Function to split a node
void splitNode(BPlusTree *tree, Node *parent, int index) {
int t = tree->order;
Node *left = parent->children[index];
Node *right = createNode(left->is_leaf);
right->next = left->next;
left->next = right;
// Move the middle key of the left node to the parent node
int middleKey = left->keys[t - 1];
int i;
// Shift keys and children of the parent node to make space for the middle key
for (i = parent->num_keys; i > index; i--) {
parent->keys[i] = parent->keys[i - 1];
parent->children[i + 1] = parent->children[i];
}
parent->keys[index] = middleKey;
parent->children[index + 1] = right;
parent->num_keys++;
// Move the keys and children from the right side of the left node to the right node
for (i = 0; i < t - 1; i++) {
right->keys[i] = left->keys[i + t];
left->keys[i + t] = 0;
if (!left->is_leaf) {
right->children[i] = left->children[i + t];
left->children[i + t] = NULL;
}
}
right->num_keys = t - 1;
left->num_keys = t - 1;
}
// Function to insert a key into the B+ tree
void insertKey(BPlusTree *tree, int key) {
int t = tree->order;
Node *root = tree->root;
if (root->num_keys == (2 * t - 1)) {
// If the root is full, create a new root and split the old root
Node *newRoot = createNode(0);
newRoot->children[0] = root;
tree->root = newRoot;
splitNode(tree, newRoot, 0);
}
Node *current = tree->root;
Node *parent = NULL;
// Traverse the tree to find the correct leaf node to insert the key
while (!current->is_leaf) {
int index = searchKey(current, key);
parent = current;
current = current->children[index];
}
// Insert the key into the leaf node
int index = searchKey(current, key);
// Shift keys to make space for the new key
for (int i = current->num_keys; i > index; i--) {
current->keys[i] = current->keys[i - 1];
}
current->keys[index] = key;
current->num_keys++;
// Split the leaf node if necessary
if (current->num_keys == (2 * t - 1)) {
if (parent == NULL) {
// If the leaf node is the root, create a new root and split the leaf node
Node *newRoot = createNode(0);
newRoot->children[0] = tree->root;
tree->root = newRoot;
parent = newRoot;
}
splitNode(tree, parent, searchKey(parent, key));
}
}
// Function to print the B+ tree (in-order traversal)
void inOrderTraversal(Node *node) {
if (node != NULL) {
int i;
for (i = 0; i < node->num_keys; i++) {
if (!node->is_leaf) {
inOrderTraversal(node->children[i]);
}
printf("%d ", node->keys[i]);
}
if (!node->is_leaf) {
inOrderTraversal(node->children[i]);
}
}
}
// Function to print the B+ tree (level-order traversal)
void levelOrderTraversal(BPlusTree *tree) {
if (tree->root == NULL) {
return;
}
Node **queue = (Node **)malloc(sizeof(Node *) * 1000); // Assuming a maximum of 1000 nodes
int front = 0, rear = 0;
queue[rear++] = tree->root;
while (front < rear) {
Node *current = queue[front++];
int i;
for (i = 0; i < current->num_keys; i++) {
printf("%d ", current->keys[i]);
}
if (!current->is_leaf) {
for (i = 0; i < = current->num_keys; i++) {
queue[rear++] = current->children[i];
}
}
}
free(queue);
}
// Function to free the memory used by the B+ tree
void freeBPlusTree(Node *node) {
if (node != NULL) {
if (!node->is_leaf) {
for (int i = 0; i < = node->num_keys; i++) {
freeBPlusTree(node->children[i]);
}
}
free(node->keys);
free(node->children);
free(node);
}
}
int main() {
BPlusTree *tree = createBPlusTree(3); // B+ tree with order 3
// Insert keys into the B+ tree
insertKey(tree, 10);
insertKey(tree,
#4 Insertion on a B+ Tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
const int ORDER = 3; // Order of the B+ tree
struct Node {
std::vector<int> keys;
std::vector < Node*> children;
bool isLeaf;
Node(bool leaf = false) : isLeaf(leaf) {}
};
class BPlusTree {
private:
Node* root;
public:
BPlusTree() : root(nullptr) {}
void insert(int key) {
if (!root) {
root = new Node(true);
root->keys.push_back(key);
} else {
insertKey(root, key);
}
}
private:
void insertKey(Node* node, int key) {
if (node->isLeaf) {
insertIntoLeaf(node, key);
} else {
int i = 0;
while (i < node->keys.size() && key > node->keys[i]) {
i++;
}
insertKey(node->children[i], key);
}
}
void insertIntoLeaf(Node* leaf, int key) {
auto it = std::lower_bound(leaf->keys.begin(), leaf->keys.end(), key);
leaf->keys.insert(it, key);
if (leaf->keys.size() > ORDER - 1) {
splitLeaf(leaf);
}
}
void splitLeaf(Node* leaf) {
Node* newLeaf = new Node(true);
int middle = leaf->keys.size() / 2;
newLeaf->keys.assign(leaf->keys.begin() + middle, leaf->keys.end());
leaf->keys.erase(leaf->keys.begin() + middle, leaf->keys.end());
if (leaf->keys.size() % 2 != 0) {
middle++;
}
insertIntoParent(leaf, newLeaf->keys[0], newLeaf);
}
void insertIntoParent(Node* left, int key, Node* right) {
if (!root) {
root = new Node();
root->keys.push_back(key);
root->children.push_back(left);
root->children.push_back(right);
} else {
Node* parent = findParent(root, left);
insertIntoInternalNode(parent, key, right);
}
}
Node* findParent(Node* node, Node* child) {
if (node->isLeaf || (node->children[0]->isLeaf && node->children[0] == child)) {
return node;
}
int i = 0;
while (i < node->children.size() && child != node->children[i]) {
i++;
}
return findParent(node->children[i], child);
}
void insertIntoInternalNode(Node* node, int key, Node* right) {
auto it = std::lower_bound(node->keys.begin(), node->keys.end(), key);
int index = it - node->keys.begin();
node->keys.insert(it, key);
node->children.insert(node->children.begin() + index + 1, right);
if (node->keys.size() > ORDER - 1) {
splitInternalNode(node);
}
}
void splitInternalNode(Node* node) {
Node* newInternalNode = new Node();
int middle = node->keys.size() / 2;
int middleKey = node->keys[middle];
newInternalNode->keys.assign(node->keys.begin() + middle + 1, node->keys.end());
newInternalNode->children.assign(node->children.begin() + middle + 1, node->children.end());
node->keys.erase(node->keys.begin() + middle, node->keys.end());
node->children.erase(node->children.begin() + middle + 1, node->children.end());
insertIntoParent(node, middleKey, newInternalNode);
}
};
int main() {
BPlusTree bpt;
// Inserting keys
bpt.insert(5);
bpt.insert(3);
bpt.insert(7);
bpt.insert(1);
bpt.insert(4);
bpt.insert(6);
bpt.insert(8);
// Perform any additional operations or print the tree structure as needed
return 0;
}
Demonstration
Insertion on a B+ Tree-DevsEnv