B-Trees
A B-Tree is a self-balancing search tree designed for systems that read and write large blocks of data, like databases and file systems.
How a B-Tree Works
A B-Tree is a “fat” search tree designed to handle massive amounts of data. Unlike a binary tree where nodes only have one key and two children, a B-Tree node can hold multiple keys and have many children.
- Self-Balancing: It automatically keeps itself perfectly balanced. All leaf nodes (the bottom of the tree) are always on the exact same level.
- Disk-Optimized: It is built to minimize slow disk reads by packing as much data into a single node (or “block”) as possible, reading huge chunks of data at once rather than node-by-node.
Real-Life Examples
- A Library Filing Cabinet: Instead of choosing between just “left” or “right,” you open a drawer containing files “A through G.” Inside, you find folders splitting the data further, drastically reducing the number of steps to find a single paper among thousands.
Technical Applications
- Databases: Both SQL and NoSQL databases heavily rely on B-Trees (specifically a variation called B+ Trees) to build their indexes, allowing them to instantly locate a specific row among millions without scanning the whole table.
- File Systems: Operating systems (like Windows NTFS or Linux Ext4) use B-Trees to quickly look up where exactly a file’s data is physically stored on your hard drive.
Time and Space Complexity
- Time Complexity: O(log n) for searching, inserting, and deleting. The tree is exceptionally shallow and wide, meaning it takes very few steps to reach the bottom.
- Space Complexity: O(n) Memory scales with the amount of data stored.
Properties of B-Tree of order M
- Every node has at most M children
- Every non-leaf node (except root) has at least ⌈M/2⌉ children
- The root has at least 2 children (if it’s not a leaf)
- All leaves are at the same level
- A non-leaf node with k children contains k-1 keys
B-Tree Implementation (Order 3)
Code Example:
Java
import java.util.*;
// B-Tree Node
class BTreeNode {
List<Integer> keys = new ArrayList<>(); // keys in node
List<BTreeNode> children = new ArrayList<>(); // child pointers
int t; // minimum degree
boolean leaf; // true if leaf node
BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
}
// Traverse all nodes
void traverse() {
int i;
for (i = 0; i < keys.size(); i++) {
if (!leaf)
children.get(i).traverse();
System.out.print(keys.get(i) + " ");
}
if (!leaf)
children.get(i).traverse();
}
// Search key
BTreeNode search(int key) {
int i = 0;
while (i < keys.size() && key > keys.get(i))
i++;
if (i < keys.size() && keys.get(i) == key)
return this;
if (leaf)
return null;
return children.get(i).search(key);
}
// Insert into non-full node
void insertNonFull(int key) {
int i = keys.size() - 1;
if (leaf) {
keys.add(0);
while (i >= 0 && keys.get(i) > key) {
keys.set(i + 1, keys.get(i));
i--;
}
keys.set(i + 1, key);
}
else {
while (i >= 0 && keys.get(i) > key)
i--;
if (children.get(i + 1).keys.size() == 2 * t - 1) {
splitChild(i + 1, children.get(i + 1));
if (keys.get(i + 1) < key)
i++;
}
children.get(i + 1).insertNonFull(key);
}
}
// Split child node
void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.t, y.leaf);
for (int j = 0; j < t - 1; j++)
z.keys.add(y.keys.get(j + t));
if (!y.leaf)
for (int j = 0; j < t; j++)
z.children.add(y.children.get(j + t));
y.keys.subList(t, y.keys.size()).clear();
if (!y.leaf)
y.children.subList(t, y.children.size()).clear();
children.add(i + 1, z);
keys.add(i, y.keys.remove(t - 1));
}
}
// B-Tree
class BTree {
BTreeNode root;
int t;
BTree(int t) {
this.t = t;
root = null;
}
// Traverse tree
void traverse() {
if (root != null)
root.traverse();
System.out.println();
}
// Search key
BTreeNode search(int key) {
if (root == null)
return null;
return root.search(key);
}
// Insert key
void insert(int key) {
if (root == null) {
root = new BTreeNode(t, true);
root.keys.add(key);
return;
}
if (root.keys.size() == 2 * t - 1) {
BTreeNode s = new BTreeNode(t, false);
s.children.add(root);
s.splitChild(0, root);
int i = 0;
if (s.keys.get(0) < key)
i++;
s.children.get(i).insertNonFull(key);
root = s;
}
else
root.insertNonFull(key);
}
// Demo
public static void main(String[] args) {
BTree tree = new BTree(3);
System.out.println("Insert: 10 20 5 6 12 30 7 17");
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.insert(6);
tree.insert(12);
tree.insert(30);
tree.insert(7);
tree.insert(17);
System.out.println("Traversal:");
tree.traverse();
int key = 6;
System.out.println("Search " + key + ": " +
(tree.search(key) != null ? "Found" : "Not Found"));
key = 15;
System.out.println("Search " + key + ": " +
(tree.search(key) != null ? "Found" : "Not Found"));
}
}