1. Why a Normal Database Index Isn't Enough
Week 4-5's B-tree index (the standard index type behind most relational databases) is excellent at "find rows where a column exactly equals, or falls within a range of, a value." A search query like "waterproof hiking boots" needs something qualitatively different: find every document containing any of these words, in any order, ranked by how relevant each match actually is — not a single exact-match lookup, but a fuzzy, ranked, multi-term query.
SELECT * FROM products
WHERE description LIKE '%waterproof%'
AND description LIKE '%hiking%'
AND description LIKE '%boots%';
-- A leading wildcard (%word) can't use a B-tree index at all --
-- this forces a full table scan, checking every single row's
-- description text against the pattern, for every query.
-- Fine for a thousand rows; unusable for a hundred million.
A dedicated search engine (Elasticsearch, and others built on similar ideas) solves this with a completely different index structure, purpose-built for exactly this query shape — Section 2.
2. The Inverted Index
A normal index maps row → its content. An inverted
index flips that: it maps word → every row containing it —
exactly the direction a search query needs.
Doc 1: "waterproof hiking boots"
Doc 2: "waterproof rain jacket"
Doc 3: "leather hiking boots"
Inverted index:
"waterproof" --> [Doc 1, Doc 2]
"hiking" --> [Doc 1, Doc 3]
"boots" --> [Doc 1, Doc 3]
"rain" --> [Doc 2]
"jacket" --> [Doc 2]
"leather" --> [Doc 3]
Query "waterproof hiking boots":
look up each term, intersect/union the document lists
--> Doc 1 matches all three terms (strongest match)
--> Doc 2 matches one term
--> Doc 3 matches two terms
Building this index means tokenizing every document into individual
terms first (splitting on whitespace/punctuation, lowercasing, often stemming —
"hiking" and "hike" reduced to the same root so a search for one matches the other).
Once built, looking up which documents contain a given word is a fast, direct lookup
— no scanning every document's text at query time, which is exactly what
Section 1's LIKE '%...%' was forced to do.
A search engine's inverted index needs updating every time a document is added, changed or removed — Week 8's queue pattern is the standard way to do this: writes go to the primary database first, and a change is published onto a queue that a separate indexing pipeline consumes to keep the search index in sync, usually with a small, accepted delay (seconds, not milliseconds) rather than the search index being updated synchronously on every write.
3. Relevance Ranking: TF-IDF & BM25
Section 2's example ranked Doc 1 highest because it matched all three query terms — real relevance scoring is more nuanced than a raw match count. The classic approach, TF-IDF, balances two signals:
- Term Frequency (TF) — how often a term appears in this document. A product description that says "waterproof" three times is probably more about waterproofing than one that mentions it once.
- Inverse Document Frequency (IDF) — how rare a term is across all documents. A match on "waterproof" (appears in relatively few documents) is more meaningful than a match on "the" (appears in nearly all of them) — common words are downweighted because they carry little distinguishing signal.
Query: "the waterproof boots"
Term "the": appears in ~95% of all documents
--> very low IDF --> contributes almost
nothing to the relevance score
Term "waterproof": appears in ~3% of all documents
--> high IDF --> a match on this term is
a strong, meaningful signal
A document matching "waterproof" is scored far above one that
only matches "the", even though naive term-counting would treat
both matches equally.
Most production search engines today use BM25, a refinement of TF-IDF that additionally accounts for document length (a match in a short, focused product title counts for more than the same match buried in a long description) and diminishes the returns of repeating a term many times (the fourth mention of "waterproof" adds much less signal than the first). The exact formula is less important for an interview than the underlying idea both share: rare, frequent, and appropriately-placed matches score higher than common, sparse ones.
4. Deep Dive: Autocomplete/Typeahead
A search box's suggestion dropdown is a different, latency-critical problem: given a partial prefix typed so far ("wat"), return the most likely completions ("waterproof jacket," "watch," "water bottle") in single-digit milliseconds, on every keystroke.
(root)
/ | \
w b ...
/
a
/
t
/ \
c e
| |
h r
(watch)
...
at "water" node: store the top-K most popular completions
directly at this node (precomputed), so a lookup for prefix
"wat" is a single tree traversal to the node, then read the
precomputed top-K list -- no scanning or re-ranking at
request time
A trie (prefix tree) indexes strings by shared prefixes, so finding every completion of "wat" means walking three edges (w → a → t) and reading whatever is stored at that node — dramatically faster than Section 2's full search-and-rank pipeline, which is far too slow to run on every keystroke. The critical design choice: the top-K popular completions per prefix are precomputed offline (from historical query logs) and stored directly at each trie node, not calculated live — trading a small amount of staleness (yesterday's popular searches, not this second's) for the speed the feature actually needs.
It's tempting to reuse Section 2's search index for autocomplete too, but the latency budgets are wildly different — search can tolerate 100-200ms, autocomplete needs single-digit milliseconds because it fires on every keystroke. Building a separate, purpose-built trie for autocomplete, kept loosely in sync with the main search index, is a stronger answer than trying to force one system to serve both latency profiles.
5. Hands-on Exercise
Design search for a 10-million-product catalog
An e-commerce catalog with 10 million products currently only supports exact SKU lookup. Add full-text product search and a typeahead suggestion box.
Requirements:
- Sketch how product titles and descriptions get tokenized and indexed into an inverted index (Section 2), including one design decision about stemming or lowercasing and why it matters for this catalog.
- Design the pipeline that keeps the search index in sync when a product's price or description changes in the primary database — name the component from Week 8 you'd reuse and why.
- Explain, using Section 3's TF-IDF/BM25 intuition, why a search for "shoes" shouldn't rank a product mentioning "shoes" once in a long, unrelated paragraph above a product titled simply "Running Shoes."
- Design the autocomplete trie for product search-box suggestions, including how the top-K completions per prefix get computed and how often they're refreshed.
- State one thing that would go wrong if the same inverted index were used to serve both full search results and autocomplete suggestions directly, without a separate trie.
For requirement 5: an inverted index is optimized for "which documents contain this term," which is a different question from "what are the most likely completions of this partial prefix" — answering the second question from the first structure would require scanning and ranking many candidate terms live, on every keystroke, which is exactly the latency problem Section 4's precomputed trie exists to avoid.
6. Knowledge Check
Four quick questions. Expand each to check your answer.
Q1
Why can't a standard B-tree database index efficiently answer a query like WHERE description LIKE '%waterproof%'?
Why can't a standard B-tree database index efficiently answer a query like WHERE description LIKE '%waterproof%'?
A leading wildcard pattern can't use a B-tree index's sorted-order structure at all, since the index is built to find values starting with a known prefix, not values containing a substring anywhere. This forces a full scan of every row's text for every query — fine at small scale, unusable at the scale a real search feature needs.
Q2
What does an inverted index map, and why does that direction make search queries fast?
What does an inverted index map, and why does that direction make search queries fast?
It maps each word to the list of documents containing it (word → documents), the reverse of a normal index's document → content mapping. Since a search query is fundamentally "which documents contain these words," looking that up directly via the inverted index is a fast lookup, instead of scanning every document's text at query time.
Q3
Why does a match on a rare word like "waterproof" contribute more to a relevance score than a match on a common word like "the"?
Why does a match on a rare word like "waterproof" contribute more to a relevance score than a match on a common word like "the"?
Inverse Document Frequency (IDF) downweights terms that appear in most documents, since matching a word nearly every document contains carries almost no information about relevance. A word appearing in only a small fraction of documents is a much stronger, more distinguishing signal when it matches, so TF-IDF/BM25 scoring weights it far more heavily.
Q4
Why is autocomplete typically built on a separate trie structure rather than reusing the main full-text search index directly?
Why is autocomplete typically built on a separate trie structure rather than reusing the main full-text search index directly?
Autocomplete fires on every keystroke and needs single-digit millisecond responses, far tighter than search's 100-200ms budget — a trie with precomputed top-K completions per prefix meets that bar with a simple tree traversal, while running the full search-and-rank pipeline on every keystroke would be far too slow.