[Review] Algorithms Behind Modern Storage Systems


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

Leave a comment