Database Indexing hard
A standard B-Tree cannot optimize `LIKE '%suffix'`. How does a Reverse Index solve this?
- A It utilizes a circular buffer architecture to ensure that the most recently updated records are always physically located at the start of the index.
- B It stores the strings in reverse character order, effectively turning a suffix-based search into a standard prefix-based B-Tree traversal.
- C It indexes the total character length of every string to allow the database to prune non-matching records based on a simple numeric range filter.
- D It utilizes specialized Trie-based data structures that are natively optimized for handling the high-frequency suffix collisions of modern datasets.
Answer: B. It stores the strings in reverse character order, effectively turning a suffix-based search into a standard prefix-based B-Tree traversal.
B-Trees are excellent at finding prefixes (`WHERE email LIKE 'john%'`) because the data is sorted. They are useless for suffixes (`WHERE email LIKE '%gmail.com'`). A Reverse Index stores the data backwards: `moc.liamg@nhoj`. The query is internally transformed to search for the prefix `moc.liamg%`. This allow the database to use its standard, high-speed B-Tree seek logic even for suffix patterns, at the cost of the CPU cycles needed to flip the strings.
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')?