What is an Inverted Index and How Does It Work?

An inverted index is the core data structure powering text search systems. It reverses the typical document to terms relationship by mapping each term to a list of documents containing it. Think of it like a book index: instead of reading every page to find mentions of "database," you look up "database" in the index and get page numbers instantly.

The structure has two main components: a term dictionary storing all unique words (the vocabulary), and postings lists for each term containing sorted document identifiers (IDs). For example, the term "search" might map to a postings list of document IDs like [3, 47, 102, 891]. Production systems typically store additional metadata in postings: term frequency (how many times the term appears in each document), positions (which word offsets), and per field statistics for scoring.

This inversion enables sublinear lookup time. Instead of scanning all documents for a query term, you jump directly to its postings list. When you search for "distributed systems," the engine looks up both terms, retrieves their postings lists, intersects them (finding documents containing both), and returns results in milliseconds even across billions of documents. Google's web search uses this architecture to handle trillions of documents with retrieval latencies under 50 milliseconds per shard.

💡 Key Takeaways

•Term dictionary stores vocabulary (all unique terms), while postings lists map each term to sorted document IDs, enabling fast lookups without scanning all documents

•Production indexes store positions in postings (increasing size by 1.5 to 3 times) to support phrase queries like "distributed systems" and generate accurate snippets, versus doc only postings for simple Boolean matching

•Compression using delta encoding and block compression (like varint or PForDelta) reduces postings storage to 10 to 30 percent of raw token stream size, critical at scale

•Positional indexes enable phrase matching and proximity queries but cost more storage. Omit positions if you only need Boolean keyword matching to save 60 to 70 percent of postings space

•Typical Lucene style deployments achieve thousands of queries per second (QPS) per shard on commodity hardware when queries are selective and caches are warm, but throughput collapses on frequent term queries without pruning

📌 Examples

Amazon retail search maintains inverted indexes for hundreds of millions of products with separate fields for title, brand, and attributes. Query "usb c cable" looks up three terms, intersects their postings, and retrieves top matches in under 20 milliseconds per shard

Wikipedia CirrusSearch using Elasticsearch shows median query latencies of tens of milliseconds for keyword queries, with p95 around 100 to 200 milliseconds under normal load handling hundreds to low thousands of QPS

Twitter Earlybird achieved indexing latency under 10 seconds from tweet creation to searchable, with p99 query latencies around 100 milliseconds per shard despite massive query spikes on trending topics

← Back to Inverted Index & Text Search Overview