Search & the Inverted Index
You'll learn to
- -Explain how an inverted index enables fast text search
The Problem: Finding Text Fast
A SQL `LIKE '%term%'` scan checks every row for a substring match, fine for a thousand rows, hopeless for a hundred million. Full-text search needs a completely different structure, built for exactly this question.
The Inverted Index
A normal index maps a document to its words. An inverted index flips that: it maps each word to the list of documents containing it. Searching for "distributed systems" becomes a fast lookup (find the document lists for "distributed" and "systems," then intersect them) instead of reading every document to check.
Imagine you have 10 million products in your store. A customer types 'red runing shoes' (with a typo!) into the search bar. A regular database would do a simple text match and find nothing. There's no product called 'runing.' A search index, powered by technology like Elasticsearch, is built specifically for this. It creates an inverted index (like the index at the back of a textbook. Instead of page->words, it maps word->documents). It handles typos (fuzzy matching: 'runing' -> 'running'), synonyms ('sneakers' also shows 'running shoes'), relevance ranking (most popular red running shoes first), faceted filtering (filter by size, brand, price range), highlighting (shows WHERE the match occurred in the text), and autocomplete ('run...' suggests 'running shoes, running shorts, running watch'). All of this in milliseconds, across millions of documents.
Examples: Elasticsearch (the dominant player), OpenSearch (AWS-managed fork), Solr, Typesense (lightweight, easy to run), Meilisearch (developer-friendly), Algolia (managed search-as-a-service)
Beyond just "does this word appear," real search engines rank results by relevance (algorithms like TF-IDF or BM25 weigh how rare and how frequent a term is in a given document), which is why "design a search engine" is really two problems: finding candidate matches fast, and ranking them well.
Writes go through the primary database as usual; a separate pipeline keeps the search index updated so search queries never touch the OLTP database directly.
Why not just run search queries directly against the primary database using its own indexes?
"A regular database index should be able to handle text search fine."
"A B-tree index (the kind a relational database uses) is built for exact-match and range lookups, not for 'find documents containing any of these words, ranked by relevance': that needs an inverted index and a ranking algorithm, a fundamentally different structure. Running that workload against the same database serving live transactional traffic also risks large scans competing with production reads and writes, which is why search gets its own dedicated index, updated asynchronously from the source of truth."