Inverted indexes

A database index maps a row's key to the row. An inverted index goes the other way: it maps each term to the list of documents containing it (a posting list). It's the core structure of search engines such as Elasticsearch, OpenSearch, Lucene, Solr and PostgreSQL's full-text search.

#Building one

1. Analyse each document: split into tokens, lowercase, remove punctuation, optionally drop stop words ("the", "a") and reduce words to stems ("running" → "run").
2. For each term, append the document ID (and often the positions where it appears) to its posting list.

doc 1: "Fast red running shoes"
doc 2: "Red rain jacket"
doc 3: "Running jacket, lightweight"

red     → [1, 2]
run     → [1, 3]
jacket  → [2, 3]
shoe    → [1]

#Querying

• red AND jacket → intersect posting lists [1, 2] ∩ [2, 3] = [2]. Posting lists are sorted, so intersection is a fast merge.
• red OR running → union.
• Phrase queries ("running shoes") use stored positions to check adjacency.
• Ranking scores matches by relevance, typically with BM25: rarer terms (high inverse document frequency) count more, repeated terms count more with diminishing returns, and long documents are normalised.

#Operating search indexes

• Near-real-time: new documents become searchable after a refresh (about a second in Elasticsearch by default), not instantly.
• Derived, not authoritative: feed the index from your system of record through an outbox or change data capture, and be able to rebuild it (transactional outbox).
• Sharded by document: each shard holds a local inverted index, so every query fans out to all shards and merges results (secondary indexes on sharded data).
• Analysers matter: the same analysis must run at index time and query time, and languages need different stemmers.

For modest needs, PostgreSQL's tsvector with a GIN index provides a capable inverted index inside the database you already run. See relational vs NoSQL.