Inverted index
An inverted index is a data structure that maps each term to the list of documents containing it, rather than mapping each document to its words. This inversion is what lets a search engine answer a query by intersecting short lists instead of scanning every document.
Take three documents:
- D1: “the crawler fetches pages”
- D2: “the index stores pages”
- D3: “the crawler follows links”
A forward index stores each document’s word list. The inverted index stores the opposite:
| Term | Posting list |
|---|---|
| crawler | D1, D3 |
| fetches | D1 |
| follows | D3 |
| index | D2 |
| links | D3 |
| pages | D1, D2 |
| stores | D2 |
Answering “crawler pages” means intersecting D1, D3 with D1, D2, which gives
D1. Two short list reads, no document scanning. That is the entire reason
search is fast.
Real indexes store more than document IDs in each posting: the positions of each term within the document, so phrase queries can be answered, and per-term weighting used later in scoring. They are also compressed and split into segments, because a single in-memory dictionary stops being practical long before you reach web scale.