Start here: the problem it solves#
TL;DRthe 30-second version
- To find every document containing a word, the obvious approach is to scan every document and check. That is O(total text) per query — at a few million documents, every search reads gigabytes.
- An inverted index flips the layout. For each term it keeps a posting list: the sorted list of document ids that contain that term. A single-word query is then one dictionary lookup that hands back the answer, without opening any document.
- A multi-word AND query is the intersection of two posting lists. Because both lists are sorted, you walk them with two pointers, always advancing the one pointing at the smaller id, and emit an id only when both point at it.
- That intersection costs about the combined length of the two lists — O(|A| + |B|) — never the size of the corpus. That is the whole reason search feels instant.
You have a few million documents — web pages, emails, product descriptions — and a user types a word. You need every document that contains that word, and you need it back in milliseconds. How do you find one word across millions of documents without reading them all?
The obvious approach is to scan. Go through each document, split it into words, and check whether the word is there. This is what grep does over a folder of files, and for a handful of files it is fine. The trouble is the cost: scanning is proportional to the total amount of text, so at a few million documents every single query reads gigabytes from disk and memory. One user, one word, gigabytes of work. Put a thousand users on it and the machine falls over.
Worse, you repeat the entire scan for every query. The documents did not change between one search and the next, yet you re-read all of them each time. All that work — splitting text into words, comparing — is thrown away the instant the query returns. You are recomputing the same thing over and over.
So the wish is clear: do the work of reading the documents once, ahead of time, and save a structure that answers any word query instantly afterwards. That one wish forces the whole design.
The mechanism: flip the layout, then merge sorted lists#
The natural way to store documents is document → words: doc1 holds "cat sat mat", doc2 holds "dog sat log". That layout answers "what words are in doc1?" instantly, but it is exactly the wrong question. A search asks the opposite: "which documents hold the word cat?" To answer that from the natural layout, you must visit every document. The layout fights the query.
So invert it. Build the other direction — word → documents. Go through every document once, and for each word, record which documents it appeared in. The result is a dictionary whose keys are terms and whose values are lists of document ids. That list is called a posting list, and each document id in it is a posting. This inverted layout answers the search question directly: to find every document with cat, look up cat and read its list.
Building it starts with tokenizing: taking a document's text and splitting it into terms. You lowercase the words (so "Cat" and "cat" match), split on spaces and punctuation, and drop stopwords — extremely common words like "the", "a", and "and" that appear in almost every document and so carry no search signal. What is left is the set of meaningful terms for that document. Then, for each term, 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 we index documents in id order, appending a new id keeps the list sorted for free. That ordering looks like a small detail, but it is the hinge the whole structure turns on, as the next step shows.
A single-word query is now trivial. To find every document with cat, look up cat in the dictionary and return its posting list — [doc1, doc3, doc5, doc6]. One lookup, and you are done. You never opened a document; you read one list. This is already a massive win over scanning, but the real payoff is the multi-word query.
Now the interesting case: "cat AND dog" — every document containing both words. You have two posting lists, cat = [doc1, doc3, doc5, doc6] and dog = [doc2, doc3, doc6], and you want the documents in both: their intersection. The naive way is to take each id in the first list and search for it in the second, which is slow. But both lists are sorted, and that changes everything.
Because both lists are sorted, you can walk them together with two pointers, one on each list. Compare the two ids the pointers sit on. If they are equal, that document is in both lists — emit it, and advance both pointers. If they are not equal, the smaller id can never appear again in the other list (everything ahead is larger), so it cannot be a match — advance the pointer sitting on the smaller id, and leave the other where it is. Repeat until one list runs out. This is the sorted-merge intersection, and it is the signature move of an inverted index.
- 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, so skip it.
- 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
Go deeperWhy the smaller pointer advances, and why sorting is what makes it work
The correctness of the merge rests entirely on the lists being sorted. When the two pointers show different ids, say cat points at doc5 and dog points at doc6, the smaller id (doc5) cannot possibly appear later in dog's list, because dog's list is sorted and everything after doc6 is even larger. So doc5 is definitively not a match, and we can drop it and move cat's pointer forward. Without the sort, we could not rule doc5 out, and we would be back to searching. The sort is what lets us make progress on every single comparison.
This is the same merge step at the heart of merge sort, and it generalizes. An AND of three terms is a merge of three lists (or, in practice, intersect two, then intersect the result with the third). An OR is the union — the same walk, but you emit from whichever pointer is smaller and only skip true duplicates. A NOT is a difference. Every Boolean query over the corpus reduces to walking sorted posting lists.
Complexity: why it beats scanning, and by how much#
A single-term query is a dictionary lookup plus reading the list: O(1) to find the term (if the dictionary is a hash table) and O(k) to return its k postings. A full scan for the same answer is O(total text in the corpus). The gap is enormous: the index reads only the documents that actually match, while the scan reads everything, matching or not.
The AND intersection of two posting lists of lengths x and y takes O(x + y) — each comparison advances at least one pointer, and there are at most x + y advances before a list runs out. Compare that to a scan-based AND, which would read the entire corpus and check each document for both words. 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 |
That last row is the whole point. A full scan's cost is set by the size of the corpus — add more documents and every query slows down, even queries for rare words. The inverted index's cost is set by how many documents match — a query for a rare word stays fast no matter how large the corpus grows, because its posting list is short. Search stays fast precisely because it decoupled query cost from corpus size.
One more optimization falls out of the O(x + y) bound. To AND several terms, start with the shortest posting list. The intersection can only shrink as you add terms, so processing the rarest term first keeps every intermediate result small. A search for "the AND platypus" should be driven by platypus (a handful of documents), never by the near-universal the — which is another reason stopwords are dropped or handled specially.
Go deeperGoing sub-linear with skip pointers
O(x + y) is already great, but when one list is far longer than the other, even reading all of the long list is wasteful. The fix is skip pointers: extra forward links placed at intervals along a posting list, so the walk can jump ahead without reading every id. When you are scanning the long list looking for id 900 and hit a skip pointer that says "the next entry after the skip is 850," you can leap past everything in between. Lucene builds a multi-level skip list over each posting list (a default skip interval of 16, only added once a term's document frequency passes a minimum of 128), guaranteeing a logarithmic number of skips to reach any target. This turns a long-list-versus-short-list intersection from O(x + y) toward O(y log x).
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, and it can do better by starting from the 1,000-entry list and skipping through the 4,000-entry one. The full scan reads all 10,000,000 documents and checks each for both words. That is a 2,000× difference — 5,000 posting comparisons versus 10 million document reads — and the gap only widens as the corpus grows, because the index's cost depends on how many documents match, not on how many documents exist.
From matching to ranking: TF-IDF and BM25
Finding the matching documents is only half of search. A query for "cat" might match ten thousand documents, and the user wants the best ones first. That is ranking, and it sits on top of the inverted index rather than inside it. The index finds the candidates; a scoring function orders them.
The classic score is TF-IDF, built from two intuitions. Term frequency (TF): a document that uses the query word many times is probably more about it. Inverse document frequency (IDF): a word that appears in almost every document (like "the") is a weak signal, while a rare word (like "platypus") is a strong one, so rare words are weighted up. Multiply them and you get a per-term, per-document weight; sum the weights of the query's terms and you have a document's score. The posting lists already store what you need — the document frequency is just the length of the posting list, and the term frequency can be stored alongside each posting.
Modern engines use BM25, a refinement of TF-IDF that adds saturation (the tenth occurrence of a word matters less than the second) and length normalization (a match in a short document counts for more than the same match buried in a long one). Lucene and Elasticsearch use BM25 as their default. The key point for this page: ranking is a number computed after the index has found the candidates. The runnable process — the part worth watching step by step — is the index build and the posting-list intersection; the score is a final calculation layered on top.
Variants worth knowing
The plain posting list — just document ids — answers Boolean queries but not everything users want. Two extensions cover most of the rest.
- Positional index — each posting stores not just the document id but the positions where the term occurs in that document. This is what makes phrase queries possible: to match "new york" as a phrase, intersect the posting lists of new and york, then keep only documents where york appears one position after new. It costs more space (positions are many per document) but enables phrase and proximity search.
- Term frequencies and document frequencies — storing how many times a term appears in each document (and, at the dictionary level, in how many documents overall) is what lets the ranking layer above compute TF-IDF or BM25 without re-reading the text. Lucene keeps these in the term dictionary and the postings file.
- Compressed postings — posting lists are huge, so they are stored compressed. The standard trick is delta encoding: instead of the ids [107, 112, 140, 141], store the gaps [107, 5, 28, 1], which are small numbers, then pack them with a variable-byte or bit-packing scheme. Delta encoding works precisely because the list is sorted, so the gaps are small and positive. This is why real search indexes are often smaller than the text they index.
The dictionary that maps terms to their posting lists is itself a data structure choice. A hash table gives O(1) exact-term lookup but no ordering. A sorted structure — a B-tree, or Lucene's finite state transducer (a compact automaton over the sorted terms) — gives O(log n) lookup but also supports prefix and range queries, so it can answer "all terms starting with cat" for wildcard search. The term dictionary and the posting lists are two separate pieces, and each is optimized on its own.
Trade-offs and when to reach for one
An inverted index is the right structure whenever you search a large, relatively static body of text by its content, and reads dominate writes. That describes search engines, log search, product catalogs, and email. It is the wrong structure when the data is not text, when you need the whole record by a primary key, or when writes are as frequent as reads.
- For: full-text search over many documents, Boolean and phrase queries, and any "which records contain this value" question across a large set. The read path is unbeatable because it touches only the matching postings.
- Against (write-heavy or real-time): every document indexed must update every one of its terms' posting lists, and posting lists are usually stored in immutable, compressed segments. So updates are batched — indexes rebuild or merge segments rather than edit in place, which adds latency between writing a document and being able to search it (near-real-time, not instant).
- Against (point lookups by key): to fetch one record by its id, a hash table or B-tree is the right tool. The inverted index answers the opposite question — given a value, which records have it — and is overkill (and the wrong shape) for a simple key lookup.
Inverted index vs forward index vs full scan vs trie
| Inverted index | Forward index | Full scan | Trie | |
|---|---|---|---|---|
| Maps | term → documents | document → terms | (nothing precomputed) | prefix → completions |
| Find docs with a word | O(1) + O(matches) | O(all documents) | O(total text) | n/a |
| Multi-word AND | O(x + y) merge | O(all documents) | O(total text) | n/a |
| Best for | search by content | "what's in this doc?" | one-off small data | autocomplete |
| Build cost | Index every doc once | Free (natural layout) | None | Insert every key |
The forward index is the natural document→words layout; it answers "what does this document contain?" but forces a full scan to search by content. The inverted index is its mirror, built specifically so the search question is a lookup. A trie (the prefix tree behind autocomplete) is a different structure for a different job — completing a prefix, not finding documents by word — and the two are often used together: a trie or FST for the term dictionary, posting lists for the documents.
Where inverted indexes run in the wild
- Apache Lucene — the open-source library at the core of Elasticsearch, OpenSearch, and Solr. Each Lucene segment is an inverted index: a term dictionary (stored as a finite state transducer, with per-term document frequency) pointing at posting lists, with multi-level skip lists to accelerate intersections. It is the reference implementation of everything on this page.
- Elasticsearch and Solr — distributed search engines built on Lucene. They shard the inverted index across machines, so a query fans out to each shard's index and merges the results. The single-node structure is exactly the posting-list index; the distribution is layered around it.
- Google and web search — the original motivation. Google's early architecture (the 1998 paper) is an inverted index over the web, with posting lists ("barrels") of document ids plus positions and formatting, ranked by PageRank and text scores. Every web search is a posting-list intersection at planetary scale.
- Postgres GIN and MongoDB text indexes — general-purpose databases embed inverted indexes for full-text search. Postgres's GIN (Generalized Inverted Index) maps each lexeme to the rows containing it; a text search is a posting-list lookup inside the database.
- Log and observability search — systems like Elasticsearch-backed logging or Loki index log lines by their terms so "show me every log containing this request id" is a posting-list lookup, not a scan of terabytes of logs.
Common misconceptions & gotchas
Why must the posting lists be sorted? Couldn't I store them in any order?
The sort is what makes the two-pointer intersection work. When the pointers show different ids, the sort guarantees the smaller one can't appear later in the other list, so you can skip it and make progress on every comparison. Without sorting, an AND would degrade to searching one list for each id in the other. Sorting also enables delta compression, since the gaps between consecutive sorted ids are small.
Isn't building the index just as slow as scanning? You still read every document.
Yes — building the index reads the whole corpus once, exactly like one full scan. The win is that you pay that cost a single time, then answer millions of queries cheaply. A scan pays the full cost on every query. Amortized over many searches, the index is dramatically cheaper; for a one-off search of a tiny dataset, a scan (grep) is simpler and fine.
How does the index handle updates when a new document arrives?
Not by editing posting lists in place — they're usually stored as immutable, compressed segments. New documents go into a fresh small segment, and segments are periodically merged in the background (the same idea as an LSM tree's compaction). This is why search is near-real-time: there's a short delay between indexing a document and it appearing in results, in exchange for keeping the read path fast and the storage compact.
Why drop stopwords? Aren't I losing information?
Stopwords like "the" and "and" appear in nearly every document, so their posting lists are enormous and their presence barely narrows a search. Dropping them shrinks the index and speeds up queries. The cost is that pure phrase queries containing them ("to be or not to be") get harder — which is why modern engines often keep stopwords but handle them specially (for example, only using them for ranking or phrases) rather than dropping them outright.
Is the inverted index 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 — great for equality and range lookups on structured data. An inverted index maps a term extracted from text to the documents containing it, and is built to intersect those lists for multi-word search. Both invert 'record → value' into 'value → records'; the inverted index specializes that idea for full-text search.
QuizYou run "the AND platypus" on a 10-million-document corpus. "the" appears in ~9,900,000 documents, "platypus" in 12. What is the single most important thing the query engine should do?
- Walk the two posting lists starting from "the", the longer list
- Start the intersection from "platypus", the shorter posting list, and skip through "the"
- Scan all 10 million documents to be safe
- Rebuild the index before answering
Show answer
Start the intersection from "platypus", the shorter posting list, and skip through "the" — The intersection can only be as large as the shortest list — at most 12 documents. Driving the merge from platypus's 12-entry list and skipping through the huge "the" list (with skip pointers) makes the query cost proportional to the rare term, not the common one. Starting from "the" would read millions of postings needlessly. This is why engines process the rarest term first — and why stopwords like "the" are dropped or given special handling.
In an interview
Lead with the inversion. A search engine can't scan every document per query — that's O(corpus) and far too slow — so it precomputes the opposite mapping: for each term, the sorted list of documents that contain it, called a posting list. A single-word query is then one dictionary lookup. Say that first; it's the whole idea.
Then reach for the payoff: a multi-word AND is the intersection of two sorted posting lists, done with a two-pointer merge — compare the two ids, advance the pointer on the smaller one, emit when they're equal. It's O(x + y) in the list lengths, not O(corpus). Mention the optimization that always comes up: start from the shortest posting list, because the result can only shrink, so processing the rarest term first keeps the work minimal.
Be ready for the follow-ups. How do you rank? TF-IDF or BM25, a score computed on top of the matched candidates — not inside the matching. How do you do phrases? A positional index that stores where each term occurs, then check that positions are adjacent. How do you handle updates? Immutable segments merged in the background, so search is near-real-time. Why sorted lists? Because the sort is what makes the linear-time merge (and delta compression) possible. Then open the simulator: index a few documents, watch one term's posting list grow, then run cat AND dog and watch the two pointers walk to the answer.
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
- Introduction to Information Retrieval — full text (Stanford NLP) — the complete book: postings, skip pointers, positional indexes, compression, and ranking
- Wikipedia — Inverted index — overview of record-level vs word-level (positional) inverted indexes and their trade-offs
- Apache Lucene — Lucene84PostingsFormat — a real on-disk format: term dictionary (.tim) with docfreq, posting lists (.doc), and multi-level skip data
- Apache Lucene — multi-level skip lists on posting lists (LUCENE-866) — how skip pointers accelerate posting-list intersection; default skip interval 16
- 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
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.