B+-trees: why an index lookup takes four reads
How a B+-tree index stays shallow: fanout from big disk pages gives log-base-500 height, leaf splits keep it balanced, linked leaves serve range scans.
Part of Indexes.
Read first
- Disk access cost: random vs sequential I/O
Why seek and rotation make random I/O over 100× slower than sequential I/O on a disk, and why databases use large pages and locality.
Read next
- Clustered vs unclustered index: when a scan wins
Clustered vs unclustered (secondary) indexes: why an index that pays a random read per row loses to a full table scan past a tiny selectivity.