Notesstorage🌱 seedling

Inverted Index

Also: Inverted Indexes · Postings List · Posting List · GIN Index

An index from each term to the sorted list of documents containing it (its postings list). It turns "which documents contain these words?" into a few dictionary lookups and list intersections.

Why it exists

A B-Tree on a text column sorts whole values, which can't find a word in the middle. Search needs the mapping inverted: word → documents, not document → words.

How it works

  • Analysis turns text into terms: tokenise, lowercase, drop stopwords, stem. Queries pass through the same analyzer.
  • A sorted term dictionary supports exact and prefix lookups.
  • Postings lists hold sorted document IDs (often with term frequencies and positions for phrase queries), delta-encoded and bit-packed.
  • AND queries intersect postings lists, OR queries merge them, both as linear walks over sorted lists.
  • Updating many postings per document is expensive, so engines buffer: Lucene writes immutable segments and merges them, like an LSM-Tree; Postgres GIN keeps an unsorted pending list.

Trade-offs

Gains Costs
word and containment queries without a scan one document touches many postings lists
postings compress extremely well updates are buffered, so visibility lags
works for any multi-valued field (tags, arrays, JSON keys) analyzer choices are baked into the index

In practice

  • Elasticsearch (via Lucene) stores one inverted index per segment, plus doc values for sorting and aggregation.
  • PostgreSQL GIN indexes serve full-text tsvector search, JSONB containment and array membership.
  • Substring and code search use n-gram terms instead of words, as in pg_trgm or GitHub's code search.

Pitfalls

  • Analyzer mismatch between index and query time is the classic "search can't find it" bug.
  • Very common terms have huge postings lists; stopwords and caching exist because of them.

Recall

These cards are also in your review deck, scheduled with spaced repetition.