Database Indexing medium
A standard B-Tree fails for Full Text Search (finding a word in a sentence). What structure does an Inverted Index use?
- A A Term Dictionary that maps individual words (tokens) to a 'Postings List' which contains the IDs of every document where that word appears.
- B A specialized multi-level Hash Map that utilizes every possible substring and character combination as a unique key for the entire dataset.
- C A QuadTree-based geometric index that treats every word as a set of spatial coordinates within a multi-dimensional linguistic vector space.
- D A linear Linked List structure that is optimized for sequential traversal and is natively integrated with the database's internal transaction logs.
Answer: A. A Term Dictionary that maps individual words (tokens) to a 'Postings List' which contains the IDs of every document where that word appears.
Standard B-Trees search for strings from left-to-right (Prefixes). To find a word *inside* a sentence, you need an Inverted Index. It breaks sentences into words (tokens). Each word points to a list of matching documents. When you search for 'Database', the system doesn't scan the book; it goes to the 'Database' page in the index and sees: [Page 1, Page 15, Page 300]. This is the foundation of technologies like Elasticsearch and Lucene.
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')?