The idea: an index at the back of a book, for every word
A search engine does not scan documents when you search. At write time it builds an inverted index: for every word, the list of documents that contain it. A query then only looks up a few words and combines their lists. This is the core of Lucene, and so of Elasticsearch, OpenSearch and Solr.
The page indexes four short documents. Press Index Next Doc to add them one at a time (Demo 1), then pick a query and press Search. A query sees only the documents indexed so far.
Analysis: from text to terms
Each document goes through an analyzer, a chain of a tokenizer and filters. Lucene's StandardAnalyzer with English stop words does roughly what the page does:
- Tokenizer: split on spaces and punctuation. "Lazy dog, lazy cat" → Lazy, dog, lazy, cat.
- Lowercase filter: Lazy and lazy become the same token.
- Stop filter: drop words too common to help, here
the,and,a. "The fox and the dog" keeps only fox and dog.
What is left are terms. The same analyzer runs on the query, so "Dog" in a query finds "dog" in a document. Real analyzers often add stemming (jumps → jump) and synonyms.
Posting lists, df and tf
The term dictionary holds every term, sorted. Each term points to its posting list: the IDs of the documents that contain it, in increasing order, each with the term frequency (tf), how often the term occurs there. The list's length is the document frequency (df).
| term | df | posting list (doc, tf) |
|---|---|---|
| brown | 1 | D1 (1) |
| cat | 1 | D2 (1) |
| dog | 3 | D2 (1), D3 (1), D4 (1) |
| fox | 2 | D1 (1), D4 (1) |
| jumps | 1 | D3 (1) |
| lazy | 1 | D2 (2) |
| quick | 2 | D1 (1), D3 (1) |
Documents get increasing IDs as they are indexed, so a new posting always goes at the end and every list stays sorted for free. Lucene writes postings in immutable segments and stores the ID gaps compressed, so a list of millions of IDs takes a few bytes per posting.
AND and OR: walking sorted lists
Because the lists are sorted, two lists can be combined in one pass with a pointer in each:
- AND (intersection): compare the two current IDs. If they are equal, it is a match; advance both. Otherwise advance the pointer with the smaller ID, since that document cannot be in the other list. Stop as soon as either list ends.
- OR (union): emit the smaller ID and advance its pointer; on equal IDs emit once and advance both. When one list ends, copy the rest of the other.
quick AND dog finds D3 (Demo 2), fox OR lazy gives D1, D2, D4 (Demo 3), and quick AND cat stops after two comparisons with no match (Demo 4). An AND costs at most the length of the two lists, and engines start from the shortest list. Lucene also stores skip lists inside long posting lists, so "advance to the first ID ≥ D900" jumps instead of stepping one by one.
Ranking with TF-IDF
A plain query like lazy dog means "documents with lazy or dog, best first". Each matching document gets a score, summed over the query terms:
score(d) = Σ tf(t, d) × idf(t), with idf(t) = ln(N / df(t)) and N the number of documents.
A term in many documents (dog, df 3) has a small idf and says little; a rare term (lazy, df 1) has a large one. A document that repeats a term (lazy twice in D2) scores higher too. The engine keeps one accumulator per document and adds tf × idf while it walks each posting list.
| query | scores (N = 4) | ranking |
|---|---|---|
| lazy dog (Demo 5) | D2 = 2 × 1.39 + 0.29 = 3.06; D3 = D4 = 0.29 | D2, D3, D4 |
| quick dog (Demo 6) | D3 = 0.69 + 0.29 = 0.98; D1 = 0.69; D2 = D4 = 0.29 | D3, D1, D2, D4 |
In Demo 6, D1 has only quick and D2 only dog, yet D1 ranks higher: quick is in 2 of 4 documents, dog in 3. Since Lucene 6 the default is BM25, which keeps the idea but caps the effect of a high tf and divides by document length, so a long document does not win just by being long.
Inverted index, B-tree and trie
| Index | Key | Good for |
|---|---|---|
| B-tree (Database Index) | the whole column value | equality, ranges, sorting on one value per row |
| Inverted index | each term inside the text | "contains these words", many values per row, ranking |
| Trie / FST (Trie) | characters of the term | the term dictionary itself: exact, prefix and fuzzy term lookup |
A B-tree on a text column can find rows that start with "quick", but not rows that contain "dog" somewhere. Lucene stores its term dictionary as a finite state transducer, a compressed relative of the trie, so qu* finds every term that starts with qu before any posting is read. PostgreSQL's GIN index is an inverted index inside a relational database (see PostgreSQL Index Types).
BM25 scores the documents an inverted index returns; BM25 vs Vector Search vs Hybrid compares it with vector search.
What the page leaves out
Segments, merging and near-real-time refresh; deletes as tombstones; compressed postings (delta + bit packing) and skip lists; positions and offsets for phrase queries ("lazy dog" as a phrase) and highlighting; stemming, synonyms and other languages; BM25's parameters k1 and b; sharding an index across nodes and merging the top hits; and top-k pruning such as WAND that skips documents that cannot reach the top.