Database Indexing hard
Log-Structured Merge (LSM) Trees (RocksDB, Cassandra) optimize for Write Throughput. How does their disk IO pattern differ from B-Trees?
- A LSMs buffer writes in an in-memory MemTable and then flush them to disk as immutable, sorted SSTables to ensure sequential I/O patterns.
- B LSMs utilize a sophisticated random-access write protocol that directly modifies physical pages in the background to minimize write latency.
- C LSMs intentionally disable the Write-Ahead Log (WAL) and rely on the operating system's internal page cache to ensure absolute data durability.
- D LSMs store all incoming data in a highly compressed columnar format to maximize the efficiency of analytical queries and batch processing.
Answer: A. LSMs buffer writes in an in-memory MemTable and then flush them to disk as immutable, sorted SSTables to ensure sequential I/O patterns.
LSM Trees (Log-Structured Merge Trees) are designed to overcome the high latency of random disk I/O. While B-Trees perform 'update-in-place' (which requires seeking and modifying existing pages), LSMs simply append new data to a log and buffer it in memory. When the memory buffer (MemTable) is full, it is flushed to disk as a new, immutable SSTable. This append-only design turns random writes into high-speed sequential writes, making it ideal for write-heavy systems like Cassandra or RocksDB, albeit at the cost of requiring background compaction to clean up old data copies.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- Z-Order Curves (Geohashing) map 2D data to 1D strings for indexing. What is their primary weakness?
- In-Memory databases (Hyper, HANA) often favor Adaptive Radix Trees (ART). Why?
- In LSM compaction strategies, 'Universal' (Tiered) compaction prioritizes what over 'Leveled' compaction?
- In LSM trees, what is 'Space Amplification'?
- Why is it generally ineffective to index a 'Low Cardinality' column like `Gender` ('Male'/'Female')?
- You have a composite index on `(Lastname, Firstname)`. Which query can efficiently use this index?