Database Indexing hard
LSM Trees mitigate slow reads by using Bloom Filters. What specific role do they play?
- A They implement a high-speed, lossy compression routine that automatically collapses all redundant data blocks before they reach the persistent storage layer.
- B They provide a fast, memory-resident probabilistic check that can instantly determine if a specific key is definitely NOT present within a physical data file.
- C They act as a primary index for range-based query predicates, allowing the database to prune individual records without performing a B-Tree traversal.
- D They ensure strict data integrity by preventing the accidental insertion of duplicate primary keys across different levels of the LSM tree structure.
Answer: B. They provide a fast, memory-resident probabilistic check that can instantly determine if a specific key is definitely NOT present within a physical data file.
Because LSM trees spread data across many separate SSTables, a single read might theoretically have to check dozens of files to find the latest version of a record. This is prohibitively slow. Bloom Filters solve this: they are small, RAM-cached bitmaps that can say 'No, this key is definitely not in SSTable-A'. If the filter says No, the database skips the expensive disk seek for that file entirely. If it says Yes (which might be a false positive), the database checks the disk. This dramatically speeds up 'Point Lookups' in LSM-based databases.
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?
- In LSM trees, what is 'Space Amplification'?
- Why is it generally ineffective to index a 'Low Cardinality' column like `Gender` ('Male'/'Female')?