When you type a word in a search engine, millions of pages that contain it reappear within milliseconds. It is tempting to imagine that engine “reading” your documents on the fly and comparing them with your query. It does not: scanning gigabytes of text on every search would take seconds, not milliseconds. The real speed comes from a data structure prepared in advance, the inverted index. This article explains how it is built, how it is compressed, and why it remains the heart of any search engine, from Elasticsearch to Google.
From dictionary to inverted index
A traditional book uses a forward index: we go to a page and find words there. The inverted index flips that relationship. Instead of associating pages with words, it associates each word (term) with the list of documents where it appears and, usually, with the exact position inside each one. That list of references is called a postings list. Thanks to this flip, answering “which documents contain ‘encryption’?” stops being a full scan and becomes looking up a single entry in a table.
Building the index is a costly, upfront process that runs once when a document enters the system (indexing). First comes tokenization: the text is split into minimal units called tokens. Then they are normalized (lowercasing, accent removal) and often a stemming or lemmatization step is applied, reducing word variants to a root so that “swim”, “swims” and “swimming” point to the same entry. The tokens are sorted and merged by document, generating the postings lists.
Why order matters
That postings lists are sorted by document identifier is not a whim. It enables three critical optimizations. First, fast intersection of several lists when your query has multiple terms (“encryption AND asymmetric”): with sorted lists you sweep them in parallel, advancing only the one that lags behind (intersection merge algorithm), avoiding unnecessary comparisons. Second, it enables delta compression: instead of storing every full ID, you store the difference from the previous one, which are small numbers that take fewer bits. Third, it enables skip pointers to jump over list sections that cannot contain a match.
The position inside the document is not a luxury either. Without it, an engine knows a document contains the word, but cannot tell the exact phrase “public key” apart from both terms appearing separately in different paragraphs. By storing the offsets of each token, phrase queries are resolved by checking that the positions of consecutive terms differ by a fixed offset. That is why we talk about positional indexes.
From bytes to ranking
The index does not only return which documents match: it decides which comes first. To do so, each document-term pair accumulates scores based on two ideas. Term frequency (TF) measures how often the word appears in the document; a document that repeats it is, in principle, more relevant. Inverse document frequency (IDF) penalizes terms that appear in almost every text (“the”, “of”), which barely discriminate. The most widespread combination is BM25, which applies non-linear saturation to TF (each extra occurrence is worth less beyond a certain point) and normalizes by document length so a long text does not win just for being long.
These scores are computed at query time over the postings lists, which is why those lists are kept in memory or in cached structures with very high hit rates. Adding a new document does not force a full rebuild: in-memory segment indexes accumulate and merge in the copy-on-write model typical of Lucene and Elasticsearch.
Compress to fit and to go fast
An inverted index usually takes 10 to 20 % of the original text size, and not by chance. Without compression it would fit, but disk access would become a bottleneck. The delta compression mentioned above combines with variable-length encodings (such as varint or gamma coding) that use more bits for the few large numbers and fewer for the many small ones. The goal is not just saving space: fewer bytes transferred from main memory means less latency, so compression and speed go hand in hand, against what one might intuit.
Choosing which vocabulary enters also shapes the size. Stop words are usually filtered because they do not discriminate; synonym dictionaries or n-gram tokenizers (letter fragments) allow search with tolerance to typos or in languages without clear word boundaries. Every decision is a trade-off between coverage and space.
Why it remains the centerpiece
That the inverted index is decades old has not made it obsolete. Modern search engines combine it with vectors and semantic search, but they almost never replace it: vector search provides approximate meaning, while the index provides accuracy, speed and metadata filtering. When you run a hybrid query in an engine like Elasticsearch, the exact-word part is resolved by an inverted index to which embeddings only add context. Understanding its architecture is, in practice, understanding how search engines think: not by reading documents, but by querying a dictionary built long before you arrived.
