A B-tree is a self-balancing search tree where each node holds many keys and has many children (high fanout). This keeps the tree shallow, minimizing the number of disk reads — which is exactly what databases and filesystems need.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
In a B+ tree, all values live in the leaves and leaves are linked, so range scans walk a linked list of leaves — ideal for queries like WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Time | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk and SSD access is orders of magnitude slower than memory, so the metric that matters is I/O count, not comparisons.
High fanout slashes I/O by keeping the tree only a few levels deep.
This is why nearly every relational database index (and many filesystems) is built on B+ trees rather than binary search trees.