What is an inverted index in a search engine, and how does it differ from a forward index?
answer
- Think about which way the mapping points
- Scanning every document is far too slow
- Like the index at the back of a book
- Term to documents, not document to terms
- Two parts: dictionary plus postings lists
basics
~20 sAn inverted index maps each term to the list of documents containing it, so a query is a dictionary lookup instead of a scan over documents. A forward index maps each document to its terms — the natural storage direction.
solid answer
~40 sAn inverted index flips the natural storage direction. A **forward index** maps each document to the terms it contains — the shape you get if you simply store the documents. An **inverted index** maps each *term* to a **postings list**: the sorted document IDs where that term occurs, usually with a per-document frequency and often token positions. A query for one word becomes a single dictionary lookup plus a walk of one list, rather than reading every document. Multi-term queries intersect or union postings lists, and scoring reuses the counts already stored there. The price is paid at index time: text is analysed once, the term dictionary is built sorted, postings are compressed, and updates become comparatively expensive. Forward-oriented structures do not disappear — engines keep document-oriented data for highlighting, sorting and faceting.
code
json · 6 lines// forward: document -> terms
{ "doc": 3, "terms": ["fast", "search", "engine"] }
// inverted: term -> sorted postings
{ "search": { "doc_freq": 3, "docs": [3, 9, 14] },
"engine": { "doc_freq": 2, "docs": [3, 27] } }go deeper
Be able to define both directions in one sentence each and name the two parts of an inverted index: a term dictionary and postings lists of document IDs. The book-index comparison is a fine way to open.
Explain why sorted document IDs turn boolean queries into a merge of sorted lists, and which statistics the index stores so that ranking needs no extra passes over the text.
Show you know the write-side consequences: analysis is fixed at index time, single-document updates are expensive, and engines work around that with immutable index units, tombstoned deletes and background merging.
Own the framing that a search system is several indexes at once — inverted for matching, columnar and per-document for sorting, faceting and highlighting — and that each one is a separate storage and latency budget you choose to spend.
## The problem A search engine must answer "which documents contain this word?" over millions or billions of documents, in milliseconds, for many concurrent users. Reading every document and testing it is linear in the size of the whole corpus, and the corpus is the largest thing in the system. The inverted index exists to make query cost proportional to the number of *matching* documents rather than to the number of *stored* documents. ## The forward index: document → terms If you store documents the obvious way, you have a forward index. Document 7 is a record; from its ID you can retrieve its text, or the list of terms it produced after analysis. This direction answers "what is in document 7?" in one lookup and answers "which documents contain *ranking*?" only by examining every record. ## The inverted index: term → documents Inverting means building the transpose of that relation. Conceptually you take every (document, term) pair, sort by term instead of by document, and group. The result has two parts: - **Term dictionary** — every distinct term in the corpus, held in sorted order, each entry carrying the term's document frequency (how many documents contain it) and a pointer to where its postings live. - **Postings lists** — for each term, the ascending list of document IDs containing it, typically with the term frequency in that document and, when enabled, the token positions and character offsets of each occurrence. So `search → [3, 9, 14, 27]` says exactly which documents to consider, and nothing about the other millions. ## Why this makes queries cheap Three properties fall out of the shape: 1. **Selective lookup.** A one-word query touches one dictionary entry and one list. Work scales with the number of hits, not the corpus. 2. **Cheap set algebra.** Because postings are sorted by document ID, a boolean AND is a merge of two sorted lists — linear in the shorter one when skip structures are present — and an OR is a merge union. This is why boolean queries over an inverted index are fast without any per-document work. 3. **Scoring data is already there.** Ranking models need the term frequency in the document, the document frequency of the term, and the document's length. The first two are stored in the index itself, so relevance scores are computed from numbers already being read, not by re-parsing text. ## What forward structures are still for An inverted index is a poor fit for questions that start from a document. "Show me every term in document 7 with its frequency" and "sort these 10,000 hits by price" and "count hits per category" all read *per document*. Engines therefore keep forward-oriented structures alongside the inverted one: a per-document term list (often called a term vector) for highlighting and more-like-this, a columnar per-document value store for sorting, faceting and aggregation, and the original stored content for returning results. A mature search engine is not one index; it is an inverted index plus several forward ones, each earning its storage. ## What it costs - **Build cost.** Text is analysed once, the pairs are sorted, the dictionary and postings are written. That work is real and happens on the write path. - **Storage.** Postings, and especially positions, are a substantial fraction of index size. Compression is not optional. - **Update rigidity.** Inserting one document touches the postings list of every term it contains. Most engines therefore build small immutable index units and merge them in the background rather than editing lists in place, which is why updates are visible only after a commit or refresh and why deletes are usually recorded as tombstones first. - **Analysis is baked in.** What you indexed is what you can find. Change the tokenizer or the stemmer and the existing terms are wrong; you must rebuild. ## How to say it in an interview Name both directions, name the two parts (dictionary and postings), say why sorted document IDs make boolean queries a merge, and mention that the index also carries the statistics ranking needs. Then add the honest trade-off: fast reads bought with index-time work and expensive in-place updates. That last sentence is what separates a memorised definition from understanding.
- If the inverted index is so much better for search, why do engines keep document-oriented structures at all?Because some questions start from the document. Highlighting needs the terms and offsets of one specific document; sorting and faceting need one field's value for every hit, read per document. Those are answered by forward structures — term vectors and a columnar per-document value store — plus the stored original content for returning results. The inverted index would have to be scanned end to end to answer them.
- What happens to an inverted index when a single document is updated?Logically, every term in that document has a postings list that must change, which is expensive in place. Most engines avoid it: they write new immutable index units, mark the old document as deleted with a tombstone so it is filtered from results, and reclaim the space later when background merging rewrites the affected units.
- Why does query latency depend more on how common a term is than on how large the corpus is?Because work is proportional to postings read, not documents stored. A rare term has a short list and finishes immediately; a very common term has a list proportional to the corpus and is the expensive case. That asymmetry is why stopword handling, term-frequency-aware query planning and early-termination algorithms all target the common terms.
It is the index at the back of a textbook. The chapters themselves are the forward view; the index at the back lists each concept once with the page numbers that mention it, so you never read the book to find a word.
saying these in an interview costs you the question
- Says the inverted index stores documents in reverse order
- Claims search reads each document and filters it
- Thinks it is just a hash map from document ID to text
- Believes an inverted index makes single-document updates cheap
- Assumes no forward structures exist alongside it