LSM vs. B‑Tree: RocksDB and WiredTiger for Cloud‑Native Distributed Databases

Cloud-native databases often use open-source embedded key-value stores on each node or shard. OLTP workloads are read- and write-intensive, typically relying on indexes for data access. Two main on-disk structures are prevalent: B-Trees, such as WiredTiger, and LSM-Trees, like RocksDB. This talk explores the similarities and differences in their internal implementations, as well as the trade-offs among read, write, and storage amplification. It also compares these structures to traditional fixed-size block storage in RDBMS and discusses the differences in caching the working set in memory and ensuring durability through write-ahead logging.