- On Disk IO, Part 1: Flavors of IO
- On Disk IO, Part 2: More Flavors of IO
- On Disk IO, Part 3: LSM Trees
- On Disk IO, Part 4: B-Trees and RUM Conjecture
- On Disk IO, Part 5: Access Patterns in LSM Trees
Background Knowledge & Summary
This main article focuses on data structures and algorithms that are used in modern database systems. Through a concise overview of B-trees and LSM trees, the author extends the trade-offs of each data structure to the RUM conjecture, which suggests that you can try to balance the read/update/memory overheads, but there isn’t a perfectly optimal structure.
For further information, refer to the following keynote presentation I’ve made. Explained here are the basics of I/O (including virtual memory, paging, and page swapping), B-Trees, LSM trees, Write Ahead Log and the RUM Conjecture.