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.
Part of Storage.
Read next
- RAID parity: one extra disk rebuilds any one
How RAID parity (XOR) rebuilds any one failed disk for 1/N extra space, why every write must update parity, and how RAID 5 spreads that work.
- 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.
- Buffer pool replacement: LRU, MRU and Clock
Why LRU misses every read when a scan loops over a file one page bigger than the buffer pool (sequential flooding), and when MRU or Clock does better.
- External merge sort: sorting data bigger than memory
How a database sorts data far bigger than memory with two-phase multiway merge sort (TPMMS): two passes over the data handle about M² pages.
- 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.
- Linear hashing: growing a hash index one bucket at a time
How linear hashing grows a disk hash table one bucket at a time, splitting at a pointer instead of the full bucket, versus static and extendible hashing.