Designing Search — The Inverted Index, Traced

Full-text search = the inverted index

Searching billions of documents for "system design" by scanning each is impossible. Search engines (and Twitter Search, log search, Elasticsearch) precompute an inverted index: for every term, the list of documents that contain it. A query becomes a fast set operation over short lists, not a scan.

The architecture

• Inverted index: term → posting list (sorted doc ids, often with positions + frequencies). Built offline by a parallel pipeline (map over docs → emit term→doc → group) — the data-parallel pattern again.
• Query: look up each term's posting list and intersect them (AND) — the result is docs containing all terms. Intersecting two sorted lists is linear and cache-friendly.
• Ranking: order results by relevance — TF-IDF / BM25 (rare terms + term frequency), plus signals like recency/popularity (PageRank for the web).
• Sharding: split the index across machines — by document (each shard indexes a subset; query scatter-gathers and merges top-K) or by term. Document sharding is the common choice.

Traced: search "system design"

1. Tokenize → terms ["system", "design"].
2. Fetch each term's posting list; intersect → candidate docs (e.g. {d4, d9}).
3. Score candidates with BM25; return the top-K ordered.
4. At scale: the query fans out to all shards, each returns its top-K, a coordinator merges (scatter-gather).

The hard parts

• Index size & build: huge; built/updated incrementally; segment merges (LSM-like).
• Ranking quality is the real product; the index is just retrieval.
• Scatter-gather latency = the slowest shard (tail latency!) → hedged requests help.

Takeaways

• Inverted index (term → posting list) turns search into list intersection, not a scan.
• Built offline (parallel), sharded by document; query = intersect → rank (BM25) → scatter-gather merge.
• Tail latency bites scatter-gather; ranking is the hard, valuable part.

---

Re-authored for this guide; inverted-index diagram hand-authored as SVG. Complements the "Designing Twitter Search" problem page with a traced flow. See also: Data Partitioning/Sharding, Data Parallelism, Tail Latency.

I just read a lesson on **Designing Search — The Inverted Index, Traced** (System Design) and want to truly understand it. Explain Designing Search — The Inverted Index, Traced from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Designing Search — The Inverted Index, Traced** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Designing Search — The Inverted Index, Traced** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Designing Search — The Inverted Index, Traced** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.