How an inverted index works
The simple flip, from documents-to-words into words-to-documents, that lets a search engine answer a query without reading everything.
Written by Amili, an AI writer, from the sources listed below · 23 October 2026 · 5 min read
An inverted index is a lookup table that lists, for every word, the documents (and often the positions) where it appears. Instead of scanning every page for your search terms, a search engine jumps straight to each word's list and combines them. It is the core data structure behind full-text search.
In short
- A forward index lists the words in each document; an inverted index lists the documents for each word.
- Searching becomes a lookup plus a merge of short lists, instead of a scan of everything.
- Storing word positions enables phrase search; storing counts helps ranking.
- The price is paid up front: more storage, and extra work every time a document is added or changed.
What is being inverted?
The natural way to store text is document by document: this page contains these words, that page contains those. That is a forward index. It is easy to build as documents arrive, but useless for search, because to find every page containing a word you would have to open every page.
An inverted index flips the relationship. Each word becomes a key, and next to it sits a list of the documents where it occurs, often called a postings list. Searching for a word is now a matter of jumping to its entry and reading the list. Search engines typically build the forward index first, while reading documents, and then invert it.
A worked example with three tiny documents
Imagine three documents. Document 1: cats chase mice. Document 2: dogs chase cats. Document 3: mice eat cheese. The inverted index looks like this: cats appears in 1 and 2; chase in 1 and 2; mice in 1 and 3; dogs in 2; eat in 3; cheese in 3.
A search for cats AND mice reads two lists, {1, 2} and {1, 3}, and keeps what they share: document 1. A search for cats OR cheese merges {1, 2} with {3} and returns all three. No document was opened during the search; the work was done when the index was built.
This basic version only records whether a word is present, so it can say which documents match but not which match best. That is called a Boolean index. Richer versions store how many times each word appears in each document, which helps rank results, and where each word appears, which makes phrase searches possible. If positions are stored, a search for chase cats can confirm that the two words sit side by side in document 2 and not in document 1, where they appear in the opposite order and are not adjacent.
Why is it so much faster?
Without an index, a search engine would have to read every word of every document for every query. The gap is enormous: an index over 10,000 documents can be queried in milliseconds, while a word-by-word scan of 10,000 large documents could take hours.
Most words do not appear in most documents, so the full grid of words against documents would be mostly empty. Storing only the non-empty entries, as lists, keeps the index far smaller than that grid. The lists are often compressed as well, and researchers eventually realised that compressing these lists and compressing bitmaps were essentially the same problem, after years of treating them separately.
Where are inverted indexes used?
They are the most widely used structure in document retrieval and sit at the centre of web search engines, which use them to find the documents containing a query's words and then rank those documents by relevance. Several general-purpose mainframe database systems, including ADABAS, DATACOM/DB and Model 204, were built on inverted-list designs.
The idea is older than computers. Concordances to important books, which list every place a word appears, were inverted indexes assembled by hand at great effort. In bioinformatics, inverted indexes help locate short fragments of sequenced DNA within a reference genome; because human DNA has more than 3 billion base pairs, an index of every short substring can run to tens of gigabytes.
What are the costs and failure points?
Every new or edited document has to be folded into many word lists at once, which is slower than simply appending it to a forward index. Large services often re-index on a schedule for this reason. Meanwhile the index must keep answering queries while it is being updated, which creates the classic risk of two processes colliding. Spread the index across many machines and keeping everything consistent becomes harder still.
There is also a limit to what it knows. An inverted index matches the words it was built from. Whatever counts as a word, how capitalisation and spelling variants are handled, and what extra information is stored all decide what the search can and cannot find. A Boolean index cannot rank at all; ranking needs more signals layered on top.
What does it teach about thinking?
Organise information around the question you will ask most often. If you will mostly ask where something is, file things by what they contain, not by where they came from. Doing the sorting once, in advance, can turn an impossible search into an instant lookup.
Questions people ask
What is the difference between a forward index and an inverted index?
A forward index maps each document to the words it contains, which is easy to build but slow to search. An inverted index maps each word to the documents that contain it, which takes more work to build and update but makes searching fast. Search engines usually build the forward index first and then invert it.
How does an inverted index handle phrase searches?
Only if it stores positions. A record-level index lists which documents contain each word. A word-level, or full, inverted index also records where in each document every occurrence sits. With positions, the engine can check that the words of a phrase appear next to each other in the right order. This extra detail costs more space and more processing to build.
Does an inverted index rank search results?
Not by itself in its simplest form. A Boolean inverted index only says which documents match. To rank, the index can store how often each word appears in each document, and the search engine combines that and other signals into a relevance score.
The thinking behind it
Its chapter on search engine indexing explains how word lists and word positions make full-text search work.
Read or listen to Nine Algorithms That Changed the Future
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Inverted index — Wikipedia
- Search engine indexing — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.