Java Program to Implement B+ Tree
The B+ tree is a self-balancing tree data structure commonly used in database and file systems applications. It is an extension of B-Tree and maintains sorted data in a manner that allows us for efficient insertion, deletion and search operations. The B+Trees stores all data in a leaf node while internal nodes only store keys that act as separators.
Organization of the B+ Tree
- All leaf nodes are at the same level
- Internal nodes contain keys that direct the search to the appropriate child node
- Leaf nodes contain actual data and are linked together sequentially for easier traversal
- Each node has a defined minimum and maximum number of children or keys, ensuring balance
[20, 40]
/ | \
[10, 15] [25, 30] [45, 50]
Here, the root node has two keys (20, 40), guiding where to look. The leaves contain the actual data and are linked, allowing in-order traversal.
Implementation of B+ Tree
Implementing a B+ Tree in Java involves creating classes for nodes and the tree itself. The node class would contain references to child nodes and, in the case of leaves, links to the next leaf for traversal.
- Create a class B+Tree Node to represent a node in the tree
- Create a class B+Tree to represent the B+ Tree itself, handling insertions, deletions, and searches.
- Implement insertion logic such that when a node overflows it splits
- Implement deletion logic such that when a node underflows, it borrows from siblings or merges nodes
Basic Operations in a B+ Tree:
Operation | Description | Time Complexity |
|---|---|---|
Insertion | Find the appropriate leaf node, insert the data, and manage any required splits | O(log n) |
Deletion | Find the node with the data, remove it, and re-balance if necessary | O(log n) |
Search | Traverse internal nodes based on keys until reaching the appropriate leaf node, then search within the leaf. | O(log n) |
Java Program to Implement B+ Tree
Here is a simplified Java implementation of a B+ Tree, focusing on insertions, searches, and basic re-balancing:
// Java Program to Implement B+ Tree
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// B+ Tree Node class to represent
// internal and leaf nodes
class BPlusTreeNode {
// True for leaf nodes, False for internal nodes
boolean isLeaf;
// The keys stored in this node
List<Integer> keys;
// Children nodes (for internal nodes)
List<BPlusTreeNode> children;
// Link to the next leaf node
BPlusTreeNode next;
// Constructor to initialize a node
public BPlusTreeNode(boolean isLeaf) {
this.isLeaf = isLeaf;
this.keys = new ArrayList<>();
this.children = new ArrayList<>();
this.next = null;
}
}
// B+ Tree class with basic operations: insert and search
class BPlusTree {
// Root node of the tree
private BPlusTreeNode root;
// Maximum number of keys per node
private final int order;
// Constructor to initialize the B+ Tree
public BPlusTree(int order) {
if (order < 3) {
throw new IllegalArgumentException("Order must be at least 3");
}
this.root = new BPlusTreeNode(true);
this.order = order;
}
// Find the appropriate leaf node for insertion
private BPlusTreeNode findLeaf(int key) {
BPlusTreeNode node = root;
while (!node.isLeaf) {
int i = 0;
while (i < node.keys.size() && key >= node.keys.get(i)) {
i++;
}
node = node.children.get(i);
}
return node;
}
// Insert a key into the B+ Tree
public void insert(int key) {
BPlusTreeNode leaf = findLeaf(key);
insertIntoLeaf(leaf, key);
// Split the leaf node if it exceeds the order
if (leaf.keys.size() > order - 1) {
splitLeaf(leaf);
}
}
// Insert into the leaf node
private void insertIntoLeaf(BPlusTreeNode leaf, int key) {
int pos = Collections.binarySearch(leaf.keys, key);
if (pos < 0) {
pos = -(pos + 1);
}
leaf.keys.add(pos, key);
}
// Split a leaf node and update parent nodes
private void splitLeaf(BPlusTreeNode leaf) {
int mid = (order + 1) / 2;
BPlusTreeNode newLeaf = new BPlusTreeNode(true);
// Move half the keys to the new leaf node
newLeaf.keys.addAll(leaf.keys.subList(mid, leaf.keys.size()));
leaf.keys.subList(mid, leaf.keys.size()).clear();
newLeaf.next = leaf.next;
leaf.next = newLeaf;
// If the root splits, create a new root
if (leaf == root) {
BPlusTreeNode newRoot = new BPlusTreeNode(false);
newRoot.keys.add(newLeaf.keys.get(0));
newRoot.children.add(leaf);
newRoot.children.add(newLeaf);
root = newRoot;
} else {
insertIntoParent(leaf, newLeaf, newLeaf.keys.get(0));
}
}
// Insert into the parent node after a leaf split
private void insertIntoParent(BPlusTreeNode left, BPlusTreeNode right, int key) {
BPlusTreeNode parent = findParent(root, left);
if (parent == null) {
throw new RuntimeException("Parent node not found for insertion");
}
int pos = Collections.binarySearch(parent.keys, key);
if (pos < 0) {
pos = -(pos + 1);
}
parent.keys.add(pos, key);
parent.children.add(pos + 1, right);
// Split the internal node if it exceeds the order
if (parent.keys.size() > order - 1) {
splitInternal(parent);
}
}
// Split an internal node
private void splitInternal(BPlusTreeNode internal) {
int mid = (order + 1) / 2;
BPlusTreeNode newInternal = new BPlusTreeNode(false);
// Move half the keys to the new internal node
newInternal.keys.addAll(internal.keys.subList(mid + 1, internal.keys.size()));
internal.keys.subList(mid, internal.keys.size()).clear();
// Move half the children to the new internal node
newInternal.children.addAll(internal.children.subList(mid + 1, internal.children.size()));
internal.children.subList(mid + 1, internal.children.size()).clear();
// If the root splits, create a new root
if (internal == root) {
BPlusTreeNode newRoot = new BPlusTreeNode(false);
newRoot.keys.add(internal.keys.get(mid));
newRoot.children.add(internal);
newRoot.children.add(newInternal);
root = newRoot;
} else {
insertIntoParent(internal, newInternal, internal.keys.remove(mid));
}
}
// Find the parent node of a given node
private BPlusTreeNode findParent(BPlusTreeNode current, BPlusTreeNode target) {
if (current.isLeaf || current.children.isEmpty()) {
return null;
}
for (int i = 0; i < current.children.size(); i++) {
BPlusTreeNode child = current.children.get(i);
if (child == target) {
// Parent found
return current;
}
BPlusTreeNode possibleParent = findParent(child, target);
if (possibleParent != null) {
return possibleParent;
}
}
// Parent not found
return null;
}
// Search for a key in the B+ Tree
public boolean search(int key) {
BPlusTreeNode node = findLeaf(key);
int pos = Collections.binarySearch(node.keys, key);
return pos >= 0;
}
// Display the Tree (for debugging purposes)
public void printTree() {
printNode(root, 0);
}
private void printNode(BPlusTreeNode node, int level) {
System.out.println("Level " + level + ": " + node.keys);
if (!node.isLeaf) {
for (BPlusTreeNode child : node.children) {
printNode(child, level + 1);
}
}
}
}
// Main class with example usage
public class Main {
public static void main(String[] args) {
BPlusTree tree = new BPlusTree(3);
// Insert keys into the B+ Tree
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(60);
// Print the B+ Tree structure
System.out.println("Tree after insertion:");
tree.printTree();
// Search for keys in the B+ Tree
System.out.println("Search for 30: " + tree.search(30)); // True
System.out.println("Search for 25: " + tree.search(25)); // False
}
}
Output
Tree after insertion: Level 0: [30, 50] Level 1: [10, 20] Level 1: [30, 40] Level 1: [50, 60] Search for 30: true Search for 25: false
Below is the explanation of the above program:
- Provides a basic structure for B+ Tree with insertion and search operations
- Handles leaf and internal splits with re-balancing logic
- Includes a print Tree method to visualize the tree structure
Applications of B+ Tree
- B+ Trees are widely used in applications that require efficient indexing and fast retrieval, including
- Database indexing for relational databases
- File system structures where efficient search, insertion, and deletion are critical
- Applications requiring ordered data with range queries, like in-memory databases or caches