B-tree
A B-tree is a self-balancing tree data structure that keeps data sorted and supports search, insert, and delete in O(log n) time [1]. Unlike a binary search tree (BST) where each node has at most two children, a B-tree node can hold many keys and many child pointers. This high fan-out is the whole point: it keeps the tree short, which means fewer disk reads to find anything.
The reason databases care so much about tree height comes down to disk I/O. Reading from disk is thousands of times slower than reading from memory. Every step down the tree is a potential disk seek. A BST with one million records could be 20+ levels deep. A B-tree over the same data might be only 3–4 levels deep because each node stores dozens or hundreds of keys packed into a single disk block. Less height means fewer reads, and fewer reads means fast queries.
Structure
A B-tree is made of three kinds of nodes:
- Root node: the entry point; may hold fewer keys than other nodes
- Internal nodes: store keys and child pointers, but no actual row data
- Leaf nodes: store keys and either the row data or pointers to where the data lives on disk
Every node is sized to match a disk page (typically 4KB or 16KB), so one disk read fetches one full node. Keys inside each node are stored in sorted order, so a binary search within the node is possible.
Why not a Binary Search Tree?
A BST has fan-out of 2. On disk, that means a tall tree with many levels, each requiring a separate disk read. Rebalancing a BST also uses rotations, which are expensive when nodes are on disk.
B-trees solve both problems. Instead of rotating nodes when balance breaks, B-trees split a node when it gets full and merge nodes when they get too empty. These operations keep the tree balanced with much less overhead and work naturally with disk page boundaries.
How reads and writes work
Read (lookup): Start at the root. At each node, binary-search the keys to find which child pointer to follow. Repeat until you reach a leaf. Because the tree is only 3–5 levels deep for millions of rows, this typically takes 3–5 disk reads.
Write (insert): Walk down to the correct leaf and insert the key. If the leaf is full, split it into two nodes and push the middle key up to the parent. Splits can cascade up the tree but rarely reach the root.
Write (delete): Remove the key from the leaf. If the node falls below the minimum fill threshold, borrow a key from a sibling or merge with a sibling.
Where B-trees are used
| Database | Storage Engine | Index type |
|---|---|---|
| MySQL | InnoDB | B+ tree |
| PostgreSQL | heap | B+ tree |
| SQLite | default | B+ tree |
| MongoDB | WiredTiger | B+ tree |
| Oracle | default | B+ tree |
The Indexing system in almost every relational database is built on top of B-trees. When you create a Composite index or a Covering index, the underlying structure is a B-tree. Secondary indexes are also B-trees pointing back to the primary key.
B-trees are the dominant choice for read-heavy or mixed workloads where random lookups and range scans both need to be fast. For write-heavy workloads where inserts dominate, the LSM tree offers a different trade-off worth understanding alongside this.