How does an inverted index work?

An inverted index is a data structure used to efficiently map terms (like words or numbers) to the documents or records where they appear. Unlike a forward index, which lists the terms contained in each document, an inverted index flips this relationship: it starts with terms and points to the documents that include them. This structure is fundamental to search engines and databases, enabling fast lookups for queries like “find all documents containing the word 'apple.’” At its core, an inverted index consists of two main components: a dictionary of unique terms and postings lists that link each term to the documents (and often positions within those documents) where it occurs.

To build an inverted index, documents are first parsed into individual terms through tokenization (splitting text into words, symbols, or phrases). For example, the sentence “Hello, world!” might become ["hello", “world”]. These terms are then normalized (e.g., lowercased or stemmed) to ensure consistency. Stop words like “the” or “and” are often removed to save space. Each term is then mapped to a postings list containing document IDs and optionally positional data. For instance, if the term “apple” appears in document IDs 1 and 3, the postings list for “apple” would store [1, 3]. Positional data might track that “apple” appears at character offsets 10 and 25 in document 1. This process allows the index to quickly answer questions like “Which documents contain 'apple’?” or “Where does ‘apple’ appear in document 1?”

When a user submits a search query, the inverted index retrieves the postings lists for each term in the query. For a single-term query like “apple,” the system returns the list of documents associated with that term. For multi-term queries like “apple pie,” the index intersects the postings lists of “apple” and “pie” to find documents containing both terms. Positional data can further refine results by verifying that the terms appear in sequence (e.g., “apple pie” as a phrase). Ranking algorithms like TF-IDF or BM25 then score the results based on factors like term frequency or document relevance. For example, a document where “apple” appears five times might rank higher than one where it appears once. Optimizations like compression (e.g., delta encoding for document IDs) and distributed storage (sharding across servers) ensure the index scales to handle large datasets efficiently. Tools like Elasticsearch and Apache Lucene rely on inverted indexes to power fast, flexible search capabilities in applications ranging from e-commerce to log analysis.