How an inverted index works: an interactive search engine

An inverted index is how search engines find documents containing words without reading every document. For each term it keeps a posting list, the documents that contain it. A query looks up the lists for its terms, intersects or merges them, and ranks the matches, typically by how often each term appears in a document and how rare the term is overall. Elasticsearch, Lucene, Solr and every web search engine are built on one.

The playground indexes sixteen restaurant reviews. Type a query, switch between requiring all terms and any term, and see the posting lists, the matches and their scores.

How an inverted index is built

1. Tokenize each document into terms: lowercase it, split it on punctuation and spaces, and often reduce words to a stem, so “deliveries” and “delivery” match.
2. Record postings: for each term, the documents containing it, usually with the count and the positions, which phrase queries need.
3. Sort and compress each posting list by document id; the gaps between ids are small numbers that compress well.
4. Store a dictionary from terms to where their lists start, small enough to keep in memory.

Answering a query

For “cheap pizza delivery” the engine reads three posting lists, 5, 5 and 4 entries long, and intersects them: only one review contains all three. That is 14 postings read instead of all 176 words of all 16 reviews, and at web scale the gap is the difference between milliseconds and hours. Intersection is cheapest when it starts from the shortest list and skips through the longer ones, which is why rare terms make queries fast.

Ranking: TF-IDF and BM25

Matching is not enough; results must be ordered. TF-IDF scores a document by how often each query term appears in it (term frequency) times how rare the term is across all documents (inverse document frequency, log of N over the number of documents containing it). In “quiet coffee”, “coffee” appears in 2 of 16 reviews and “quiet” in 3, so the review with both comes first and coffee counts for more than quiet. BM25, the default in Lucene and Elasticsearch, refines this so that repeating a word has diminishing returns and long documents do not win just for being long. Production search adds many more signals: freshness, popularity, location, personalisation and learned ranking models.

Common words

A word like “and” is in 15 of the 16 reviews. Its posting list is the longest to read and it barely narrows anything, and its IDF is close to zero. Classic engines dropped such stopwords; modern ones keep them, since phrases like “to be or not to be” need them, but rely on IDF to discount them and on skipping to avoid reading their lists in full.

Indexing at scale

• Shard by document: each shard indexes a slice of the documents and every query goes to every shard, which return their top results to be merged. This is what Elasticsearch does; it keeps writes simple and spreads load evenly.
• Shard by term: each shard holds the full lists for some terms, so a query touches only the shards for its terms, but popular terms make hot shards and lists must be shipped to be intersected.
• Segments: new documents go into small immutable index segments that are merged in the background, much like an LSM tree, which is why new documents become searchable after a short refresh interval rather than instantly.

An inverted index in code

import math, re
from collections import defaultdict

def tokenize(text):
    return re.findall(r"[a-z]+", text.lower())

def build(docs):
    index = defaultdict(dict)                     # term -> {doc id: count}
    for doc_id, text in enumerate(docs):
        for term in tokenize(text):
            index[term][doc_id] = index[term].get(doc_id, 0) + 1
    return index

def search(index, n_docs, query, k=10):
    scores = defaultdict(float)
    for term in set(tokenize(query)):
        postings = index.get(term, {})
        if not postings:
            continue
        idf = math.log(n_docs / len(postings))    # rare terms count for more
        for doc_id, tf in postings.items():
            scores[doc_id] += tf * idf
    return sorted(scores.items(), key=lambda kv: -kv[1])[:k]

In a system design interview

For anything with a search box, say what is indexed and how it is kept up to date: “Listings are written to Postgres and streamed through change data capture into Elasticsearch, sharded by document, with about a second of indexing delay. Queries are matched with BM25 on title and description, filtered by location and price, and re-ranked by popularity.” Expect the follow-ups: typos and synonyms, how fresh results need to be, and how a query fans out to every shard.

Read how Elasticsearch works or the guide to search ranking and relevance, or watch a strong candidate design Yelp.

Questions people ask