Inverted Index
An inverted index is a structure that maps each term in a vocabulary to the list of documents containing it, so that a query can be answered by reading the lists for its own terms rather than by examining every document.
The name describes a reversal. The natural arrangement of a collection is document-to-terms: here is a document, here are the words in it. An inverted index stores term-to-documents: here is a word, here is everywhere it occurs. Everything the structure is good at follows from that inversion.
The list stored against a term is called a posting list, and each entry a posting. A posting records at minimum which document contains the term, and usually how often, and often at which positions — positions being what allows a phrase query to require that two terms appear adjacently rather than merely in the same document.
The consequence is that query cost scales with how many documents contain the query’s terms, not with the size of the collection. A rare term is cheap to search however large the corpus is. A term present in most documents is expensive, which is why very common words are sometimes excluded from the index entirely.
The structure is decades old and remains the foundation of general-purpose text search.
In practice
An inverted index is built by processing each document through a fixed sequence — splitting text into terms, normalising them, optionally reducing them to stems, and discarding those on a stop list — then recording the surviving terms against the document’s identifier.
That pipeline determines what can ever be matched. The same processing must be applied to the query, because the index contains processed terms and only processed terms. A mismatch between the two removes matches silently: a query term that stems differently from the way the corpus was stemmed will not be found, and the text plainly containing the word is still not returned.
The structure finds candidates and does not rank them. A posting list says which documents contain a term; deciding which of them to return first requires a scoring function applied over the postings and the collection-wide statistics the index also maintains. See BM25.
Its operational profile is the complement of a vector index’s. Adding a document means appending to the posting lists of its terms, which is incremental and cheap, and there is no model to version and no space to invalidate. Deletion is usually recorded rather than performed, with the lists compacted later. Because scoring depends on collection statistics, a document’s score can change as unrelated documents are added. See vector index.
Fields are handled by indexing them separately, so a title and a body become distinct term spaces over the same document and can be weighted differently.
Commonly confused with
Sparse retrieval. The method; the inverted index is the structure that makes it fast. Sparse retrieval names a family of term-matching approaches, and every practical member of it is implemented over an inverted index. See sparse retrieval.
BM25. A scoring function computed over the candidates the index supplies. The index locates, the function orders. The two are so consistently used together that they are frequently described as one component.
Full-text index. The product-level name for the same structure in databases and search engines. It describes an exposed feature; “inverted index” names the implementation.
Vector index. Answers nearest-neighbour queries over dense vectors and can match text that shares no terms with the query. The inverted index answers term-containment queries exactly and cannot. Systems running both over one corpus keep two structures in step.
Forward index. The uninverted arrangement, mapping a document to its own terms. Search engines commonly maintain one alongside the inverted index, because some operations — highlighting a snippet, recovering a document’s field values — need to read a single document rather than a single term.
Usage notes
“Index” alone is ambiguous in retrieval writing and may mean this structure, a vector index, a database index, or a billable product resource. Where both retrieval families are under discussion the word needs qualifying every time.
A term in the index is not a word. It is whatever the analysis pipeline produced, which may be a stem, a lowercased fragment, an n-gram, or a token from a character-level scheme. Reasoning about what the index contains in terms of words is reliable only for simple configurations.
Learned sparse methods use the same structure while replacing counted term weights with model-produced ones, and may record terms the document does not literally contain. The index is unchanged; what is written into it is not.
“Inverted” occasionally confuses on first encounter, since nothing about the index is upside-down and the arrangement it inverts is rarely stated. The word is historical and universal, and no clearer alternative is in use.