In this lesson, you will learn how an inverted index maps individual words to their specific locations within a dataset to enable lightning-fast text searches.
The Problem with Linear Scanning
Imagine you have a database of 10,000 documents. If you perform a standard SELECT with a LIKE '%keyword%' clause, the database must perform a "full table scan," reading every single row to see if your word exists. This is incredibly slow. An inverted index flips this problem on its head by acting like the index at the back of a textbook: instead of scanning every page for a topic, you look up the topic to see exactly which pages it appears on.
Anatomy of the Mapping
An inverted index consists of two primary components: the Vocabulary and the Postings List.
- The Vocabulary (Dictionary): This is a sorted list of all unique words (terms) found across your documents.
- The Postings List: This is a list of references associated with each term, indicating which document ID (or row ID) contains that word.
Consider these two documents:
- Doc 1: "Database indexing is fast"
- Doc 2: "Indexing is important"
The resulting inverted index structure would look like this:
| Term | Postings List (Doc IDs) |
|---|---|
| Database | [1] |
| indexing | [1, 2] |
| is | [1, 2] |
| fast | [1] |
| important | [2] |
How It Powers Queries
When you search for the word indexing, the database engine doesn't touch the actual rows of your table. It simply jumps to the "indexing" entry in the vocabulary, finds the associated postings list [1, 2], and instantly knows exactly which rows to return. By eliminating the need to read irrelevant records, the database shifts from a slow, linear search to a highly efficient lookup.
Because this structure grows as you add more text, the database often manages this in the background, updating the vocabulary and appending to the postings lists whenever a record is inserted or modified.
Key Takeaway: An inverted index replaces slow, full-table scans with a high-performance mapping of unique terms to a list of specific document identifiers.