Course contentsShow
← System Design
Lesson 1746 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Index Construction at Scale

Building inverted indexes for billions of documents using distributed batch processing.

Index Construction at Scale

You'll learn how to build inverted indexes for billions of documents using distributed batch processing without overwhelming a single machine.

The Challenge of Scale

Building an inverted index for a few thousand documents on one machine is straightforward: read, tokenize, build in-memory structures, write to disk. But what happens when you have billions of web pages, each with thousands of tokens? The volume of data far exceeds a single machine's memory and processing capacity.

Distributed Batch Processing Approach

The solution is MapReduce-style distributed processing. Think of it like sorting a massive library: instead of one person cataloging every book, you split the work among dozens of workers, each handling a subset, then merge their catalogs.

Map Phase:

  • Distribute documents across many worker machines
  • Each worker tokenizes its assigned documents
  • Workers emit (token, docID) pairs
  • Output: intermediate files with unsorted token-document associations

Shuffle Phase:

  • Group all occurrences of the same token together across workers
  • Redistribute data so one machine handles all instances of "python", another handles "java", etc.

Reduce Phase:

  • Each reducer receives all (token, [docIDs]) for specific tokens
  • Build sorted posting lists per token
  • Write final index segments to distributed storage

Optimizations for Billions of Documents

  • Partitioning: Split final index by token prefix (a-c, d-f) for parallel querying
  • Compression: Use delta encoding and variable-length integers to reduce storage
  • Incremental updates: Build delta indexes for new documents, merge periodically

Key Takeaway:
Building inverted indexes at scale requires distributed batch frameworks (like MapReduce or Spark) to partition documents across workers, aggregate token postings in a shuffle phase, and produce compressed index segments that can be queried in parallel.