The Inverted Index

You want to find all articles about Python in a corpus of 10 million documents. grep opens each file, reads it byte by byte, and checks if it contains “python”. Ten million files later, you have your answer—but you could have waited hours. Google, Elasticsearch, and every search engine in the world chose a different path decades ago: build an inverted index once at write time, then answer any query in milliseconds regardless of corpus size.

The flip: from scanning every document to looking up one term in a dictionary.

The Naive Way: Scan Everything

The obvious approach to search is linear. Given a query term, open every document and check if it contains that term:

results = []
for doc in corpus:
    if query_term in doc.text:
        results.append(doc)

This is what grep does—it streams each file, scans character by character, and reports matches. For 10 million documents, you’re doing 10 million reads. If each read takes 10 milliseconds (disk latency), you’re at 100,000 seconds. If your corpus is 1 terabyte, you’re reading terabytes of data off disk. This is O(corpus_size) per query and completely unscalable.

The problem compounds with multiple terms. Searching for “python AND testing” requires scanning all 10 million documents again to find intersections. Boolean operators turn the cost multiplicative.

The Breakthrough: Flip the Index

Instead of storing documents and scanning them for terms, store terms and precompute which documents contain them. This is an inverted index—an off-by-one name from a simpler “forward index” that maps documents to words. An inverted index is a sorted dictionary: {term → [doc1, doc3, doc7, ...]}.

At write time, when you index a new document, you extract all its terms, normalize them, and add the document ID to each term’s posting list. At read time, to find documents with “python”, you do a single dictionary lookup. To find documents with “python AND testing”, you fetch both posting lists and intersect them. The query cost is now O(log N terms) to find each term, plus O(posting_list_size) to scan the results—completely decoupled from corpus size.

Google’s 10 million documents now yield their answer in single-digit milliseconds.

How Ingestion Works

Building an inverted index is a pipeline:

1. Tokenize: Split raw text into words. "Python code testing code" becomes ["Python", "code", "testing", "code"].
2. Lowercase: Normalize case. "Python" becomes "python". Now “Python” and “python” map to the same posting list.
3. Stem (optional): Reduce words to their root. "testing" and "tested" both become "test". This deduplicates synonyms and improves recall.
4. Build postings: For each unique term, record the document ID (and position, if you want phrase search). python: [1, 2], code: [1, 2], testing: [2].

Once this pipeline runs at write time, reads are trivial. You don’t rescan documents—the answer is already precomputed.

Posting-List Compression: Delta + Varint

A naive posting list for the term “python” in a 100-million-document corpus stores 100-million document IDs. Each ID is an integer—typically 8 bytes on disk. That’s 800 MB just for one term. Multiply by 10 million unique terms in English, and you’d need terabytes of storage. Elasticsearch and Lucene would be unusable.

The solution is delta encoding + varint encoding:

Delta encoding: Posting lists are sorted by document ID. Instead of storing absolute IDs [1, 3, 7, 15], store the differences: [1, +2, +4, +8]. Differences are smaller numbers and compress better.

Varint encoding: Numbers smaller than 128 fit in one byte. Numbers up to 16K fit in two bytes. Elasticsearch uses a variable-length encoding where small numbers use fewer bytes. The difference +2 takes 1 byte instead of 8.

The result: a posting list that took 800 MB now takes 10–50 MB. A 16–80× compression ratio without losing random access—you can still seek to the Nth document ID in O(log N) time. This is why Elasticsearch can index billions of documents on a single machine.

Ingestion pipeline (write-time cost) and AND-query intersection (read-time benefit).

AND-Queries and List Intersection

To find documents with both “python” AND “testing”:

1. Fetch posting list for “python”: [1, 2, 5, 8].
2. Fetch posting list for “testing”: [2, 7, 8].
3. Intersect them: [2, 8] (only doc 2 and doc 8 contain both terms).

If posting lists are sorted, intersection is O(n + m) where n and m are the sizes of the lists. Iterate the smaller list, checking membership in the larger one. No hash tables, no surprises. For OR-queries, you merge the lists instead; for NOT-queries, you subtract.

Multi-term queries scale sublinearly: the intersection shrinks as you add more AND clauses. The query cost is the size of the smallest posting list, not the corpus size.

Why This Works at Scale

Elasticsearch indexes trillions of documents because it makes reads cheap and concentrates cost at write time:

• Read-heavy asymmetry: Most systems see 100–1000 reads per write. A search engine handles millions of queries per second but processes new documents continuously in the background.
• Parallel ingestion: Indexing runs offline or in a bulk pipeline. A document delay of seconds is fine; a query delay of seconds is not.
• Sorted posting lists: Compression, intersection, and skip-scanning all rely on sorted order. Building the index at write time means you sort once.
• Time-based eviction: Old posting lists are pruned. A news search engine discards articles older than 30 days, keeping the index fresh and bounded.

When NOT to Use an Inverted Index

Inverted indexes are overkill if you don’t need full-text search:

• Range queries (age > 30): Use a B-tree or column index. An inverted index for “age” gives you documents containing the word “age”—not what you want.
• Numeric joins (orders.user_id = users.id): Use a foreign-key index or hash join. Inverted indexes are text-first.
• Write-heavy streams (logs, metrics): If 99% of operations are inserts, the write-time cost of indexing dominates. Use a column-oriented format (Parquet, ORC) or a time-series database instead.
• Small datasets: For a 1,000-document corpus, a linear scan is fine. Inverted indexes add complexity and overhead that don’t pay off until corpus size is in the millions.

The Trade-Offs

An inverted index is a bet that you will read far more than you write. It trades write latency and complexity for read latency and scalability:

• Space: Posting-list compression gives you a 10–50× reduction, but you still need extra storage for the index. Lucene’s segment files often match document size.
• Latency: Write latency increases—every insert touches multiple posting lists and flushes buffers. Read latency plummets.
• Consistency: Inverted indexes are usually asynchronous—a new document may not appear in search results for seconds or minutes. Real-time indexes (segment flushes every 1–5 seconds) sacrifice throughput for freshness.
• Complexity: Index maintenance (merging segments, handling deletions, compressing postings) is complex. You’re not building this from scratch; you’re using Elasticsearch, Lucene, or Meilisearch.

The reason every major search engine chose this path is that the asymmetry is real. Users tolerate a 5-second indexing delay. They do not tolerate 5-second search delays. Inverted indexes make that trade-off obvious in the architecture.

---

Key Takeaway: An inverted index is a write-time investment that buys read-time freedom. It transforms search from O(corpus size) to O(query specificity), enabling full-text search at any scale. The cost is upfront—tokenization, stemming, compression, and segment management—but the payoff is immediate: queries that would take hours with grep complete in milliseconds.