The Inverted Index

Type a word into any search box — the results appear before your finger leaves the key. Billions of documents. Milliseconds. How?

The naive answer is embarrassingly wrong: read every document, check if the word is there, repeat. For a billion pages that would take minutes even on the fastest hardware. Nobody does this.

The real answer is a pre-built map called an inverted index. Instead of "document → words it contains," you flip it: word → list of documents that contain it. Each entry in that list is called a postings list, and each item in the list is a posting — a document identifier, sometimes with extra data like the word's position or how often it appears.

Building the index is expensive — you read every document exactly once, tokenize it, and record where each token appears. But once the index is built, answering a query is just a lookup: find the term, grab its postings list. For a multi-word query you intersect the lists of each term. Intersection of two sorted lists of length $n$ and $m$ takes $O(n + m)$ time — fast, regardless of how many documents you never had to touch.

The inverted index is not a new idea. Early information-retrieval systems from the 1960s used it. What changed is scale: modern engines hold indexes measured in petabytes, sharded across thousands of machines. The core idea, however, is identical to what you will build in the demo below.

The demo below pre-loads four short documents. Click Build index to tokenize them and construct the postings lists. Then type one or more words in the query box and click Search — the engine intersects the relevant lists and highlights every matching document.

<!-- {{c_html_intro}} -->
<div class="toolbar">
  <button id="btn-build" type="button">{{btn_build}}</button>
  <label class="show-label">
    <input type="checkbox" id="chk-postings"> {{chk_label}}
  </label>
</div>
<div id="docs-area" class="docs-area"></div>
<div id="index-area" class="index-area hidden"></div>
<div class="query-row">
  <input id="query-input" type="text" placeholder="{{input_placeholder}}">
  <button id="btn-search" type="button" disabled>{{btn_search}}</button>
</div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
.toolbar { display: flex; align-items: center; gap: .7rem; margin-bottom: .6rem; flex-wrap: wrap; }
.show-label { font-size: 13px; display: flex; align-items: center; gap: .3rem; cursor: pointer; }
.docs-area { display: grid; gap: .5rem; margin-bottom: .7rem; }
.doc-card { background: #f0f4f8; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .7rem; }
.doc-card.hit { background: #d4edda; border-color: #a3cfb3; }
.doc-id { font-weight: 700; color: #1d3557; margin-bottom: .2rem; font-size: 12px; }
.doc-text { line-height: 1.45; }
.doc-text mark { background: #ffe066; border-radius: 3px; padding: 0 2px; }
.index-area { margin-bottom: .7rem; background: #f8f9fb; border: 1px solid #dde3ea;
              border-radius: 8px; padding: .5rem .7rem; }
.index-area.hidden { display: none; }
.index-title { font-weight: 700; font-size: 12px; color: #555; margin-bottom: .35rem; }
.postings-grid { display: grid; grid-template-columns: auto 1fr; gap: .18rem .6rem; align-items: baseline; }
.pt { font-family: ui-monospace, monospace; font-size: 12px; color: #1d3557; font-weight: 700; white-space: nowrap; }
.pl { font-family: ui-monospace, monospace; font-size: 12px; color: #444; }
.pl .active-doc { color: #0a7d33; font-weight: 700; }
.query-row { display: flex; gap: .5rem; }
input[type=text] { flex: 1; padding: .38rem .6rem; border: 1px solid #adb1b8; border-radius: 7px;
                   font: 14px system-ui; min-width: 0; }
.status { margin-top: .5rem; font-weight: 600; min-height: 1.3em; font-size: .95rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #555; }

// Code not found

Notice what happens with multi-word queries: each extra term shrinks the result set because only documents that contain all words survive the intersection. Checking the "Show postings" box lets you watch exactly which lists are being walked. A brute-force scan would read every document for every query; the index reduces the work to reading only the relevant postings lists — typically a tiny fraction of the corpus.

Building the index requires reading every token in every document exactly once. If the corpus has $N$ total tokens across all documents, the build cost is $O(N)$. After sorting the postings lists (also $O(N \log N)$ in the number of postings) the index is ready.

Querying a single term returns its postings list in $O(1)$ (a hash-table lookup) or $O(\log V)$ (a B-tree lookup, where $V$ is the vocabulary size). That list has $k$ entries, so fetching all postings costs $O(k)$ — and $k$ is typically far smaller than the corpus size.

Intersecting two sorted postings lists of lengths $k_1$ and $k_2$ takes $O(k_1 + k_2)$ time with a simple two-pointer merge. Chaining $t$ terms costs $O(k_1 + k_2 + \dots + k_t)$. Because you process only the lists of matching terms, the work is proportional to the answer size, not the corpus size. A query that matches 0.01 % of a billion-document corpus touches roughly 0.01 % of the total postings — the rest are never read.

Space is $O(N)$ too: each token occurrence becomes one posting, so the total number of postings equals the total number of token occurrences in the corpus.

The catch is freshness: updating an immutable sorted file is expensive. Real engines write new postings into small in-memory buffers (called delta indices or journal indices), then periodically merge them into the main index in a process called segment merging — the same idea used in pattern matching and log-structured storage. This keeps write throughput high while reads remain fast.

The inverted index is one of the most widely deployed data structures in computing:

• Web search: Google, Bing and every major search engine maintain petabyte-scale inverted indexes, sharded across thousands of servers. The index is what lets them answer queries in under 200 milliseconds globally.
• Database full-text search: PostgreSQL's tsvector, MySQL's FULLTEXT index, and Elasticsearch all implement variants of the inverted index to make WHERE content LIKE '%word%' queries orders of magnitude faster.
• Code editors and IDEs: "Find all references" and "Go to definition" features are powered by in-memory inverted indexes built when you open a project. The same structure underlies tools like ripgrep.
• E-commerce and faceted search: when you filter by brand, price range, and color simultaneously, the engine intersects three postings lists — one per facet value.
• Genomics: sequence databases use inverted-index-like structures (k-mer indexes) to find which genomes contain a given short sequence, enabling fast alignment in tools like BLAST.

Whenever you need to answer "which items contain this term?" over a large corpus without scanning everything, an inverted index — or a close relative — is the right tool. It sits at the heart of pattern matching algorithms and is the backbone of modern information retrieval.

The inverted index is a beautiful trade-off: pay a one-time cost to read every document and record where every word appears; thereafter, answer any query in time proportional to the number of matching documents, not the size of the corpus.

That trade-off is the reason search boxes feel instant. It is also, at its core, a lesson about algorithm design: the right pre-processing step can turn an intractable scan into a trivial lookup. The next time a result appears before you finish typing, you are seeing sixty years of that idea at work.