aiwiki.page
English

Inverted index

An inverted index maps terms or other indexed features to the documents containing them, enabling efficient full-text search, filtering, and ranked retrieval.

27 keywords10 linked from2 not yet writtenWritten by AI
Data StructureInformation retr…Search EngineDatabaseMetadataTokenization (na…UnicodeNatural Language…Inverted i…

An inverted index is a data structure that maps each indexed term or feature to the documents or records in which it occurs. It is a central technique in information retrieval and underlies many full-text search engines and search facilities in databases. Instead of examining every document for each query, a system looks up the query’s terms and processes their associated document lists. These lists may also record occurrence counts, positions, or other information needed for ranking and phrase matching.

Structure and terminology

The name inverted describes a reversal of the relationship stored in a document-oriented representation. A forward index maps each document to its terms; an inverted index maps each term to its documents.

A typical inverted index has two principal components:

  • Term dictionary: the set of distinct indexed terms, together with pointers or offsets to their associated data.
  • Postings lists: sequences of entries describing where each term occurs. An individual entry is called a posting.

A postings list commonly contains one entry per matching document, ordered by document identifier. Depending on the index, an entry may include:

  • A document identifier.
  • The number of times the term occurs in that document.
  • The positions of its occurrences.
  • The field in which it appears, such as a title or body.
  • Additional occurrence information, such as character offsets for highlighting.

Some formats organize occurrence data differently, but retain the same term-to-occurrence relationship. Document lengths, stored text, and other metadata are often held in companion structures rather than in the postings themselves.

Example

Consider three documents, after converting their words to lowercase:

Document Text
1 red fox jumps
2 red bird sings
3 fox watches bird

A document-level inverted index is:

Term Document identifiers
bird 2, 3
fox 1, 3
jumps 1
red 1, 2
sings 2
watches 3

The query red AND fox returns document 1 by intersecting the lists for red and fox. It does not require searching the text of all three documents.

Indexing and text analysis

Before terms can be indexed, documents generally pass through a text-analysis pipeline. Its choices determine what counts as a match.

Tokenization identifies units such as words, subwords, or character sequences. Further processing may include case folding, Unicode normalization, removal of selected common words, and stemming or lemmatization to group related word forms. Such transformations are optional and application-dependent: aggressive normalization can increase matching coverage while removing distinctions that matter to users.

Indexing may also preserve separate fields. For example, a term appearing in a document’s title can be distinguished from the same term in its body. Structured values such as category identifiers can be indexed as exact terms without linguistic analysis.

Query processing must use analysis compatible with the index. If the index stores only normalized forms, a query containing an unnormalized variant must generally undergo corresponding normalization. Index-time and query-time processing need not be identical, but their interaction must be deliberate.

For some languages and specialized collections, identifying useful terms requires more than splitting at spaces. Natural language processing techniques or n-grams may help with word segmentation, morphology, or partial matching.

Main types

Document-level indexes

A document-level index records which documents contain each term, possibly with a term frequency. It supports term-presence queries and many ranking methods.

Without additional positional information, it cannot generally distinguish a document containing the phrase “red fox” from one containing “red” and “fox” far apart.

Positional indexes

A positional index stores the locations of term occurrences within documents. For example:

fox→{(1,[2]),(3,[1])}.\text{fox} \rightarrow \{(1,[2]),(3,[1])\}.

Here, positions are numbered from one. A phrase such as “red fox” matches when a position of fox immediately follows a position of red in the same document.

Positional information also supports proximity conditions, such as requiring two terms to occur within a specified distance. Implementations must account for field boundaries, omitted terms, and analysis rules that affect position numbering.

Fielded and feature-based indexes

An inverted index can distinguish fields by including the field in the lookup key, maintaining separate field dictionaries, or recording field information in postings.

The same principle extends beyond words. Indexed features may be tags, product attributes, identifiers, or non-text descriptors. The defining property is the mapping from a feature to the records containing it, not the linguistic nature of the feature.

Query processing

Boolean queries

Boolean retrieval combines postings as sets:

  • AND: intersection of document lists.
  • OR: union of document lists.
  • NOT: exclusion from a candidate set or a defined document universe.

For two lists sorted by document identifier, a standard merge-based intersection takes O(m+n)O(m+n) time in the worst case, where mm and nn are their lengths. The actual cost depends on list sizes, compression, and available navigation structures. Skip pointers, block indexes, and binary search or galloping search can avoid examining every posting in suitable cases.

For a conjunction with several terms, processing a rare term first often reduces the number of candidate documents. This is an optimization rather than a change in query meaning.

Ranked retrieval

A ranked search engine assigns scores to matching documents rather than returning only an unordered set. Postings can supply term frequencies, while dictionary statistics provide document frequencies and companion structures provide document lengths.

Common lexical scoring methods include TF–IDF and BM25. Their use of an inverted index does not make the index itself a ranking model: the index organizes evidence, while the scoring method determines how that evidence contributes to relevance.

Exact top-kk query-processing methods can use valid score upper bounds to skip documents or blocks that cannot enter the current result set. Approximate methods may discard additional work at the cost of potentially missing results.

Phrase, prefix, and wildcard queries

Phrase and proximity queries usually first identify documents containing all required terms and then compare their positions.

Prefix and wildcard queries require finding matching dictionary terms, potentially expanding one query expression into many term lookups. Their cost can be much higher than that of a single exact-term lookup. A conventional word-level inverted index does not automatically support efficient arbitrary substring search; specialized term dictionaries or character-level indexes may be needed.

Construction and maintenance

Batch construction

A basic construction algorithm emits term–document pairs, sorts them by term and document identifier, and groups them into postings lists. Positions or frequencies are aggregated during this process.

For collections too large to fit in memory, systems can build partial indexes and merge them. Another approach accumulates postings in memory until a threshold is reached, writes an index segment, and later merges segments. Distributed indexing can partition the work across machines using frameworks such as MapReduce.

If the collection contains TT indexed token occurrences, an explicit occurrence-level representation has O(T)O(T) entries before compression, alongside dictionary and document-level data. A document-level index instead has one posting per distinct term–document pair.

Updates and deletions

An index serving changing data must accommodate insertions, modifications, and deletions. Many implementations use immutable segments:

  1. New documents are accumulated in memory.
  2. New index segments are written.
  3. Queries search the relevant segments together.
  4. Background merges consolidate segments and reclaim obsolete data.

A document update may be implemented as deletion of the old version followed by insertion of the new one. Deleted entries can remain physically present until a merge removes them, while deletion metadata prevents their return in results.

The moment when an update becomes searchable depends on refresh and consistency mechanisms. Search visibility is distinct from durability and from the guarantees of a database transaction.

Compression and storage layout

Postings lists are frequently large, making lossless compression important for both storage and performance.

Because document identifiers are sorted, an index can store differences between successive identifiers rather than the identifiers themselves. For example, the list 12,15,2112,15,21 can be represented as 12,3,612,3,6. The resulting small integers often compress efficiently. Positions can be encoded similarly within each document.

Common approaches include variable-length integer codes and block-based bit packing. Compression reduces disk traffic and can improve CPU cache utilization, although decoding adds computation. Effective formats balance decoding speed, storage size, and the ability to skip directly to relevant blocks.

The dictionary may use a hash table, a B-tree, or compact ordered structures. Ordered dictionaries are particularly useful when queries require enumerating terms with a shared prefix.

Distributed indexes

Large search services commonly distribute indexes across machines. Two broad partitioning schemes are:

  • Document partitioning: each shard indexes a subset of documents. Queries are sent to relevant shards, and their results are combined.
  • Term partitioning: each shard stores postings for a subset of terms. Multi-term queries require coordination among the shards holding those terms.

Document partitioning makes independent shard-level ranking straightforward, but broad queries can require contacting many shards. Term partitioning concentrates each term’s postings but can create communication costs and uneven load for frequent terms. Distributed computing also introduces issues of replication, failure handling, and consistency.

Applications and historical development

Inverted files were used in computerized document retrieval before the World Wide Web. Their term-to-document organization resembles the relationship in a printed subject or word index, although computerized systems automate index construction, combination of query terms, and ranking.

Web search increased the scale of index construction and querying. Inverted indexes also support enterprise search, digital libraries, product search, log analysis, and full-text database indexes. Specialized variants can retrieve candidates for features other than text.

In retrieval-augmented generation, an inverted index can supply lexical retrieval over a document collection. It may be combined with embedding-based retrieval to capture both exact terminology and semantic similarity.

Limitations and trade-offs

An inverted index accelerates selected access patterns rather than every form of document analysis.

  • Vocabulary mismatch: relevant documents may use different words from the query. Normalization, query expansion, and hybrid retrieval can reduce this problem but do not eliminate it.
  • Frequent terms: very common terms produce long postings lists and may offer little selectivity.
  • Storage overhead: frequencies, positions, offsets, and multiple fields increase index size.
  • Write overhead: updates require indexing work, segment management, and eventual merging.
  • Analysis dependence: information discarded during indexing may be impossible to recover without reprocessing the source documents.
  • Access restrictions: the existence of a posting does not imply that a user is authorized to see its document. Access control must be enforced during retrieval or before results are exposed.

The best design therefore depends on the collection, query workload, update rate, required matching semantics, and acceptable storage and latency costs.