How Search Engines Work — Understanding Inverted Indexes and TF-IDF with Interactive Diagrams

Introduction

Google Search, code search in an IDE, and product search on a shopping site all have to find the documents that match a query in a large collection quickly and put them in order. They are all built on the same basic search engine techniques.

Three of these techniques are central, and this article shows each one with interactive diagrams:

1. Inverted Index — a data structure that maps each word to the documents containing it
2. Boolean Search — processing queries as set operations
3. TF-IDF / BM25 — scores used to rank search results

Search Engine Architecture

From collecting documents to returning results, the work splits into roughly 6 stages. This article covers text analysis, index building, query processing, and ranking.

Text Analysis — Breaking Documents into Tokens

When a search engine receives a document, it first runs text analysis, turning the raw text into searchable units called tokens.

The pipeline has four steps:

1. Character Normalization

Apply Unicode normalization and case conversion, so that "The" and "the" become the same token.

2. Tokenization

Split text into individual words (tokens). In English this is usually done on whitespace. Languages like Japanese, which don't put spaces between words, need another method, such as morphological analysis with tools like MeCab or Kuromoji.

3. Stopword Removal

Remove words like "the", "is", and "on" that appear very often and carry little information for telling documents apart. This shrinks the index and can improve search precision.

4. Stemming / Lemmatization

Reduce words to their root form: "running" → "run", "cats" → "cat". Different forms of the same word then match each other, which improves search recall.

Inverted Index — From Words to Documents

Why We Need an Inverted Index

A naive full-text search scans each document from start to finish looking for the keywords. For $N$ documents that takes $O(N \times L)$ time ($L$ being average document length), which stops being practical as the document count grows.

An inverted index removes the need for this full scan.

Forward Index vs Inverted Index

A forward index maps "document → contained terms":

Forward Index:
  D1 → [cat, sat, mat]
  D2 → [cat, dog]
  D3 → [dog, sat, log]

An inverted index reverses this mapping, storing "term → documents containing that term":

Inverted Index:
  cat → [D1, D2]
  dog → [D2, D3]
  log → [D3]
  mat → [D1]
  sat → [D1, D3]

The list of document IDs attached to each term is called a posting list. With a hash-based term dictionary, finding the posting list for a keyword takes expected $O(1)$ (or $O(\log T)$ with a tree/FST-style dictionary over $T$ terms). Most of the actual query time goes into reading and combining the posting lists once they are found.

Interactive Demo: Building and Searching an Inverted Index

The demo below builds an inverted index from 3 documents and then runs a search query against it, one step at a time.

Posting List Structure

In real search engines, posting lists often store more than document IDs:

An index that includes position information is called a positional index. Because it knows where each word occurs, it can answer phrase searches like "cat sat".

Query Processing — Boolean Search Model

The query is tokenized the same way as the documents, and the inverted index is then used to find matching documents. The most basic model is Boolean search.

AND (Intersection)

"cat AND sat" computes the intersection of the posting lists for cat and sat. Since both lists are sorted by document ID, a merge that walks both lists with two pointers processes them in $O(n + m)$ time, where $n$ and $m$ are the list lengths.

def intersect(p1, p2):
    result = []
    i, j = 0, 0
    while i < len(p1) and j < len(p2):
        if p1[i] == p2[j]:
            result.append(p1[i])
            i += 1
            j += 1
        elif p1[i] < p2[j]:
            i += 1
        else:
            j += 1
    return result

OR (Union)

"cat OR sat" returns the union of both posting lists — all documents containing either term.

Query Optimization

With several AND conditions, processing the term with the shortest posting list first keeps intermediate results small and makes the query faster.

Ranking — TF-IDF and BM25

Boolean search only says whether a document matches or not. In practice we want to order documents by how relevant they are to the query, and TF-IDF and BM25 are scores for doing that.

TF: Term Frequency

The more frequently a term appears in a document, the more likely that document is relevant to that term.

IDF: Inverse Document Frequency

$N$ is the total number of documents, and $\text{df}(t)$ is the number of documents containing term $t$. Words like "the" that appear everywhere have low IDF, while words like "algorithm" that appear in few documents have high IDF. A word that occurs in only a few documents is a better clue for telling documents apart, and IDF puts that idea into a formula.

TF-IDF Score

For multi-term queries, TF-IDF scores for each term are summed to produce the document's final score.

Calculation Demo

The demo below calculates TF-IDF scores and shows how they decide the ranking.

BM25: Improving on TF-IDF

TF-IDF has weaknesses. For example, a document where a term appears 100 times gets 100× the score of one where it appears once, but it isn't necessarily 100× as relevant.

BM25 (Best Matching 25) is a refinement of TF-IDF used by many search engines (it has been Lucene's default since 6.0).

Here $|d|$ is the length of document $d$ in terms, and $\text{avgdl}$ is the average document length. It has two parameters:

• $k_1$ (commonly 1.2–2.0; Lucene's default is 1.2): Controls TF saturation. If $K = k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)$, then the saturation factor $\frac{\text{TF} \cdot (k_1+1)}{\text{TF}+K}$ asymptotically approaches $(k_1 + 1)$ rather than growing without bound
• $b$ (commonly 0.75): Document length normalization. Longer documents tend to have higher TF simply because they contain more words; $b$ corrects for this bias

Practical Topics

Index Compression

Posting lists are sorted integer sequences of document IDs, so they can be efficiently compressed using delta encoding combined with Variable Byte Encoding:

Original list:    [101, 105, 108, 120]
Delta encoding:   [101,   4,   3,  12]  ← smaller numbers
Variable bytes:   efficiently packed into bytes

Distributed Search

Large-scale search engines shard (partition) the index across multiple nodes. Queries are sent to all shards (scatter), and the results from each shard are merged (gather) into the final ranking. Elasticsearch and similar systems work this way.

Apache Lucene and Elasticsearch

Apache Lucene is a full-text search library written in Java and built on inverted indexes; it is the de facto standard in this area. Internally it uses optimizations such as:

• Segmentation: Split the index into immutable segments, parallelizing reads and writes
• Skip lists: Jump ahead within a posting list, which speeds up operations like intersection
• Block encoding: Encode posting lists in blocks so they can be processed quickly with SIMD

Elasticsearch is a distributed search engine built on Lucene, providing REST APIs, clustering, and near-real-time indexing.

Summary

An inverted index stores a "term → posting list" mapping, and looking up a term in the dictionary takes expected $O(1)$ with a hash or $O(\log T)$ with a tree/FST. Boolean search answers queries with set operations on sorted posting lists. TF-IDF and BM25 combine how often a term appears in a document with how few documents contain it, and use the result to rank matches.

When you type a few words into a search box and the results come back right away, this is the kind of work happening underneath: inverted index lookups followed by score calculation.

References

• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008.
• S. Robertson, H. Zaragoza. The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval, 2009.
• Apache Lucene Documentation