Inverted index in search engines

WHAT THIS TESTS This checks whether you understand the foundational data structure behind text search and why it makes search fast.

A GOOD ANSWER COVERS An inverted index maps each distinct term in a corpus to a postings list: the set of documents that contain that term, usually with extra information like term frequency and the positions where it appears. It is the inverse of a forward index, which maps each document to the list of terms it contains. To answer a query like dog AND cat, the engine looks up the postings list for dog and for cat and intersects them, immediately yielding matching documents.

WHY IT IS FUNDAMENTAL Without it, finding documents containing a word would require scanning the full text of every document, which is linear in the total corpus size and hopeless at scale. The inverted index turns search into a direct lookup plus set operations on relatively short postings lists, which is dramatically faster and is exactly what Lucene, and therefore Elasticsearch and OpenSearch, build at index time. It also enables relevance scoring, because the stored term frequencies and document frequencies feed ranking formulas like BM25.

COMMON WRONG ANSWERS Describing a forward index by mistake. Saying a relational database with a LIKE query or a B-tree on the text column would be equivalent; those cannot efficiently do arbitrary term matching across large text. Forgetting that positions enable phrase queries.

LIKELY FOLLOW-UPS How are postings lists compressed. How does analysis produce the terms. How does BM25 use the index. How are phrase queries answered using positions.

ONE CONCRETE EXAMPLE Indexing two documents, one saying the quick fox and one saying the lazy dog, produces postings like the to docs 1 and 2, quick and fox to doc 1, lazy and dog to doc 2. A search for fox jumps straight to its postings list and returns doc 1 without touching doc 2.