B-Trees
A B-tree is a self-balancing tree data structure that maintains sorted data and guarantees O(log n) time for search, insertion, and deletion. Unlike Binary Search Trees, which store one key per node, B-trees store multiple keys per node and can have many children — a high branching factor that dramatically reduces tree height, making them ideal for disk-based storage systems where minimizing I/O operations is the primary performance constraint.
B-trees are the foundational data structure behind most relational database indexes (PostgreSQL, MySQL InnoDB, SQLite) and filesystem metadata structures (NTFS, HFS+, ext4). The reason is physical: a B-tree node is typically sized to match a disk block or memory page (4–16KB), so each node read fetches hundreds of keys at once, and the logarithmic depth means even billion-record tables require only 3–4 disk reads per lookup.
Key Concepts
Minimum Degree (t) — Every B-tree is parameterized by a minimum degree t ≥ 2. Each non-root node must have at least t-1 keys and at most 2t-1 keys. This constraint keeps the tree balanced: all leaf nodes sit at the same depth, and the branching factor is bounded.
Node Structure — Each node contains:
- An ordered array of keys (up to
2t-1) - An array of child pointers (up to
2tchildren for internal nodes) - A count of current keys
Node Splitting — When inserting into a full node (one with 2t-1 keys), the node splits at the median key. The median is promoted to the parent, and the node divides into two nodes of t-1 keys each. Splits propagate upward; when the root splits, tree height increases by one — the only way a B-tree grows taller.
Search — At each node, perform a linear (or binary) scan of keys to find the subtree to descend into. With branching factor up to 2t, tree height is O(log_t n), which is far shallower than a binary tree’s O(log₂ n) for large t.
Deletion — More complex than insertion. If deleting from a leaf leaves it underfull (fewer than t-1 keys), rebalance by borrowing a key from a sibling or merging with a sibling, then adjusting the parent key.
B+ Tree Variant
The B+ tree is the variant most commonly found in database systems. It differs from the base B-tree in one critical way: all data records are stored only in leaf nodes. Internal nodes store only routing keys (copies of keys, not actual records). Leaf nodes are linked in a sorted doubly-linked list.
This design enables:
- Range queries — Scan leaf nodes sequentially without traversing internal nodes
- Higher branching factor — Internal nodes contain only keys (no data pointers), fitting more keys per disk block
- Simpler deletion — Internal key deletions don’t affect stored data
The trade-off: point lookups always traverse to a leaf, even when the key appears in an internal node. For range-heavy workloads (typical in databases), B+ trees dominate.
Comparison with Binary Search Trees
| Property | BST | B-Tree |
|---|---|---|
| Keys per node | 1 | Up to 2t-1 |
| Tree height | O(log₂ n) — can degrade to O(n) | O(log_t n) — always balanced |
| Disk I/O per lookup | O(log n) node reads | O(log_t n) — far fewer |
| Balance guarantee | None (without AVL/Red-Black) | Structural |
| Use case | In-memory ordered maps | Disk indexes, filesystems |
A balanced BST (AVL or Red-Black) keeps O(log n) height but still performs one comparison per node. For n = 1 billion with t = 500, a B-tree has height ~4 versus ~30 for a BST.
Common Pitfalls
- Choosing
ttoo small — small branching factor wastes the B-tree’s disk-I/O advantage - Confusing B-trees and B+ trees — most “B-tree indexes” in databases are actually B+ trees
- Assuming B-trees are always faster than Hash Tables — hash tables have O(1) point lookups but cannot support range queries or ordered traversal
Best Practices
- Match node size to the storage system’s block/page size for optimal I/O
- Use B+ trees (not base B-trees) for range-scan workloads
- For in-memory ordered maps, prefer Red-Black trees or skip lists — B-trees’ disk-I/O advantage disappears in RAM
Related Topics
- Searching Algorithms — B-tree search is a generalized form of binary search applied at each node
- Sorting Algorithms — B-trees maintain sorted order, enabling efficient ordered iteration
- Data Structures Overview — B-trees in the broader landscape of data structure selection