What Is an Inverted Index
You'll learn: How an inverted index powers lightning-fast full-text search by flipping the relationship between documents and words.
The Core Data Structure
An inverted index is the fundamental data structure that makes modern search engines fast. While a normal "forward" index maps documents to the words they contain, an inverted index reverses this: it maps each unique term (word) to a list of documents that contain it.
Think of it like a book's index at the back. Instead of reading every page to find mentions of "coffee," you look up "coffee" in the index and jump straight to pages 47, 103, and 201.
How It Works
When you search for "system design," the search engine:
- Looks up "system" in the inverted index → finds documents [5, 42, 108, ...]
- Looks up "design" in the inverted index → finds documents [5, 67, 108, ...]
- Intersects these lists to find documents containing both terms
Without an inverted index, you'd need to scan every document sequentially—impossibly slow at web scale.
Structure
Term → Posting List (Document IDs)
-----------------------------------------
"search" → [1, 3, 7, 15, 22, ...]
"engine" → [1, 4, 7, 19, 25, ...]
"distributed" → [3, 12, 15, 28, ...]
Each term points to a posting list—the ordered sequence of document IDs where that term appears. These lists enable the Boolean query operators and TF-IDF scoring you've already learned about.
The inverted index transforms search from an O(n) scan of all documents into an O(k) lookup, where k is the number of matching documents—a massive speedup that makes real-time search possible.
Key Takeaway: An inverted index maps terms to document lists, inverting the natural document→word relationship to enable fast keyword lookup at the heart of every search system.