B-Tree / B+ Tree from Scratch (2026)
A B-Tree is a self-balancing multi-way search tree designed for block-oriented storage like databases and file systems. Each node can contain multiple keys (up to 2t−1 where t is the minimum degree) and have up to 2t children. B-Trees minimize disk I/O by keeping nodes wide and shallow, with height typically under 4 for millions of records.
The B+ Tree variant stores all actual data in the leaves, while internal nodes act as pure routing indexes. Leaf nodes are linked together for efficient range scans. This makes B+ Trees the standard index structure in relational databases like MySQL, PostgreSQL, and SQLite.
B-Tree Insertion and Splitting
Insertions happen at leaf nodes. When a node becomes full (≥ 2t−1 keys), it splits into two nodes of t−1 keys each, and the middle key moves up to the parent. This splitting can propagate upward, and if the root splits, a new root is created, increasing tree height.
void insertNonFull(Node* node, int key) {
int i = node->n - 1;
if (node->leaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i]; i--; }
node->keys[i + 1] = key; node->n++;
} else {
while (i >= 0 && key < node->keys[i]) i--; i++;
if (node->children[i]->n == 2 * t - 1) {
splitChild(node, i, node->children[i]);
if (key > node->keys[i]) i++;
}
insertNonFull(node->children[i], key);
}
}B+ Tree Structure
In a B+ Tree, internal nodes store only keys for routing. All data records reside in leaf nodes, which are linked in a linked list. Range queries become fast sequential scans across leaf pages. Deletion may require merging sibling nodes when underflow occurs.
# Python: B+ Tree node skeleton
class BPlusNode:
def __init__(self, is_leaf=False):
self.is_leaf = is_leaf
self.keys = []
self.children = [] # pointers for internal; values for leaf
self.next = None # linked list for leaf nodesFrequently Asked Questions
What is the minimum degree t in a B-Tree?
The minimum degree t defines the range of keys per node: every node (except root) must have at least t−1 keys and at most 2t−1 keys. Typical values of t range from 50 to 2000 for disk-based trees.
Why are B+ Trees preferred for databases over B-Trees?
B+ Trees store all data in leaves with linked list connections, enabling efficient range queries with sequential I/O. Internal nodes are pure index, allowing more keys per page and reducing tree height.
Originally published on Ayodhyyya. Last updated June 1, 2026.