Inverted Index

The index is logically split into two main parts: a dictionary of unique terms and a postings list for each term. The dictionary is a sorted list of all unique tokens found in the document collection. For each term, a postings list stores the identifiers of every document containing that term, along with metadata like term frequency and positional offsets for phrase matching.

Building an inverted index at scale typically uses Blocked Sort-Based Indexing (BSBI). The process involves:

• Collecting term-documentID pairs from each document.
• Sorting these pairs by term as the primary key.
• Grouping by term to create the final postings lists. This external sorting algorithm is critical for indexing corpora that vastly exceed available RAM.

To accelerate multi-term Boolean AND queries, postings lists often include skip pointers. These are intra-list shortcuts that allow the query engine to jump ahead to a specific document ID without scanning every entry. For example, when intersecting the postings list for 'machine' and 'learning', a skip pointer on the longer list can bypass thousands of irrelevant document IDs.

Postings lists are highly compressible. Since document IDs are stored in ascending order, they are converted to d-gaps (the difference between consecutive IDs). Small gaps are then encoded using variable-byte or Elias gamma coding to minimize storage. This drastically reduces the memory footprint and I/O cost, keeping the index in RAM for maximum performance.

A non-positional index stores only document IDs and term frequencies, sufficient for basic ranking functions like BM25. A positional index expands the postings to include the exact byte or word offset of each term occurrence. This added granularity is essential for phrase queries (e.g., 'artificial intelligence') and proximity operators, at the cost of roughly 2-4x larger index size.

While a static index is built offline, dynamic systems like Elasticsearch use a Log-Structured Merge (LSM) tree approach. New documents are written to a small, mutable in-memory buffer. When the buffer is full, it is flushed to disk as a new immutable segment. A background process continuously merges these smaller segments into larger ones, optimizing the index without blocking writes.

A retrieval paradigm that represents documents and queries as high-dimensional, mostly-zero vectors where non-zero dimensions correspond to explicit term weights. This sparsity enables efficient matching via inverted indices, as only the postings lists for query terms need to be traversed. Contrasts with dense retrieval, which uses compact embeddings and approximate nearest neighbor search.

The process of identifying relevant documents based on the exact overlap of words or character sequences between a query and a document. The inverted index is the primary engine for lexical matching, enabling sub-millisecond lookups. Its main limitation is the vocabulary mismatch problem, where relevant documents using synonyms or paraphrases are missed.

An exact-match retrieval model where queries are expressed as Boolean expressions of terms using operators like AND, OR, and NOT. The inverted index evaluates these queries by performing set operations on postings lists—intersecting lists for AND, merging for OR. This model returns documents that precisely satisfy the logical condition, with no relevance ranking.

A search technique requiring terms to appear in a document in the exact specified order and adjacency. Implemented using positional information stored in the postings list. For a phrase like 'machine learning', the engine retrieves the postings list for both terms and checks for adjacent positions, avoiding false matches where the words appear far apart.

A search engine component that processes raw text into a stream of tokens before indexing. It applies a tokenizer (splitting on whitespace/punctuation) and a chain of filters (lowercasing, stemming, stop word removal). The quality of the inverted index depends directly on analyzer configuration—aggressive stemming improves recall but may hurt precision.