Also known as: postings list, term index, keyword index
An inverted index maps each term to the list of documents (and positions) where it appears. The classical data structure behind keyword search — sub-millisecond lookups over billions of documents and the substrate every BM25 implementation builds on.
An inverted index is the data structure that makes keyword search fast. For every term in the corpus vocabulary, it stores a postings list — the documents that contain that term, plus per-document metadata (term frequency, positions, field).
A toy example. Indexing three documents:
Yields postings:
cat → [(D1, tf=1, pos=[1])]sat → [(D1, tf=1), (D2, tf=1)]dog → [(D2, tf=1)]the → [(D1, tf=2), (D2, tf=2)]A query for cat sat reads the two postings lists, intersects them on doc ID, and returns D1. No document is ever scanned.
Every classical retrieval algorithm — Boolean, TF-IDF, BM25 — is a scoring function applied to postings-list intersections. A single inverted index serves Boolean filters, BM25 ranking, phrase search, and faceted search simultaneously, because the index just delivers postings; the scoring function is a thin layer above.
Modern open-source implementations store postings in compressed blocks (variable-byte, Roaring bitmaps, FOR-delta), so a billion-doc index fits in tens of GB and decodes at GB/s. That is what gives first-pass retrieval its sub-millisecond budget over corpora that wouldn’t fit in vector RAM.
Beyond the doc ID, each posting typically carries:
Storing positions roughly doubles index size; many production systems index positions only for fields that actually need phrase queries.
Lucene encodes each postings list as a sequence of compressed blocks of 128 doc-IDs. The doc-IDs are delta-encoded (only the difference from the previous ID is stored), then run through Frame-of-Reference + PFOR-Delta compression, which packs each block into the minimum number of bits needed for its largest delta. Term frequencies are stored in a parallel block, positions in another. The result is roughly 2 to 4 bits per posting on web-scale corpora, low enough that postings for hot terms stay in OS page cache. Tantivy and Quickwit use the same block layout with minor codec tweaks; modern engines diverge mostly on impact-ordering vs doc-ID-ordering, not on compression.
Hybrid stacks ( hybrid search ) run an inverted-index query and a dense ANN query in parallel, then fuse the two ranked lists. The inverted index handles rare exact tokens — model numbers, proper nouns, identifiers — that embeddings systematically underweight. The ANN handles paraphrases and synonyms the index can’t see. Two failure modes, two complementary indexes.
Beyond compression, recent inverted-index engines add:
These are why a single-machine BM25 over 100M docs still serves p99 of about 30ms.
A forward scan visits every document and asks 'do you contain term T?'. An inverted index already has the answer pre-computed — it jumps straight to the postings list for T. For a 100-million-document corpus that's the difference between hours and microseconds per query.
Each posting stores the term's positions inside the document, not just a doc ID. To match the phrase 'reciprocal rank fusion' you intersect the postings lists for all three terms and keep only documents where their positions are consecutive. Proximity scoring (terms within N tokens) is the same idea with a wider window.
Models like SPLADE expand a query or document into a weighted bag of terms — many of which never appeared in the original text. The inverted-index machinery is unchanged; the postings list just gets fed model-generated terms with model-generated weights instead of raw token counts.
