Inverted Index: How Search Engines Find Your Keywords

WHY IT EXISTS To solve the problem of finding a word within a huge collection of documents without reading every single one. Linearly scanning millions of documents for a keyword is too slow for interactive applications like search. An inverted index provides a shortcut.

THE MENTAL MODEL Think of the index at the back of a textbook. The book's pages are your documents. Instead of flipping through every page to find the term "Byzantium," you go to the index, find "Byzantium," and get a list of page numbers: 42, 113, 205. An inverted index does exactly this, but for words and documents.

HOW IT WORKS An inverted index consists of two parts. First, a vocabulary (or lexicon) which is a list of all unique terms found across all documents. Second, for each term, a "postings list" which is a list of identifiers for the documents that contain that term. When you search for "database", the system looks up the term in the vocabulary and instantly gets the list of all documents that contain it, avoiding a full scan.

WHEN TO USE IT Use an inverted index for any system requiring fast full-text search, where read performance is the priority. It's the fundamental data structure for document retrieval systems, powering search engines, log analysis platforms like Elasticsearch, and modern databases with full-text search capabilities.

WHEN NOT TO USE IT Avoid this structure for write-heavy workloads where documents are constantly being added or modified. Every write operation forces a costly update to the index, which can become a major performance bottleneck. For simple lookups by a known document ID, a standard index or hash map is more efficient.

ONE CANONICAL EXAMPLE A web search engine is the classic example. It crawls billions of web pages (documents) and builds a massive inverted index. The terms are the words from those pages, and the postings lists contain the URLs. When you search, the engine looks up your keywords in this index to quickly find and rank relevant pages.