Inverted Index

The data structure underneath classical search engines — a map from each term in the corpus to the list of documents containing it, enabling sub-millisecond keyword lookup.

An inverted index flips the document → terms relationship into terms → documents. Lookups for a query word jump straight to the list of products that contain it, instead of scanning every product. Postings lists also store positions, frequencies, and field weights so BM25 scoring can be computed on the fly.

Lucene, Elasticsearch, OpenSearch, and Postgres FTS all build on this primitive. Modern variants compress postings (delta encoding, FOR/PFOR), skip-list-index them for fast intersection, and merge segments in the background to keep query latency bounded as the catalog grows.

For ecommerce, the inverted index is what makes BM25 fast enough to be the first-stage retriever even with hundreds of thousands of products. Vector search uses a different index (HNSW, IVF) — the two coexist in hybrid search systems.

Related terms

BM25

A probabilistic ranking function that scores how relevant a document is to a query based on term frequency, document length, and rarity across the corpus.

TF-IDF

Term Frequency × Inverse Document Frequency — the classical weighting scheme that scores a term high when it appears often in a document but rarely across the corpus.

Browse all glossary terms