B-Tree Height and Disk I/O
What you'll learn: How B-Tree height directly determines the number of disk accesses needed to find data in a database.
Why Height Matters in Databases
When your B-Tree index lives on disk (not in memory), every time you traverse from one node to another, you typically perform a disk I/O operation—one of the slowest operations in computing. The height of your B-Tree tells you the maximum number of disk reads needed to find any key.
The Height Formula
B-Tree height grows logarithmically with the number of keys. With a fan-out factor (branching factor) of d, a B-Tree of height h can store approximately d^h keys.
For example:
- Fan-out of 100, height 3: ~1,000,000 keys
- Fan-out of 100, height 4: ~100,000,000 keys
This means even massive databases require surprisingly few disk accesses!
The Disk Access Connection
If your B-Tree has height 3:
- Search: Up to 3 disk reads (root → internal → leaf)
- Insertion: Up to 3 reads + possible writes for splits
- Deletion: Similar pattern
Compare this to a binary search tree storing the same million keys: you'd need up to log₂(1,000,000) ≈ 20 disk accesses. The high fan-out of B-Trees is specifically designed to minimize height and thus minimize expensive disk I/O.
Why B-Trees Stay Short
B-Trees keep nodes highly populated (typically 50-100% full) and use large fan-out factors (often 100-200 or more). This "wide and shallow" structure is perfect for disk-based storage, where reading one large node costs nearly the same as reading a small one.
Key Takeaway: B-Tree height determines worst-case disk I/O cost; by keeping trees shallow through high fan-out, databases can access millions of records with just 2-4 disk reads.