Inverted Index

A data structure that maps terms to the documents (or positions) containing them — the reverse of a document mapping terms. Given the term "quantum," an inverted index returns the list of all documents where "quantum" appears, typically with metadata like frequency and position.

Every full-text search system is built on some form of inverted index. Lucene, SQLite FTS, PostgreSQL's GIN indexes, and even indexeddb's multiEntry indexes are all variations on the same idea: precompute the term-to-document mapping at write time so reads only touch relevant documents.

Structure

A minimal inverted index is a dictionary of term → posting list, where each posting list is the set of document IDs containing that term. More sophisticated versions store term frequency (for TF-IDF/BM25 scoring), positions (for phrase queries), and field information (for multi-field search).

Building one

At write time: tokenize the document, optionally stem and remove stopwords, then append the document ID to each term's posting list. At query time: look up each query term's posting list, intersect them (for AND queries) or union them (for OR queries).

The full-text-search-indexeddb article demonstrates a minimal version using IndexedDB's multiEntry flag — the browser's B-tree index machinery does the posting list work automatically.

Cost

Inverted indexes trade write speed and storage for read speed. Every document insert updates multiple posting lists. Storage roughly doubles because you keep both the original text and the index. For read-heavy workloads like search, this tradeoff is almost always worth it.