Inverted index

An inverted index is a data structure that maps from content — typically words or terms — to the locations where that content appears in a document collection. Unlike a forward index, which maps documents to their terms, the inverted index maps terms to documents, enabling efficient full-text search, phrase queries, and relevance ranking. It is the foundational data structure of search engines, document databases, and information retrieval systems, and its design reveals the fundamental tension between the sequential nature of text and the random-access nature of query resolution.

The construction of an inverted index involves tokenization — breaking text into discrete terms — and the creation of a postings list for each term, recording the documents (and often the positions within documents) where the term occurs. Query processing merges postings lists for multiple terms, which is efficient when the terms are rare but can become a bottleneck for common terms (so-called stop words). The inverted index is therefore not a neutral infrastructure; it is optimized for a specific distribution of query terms and document lengths, and its performance degrades when the query distribution diverges from the assumptions of its design.