Data & storage

Search Index

Instead of scanning every document for a query, a search engine looks up each term in a precomputed inverted index that maps terms straight to the documents containing them.

✗ The problem

Scanning every document doesn't scale

Naive full-text search reads every document, every time. Fine for 10 files — hopeless for millions.

for doc in allDocs {                // O(N) docs
  if doc.text.includes(query) {    // O(len) scan each
    results.push(doc);
  }
}
// 10M docs × 2KB text = gigabytes re-read on EVERY query

Cost is O(N × doc length) per query — it gets slower as the corpus grows, forever.

✓ How it works

Build the index once, query it many times

Tokenize every doc, then invert: for each term, store the list of doc ids that contain it (a posting list). A query looks up its terms and intersects the posting lists.

index = {
  "cat": [1, 3],
  "dog": [2, 3],
  "log": [2, 4]
}

// query: "cat dog"  (AND)
intersect(index.cat, index.dog)
// → [3]  only doc 3 has BOTH terms

Docs

D1, D2, D3…

↓ tokenize

Terms

cat, dog, log…

↓ invert

Inverted Index

term → [doc ids]

✓ See it live

Click a term — get docs straight from the index

5 fixed docs, indexed below. Click one term for a direct lookup, or two terms to see their posting lists intersected (AND).

Click a term to search the index…

0 terms selected

✓ Takeaway

Precompute the lookup, don't repeat the scan

Build once: precompute term → doc ids so queries are O(1)-ish hash lookups, not O(N) scans.
Combine terms by intersecting (AND) or unioning (OR) posting lists.
Rank the matches with TF-IDF or BM25; add stemming and stop-word removal to match more variants.
You already use it: Lucene, Elasticsearch, Postgres full-text search (GIN indexes) all run on this idea.
For meaning-based (not just keyword) matches, combine with vector search for hybrid retrieval.

Back to all topics →