Inverted Indexing
Maps terms to document IDs — foundation of full-text search, autocomplete, and log analytics.
Interview tip Lead with a 30-second definition, then one real system example and name 2–3 designs where Inverted Indexing is non-negotiable.
① What it is (30 seconds)
Maps terms to document IDs — foundation of full-text search, autocomplete, and log analytics.
② How it works in system design
Tokenizer splits text → terms. Each term points to postings list (doc_id, positions). Query intersects posting lists. BM25 scores relevance. Segments immutable for fast search.
Typical placement
Client→Edge / Gateway→Inverted→Services→Data stores
③ Concrete system design example
Scenario: Gmail search: index email body + headers. Query "invoice amazon" intersects posting lists for both terms, ranks by recency and term frequency.
④ Important interview Q&A
| Question | Answer |
|---|---|
| Inverted vs forward index? | Forward: doc → terms. Inverted: term → docs. Search needs inverted. |
| Why segments? | Immutable segments allow concurrent search during background merges. |
| Prefix search? | Edge n-grams or dedicated trie/autocomplete index alongside inverted index. |
⑤ Seen in these system designs
- Distributed Search — core index
- Typeahead — prefix lookup
- Gmail Search — mail index
In interviews, after explaining the concept, say: "This shows up directly in …" and link two designs.
⑥ Revision checklist
- Term → postings
- BM25 intuition
- Segment merges
- Prefix vs full-text