What is an inverted index and how does it power Elasticsearch search?
Understand the inverted index that powers Elasticsearch: term-to-document mapping, posting lists, text analysis, and BM25 relevance scoring.
Expected Interview Answer
An inverted index is a data structure that maps each unique term to the list of documents (and positions) where it appears, rather than mapping documents to their words. It powers Elasticsearch by letting a search jump straight to the documents containing a term instead of scanning every document, making full-text search extremely fast.
When a document is indexed, its text is analyzed: tokenized into terms, lowercased, and often stemmed or filtered. Each resulting term becomes a key in the inverted index pointing to a posting list of matching document IDs plus term frequencies and positions. At query time Elasticsearch looks up the query terms, intersects or unions their posting lists, and scores results using relevance algorithms like BM25. Positions also enable phrase and proximity matching.
- Turns full-text search from O(n) scans into fast term lookups
- Stores term frequencies and positions for relevance scoring
- Enables phrase, proximity, and fuzzy matching
- Scales to billions of documents across shards
- Underpins ranked results via BM25 scoring
AI Mentor Explanation
An inverted index is like the index at the back of a cricket almanack that lists 'century' and next to it every page where a century is recorded. Instead of reading the whole book to find centuries, you look up the word and jump straight to the pages. Elasticsearch does the same: it looks up a term and instantly knows which documents contain it.
Step-by-Step Explanation
Step 1
Analyze the text
Each document's text is tokenized, lowercased, and often stemmed into terms by an analyzer.
Step 2
Build posting lists
Each term becomes a key pointing to a posting list of document IDs, term frequencies, and positions.
Step 3
Store the index
The inverted index is written into immutable Lucene segments within each shard.
Step 4
Look up query terms
At query time the analyzer processes the query and its terms are looked up in the index.
Step 5
Combine and score
Posting lists are intersected or unioned, and matches are ranked with BM25 relevance scoring.
What Interviewer Expects
- Defines inverted index as term-to-document mapping
- Explains text analysis (tokenizing, lowercasing, stemming)
- Knows posting lists hold frequencies and positions
- Connects positions to phrase/proximity queries
- Links the structure to BM25 relevance scoring
Common Mistakes
- Describing it as a document-to-term (forward) index
- Forgetting that analysis transforms terms before indexing
- Assuming search speed comes from caching rather than the index structure
- Overlooking that term positions enable phrase matching
Best Answer (HR Friendly)
“An inverted index is like the index at the back of a book: it lists each word and the pages where it appears. Elasticsearch builds one for your data so that when you search for a word, it can jump straight to the matching documents instead of reading everything, which is why search is so fast.”
Code Example
Documents:
doc1: "fast wireless headphones"
doc2: "wireless keyboard"
Inverted index (term -> documents):
fast -> [doc1]
wireless -> [doc1, doc2]
headphones -> [doc1]
keyboard -> [doc2]
Search "wireless" -> instantly returns doc1, doc2Follow-up Questions
- What role does the analyzer play before indexing?
- How does BM25 use term frequency and document frequency?
- How do term positions enable phrase queries?
- Why are Lucene segments immutable?
- How does the inverted index differ from a forward index?
MCQ Practice
1. An inverted index maps:
An inverted index maps each term to a posting list of documents that contain it, enabling fast lookups.
2. What happens to text during indexing?
An analyzer tokenizes and normalizes text into terms before they are added to the inverted index.
3. Term positions in the index primarily enable:
Storing positions lets Elasticsearch match phrases and terms that appear near each other.
Flash Cards
What is an inverted index? — A structure mapping each term to the documents (and positions) where it appears, enabling fast full-text lookups.
What is a posting list? — The list of document IDs, term frequencies, and positions associated with a single term.
Why is it fast? — Searching looks up terms directly instead of scanning every document.
What enables phrase matching? — Storing term positions within each document in the posting list.
Continue Learning
Related Interview Questions
What is Elasticsearch and what problems does it solve?
easy
A user searches for a word that is plainly in the document and gets nothing back. How do you debug it?
medium
What is the difference between Elasticsearch and a relational database?
medium
Why do BM25 relevance scores often surprise people, and how do you tune relevance in production?
hard