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:
distributedsystemarchitecture- ...
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:
- Looks up both terms in the dictionary (fast hash or B-tree lookup)
- Retrieves their postings lists
- Intersects the lists to find documents containing both
- 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.