Inverted Index

Definition

An inverted index maps each word to the list of documents that contain it, the reverse of a document listing its words. Search engines use it to find the documents matching a query quickly, without scanning every document.

In plain terms

A book’s index works the same way: look up a term, get page numbers. Building the index takes one pass over the documents (see Tokenization); answering a query then means looking up each query word and combining the lists: intersect them for “all words must appear”, merge them for “any word”.

The lists can also hold positions and counts, which supports phrase search and ranking with TF-IDF or BM25. An index is a copy made at a moment in time, so it can lag behind the documents unless it is updated.

Example

Three tiny documents: d1 “cheap flights”, d2 “cheap hotels”, d3 “flights to rome”.

The query “cheap flights” (both words) intersects [d1, d2] with [d1, d3] and returns d1, after looking at two lists and no document text.

Common misunderstandings

• “The index is the documents.” It is a derived structure; the documents live elsewhere.
• “The index is always up to date.” New and changed documents appear only after they are indexed.
• “A search reads every document.” The index exists precisely so that it does not.