Start here: the problem it solves#
TL;DRthe 30-second version
- The obvious way to find a word is to scan every document. That costs O(total text) per query. At a few million documents, every search reads gigabytes.
- An inverted index flips the layout. For each word it keeps a posting list, the sorted list of document ids that contain it. A one-word query is one lookup.
- A two-word AND query is the intersection of two sorted lists, walked with two pointers. It costs O(|A| + |B|), never the size of the corpus.
The obvious approach is to scan. Go through each document, split it into words, and check. This is what grep does over a folder, and for a handful of files it's fine. But scanning costs the total amount of text. At a few million documents, every query reads gigabytes. Put a thousand users on it and the machine falls over.
And you repeat the scan for every query. The documents didn't change between one search and the next, but you re-read all of them anyway. So the wish is clear. Read the documents once, ahead of time, and save a structure that answers any word query instantly.
The mechanism: flip the layout, then merge sorted lists#
The natural way to store documents is document to words. doc1 holds "cat sat mat", doc2 holds "dog sat log". That layout answers "what words are in doc1?" instantly. But a search asks the opposite: "which documents hold cat?" From the natural layout, you have to visit every document.
So invert it. Go through every document once, and for each word, record which documents it appeared in. The result is a dictionary. Its keys are terms, and each value is the list of document ids that contain that term. That list is called a posting list. To find every document with cat, look up cat and read its list.
Building it starts with tokenizing, which means splitting a document's text into terms. You lowercase the words so "Cat" and "cat" match. You split on spaces and punctuation. And you drop stopwords, very common words like "the" and "and" that appear in almost every document and so carry no search signal. Then, for each term left, you append the document's id to that term's posting list.
the same six tiny documents, stored the natural way and then inverted into posting lists
One rule makes everything downstream work: keep every posting list sorted by document id. Since you index documents in id order, appending keeps the list sorted for free.
A single-word query is now one lookup. cat gives back [doc1, doc3, doc5, doc6]. You never opened a document. The real payoff is the multi-word query.
Take "cat AND dog", every document with both words. You have cat = [doc1, doc3, doc5, doc6] and dog = [doc2, doc3, doc6], and you want the ids in both. Because both lists are sorted, you can walk them together with one pointer on each.
- Put a pointer at the start of each posting list. Compare the two document ids they point at.
- If the ids are equal, that document contains both terms. Add it to the result and advance both pointers.
- If the ids differ, advance the pointer on the smaller id. That id can't match anything left in the other list.
- Stop when either pointer runs off the end of its list. No further matches are possible.
cat = [doc1, doc3, doc5, doc6], dog = [doc2, doc3, doc6] — the matches are the ids both lists share
Complexity: why it beats scanning, and by how much#
An AND of two lists of lengths x and y takes O(x + y). Each comparison advances at least one pointer, so there are at most x + y steps. If cat and dog each appear in a few thousand documents out of a few million, the intersection touches a few thousand postings. The scan touches millions of documents. That is the difference between milliseconds and minutes.
| Operation | Inverted index | Full scan of corpus |
|---|---|---|
| Find one term | O(1) lookup + O(k) postings | O(total text) |
| AND of two terms | O(x + y) | O(total text) |
| Cost grows with | How many docs match | How big the corpus is |
One optimization falls out of that bound. To AND several terms, start with the shortest posting list. The result can only shrink as you add terms, so the rarest term first keeps every intermediate result small.
PredictA corpus has 10 million documents. The word "quantum" appears in 4,000 of them and "entanglement" in 1,000. Roughly how much work does "quantum AND entanglement" cost with an inverted index, and how much would a full scan cost?
Hint: The intersection is O(x + y) in the posting-list lengths. The scan is O(number of documents).
The inverted index walks the two posting lists: about 4,000 + 1,000 = 5,000 comparisons. The full scan reads all 10,000,000 documents and checks each for both words. That is a 2,000× difference, and the gap only widens as the corpus grows, because the index's cost depends on how many documents match, not on how many exist.
If this comes up in an interview#
Why must the posting lists be sorted?
The sort is what makes the two-pointer intersection work. When the pointers show different ids, the smaller one can't appear later in the other list, so you skip it and make progress on every comparison.
How do you rank the results?
Ranking sits on top of the index. The index finds the candidates, and a score orders them. TF-IDF weighs a document up when it uses the query word many times (term frequency) and weighs a rare word up over a common one (inverse document frequency).Lucene and Elasticsearch default to BM25, a refinement that adds saturation and length normalization.
How do you match a phrase like "new york"?
With a positional index. Each posting stores the positions where the term occurs in the document, not just the document id. Intersect the lists for new and york, then keep only documents where york appears one position after new.
How does the index handle a new document?
Not by editing posting lists in place. They live in immutable, compressed segments. A new document goes into a fresh small segment, and segments are merged in the background, the same idea as an LSM tree's compaction. So search is near-real-time: a short delay between indexing a document and seeing it in results.
Is this the same as a database index?
They're cousins. A B-tree index on a column maps a key to the rows with that exact value, which is right for equality and range lookups. An inverted index maps a term pulled out of text to the documents containing it, and is built to intersect those lists.
Trade-offs and when to reach for one
An inverted index is the right structure when you search a large, mostly static body of text by its content, and reads dominate writes. That describes search engines, log search, product catalogs, and email. A document is indexed once and searched millions of times.
| The question | Reach for | Why |
|---|---|---|
| Which documents contain this word? | Inverted index | A term → documents map. A query touches only the matching postings. |
| What's in this document? | Forward index | The natural document → terms layout. Free to build, but searching by content means a full scan. |
| Fetch one record by its key | Hash table or B-tree | A key → record map. The inverted index answers the opposite question. |
| Complete a prefix (autocomplete) | Trie | A prefix → completions map. Often paired with posting lists as the term dictionary. |
| One-off search of a small folder | Full scan (grep) | Nothing to build. Building an index costs one full read of the corpus anyway. |
- Write-heavy or real-time data works against it. Every new document must update every one of its terms' posting lists, and those lists live in immutable, compressed segments. So updates are batched, and there's a short delay before a new document is searchable.
- When one list is far longer than the other, even reading all of the long list is wasteful. Skip pointers are extra forward links placed along a posting list, so the walk can jump ahead without reading every id. Lucene builds a multi-level skip list over each posting list (default skip interval 16). That moves a long-versus-short intersection from O(x + y) toward O(y log x).
- Posting lists are huge, so they're stored compressed. The standard trick is delta encoding: instead of the ids [107, 112, 140, 141], store the gaps [107, 5, 28, 1], then pack those small numbers. This works because the list is sorted. It's why real search indexes are often smaller than the text they index.
- Where it runs. Apache Lucene, the core of Elasticsearch, OpenSearch, and Solr, stores each segment as an inverted index: a term dictionary pointing at posting lists, with skip lists over them. Elasticsearch shards that index across machines and merges the results. Google's 1998 architecture is an inverted index over the web, with posting lists that hold positions. Postgres GIN and MongoDB text indexes embed one inside the database.
References & further reading
- Manning, Raghavan & Schütze — Introduction to Information Retrieval, Ch. 1 (Boolean retrieval) — the canonical reference: building an inverted index and the O(x+y) posting-list intersection algorithm
- Apache Lucene — Lucene84PostingsFormat — a real on-disk format: term dictionary (.tim) with docfreq, posting lists (.doc), and multi-level skip data
- Brin & Page — The Anatomy of a Large-Scale Hypertextual Web Search Engine (Google, 1998) — Google's original inverted index over the web: barrels, posting lists with positions, and ranking
- PostgreSQL — GIN (Generalized Inverted Index) documentation — an inverted index inside a relational database, powering full-text search over rows