Search & Inverted Indexes
The data structure behind full-text search — mapping words to documents, the exact opposite direction a normal index goes.
Overview
An inverted index is the data structure behind full-text search engines like Elasticsearch — instead of mapping documents to the words they contain, it maps each word to the list of documents containing it, which is exactly the direction a search query ('find documents containing this word') actually needs to go.
Why It Exists
A relational database's B+ Tree index is built for exact-match and range lookups on structured columns — it's a poor fit for 'find documents whose text is relevant to this fuzzy phrase, ranked by how relevant they are.' Inverted indexes, paired with a relevance-scoring algorithm, exist specifically to answer that fundamentally different kind of question efficiently, at a scale a B+ Tree index was never designed for.
Real World Example
Searching an e-commerce catalog for 'wireless bluetooth headphones' — the search engine looks up each of those terms in its inverted index, finds the documents containing them, and uses BM25 to score and rank the results by relevance, accounting for term frequency, document length, and how rare or common each search term is across the whole catalog. A plain SQL `LIKE '%wireless%'` query can't do any of that — it can only tell you which rows contain the literal substring, with no concept of relevance at all.
Example Data
A tiny inverted index — term to document list, the opposite direction of a normal index
| Term | Documents Containing It |
|---|---|
| wireless | doc_12, doc_45, doc_88 |
| bluetooth | doc_12, doc_23, doc_88 |
| headphones | doc_12, doc_88, doc_91 |
How Search Actually Works Under the Hood
The Inverted Index — Word to Documents, Not Documents to Words
A normal database index maps a row to its column values. An inverted index maps each distinct term to the list of documents (and often positions) containing it — the exact lookup direction a search query needs.
Tokenization — Breaking Text Into Searchable Terms
Before indexing, text is broken into individual terms (tokens), often lowercased, stemmed (reducing 'running' to 'run'), and stripped of common stop words. The inverted index is built from these processed tokens, not the raw text.
BM25 — Scoring Relevance, Not Just Matching
Once matching documents are found, BM25 ranks them by relevance — weighting how often each search term appears in a document, how rare that term is across the whole collection, and normalizing for document length so long documents don't win purely by containing more words.
Diagram
Documents in, tokenized and inverted; a query comes back out ranked by relevance
Documents indexed
Tokenized into terms
Inverted index built
term → list of documents
Query arrives
terms looked up in the index
Matches scored via BM25
ranked results returned
Common Mistakes
Trying to build full-text search with SQL LIKE queries at scale
Why: A LIKE query with a leading wildcard (`'%word%'`) can't use a standard B+ Tree index at all, forcing a full table scan on every search — this doesn't scale past a small dataset.
Fix: Use a dedicated search engine (Elasticsearch, OpenSearch) or a database's built-in full-text search feature, which is usually its own inverted-index-based subsystem, once search needs go beyond exact or prefix matching.
Assuming relevance ranking is just about how many times a word appears
Why: BM25 specifically accounts for how rare a matched term is across the whole corpus (a rare matched term counts for more than a common one) and normalizes for document length — naive word-count scoring produces noticeably worse rankings.
Fix: Trust the relevance algorithm's more nuanced scoring rather than reimplementing a simpler word-count heuristic.
Not re-indexing after tokenization or analyzer rules change
Why: An inverted index is built from terms as they were tokenized at index time — changing tokenization rules (stemming, language analyzers) later doesn't retroactively apply to already-indexed documents.
Fix: Reindex existing documents whenever tokenization or analyzer settings change meaningfully.
Interview Questions
What does an inverted index actually map, and why is that direction useful for search?
It maps each term to the list of documents containing it — the reverse of a normal index, which maps a row to its values. That direction is exactly what a search query needs: given a search term, find every document that contains it, instead of checking one document at a time.
Why can't a typical SQL `LIKE '%word%'` query use a B+ Tree index?
A B+ Tree index is sorted by the indexed value's prefix, so it can only efficiently support lookups and ranges that start from a known prefix. A wildcard at the start of the pattern means there's no fixed prefix to search from, forcing the engine to check every row instead.
Two documents both contain the search term 'database' the same number of times, but the search engine ranks them very differently. What BM25 factors could explain that?
BM25 also weighs document length (a shorter document matching the same term count is considered more relevant, since the term makes up a larger share of its content) and the rarity of any other matched terms shared between the query and each document — if one document also matches a rarer query term the other doesn't, that alone could shift the ranking meaningfully even with identical counts for 'database.'
Production Best Practices
Do
✓Use a dedicated search engine or built-in full-text search feature once search needs exceed exact/prefix matching.
✓Trust relevance scoring (BM25) over simpler custom-built heuristics.
✓Reindex documents whenever tokenization or analyzer configuration changes.
Don't
✗Don't rely on SQL LIKE with leading wildcards for search at any real scale.
✗Don't assume raw term frequency alone determines relevance ranking.
✗Don't assume a tokenizer change applies retroactively without reindexing.
Comparison
| Optimized For | Query Shape | Ranking | |
|---|---|---|---|
| B+ Tree Index | Exact match, ranges on structured columns | WHERE column = / BETWEEN | None — exact match only |
| Inverted Index | Full-text relevance search | Fuzzy, multi-term text queries | BM25 relevance scoring |