[Review] Algorithms Behind Modern Storage Systems

Article

• Algorithms Behind Modern Storage Systems (ACM Queue, Mar+Apr 2018)

• 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.

Keynote Presentation