Introduction

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 nn and mm takes O(n+m)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.

Try It

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.

<!-- Main layout: toolbar (build + show-postings toggle), doc cards, index panel, query row, status -->
<div class="toolbar">
  <button id="btn-build" type="button">Build index</button>
  <label class="show-label">
    <input type="checkbox" id="chk-postings"> Show postings
  </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="e.g. fast search">
  <button id="btn-search" type="button" disabled>Search</button>
</div>
<div id="status" class="status"></div>

/* Styles: cards, postings grid, query row, status colours */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Four short documents — the corpus to be indexed */
const CORPUS = [
  { id: 'D1', text: 'The inverted index makes search fast and efficient.' },
  { id: 'D2', text: 'Full-text search relies on an inverted index for speed.' },
  { id: 'D3', text: 'An index maps every term to the documents that contain it.' },
  { id: 'D4', text: 'Search engines build an index once and query it many times.' }
];

/* Tokenise: lowercase, strip punctuation, split on whitespace */
function tokenize(text) {
  return text.toLowerCase().replace(/[^a-z0-9\s]/g, '').split(/\s+/).filter(Boolean);
}

/* Build the inverted index: term -> sorted list of doc IDs */
let INDEX = null;
function buildIndex(corpus) {
  const idx = {};
  for (const doc of corpus) {
    const tokens = tokenize(doc.text);
    const seen = new Set();
    for (const tok of tokens) {
      if (!idx[tok]) idx[tok] = [];
      if (!seen.has(tok)) { idx[tok].push(doc.id); seen.add(tok); }
    }
  }
  /* Sort each postings list for fast intersection */
  for (const k of Object.keys(idx)) idx[k].sort();
  return idx;
}

/* Two-pointer sorted-list intersection — O(k1 + k2) */
function intersect(lists) {
  if (lists.length === 0) return [];
  let result = lists[0].slice();
  for (let i = 1; i < lists.length; i++) {
    const b = lists[i];
    const merged = [];
    let ai = 0, bi = 0;
    while (ai < result.length && bi < b.length) {
      if (result[ai] === b[bi]) { merged.push(result[ai]); ai++; bi++; }
      else if (result[ai] < b[bi]) ai++;
      else bi++;
    }
    result = merged;
  }
  return result;
}

/* Render document cards, highlight hits and matched terms */
function renderDocs(hitSet, termsToMark) {
  const area = document.getElementById('docs-area');
  area.innerHTML = '';
  for (const doc of CORPUS) {
    const card = document.createElement('div');
    card.className = 'doc-card' + (hitSet && hitSet.has(doc.id) ? ' hit' : '');
    const idDiv = document.createElement('div');
    idDiv.className = 'doc-id';
    idDiv.textContent = doc.id;
    const textDiv = document.createElement('div');
    textDiv.className = 'doc-text';
    if (termsToMark && termsToMark.size > 0) {
      /* Regex-highlight all matched terms in the document text */
      const escaped = doc.text.replace(/[.*+?^${}()|[\]\\]/g, '\\amp;');
      const words = [...termsToMark].map(t => t.replace(/[.*+?^${}()|[\]\\]/g, '\\amp;'));
      const re = new RegExp('(' + words.join('|') + ')', 'gi');
      textDiv.innerHTML = doc.text.replace(re, '<mark>$1</mark>');
    } else {
      textDiv.textContent = doc.text;
    }
    card.appendChild(idDiv);
    card.appendChild(textDiv);
    area.appendChild(card);
  }
}

/* Render the postings panel; highlight active query terms */
function renderIndex(activeTerms) {
  const area = document.getElementById('index-area');
  if (!INDEX) { area.classList.add('hidden'); return; }
  area.classList.remove('hidden');
  const title = document.createElement('div');
  title.className = 'index-title';
  title.textContent = 'Postings lists (term → documents):';
  const grid = document.createElement('div');
  grid.className = 'postings-grid';
  const entries = Object.entries(INDEX).sort((a, b) => a[0].localeCompare(b[0]));
  for (const [term, docs] of entries) {
    const termEl = document.createElement('div');
    termEl.className = 'pt';
    termEl.textContent = term + ':';
    const listEl = document.createElement('div');
    listEl.className = 'pl';
    if (activeTerms && activeTerms.has(term)) {
      listEl.innerHTML = docs.map(d => `<span class="active-doc">${d}</span>`).join(', ');
    } else {
      listEl.textContent = docs.join(', ');
    }
    grid.appendChild(termEl);
    grid.appendChild(listEl);
  }
  area.innerHTML = '';
  area.appendChild(title);
  area.appendChild(grid);
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

/* Build button: construct index, unlock search */
document.getElementById('btn-build').addEventListener('click', () => {
  INDEX = buildIndex(CORPUS);
  renderDocs(null, null);
  const chk = document.getElementById('chk-postings');
  if (chk.checked) renderIndex(null);
  document.getElementById('btn-search').disabled = false;
  setStatus(i18nFmt('Index built — %n% unique terms.', { n: Object.keys(INDEX).length }), 'info');
});

/* Search button: look up each term, intersect postings lists */
document.getElementById('btn-search').addEventListener('click', () => {
  if (!INDEX) return;
  const raw = document.getElementById('query-input').value.trim();
  if (!raw) { setStatus('Type a query first.', 'bad'); return; }
  const terms = tokenize(raw);
  const missing = terms.filter(t => !INDEX[t]);
  if (missing.length > 0) {
    setStatus(i18nFmt('Term not in index: %t%', { t: missing.join(', ') }), 'bad');
    renderDocs(new Set(), null);
    const chk = document.getElementById('chk-postings');
    if (chk.checked) renderIndex(new Set(terms.filter(t => INDEX[t])));
    return;
  }
  const lists = terms.map(t => INDEX[t]);
  const hits = intersect(lists);
  const hitSet = new Set(hits);
  const termSet = new Set(terms);
  renderDocs(hitSet, termSet);
  const chk = document.getElementById('chk-postings');
  if (chk.checked) renderIndex(termSet);
  if (hits.length > 0) {
    setStatus(i18nFmt('Found %n% document(s): %docs%', { n: hits.length, docs: hits.join(', ') }), 'ok');
  } else {
    setStatus('No documents match all query terms.', 'bad');
  }
});

document.getElementById('chk-postings').addEventListener('change', (e) => {
  if (e.target.checked) renderIndex(null);
  else document.getElementById('index-area').classList.add('hidden');
});

document.getElementById('query-input').addEventListener('keydown', (e) => {
  if (e.key === 'Enter') document.getElementById('btn-search').click();
});

/* Initial render — show docs before the index is built */
renderDocs(null, null);
Result
Console

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.

The Real Complexity

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

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

Intersecting two sorted postings lists of lengths k1k_1 and k2k_2 takes O(k1+k2)O(k_1 + k_2) time with a simple two-pointer merge. Chaining tt terms costs O(k1+k2+⋯+kt)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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/inverted-index/Content licensed under CC BY-NC 4.0.