Inverted indexes
From every word to the documents that contain it: how search answers in milliseconds.
01The intuition
The problem it solves
You want every page in a 1,000-page textbook that mentions "mitochondria". Reading the book cover to cover takes a day. The index at the back takes ten seconds: it lists each important word with the pages it appears on. The index was built once, by someone who read the whole book, so that every later reader does not have to.
A search engine faces this with a billion documents and a query that must be answered in 200 ms. Scanning documents for the query words is impossible at that scale; the inverted index is the book index made enormous: for every word, a sorted list of the documents containing it.
Build it one piece at a time
Step 1: tokenize. Split each document into words, lowercase them, strip punctuation, and optionally reduce them to stems ("running" → "run"). Give each document a number.
Step 2: post the words. For every word, append the document number to that word's list, called a postings list. Keep the list sorted by document number.
| After indexing | Index contents |
|---|---|
| doc 1: "the cat sat" | the → [1], cat → [1], sat → [1] |
| doc 2: "the cat ran" | the → [1, 2], cat → [1, 2], sat → [1], ran → [2] |
| doc 3: "a dog ran" | the → [1, 2], cat → [1, 2], sat → [1], ran → [2, 3], a → [3], dog → [3] |
Step 3: answer a query. "cat ran" means documents in both lists: intersect [1, 2] and [2, 3] by walking both sorted lists together, which gives [2]. "cat OR dog" is a merge. Because the lists are sorted, intersection is linear in their lengths, and skip pointers let the walk jump ahead.
Step 4: store enough to rank. Alongside each document number store how many times the word appears and where (positions), so phrase queries ("cat ran" as adjacent words) work and so a document that mentions a word often can score higher. A rarer word carries more weight than a common one; that ratio (term frequency times inverse document frequency, refined into BM25) is the starting point of every ranker.
Step 5: make it big. Compress the postings (store gaps between document numbers, which are small and pack into a byte or two). Split the index into shards by document, so each shard indexes a slice of the collection and a query goes to all shards in parallel and merges the top results (scatter-gather). Build new segments for new documents and merge them in the background rather than editing lists in place, the same shape as an LSM tree.
Why it works, with the numbers
The index turns a scan over all documents into a walk over only the documents that matter:
cost of "cat AND ran" ≈ |postings(cat)| + |postings(ran)|, independent of the total number of documents
A word appearing in one document in a thousand has a postings list of a million entries in a billion-document collection; compressed to about 1 byte per gap it is 1 MB, read from memory in well under a millisecond. The whole index is typically a tenth to a third of the size of the text. The guarantee is that every document containing the query words is found. The failure modes are stop words ("the" has a billion-entry list; drop it or handle it specially), a word that appears everywhere in a hot shard, index freshness (a new document is not searchable until its segment is built, seconds in a good design, hours in a bad one), and tokenization mismatches where the query is split differently from the documents.
The trade-off you must say out loud
The index trades write cost and storage for read speed: every document is processed once more at index time and takes space twice. Say how fresh the index must be (seconds for tweets, hours for the web) because that decides segment size and merge frequency. The interviewer's follow-up is usually "how do you rank, not just find?", and the answer separates retrieval (the index gives candidates) from ranking (a scoring pipeline orders them), which is the ranking pipeline article.
Where it shows up in the 100 Google problems
- Design Google Search: the index is the system; sharding, replication and freshness are the deep dives.
- Design Twitter search: tiny segments built every few seconds, sharded by time so recent tweets are hot.
- Design Gmail: one small index per mailbox, built as mail arrives, so a user's search never touches anyone else's mail.
- Design job alerts for Google Careers: the index is inverted the other way, saved searches indexed so a new posting can find the queries that match it.
- Design a log collection and aggregation pipeline: logs indexed per time bucket so a search over the last hour touches only that bucket.