Why is it called inverted?

It reverses the document-to-terms relationship into a term-to-documents relationship.

Does an inverted index store the original document?

It may coexist with stored source fields, but the postings structure itself does not necessarily contain the complete original content.

Can it support ranked results?

Yes. Stored occurrence and collection statistics can support scoring, while the ranking formula remains a separate choice.

AI Glossary / Retrieval and knowledge systems / Intermediate

Inverted index

Definition

An inverted index is a search data structure that maps terms to the documents or records in which they occur. Each term points to a postings list containing relevant document identifiers and, optionally, information such as occurrence counts or positions. It lets a search system locate matching material without rereading every document for each query.

What it means

A document naturally gives you a sequence of words. An inverted index reverses that relationship: starting with a word, you can find the documents that contain it. This arrangement supports efficient term-based search over large collections.

The index is a representation of the collection, not the complete source content or a relevance judgment. What it can retrieve depends on which fields were indexed and how text was processed. A word absent from the index might be missing from the source, excluded by preprocessing or present in material that was never successfully indexed.

How it works

During indexing, the system extracts text, tokenizes it and applies specified normalization rules. It records each term's occurrences against document identifiers, then organizes the postings so they can be accessed and combined efficiently. Repeated occurrences may be represented by a frequency or a list of positions rather than duplicate document identifiers.

At query time, the system looks up query terms and processes their postings. AND can intersect document lists; OR can combine them. Ranked retrieval can use stored statistics to score candidates. A positional index additionally supports checks for phrases and proximity.

Changes to documents must be reflected in the index through an update process. Storage, compression, indexing time and query speed are related engineering choices, so an index is not free to build or maintain.

Three practical examples

1. An internal search engine finds documents containing a project code by looking up the code's postings rather than scanning all file contents.

2. A support portal uses term frequencies and document statistics from an index to rank articles matching a user's query.

3. An archive uses positional postings to distinguish an exact phrase from documents that merely contain the same words far apart or in a different order.

Think of it this way

Think of the index at the back of a book. Starting with a topic, you see where it appears instead of turning every page. A digital inverted index applies a related principle to many documents and can store much more detail about each occurrence. The index helps locate material; it does not determine whether the passage answers your question correctly.

Worked example

Consider three invented documents after simple lowercasing and space-based tokenization. D1 is red boat floats, D2 is blue boat sails, and D3 is boat red paint. Number token positions from one.

The term red has positional postings D1 at position 1 and D3 at position 2. Boat has D1 at position 2, D2 at position 2 and D3 at position 1. Blue has D2 at position 1.

For red AND boat, intersect the document sets {D1, D3} and {D1, D2, D3}. The result is {D1, D3}. For red OR blue, combine {D1, D3} with {D2}, giving all three documents.

For the exact phrase red boat, check that a boat position immediately follows a red position. D1 qualifies because positions 1 and 2 have the required order. D3 fails because boat precedes red. A document-only index could identify D1 and D3 as candidates but could not establish this phrase relationship from membership alone.

The example assumes the stated tokenization and complete indexing. Different handling of punctuation, fields or token positions would need to be accounted for explicitly.

Illustrative case study

Fictional case: Alder Records notices that new policy documents are visible in storage but absent from search. Engineers trace the problem to an indexing job that failed to extract text from a new file format.

They repair extraction, rebuild the affected index entries and verify term and phrase queries against the source documents. The team also adds checks for indexing delays and extraction failures. Improving the ranker would not have solved this issue because the relevant documents had never entered the searchable representation.

Common misconceptions and mistakes

An inverted index is not a ranking algorithm. It supplies information that different retrieval models can use. It also does not automatically provide semantic matching between words that never share indexed representations.

A posting is not necessarily just a document identifier; richer indexes can store frequencies, positions and field information. Phrase matching cannot be inferred from term co-occurrence alone. An index may lag behind source updates, and removing a source document requires the search system to handle its indexed representation appropriately. Access controls must also be enforced when retrieving results.

Business use

Inverted indexes are useful when applications need efficient keyword, phrase or structured text search. Design the indexed fields and text analysis around the queries users need to express. Retain identifiers that reliably connect results back to their source records.

Monitor extraction coverage, update latency and search behavior after configuration changes. Test exact codes, common words, punctuation and representative phrases, since analysis choices can change what matches. Assess index size and maintenance effort alongside query latency. When combining lexical and vector retrieval, evaluate their complementary strengths rather than assuming either representation makes the other unnecessary.

Check your understanding

Two terms occur in the same document. Does a document-only inverted index prove that they appear next to each other?

Answer: No. It proves co-occurrence in that document. Phrase verification requires positions or another representation that captures the required order and adjacency, or a separate source-content check.

Related terms

Tokenization
Positional index
postings list
document identifier
term frequency
Boolean query
BM25 and index compression

Learn next

build a tiny inverted index by hand, then add token positions. Compare AND, OR and phrase queries. Finally, change one preprocessing rule and trace how both the stored postings and matching queries must change together.

Sources

Primary sources: Manning, Raghavan and Schuetze, Introduction to Information Retrieval, A first take at building an inverted index: https://nlp.stanford.edu/IR-book/html/htmledition/a-first-take-at-building-an-inverted-index-1.html

The same authors, Processing Boolean queries: https://nlp.stanford.edu/IR-book/html/htmledition/processing-boolean-queries-1.html

The same authors, Positional indexes: https://nlp.stanford.edu/IR-book/html/htmledition/positional-indexes-1.html

Previous: Inverted Dirichlet distribution Next: IPA