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

Inverted Index Structure

The core data structure mapping terms to documents, enabling fast term-based lookups for search queries.

Inverted Index Structure

What You'll Learn

You'll learn how an inverted index maps terms to documents, forming the backbone of fast search engine lookups.

The Core Idea

An inverted index is essentially a giant lookup table that flips the traditional document-to-words relationship upside down. Instead of asking "What words are in document 42?", it answers "Which documents contain the word 'system'?"

Think of it like a book's index at the end: when you want to find "distributed systems," you flip to the index, see "pages 23, 87, 104" listed, and jump directly there. An inverted index does this at massive scale for search engines.

Structure Components

The inverted index has two main parts:

Dictionary (Vocabulary)

A sorted list of all unique terms extracted during tokenization:

  • distributed
  • system
  • architecture
  • ...

Postings Lists

For each term, a list of documents where it appears:

"distributed" → [doc5, doc23, doc89, doc102, ...]
"system"      → [doc5, doc12, doc23, doc45, ...]

Each posting can include additional metadata:

  • Term frequency: how often the term appears in that document
  • Position offsets: where exactly in the document
  • Field information: title vs body vs metadata

Why It's Fast

When a user searches for "distributed system," the search engine:

  1. Looks up both terms in the dictionary (fast hash or B-tree lookup)
  2. Retrieves their postings lists
  3. Intersects the lists to find documents containing both
  4. Ranks results using the stored metadata

This turns a potentially exhaustive document scan into two fast lookups and a set intersection.

Key Takeaway:
The inverted index is the fundamental data structure that makes search engines fast by mapping each term to the documents that contain it, enabling instant term-based lookups across billions of documents.