Inverted Index: The Foundation of Full-Text Search

An inverted index is the data structure that makes full-text search fast. Understanding how it works explains why match queries are O(1) lookups rather than O(n) scans.

Forward index vs inverted index

• A forward index maps document IDs to their contents — doc:1 = ["spring", "boot", "java"] — which means finding all documents containing "boot" requires scanning every document's word list: O(n)
• An inverted index flips this: it maps each unique term to the list of documents containing it — "boot" -> [doc:1, doc:3, doc:7] — which means searching for "boot" is a single lookup in the term dictionary: O(1) to find the list, then O(k) to retrieve k matching documents

How Elasticsearch builds it

• When a document is indexed, its text fields pass through the analysis pipeline — the analyzer tokenizes the text into terms, applies filters (lowercase, stop-words, stemming), and stores each term with a posting list (the list of document IDs that contain the term)
• to_tsvector('spring boot framework') in PostgreSQL and Elasticsearch's analyzer both produce the same conceptual result: a set of normalized tokens with their positions

Posting lists and relevance scoring

• The inverted index stores not just which documents contain a term, but how often the term appears in each document and the total frequency across the corpus — which means BM25 relevance scoring can be computed efficiently from the posting list data without re-reading documents
• BM25 (the default scoring algorithm) scores higher for: terms that appear frequently in the document, terms that appear rarely across the corpus (high IDF), shorter documents

Why full-text search can't use a B-tree

• A B-tree finds documents where a field equals an exact value or falls in a range — WHERE title = 'spring boot' or WHERE price BETWEEN 10 AND 100; it can't find documents where a field contains a word
• The inverted index is the only structure that maps terms to documents efficiently across the full corpus