Database Indexing hard
In LSM trees, what is 'Space Amplification'?
- A The ratio of total system RAM to persistent disk storage, which determines the maximum size of the buffer pool for active indexing operations.
- B The physical expansion of the primary data files that occurs when multiple non-clustered indexes are added to a single table for performance.
- C The growth rate of the database's internal transaction and debug logs during periods of exceptionally high write-concurrency and throughput.
- D The ratio of physical disk space used versus the actual live data size, caused by old record versions persisting until background compaction runs.
Answer: D. The ratio of physical disk space used versus the actual live data size, caused by old record versions persisting until background compaction runs.
Because LSM trees are append-only, updates and deletes don't immediately remove old data; they just add a new version or a 'tombstone'. The old versions stay on disk in older SSTables until the database performs a 'Compaction' to merge files and reclaim space. This results in 'Space Amplification', where the database might use 2x or 3x more disk space than the actual combined size of all current records. Choosing between Leveled and Tiered compaction allows developers to trade off between this space overhead and write performance.
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?
- Log-Structured Merge (LSM) Trees (RocksDB, Cassandra) optimize for Write Throughput. How does their disk IO pattern differ from B-Trees?
- In LSM compaction strategies, 'Universal' (Tiered) compaction prioritizes what over 'Leveled' compaction?
- 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?