Algorithm
A B+ tree (B-plus tree) is a self-balancing tree data structure that maintains sorted data and allows searches, insertions, deletions, and sequential access in logarithmic time. B+ trees are particularly well-suited for storing and managing large amounts of data on disk or in other secondary storage devices. They are commonly used in databases and file systems.
Here are some key features and characteristics of B+ trees:
-
Balanced Structure: B+ trees are balanced, meaning that the height of the tree remains relatively constant even as data is inserted or deleted. This ensures that operations like search, insert, and delete have logarithmic time complexity.
-
Node Structure: The internal nodes of a B+ tree contain key values that act as separators, guiding the search process. Leaf nodes, on the other hand, contain actual data entries sorted in order. Each leaf node is linked to its neighboring leaf nodes, facilitating sequential access.
-
Sequential Access: B+ trees support efficient range queries and sequential access to data due to the linked structure of leaf nodes. This makes B+ trees particularly well-suited for applications that involve range queries, such as retrieving a range of values from a database.
-
Ordered Keys: Keys in a B+ tree are stored in sorted order, making range queries and searches more efficient. This ordered structure is maintained as keys are inserted or deleted.
-
Insertion and Deletion: When a new key is inserted or an existing key is deleted, the tree is rebalanced to maintain its properties. This involves redistributing keys among nodes and potentially splitting or merging nodes.
-
Internal Nodes vs. Leaf Nodes: Internal nodes contain keys that guide the search process, but they do not store the actual data. The data is stored in the leaf nodes, which are linked together to allow for sequential access.
-
Degree: B+ trees have a parameter known as the degree or order, denoted as B. The maximum number of children a node can have is 2B, and the minimum is B.
-
Efficient for Disk Storage: B+ trees are well-suited for use in databases and file systems that store large amounts of data on disk. The design of B+ trees minimizes disk I/O operations, as the tree structure allows for efficient retrieval of data.
B+ trees are widely used in database management systems to implement indexes, ensuring fast retrieval of data while minimizing disk I/O. Their balanced structure and sequential access properties make them efficient for a variety of applications where data needs to be stored, retrieved, and searched efficiently.
Code Examples
#1 B+ Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, is_leaf=True):
self.is_leaf = is_leaf
self.keys = []
self.children = []
class BPlusTree:
def __init__(self, order):
self.root = Node()
self.order = order
def search(self, key, node=None):
node = node or self.root
if node.is_leaf:
for i, k in enumerate(node.keys):
if key == k:
return True
return False
else:
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
return self.search(key, node.children[i])
def insert(self, key):
if self.search(key):
print(f"Key {key} already exists in the B+ tree.")
return
if len(self.root.keys) == (2 * self.order - 1):
new_root = Node(is_leaf=False)
new_root.children.append(self.root)
self.split(new_root, 0)
self.root = new_root
self._insert(self.root, key)
def _insert(self, node, key):
if node.is_leaf:
node.keys.append(key)
node.keys.sort()
else:
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if len(node.children[i].keys) == (2 * self.order - 1):
self.split(node, i)
if key > node.keys[i]:
i += 1
self._insert(node.children[i], key)
def split(self, parent, index):
new_node = Node(is_leaf=parent.children[index].is_leaf)
split_index = self.order - 1
new_node.keys = parent.children[index].keys[split_index + 1:]
parent.children[index].keys = parent.children[index].keys[:split_index]
if not parent.children[index].is_leaf:
new_node.children = parent.children[index].children[split_index + 1:]
parent.children[index].children = parent.children[index].children[:split_index + 1]
parent.keys.insert(index, parent.children[index].keys[split_index])
parent.children.insert(index + 1, new_node)
def display(self, node=None, level=0):
node = node or self.root
print(f"Level {level}:", node.keys)
if not node.is_leaf:
for child in node.children:
self.display(child, level + 1)
# Example usage:
bplus_tree = BPlusTree(order=3)
keys_to_insert = [3, 7, 11, 2, 5, 8, 12, 1, 4, 6, 9, 10]
for key in keys_to_insert:
bplus_tree.insert(key)
bplus_tree.display()
#2 B+ Tree implement in Java
Code -
Java Programming
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class BPlusTree {
private Node root;
private int order; // Order of the tree
// Constructor
public BPlusTree(int order) {
this.root = null;
this.order = order;
}
// Search operation
public String search(int key) {
return search(root, key);
}
private String search(Node node, int key) {
if (node == null) {
return "Key not found";
}
if (node.isLeafNode()) {
LeafNode leafNode = (LeafNode) node;
return leafNode.getValue(key);
}
InternalNode internalNode = (InternalNode) node;
int index = internalNode.findIndex(key);
return search(internalNode.getChild(index), key);
}
// Insert operation
public void insert(int key, String value) {
if (root == null) {
root = new LeafNode(key, value);
} else {
Pair pair = insert(root, key, value);
if (pair != null) {
InternalNode newRoot = new InternalNode(pair.key, root, pair.node);
root = newRoot;
}
}
}
private Pair insert(Node node, int key, String value) {
if (node.isLeafNode()) {
LeafNode leafNode = (LeafNode) node;
return leafNode.insert(key, value);
}
InternalNode internalNode = (InternalNode) node;
int index = internalNode.findIndex(key);
Pair pair = insert(internalNode.getChild(index), key, value);
if (pair == null) {
return null;
}
if (internalNode.isFull()) {
return internalNode.split(pair);
} else {
internalNode.insert(pair.key, pair.node);
return null;
}
}
// Node interface
private interface Node {
boolean isLeafNode();
boolean isFull();
Node getChild(int index);
}
// Leaf node
private class LeafNode implements Node {
private List < Integer> keys;
private List values;
private LeafNode next;
public LeafNode(int key, String value) {
keys = new ArrayList < >();
values = new ArrayList<>();
keys.add(key);
values.add(value);
next = null;
}
public boolean isLeafNode() {
return true;
}
public boolean isFull() {
return keys.size() == order;
}
public Node getChild(int index) {
return null;
}
public String getValue(int key) {
int index = keys.indexOf(key);
return index != -1 ? values.get(index) : "Key not found";
}
public Pair insert(int key, String value) {
int index = 0;
while (index < keys.size() && keys.get(index) < key) {
index++;
}
keys.add(index, key);
values.add(index, value);
if (isFull()) {
LeafNode newLeaf = split();
return new Pair(newLeaf.keys.get(0), newLeaf);
} else {
return null;
}
}
private LeafNode split() {
int from = keys.size() / 2;
int to = keys.size();
LeafNode newLeaf = new LeafNode(keys.get(from), values.get(from));
newLeaf.keys.addAll(keys.subList(from, to));
newLeaf.values.addAll(values.subList(from, to));
keys.subList(from, to).clear();
values.subList(from, to).clear();
newLeaf.next = next;
next = newLeaf;
return newLeaf;
}
}
// Internal node
private class InternalNode implements Node {
private List < Integer> keys;
private List children;
public InternalNode(int key, Node leftChild, Node rightChild) {
keys = new ArrayList < >();
children = new ArrayList<>();
keys.add(key);
children.add(leftChild);
children.add(rightChild);
}
public boolean isLeafNode() {
return false;
}
public boolean isFull() {
return keys.size() == order - 1;
}
public Node getChild(int index) {
return children.get(index);
}
public int findIndex(int key) {
int index = 0;
while (index < keys.size() && keys.get(index) < key) {
index++;
}
return index;
}
public void insert(int key, Node child) {
int index = findIndex(key);
keys.add(index, key);
children.add(index + 1, child);
}
public Pair split(Pair pair) {
int from = (keys.size() + 1) / 2;
int to = keys.size();
InternalNode newInternal = new InternalNode(keys.get(from - 1),
children.get(from - 1), pair.node);
newInternal.keys.addAll(keys.subList(from, to));
newInternal.children.addAll(children.subList(from, to + 1));
keys.subList(from - 1, to).clear();
children.subList(from - 1, to + 1).clear();
return new Pair(keys.get(from - 1), newInternal);
}
}
// Helper class to return a pair of key and node
private static class Pair {
private int key;
private Node node;
public Pair(int key, Node node) {
this.key = key;
this.node = node;
}
}
}
public class Main {
public static void main(String[] args) {
BPlusTree bPlusTree = new BPlusTree(3);
// Insert key-value pairs
bPlusTree.insert(1, "One");
bPlusTree.insert(2, "Two");
bPlusTree.insert(3, "Three");
bPlusTree.insert(4, "Four");
bPlusTree.insert(5, "Five");
// Search for keys
System.out.println("Search key 3: " + bPlusTree.search(3));
System.out.println("Search key 6: " + bPlusTree.search(6));
}
}
#3 B+ Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#define ORDER 4
typedef struct Node {
int is_leaf;
int num_keys;
int keys[ORDER - 1];
struct Node* children[ORDER];
struct Node* next;
} Node;
Node* create_node() {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->is_leaf = 1;
new_node->num_keys = 0;
new_node->next = NULL;
for (int i = 0; i < ORDER - 1; i++) {
new_node->keys[i] = 0;
new_node->children[i] = NULL;
}
new_node->children[ORDER - 1] = NULL;
return new_node;
}
Node* insert(Node* root, int key) {
if (root == NULL) {
Node* new_node = create_node();
new_node->keys[0] = key;
new_node->num_keys = 1;
return new_node;
}
if (root->is_leaf) {
int i = root->num_keys - 1;
while (i >= 0 && key < root->keys[i]) {
root->keys[i + 1] = root->keys[i];
i--;
}
root->keys[i + 1] = key;
root->num_keys++;
} else {
int i = root->num_keys - 1;
while (i >= 0 && key < root->keys[i]) {
i--;
}
i++;
Node* new_child = insert(root->children[i], key);
if (new_child != root->children[i]) {
int j = root->num_keys - 1;
while (j >= i) {
root->keys[j + 1] = root->keys[j];
root->children[j + 2] = root->children[j + 1];
j--;
}
root->keys[i] = new_child->keys[0];
root->children[i + 1] = new_child;
root->num_keys++;
}
}
if (root->num_keys >= ORDER - 1) {
// Split the node
Node* new_root = create_node();
new_root->is_leaf = 0;
new_root->children[0] = root;
root = new_root;
}
return root;
}
void print_tree(Node* root) {
if (root != NULL) {
for (int i = 0; i < root->num_keys; i++) {
printf("%d ", root->keys[i]);
}
printf("\n");
if (!root->is_leaf) {
for (int i = 0; i < = root->num_keys; i++) {
print_tree(root->children[i]);
}
}
}
}
int main() {
Node* root = NULL;
// Insert keys into the B+ tree
int keys[] = {3, 8, 1, 4, 6, 2, 10, 12, 7, 5};
int num_keys = sizeof(keys) / sizeof(keys[0]);
for (int i = 0; i < num_keys; i++) {
root = insert(root, keys[i]);
}
// Print the B+ tree
printf("B+ Tree:\n");
print_tree(root);
return 0;
}
#4 B+ Tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
const int ORDER = 3; // B+ tree order
// Node class representing a B+ tree node
template < typename T>
class Node {
public:
bool isLeaf;
vector<T> keys;
Node < T>* parent;
vector<Node*> children;
Node() {
isLeaf = true;
parent = nullptr;
}
};
// BPlusTree class
template < typename T>
class BPlusTree {
public:
Node* root;
BPlusTree() {
root = nullptr;
}
// Function to insert a key into the B+ tree
void insert(T key) {
if (!root) {
root = new Node < T>();
root->keys.push_back(key);
} else {
Node < T>* current = findLeafNode(key, root);
// Insert the key into the node
insertIntoNode(current, key);
// Split the node if necessary
while (current->keys.size() >= ORDER) {
current = splitNode(current);
}
}
}
// Function to search for a key in the B+ tree
bool search(T key) {
Node < T>* leaf = findLeafNode(key, root);
for (T k : leaf->keys) {
if (k == key) {
return true;
}
}
return false;
}
// Function to display the B+ tree (inorder traversal)
void display() {
display(root);
cout << endl;
}
private:
// Function to find the leaf node where a key should be inserted
Node < T>* findLeafNode(T key, Node* current) {
if (current->isLeaf) {
return current;
} else {
int i = 0;
while (i < current->keys.size() && key > current->keys[i]) {
i++;
}
return findLeafNode(key, current->children[i]);
}
}
// Function to insert a key into a non-leaf node
void insertIntoNode(Node < T>* node, T key) {
int i = 0;
while (i < node->keys.size() && key > node->keys[i]) {
i++;
}
node->keys.insert(node->keys.begin() + i, key);
}
// Function to split a node into two nodes
Node < T>* splitNode(Node* node) {
Node* new_node = new Node();
int split_index = node->keys.size() / 2;
// Move half of the keys to the new node
new_node->keys.insert(new_node->keys.begin(),
node->keys.begin() + split_index,
node->keys.end());
node->keys.erase(node->keys.begin() + split_index, node->keys.end());
// Update the parent pointers
new_node->parent = node->parent;
node->parent = new_node;
// Update the parent's children pointers
if (new_node->parent) {
int i = 0;
while (i < new_node->parent->keys.size() &&
new_node->keys[0] > new_node->parent->keys[i]) {
i++;
}
new_node->parent->children.insert(new_node->parent->children.begin() + i + 1, new_node);
}
// If the root is split, create a new root
if (node == root) {
Node < T>* new_root = new Node();
new_root->keys.push_back(new_node->keys[0]);
new_root->children.push_back(node);
new_root->children.push_back(new_node);
node->parent = new_root;
new_node->parent = new_root;
root = new_root;
}
return new_node;
}
// Function to display the B+ tree (inorder traversal)
void display(Node < T>* current) {
if (current) {
int i;
for (i = 0; i < current->keys.size(); i++) {
if (!current->isLeaf) {
display(current->children[i]);
}
cout << current->keys[i] << " ";
}
if (!current->isLeaf) {
display(current->children[i]);
}
}
}
};
int main() {
BPlusTree < int> tree;
// Insert keys into the B+ tree
tree.insert(3);
tree.insert(8);
tree.insert(2);
tree.insert(1);
tree.insert(6);
tree.insert(4);
tree.insert(5);
tree.insert(7);
// Display the B+ tree
cout << "B+ Tree: ";
tree.display();
// Search for keys in the B+ tree
cout << "Search for key 4: " << (tree.search(4) ? "Found" : "Not Found") << endl;
cout << "Search for key 9: " << (tree.search(9) ? "Found" : "Not Found") << endl;
return 0;
}
Demonstration
B+ Tree-DevsEnv