Design a Search Engine: Inverted Indexes, BM25, and Web-Scale Retrieval

Type new york times into a search box and you expect the ten best matches out of tens of billions of pages in under 200 milliseconds. That gap — between the scale of the corpus and the latency budget — is the entire design problem. You cannot scan the web per query, so almost every decision in a search engine is about doing work ahead of time and doing as little as possible at request time.

The machine that makes this possible is the inverted index, and the art is in how you build it, rank against it, shard it, and keep it fresh. This walkthrough uses the interview rubric — requirements, capacity, architecture, data model, then the deep dives that actually decide the outcome.

Functional and non-functional requirements#

Pin the scope first. A general web search engine needs to:

• Crawl and ingest documents continuously and store their raw content.
• Index the text so any term maps to the documents containing it.
• Query with multi-term boolean matching (AND by default), phrase matching ("new york"), and return a ranked top-K.
• Rank results by relevance, not just presence — the difference between a useful engine and grep.

The non-functional targets are what make it hard:

Reads dominate writes by orders of magnitude, and stale results are tolerable for seconds while a fully unavailable search box is not. That asymmetry justifies immutable index segments and read replicas throughout.

Capacity estimation: sizing the index#

Estimates keep the design honest. Assume 50 billion documents, ~1 KB of indexable text each, and ~1,000 unique terms per document.

• Postings: 50B docs × 1,000 terms ≈ 5 × 10¹³ postings (one entry per term-in-document).
• Compressed size: doc IDs within a posting list are sorted, so delta + variable-byte encoding gets each posting down to ~2 bytes. That is ~100 TB for the raw inverted index. Add a term dictionary (~50 GB) and skip tables (~10% overhead), landing near 120 TB.
• Shards: at ~500 GB per shard, that's ~240 shards. With 2× replication, ~480 index nodes.
• Query load: 100K QPS peak, scattered across 240 shards, is 24M intra-cluster RPCs/sec. A result cache with a 40% hit rate on common queries drops that to ~15M — which is why caching is not optional at this scale.
• Forward index (for snippets and highlighting) adds roughly another 50 TB compressed.

These numbers set the shape of everything else: you are partitioning across hundreds of nodes, every posting-list byte matters, and the aggregation fan-out is itself a bottleneck worth engineering around.

How an inverted index works#

The inverted index maps each term to a posting list — the documents that contain it. Each posting is a tuple of (doc_id, term_frequency, positions), where positions record where in the document the term appears (needed for phrase queries).

Physically it splits into two structures. The term dictionary — often a Finite State Transducer or a sorted B-tree — supports fast exact and prefix lookup from a term to the location of its posting list. The posting lists themselves live on disk, compressed, with doc IDs sorted so delta encoding shrinks them. Lucene-style segments are append-only and immutable, which lets the engine memory-map them for reads and merge them via background compaction instead of rewriting in place.

Two structures earn their keep during queries. Skip lists embedded in each posting list let an AND intersection jump ahead — when walking york AND times, if the york cursor is at doc57 and times is at doc33, the walker skips times forward past doc57 in one hop rather than scanning every entry. This turns intersection from linear in list length into something closer to linear in the result size.

Ranking: why BM25 beats TF-IDF#

Matching finds candidates; ranking orders them. The classic score is TF-IDF: tf × log(N/df), rewarding terms that appear often in a document but rarely across the corpus. It has two flaws. Term frequency grows without bound, so a page that repeats "york" fifty times keeps accumulating score, and there is no correction for document length, so long documents unfairly rack up matches.

BM25 fixes both. It applies a saturation function to term frequency:

The k1 parameter (≈1.2) makes term frequency plateau — the 50th occurrence of "york" adds almost nothing over the 5th. The b parameter (≈0.75) normalizes by document length dl against the corpus average avgdl, so a 10,000-word page doesn't beat a tight 200-word answer purely on size. These priors match human relevance judgments better on TREC benchmarks, and BM25 degrades gracefully across short and long documents — which is why Elasticsearch and Lucene made it the default in 2016.

Tracing one query end to end#

Follow "new york" as a phrase query against a small cluster of 3 shards:

The two-phase idea is the performance win: doc-ID intersection is cheap, and the expensive position decode runs only on the handful of documents that already matched both terms. Hot phrases like new york can be pre-indexed as shingles (a single token new_york) so they skip the position decode entirely.

Crawler-to-indexer pipeline and freshness#

The index has to be fed. The crawler fetches pages, throttled per host by a URL frontier — a priority queue keyed by domain with per-domain token buckets, so you stay polite and don't hammer one site. Raw HTML lands in a content store (S3/GFS), and each fetch emits (url, content_hash, fetched_at) onto a Kafka topic.

Downstream, a deduper suppresses near-duplicates using simhash (mirrors and syndicated copies are everywhere), then the indexer runs an analyzer pipeline — tokenize, stem, normalize case and diacritics — and writes immutable per-shard segments that a background compactor periodically merges.

Freshness is tiered because rebuilding 120 TB is a weekly job, not a per-second one:

• A realtime tier absorbs new documents into in-memory segments flushed every few minutes, so breaking news is searchable in seconds.
• A historical tier holds the bulk corpus, rebuilt on a slower batch cadence.
• The query node merges results across both tiers at request time, so callers see one unified ranking.

Sharding: document vs term partitioning#

At 240 shards you must choose a partitioning axis, and the two options are not close in practice.

Document partitioning wins because multi-term queries stay local — each shard intersects its own posting lists and returns a small top-K, so the network only carries results, not raw postings. The cost is fan-out: every query scatters to every shard. You bound the fan-in with two-tier aggregation (rack-local aggregators feeding a global aggregator) and cut tail latency with hedged requests — send a duplicate to a replica and take whichever answers first, so one slow node doesn't drag p99.

Adding a learning-to-rank layer#

BM25 alone leaves relevance on the table. Production engines run two-stage retrieval: BM25 cheaply pulls the top ~1,000 candidates per shard, then a learned reranker scores only the top ~100 merged candidates. That reranker — a gradient-boosted tree like LambdaMART, or a cross-encoder transformer — consumes hundreds of features: BM25 score, PageRank, click-through rate, freshness, query-document semantic similarity, and personalization signals.

The training data comes from click logs, but raw clicks are biased toward whatever ranked high already, so you correct with inverse propensity weighting and derive relevance labels from dwell time rather than the click alone. The reranker runs on the aggregator node, where all the per-document feature joins can happen once, and models ship through a feature store and model registry so serving stays decoupled from training.

How this shows up in interviews#

Interviewers use this problem to see whether you can hold two scales in your head at once — the algorithmic (how does an intersection actually run) and the systemic (how do you spread 120 TB across 480 nodes without melting the network). Strong candidates state the inverted index within the first few minutes, then immediately reach for the trade-offs: BM25 over TF-IDF and why, document over term partitioning and why, two-phase phrase matching to avoid decoding positions you don't need.

The capacity math is a common gate. If you can turn "50 billion documents" into "~100 TB, ~240 shards, and a fan-out problem" out loud, you've shown the interviewer you reason in numbers. The follow-ups are almost always freshness (the realtime-versus-batch tier split) and ranking quality (the retrieve-then-rerank pipeline). Have an opinion ready on each.

Further learning#

• Design FB Post Search w/ ex-Meta Interviewer — Hello Interview walks through search-index design with an interviewer's eye for the trade-offs that score points.
• Design Top K Problem — the same top-K merge and heap machinery that a search aggregator leans on.
• Design a Proximity Service — another index-and-shard problem where the partitioning key decides everything.
• Design YouTube — pipelines, storage tiers, and read-heavy scaling in a different domain.
• Design Instagram — fan-out, caching, and feed ranking that rhyme with search-result ranking.

Ready to practice? Work through the search-engine roadmap on YeetCode to drill the requirements, capacity math, and deep dives interactively.

FAQ#

What is an inverted index and why is it central to search?#

An inverted index maps every term to a posting list of the documents that contain it, each posting carrying the document ID, term frequency, and the positions where the term appears. It is central because it inverts the naive relationship — instead of scanning documents to find a query's terms, you jump straight from a term to its documents in one lookup. That is what makes sub-200-millisecond queries over tens of billions of pages possible: the expensive work of reading every document happens once at index time, not once per query.

Why do modern search engines use BM25 instead of TF-IDF?#

TF-IDF lets term frequency grow without bound and ignores document length, so a page that repeats a keyword or simply runs long accumulates unfairly high scores. BM25 adds a saturation function (tuned by k1) so repeated terms plateau in value, and length normalization (tuned by b) so long documents don't win on size alone. These corrections track human relevance judgments far better on standard benchmarks, which is why Lucene and Elasticsearch switched their default scorer to BM25 in 2016.

Should you shard a search index by document or by term?#

Shard by document. In document partitioning each shard holds a complete index over a slice of the corpus, so a multi-term query intersects posting lists locally and returns only a small top-K — the network carries results, not raw postings. Term partitioning puts each term's full posting list on one node, which is efficient for single-term queries but turns multi-term AND queries into shipping entire posting lists across the network. Document partitioning is the default in Elasticsearch and Solr for exactly this reason; you pay for it with query fan-out, which two-tier aggregation and hedged requests keep in check.

How does a search engine keep results fresh without rebuilding the whole index?#

It splits the index into tiers by update cadence. A realtime tier ingests new documents into small in-memory segments that flush every few minutes, so fresh pages become searchable in seconds. The bulk of the corpus lives in a historical tier rebuilt on a slower batch schedule, since re-encoding a hundred-terabyte index is a periodic job, not a continuous one. At query time the engine scatters to both tiers and merges their results, so a single ranked list reflects both the latest documents and the deep archive.

How do phrase queries like "new york" work efficiently?#

Postings store term positions, so a phrase query first intersects the posting lists of its terms to find documents containing all of them, then verifies that the positions are adjacent — position(york) = position(new) + 1. The efficiency trick is two-phase evaluation: cheap doc-ID intersection runs first, and the costlier position decode runs only for the documents that already survived intersection. For hot phrases, engines pre-index common bigrams as shingles (a single token like new_york) so those queries skip position decoding entirely.