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.
Part of Storage.
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
- 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.
- Undo and redo logging: write-ahead logging (WAL)
How write-ahead logging (WAL) makes transactions atomic and durable: undo, redo and undo/redo logs, their write rules, crash recovery, steal and force.