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
tsvectorsearch, JSONB containment and array membership. - Substring and code search use n-gram terms instead of words, as in
pg_trgmor 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.
Connections
- Learn first
- Secondary Index
- Builds on this
- Full-Text Search
- Related
- LSM-Tree
- In real systems
- ElasticsearchPostgreSQL
- Mentioned
- B-Tree
Recall
These cards are also in your review deck, scheduled with spaced repetition.