Inverted Index Explained: How Full-Text Search Works
On this page
What is an inverted index?
To find "replication" in a textbook, you don't read every page. You look it up in the index at the back, which lists the pages where it appears. An inverted index is the same idea: instead of documents pointing to words, words point to documents.
How an inverted index is built
Three short documents:
doc 1: "The cat sat"
doc 2: "The cat ran"
doc 3: "The dog sat"After analysis (lowercasing, splitting into words, Day 6), each term points to its postings list: the documents, and positions within them, where it appears.
term postings (doc:position)
"cat" -> [1:1, 2:1]
"dog" -> [3:1]
"ran" -> [2:2]
"sat" -> [1:2, 3:2]
"the" -> [1:0, 2:0, 3:0]The term dictionary is sorted, so looking up a term is fast even with millions of distinct terms.
How queries use the inverted index
cat: look up one term, get docs 1 and 2. No document is scanned.cat sat(either word): union of the two postings lists, docs 1, 2 and 3. Docs matching both rank higher."cat sat"as a phrase: intersect the lists and check that the positions are consecutive: only doc 1.
Postings also store term frequencies, and the index keeps document frequencies and field lengths: exactly the numbers relevance scoring needs (Day 9).
Why analysis decides what can be found
The index only contains terms produced by the analyzer, and queries are analyzed the same way. On the course's lab cluster, an article titled "Tuning Databases for Performance" was not matched by the word database in a title search, because the standard analyzer keeps databases and database as different terms. With the english analyzer, which stems words, laptops in a query matched laptop in product descriptions. Choosing analyzers is choosing what counts as the same word (Day 6).
Lucene segments, refresh and merges
Elasticsearch builds on Apache Lucene. Each shard is a Lucene index made of immutable segments:
- New documents go into an in-memory buffer, then a new segment every refresh (once per second by default), which is why search is near real-time.
- Segments never change; deletes are marked and cleaned up when segments merge in the background.
- Besides the inverted index, Lucene keeps doc values (column-oriented storage for sorting and aggregations), stored fields (the original
_source), and vector indexes (HNSW graphs, Day 21).
What an inverted index is good and bad at
- Fast: term lookups, combining many conditions, ranking.
- Expensive: queries that can't use the term dictionary directly, such as leading wildcards (
*phone) or regular expressions, which walk many terms. Design fields for the queries you need instead (Day 11). - Updates rewrite: changing a document means indexing a new version and marking the old one deleted.
Check yourself
A query looks up a few terms in a sorted dictionary and reads their postings lists, instead of scanning every document.
It intersects the postings lists of the terms to find documents containing all of them, then uses the stored positions to check that the terms appear next to each other and in the right order.
The standard analyzer doesn't stem, so they are different terms in the index; a stemming analyzer like english would map both to one term.
An immutable mini-index. New documents go into new segments at refresh time, deletes are marks, and background merges combine small segments and remove deleted documents.
Substring searches in the middle of words, since terms are matched whole; frequent updates to large documents, since segments are immutable and every update rewrites the document; and joins between documents, which it simply doesn't support.