The Inverted Index — How Search Actually Works Underneath

search1-1 named the inverted index as this engine's own primary structure. This chapter formally explains what it actually is — and revisits a structure this site already covered once before, at a smaller scale.

What an Inverted Index Actually Is

A "forward" index maps a document to its own content — the way a book's table of contents maps a chapter to a page. An inverted index does the opposite: it maps each individual term to the list of documents containing it — exactly like a book's own back-of-book index, mapping a word to the page numbers it appears on.

A Concrete Worked Example

Indexing two tiny documents — "the quick brown fox" (doc 1) and "the lazy dog" (doc 2) — produces an inverted index roughly shaped like this:

the    -> [doc 1, doc 2]
quick  -> [doc 1]
brown  -> [doc 1]
fox    -> [doc 1]
lazy   -> [doc 2]
dog    -> [doc 2]

A search for "fox" becomes a direct, structured lookup of the term fox in this table — not a scan through every document's own raw text.

Analysis — Turning Text Into Terms

Before terms go into the inverted index, text passes through an analyzer: tokenization (splitting text into individual words), normalization (lowercasing), and often stemming (reducing words to a root form — "running" → "run") and stop-word removal. This directly echoes postgres1-6's own to_tsvector() material — lexemes, stop words, stemming — except here it's the actual foundation the entire engine is built on, not a bolt-on feature reached for occasionally.

Revisiting postgres1-7's Own GIN Material

postgres1-7 explained GIN as storing "a mapping from each individual component of a value... to the list of rows containing it." That's genuinely, literally the same core concept — an inverted index — just applied at smaller scale. The real difference is architectural: in Postgres, GIN is one index type among several (per postgres1-7's own comparison table — B-tree/GIN/GiST/BRIN/Hash), reached for specifically when JSONB containment or full-text search is needed, while the rest of the engine is built around ordinary structured relational data. Here, per search1-1's own throughline, the inverted index isn't one option among several — it's the engine's own primary, foundational structure, used for every field by default unless deliberately configured otherwise.

Why This Explains Fast Full-Text Search at Scale

Because searching means directly looking up a term in the inverted index — a fast, structured operation — rather than scanning every document's own raw text, search stays fast even as the number of documents grows very large. This is the exact same underlying performance principle GIN itself relies on in Postgres (postgres1-7), just built here as the engine's own foundational structure rather than an add-on index type.

Postings Lists & What Else They Store

A postings list doesn't just record which documents contain a term — it typically also stores term frequency (how many times the term appears in that document) and position (where in the document). This extra information is exactly what search1-6's own relevance-scoring chapter needs.

Hands-On Exercises