# Inverted indexes

> Map each term to the documents that contain it — the structure behind full-text search.

Concept · Data structures for scale · https://levelcode.org/concepts/inverted-index

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.

```text
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](https://levelcode.org/concepts/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](https://levelcode.org/concepts/secondary-indexes-partitioned)).
- **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](https://levelcode.org/concepts/sql-vs-nosql).