B-Tree: Self-Balancing Engine Of Modern Database

Imagine you are the librarian of the world’s largest library - billions of books, organized across thousands of shelves. A binary search tree forces you to check one shelf at a time, left or right, all the way down a potentially enormous staircase. Now imagine instead that each shelf can hold dozens of lables, pointing you to one of dozens of sub-sections in a single glance. You reach the right book in just a few steps, no matter how vast the collection.

That is exactly the idea behind m-Way Search Tree and its well-disciplined sibling, the B-Tree - the backbone of virtually every database and filesystem you have ever used. This post walks through both structures from first principles, complete with the algorithms and C++ code you need to truly understand them.

1. The m-Way Search Tree

What is an m-Way Search Tree?

A Binary Search Tree (BST) allows each node to hold exactly one key and branch into at most two children. An m-Way Search Tree (also written m-way tree) generalises this idea: each node can hold up to $m - 1$ keys and branch into up to $m$ children. The formal definition is:

An m-way search tree is a search tree where every node has at most $m - 1$ keys (stored in ascending order) and at most $m$ children (subtrees), some of which may be empty.

For a node containing $k$ keys ${v_1, v_2, \ldots, v_k}$, there are exactly $k+1$ subtrees ${T_1, T_2, \ldots, T_{k+1}}$ satisfying the classic BST ordering constraint extended to multiple keys:

\[T_1 < v_1 < T_2 < v_2 < \cdots < v_k < T_{k+1}\]

More precisely:

Subtree	Key range
$T_1$	$(-\infty,\ v_1)$
$T_i$ for $2 \leq i \leq k$	$(v_{i-1},\ v_i)$
$T_{k+1}$	$(v_k,\ +\infty)$

A Concrete Example:

Operations on m-Way Search Tree

Traversal

An m-way tree can be traversed using standard graph-traversal strategies:

Depth-First Traversal (DFT): visit a node, then recursively visits each child. An in-order variant (visit left subtree → key → next subtree → next key → …) produces keys in sorted order, exactly like a BST in-order traversal.

Breadth-First Traversal (BFT): uses a queue to visit nodes level by level, useful for printing the tree structure.

Searching

Searching follows the same top-down logic as in a BST, extended to multiple keys per node:

1. Start at the root.
2. At each node, compare the target key $k$ against the sorted keys $v_1 < v_2 < \cdots < v_n$ (binary search can be used here).
3. If $k = v_i$ for some $i$, the search succeeds.
4. Otherwise, determine which subtree $T_i$ could contain $k$ based on the intervals above, and recurse.
5. If a null (empty) subtree is reached, $k$ is not in the tree.

/* Simple recursive search in an m-way search tree.
   Each node stores m - 1 keys and m child pointers. */
#include <iostream>
#define M 5

struct mWayNode {
  int count;                  // Current number of keys in this node
  int keys[M - 1];            // Array holding up to M - 1 sorted keys
  struct mWayNode *child[M];  // Array of raw pointers to M children
};

/* Returns the node containing key k, or nullptr if not found. */
mWayNode* mway_search(mWayNode* root, int target) {
  if (root == nullptr) return nullptr;
  int i = 0;
  // Find the first key >= target
  while (i < root->count && target > root->keys[i]) {
    i++;
  }
  if (i < root->count && target == root->keys[i]) {
    return root; // Found
  }
  return mway_search(root->child[i], target);
}

Insertion

Insertion into an m-way tree is straightforward but does not enforce balance:

1. Search for the key until an empty subtree is encountered.
2. If the parent node of that empty subtree still has room (fewer than $m - 1$ keys), insert the key directly to it.
3. Otherwise, create a new leaf node and attach it as a child.

The critical weakness here is that a naive m-way tree can degrade into a linked list if keys are inserted in sorted order - exactly like an unbalanced BST. This is the problem that B-Tree solves.

Deletion

Deletion from an m-way tree mirrors BST deletion:

• If the key $v$ is between two empty child pointers, delete it directly.
• If $v$ has non-empty subtrees, replace it with either the in-order predecessor (largest key in its left subtree) or the in-order successor (smallest key in its right subtree), then recursively delete that replacement key from the subtree.

2. The B-Tree - Discipline Balance

Problems with Plain m-Way Trees

An m-way Tree gives us breadth, but no height guarantee. In the worst case it is as tall as a linked list: $O(n)$ height and $O(n)$ search time. For a database storing millions of records on disk every level traversal may cost a costly disk I/O. We need a structure that stays short no matter what.

Enter the B-Tree, invented by Rudolf Bayer and Edward M. McCreight in 1972. A B-Tree is an m-Way Search Tree with strict rules that guarantee balance at all times.

Formal Definition

A B-Tree of order $m$ ($m > 2$) is an m-Way Search Tree satisfying:

1. The root has at least 1 key (at at least 2 chilldren if it is not a leaf).
2. Every non-root node has at least $\left\lfloor \dfrac{m-1}{2} \right\rfloor$ keys.
3. Every non-root internal node has at least $\left\lceil \dfrac{m}{2} \right\rceil$ children.
4. All leaf nodes are at the same depth (height).
5. Each node has at most $m - 1$ keys and at most $m$ children.

Following is an example of a B-Tree of order 4:

We can see in the above diagram that all the leaf nodes are at the same level and all non-leaf nodes have no empty sub-tree and have number of keys one less than the number of their children.

Notation and Common Variants

Name	Notation	Min keys (non-root)	Max keys	Max children
B-Tree of order 3	(2,3)-tree / 2-3 tree	1	2	3
B-Tree of order 4	(2,4)-tree / 2-3-4 tree	1	3	4
B-Tree of order $m$	$(\lceil m/2 \rceil, m)$-tree	$\lfloor(m-1)/2\rfloor$	$m-1$	$m$

Height Bound

The height of a B-Tree with $n$ keys and order $m$ satisfies:

\[h \leq \log_{\lceil m/2 \rceil} \left\lfloor \frac{n+1}{2} \right\rfloor\]

This is an extraordinarily slow-growing function. A B-Tree of order 1001 (typical for a disk-based databases with 4 KB blocks) storing one billion keys has height at most 3. Three disk reads to find any record in a billion-record database - that is the power of the B-Tree.

3. B-Tree Operations in Depth

Searching

Search in B-Tree is identical to search in an m-way tree, described above. Because the tree is guaranteed to have height $O(\log n)$, the search complexity is always:

Case	Time
Best	$O(\log n)$
Average	$O(\log n)$
Worst	$O(\log n)$

Insertion

Insertion always targets a leaf node. The key invariant: a node must never exceed $m - 1$ keys. If inserting into a full leaf would violate this, the ndoe is split before insertion proceeds.

The Split Operation

When a node overflows (has $m$ keys after insertion), it is split into two nodes around its median key:

• Left node: keys to the left of the median.
• Right node: keys to the right of the median.
• Median key: promoted up to the parent node.

If the parent also overflows, the split propagates upward recursively. If the root splits, a new root is created - this is the only way a B-Tree grows taller.

Worked Example: Inserting 21 into a 3-Way B-Tree

Starting state (order-3 B-Tree, max 2 keys per node):

Deletion

Deletion from a B-Tree is the most complex operation because it must handle two distinct scenarios: the key lives in a leaf node, or in an internal node.

The Two Rebalancing Cases After Deletion

When a node loses a key and drops below the minimum key count ($\lfloor(m-1)/2\rfloor$), one of two fixes is applied:

Case 1: Borrow from a sibling (Rotation): If an adjacent sibling node has more than the minimum number of keys, we can borrow one:

• Promote the sibling’s key closest to the separator into the parent.
• Demote the parent’s seperator key down into the deficient node.

Case 2: Merge nodes: If no sibling has a spare key, merge the deficient node $N$, the parent separator key $p$, and an adjacent sibling $L$ into single node:

\[\{L_1, \ldots, L_s,\ p,\ N_1, \ldots, N_t\}\]

Then remove $p$ from the parent. If this causes the parent to underflow, propagate the fix upward recursively. If the root is emptied by this process, the tree’s height decreases by one.

Before:    [...| p |...]          After:       [...  ...]
          /             \                           |
    [L1...Ls]       [N1...Nt]           [L1...Ls | p | N1...Nt]

Deletion of a Key from an Internal Node

When the target koey $k$ is in an internal node, it cannot simply be removed (it is a separator for children). The standard approach:

1. Find the in-order predecessor (the largest key in the left subtree of $k$) or the in-order successor (the smallest key in the right subtree of $k$).
2. Copy that predecessor/successor into the position of $k$.
3. Recursively delete the predecessor/successor from the appropriate leaf node.

This reduces the problem to leaf deletion, which is handled by the borrow or merge cases above.

Worked Example: Deleting 26 from a 3-Way B-Tree:

4. Complexity Analysis

All three core operations in a B-Tree share the same asymptotic behavior because the height $h$ of the tree is logarithmically bounded:

\[h \leq \log_{\lceil m/2 \rceil} \left\lfloor \frac{n+1}{2} \right\rfloor = O(\log n)\]

At each level, scanning keys within a node takes $O(m)$ time (or $O(\log m)$ with binary search). Since $m$ is a fixed constant (determined by the disk block size), the per-level work is $O(1)$ in terms of $n$.

Operation	Best	Average	Worst	Notes
Search	$O(\log n)$	$O(\log n)$	$O(\log n)$	Height-bounded
Insert	$O(\log n)$	$O(\log n)$	$O(\log n)$	Splits propagate upward at most $h$ times
Delete	$O(\log n)$	$O(\log n)$	$O(\log n)$	Borrows/merges at most $h$ levels
Traverse	$O(n)$	$O(n)$	$O(n)$	Must visit every key
Space	$O(n)$	$O(n)$	$O(n)$	Each node stores $O(m)$ keys

The $O(n)$ space complexity follows because each of the $n$ keys is stored in exactly one node, and each node stores at most $m - 1$ keys and $m$ child pointers.

5. Real-World Applications

The B-Tree is arguably the most impactful data structure ever deployed in production systems:

Relational Databases (MySQL InnoDB, PostgreSQL): Primary and secondary indexes are almost universally implemented as B-Trees or their derivative, the B+ Tree (where all data records are stored in the leaves and internal nodes hold only routing keys). This layout maximises disk-blocks utilisation during range queries.

Filesystems (NTFS, HFS+, ext4 with HTree): Directory entries are indexed using B-Trees, enabling rapid file lookup in directories containing hundreds of thousands of files.

Key-Value Stores (LMDB, BoltDB): These embed a B-Tree into a memory-mapped file for persistent, ACID-compliant storage with $O(\log n)$ read and write performance.

Operating System Virtual Memory: Some OS kernels use B-Trees to manage virtual memory areas (VMAs), allowing efficient lookup of memory-mapped regions.

❮ ❯