WikiGalaxy
Introduction to B-Trees
Definition
A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is commonly used in databases and file systems.
Properties
B-trees are characterized by their branching factor, which determines the number of children each node can have. They ensure that the tree remains balanced, with all leaf nodes at the same depth.
class BTree {
private int T;
private Node root;
class Node {
int[] keys;
int t;
Node[] children;
int n;
boolean leaf;
Node(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2*t-1];
this.children = new Node[2*t];
this.n = 0;
}
}
BTree(int t) {
this.T = t;
this.root = null;
}
}
Insertion
Insertion in a B-tree involves finding the appropriate leaf node where the key should be added, and then splitting nodes as necessary to maintain the tree's properties.
B-Tree Node Splitting
Splitting Nodes
When a node becomes full during insertion, it is split into two nodes, and the middle key is promoted to the parent node. This process ensures that the B-tree remains balanced.
void splitChild(Node parent, int i, Node fullChild) {
Node newNode = new Node(fullChild.t, fullChild.leaf);
newNode.n = t - 1;
for (int j = 0; j < t-1; j++)
newNode.keys[j] = fullChild.keys[j+t];
if (!fullChild.leaf) {
for (int j = 0; j < t; j++)
newNode.children[j] = fullChild.children[j+t];
}
fullChild.n = t - 1;
for (int j = parent.n; j >= i+1; j--)
parent.children[j+1] = parent.children[j];
parent.children[i+1] = newNode;
for (int j = parent.n-1; j >= i; j--)
parent.keys[j+1] = parent.keys[j];
parent.keys[i] = fullChild.keys[t-1];
parent.n++;
}
B-Tree Search Operation
Searching Keys
Searching in a B-tree is efficient due to its balanced structure. The search operation navigates from the root to the leaf, choosing the appropriate child pointer based on the key comparisons.
Node search(Node node, int key) {
int i = 0;
while (i < node.n && key > node.keys[i])
i++;
if (i < node.n && key == node.keys[i])
return node;
if (node.leaf)
return null;
return search(node.children[i], key);
}
Deletion in B-Trees
Deleting Keys
Deleting a key from a B-tree involves several cases, such as removing a key from a leaf, or from an internal node, which might require merging nodes to maintain balance.
// Pseudo code for deletion
void deleteKey(int key) {
// Implement deletion logic here
}
Applications of B-Trees
Use Cases
B-trees are widely used in database systems and file systems. They are particularly useful for indexing large amounts of data stored on disk, as they minimize disk I/O operations.
// Example of B-tree usage in databases
class DatabaseIndex {
BTree bTreeIndex;
DatabaseIndex(int order) {
bTreeIndex = new BTree(order);
}
void insertRecord(int key) {
// Insert record logic using B-tree
}
}
