How Inverted Indexes Power Full-Text Search (Elasticsearch, Lucene, and BM25)

Quick Answer

An inverted index maps every unique word to the list of documents that contain it, so a search engine never has to scan documents it already knows don't match. Elasticsearch and Lucene build one of these per field, then rank the matching documents with BM25, a scoring function built on term frequency, inverse document frequency, and document length. Below, both are built from scratch in Python and run against a real query with real scores.

Why a Search Engine Can't Just Scan Every Document

Suppose you have a million blog posts and someone searches for python search index. The naive approach is to loop over every post and check whether it contains those words. That's an O(n) scan: double the number of posts and you double the search time, every single time someone searches, forever. Grep does this, and grep works fine on a folder of source files, but it does not work as your "search engine" for a million documents where you need results in tens of milliseconds.

The fix search engines actually use is to do the expensive work once, in advance, at indexing time, so that querying becomes cheap. Instead of asking "does this document contain the word 'python'" for every document on every query, you build a lookup table once: for a given word, which documents contain it. That table is called an inverted index, and it's the single data structure underneath Elasticsearch, Solr, and every Lucene-based search system.

It's called "inverted" because it flips the natural direction of the data. A document naturally maps to the words it contains (forward index: doc → words). What you actually need for search is the reverse: word → documents. Building that reversal is most of what "indexing" means in a search engine.

Building One From Scratch

Here's a small corpus of eight one-line documents, tokenized (split into lowercase words) and turned into a real inverted index in Python. Each entry in the index maps a term to a dictionary of {document_id: term_frequency} — how many times that word appears in that specific document, which BM25 will need later.

import re
from collections import defaultdict

docs = {
    1: "Python is a popular language for beginners learning to code",
    2: "Java is a popular language used for enterprise backend systems",
    3: "Python and Java are both used to teach programming to students",
    4: "Redis is an in memory data store used for caching and queues",
    5: "Elasticsearch is a search engine built on top of Lucene",
    6: "Lucene is a Java library that implements a full text search index",
    7: "Students learning Python often start with simple coding exercises",
    8: "A search engine ranks documents using an inverted index and scoring",
}

TOKEN_RE = re.compile(r"[a-z0-9]+")

def tokenize(text):
    return TOKEN_RE.findall(text.lower())

inverted_index = defaultdict(dict)
doc_lengths = {}

for doc_id, text in docs.items():
    tokens = tokenize(text)
    doc_lengths[doc_id] = len(tokens)
    tf_counts = defaultdict(int)
    for t in tokens:
        tf_counts[t] += 1
    for term, tf in tf_counts.items():
        inverted_index[term][doc_id] = tf

Run that, and print the postings for the three words we're about to query on, and this is the real output:

'python' -> {1: 1, 3: 1, 7: 1}
'search' -> {5: 1, 6: 1, 8: 1}
'index'  -> {6: 1, 8: 1}

That's the whole trick. To find documents containing "python", you don't touch documents 2, 4, 5, 6, or 8 at all — you go straight to the postings list for the term python and read off {1, 3, 7}. The list of doc IDs for each term is called a postings list, and it's usually stored sorted by document ID so that combining postings lists for a multi-word query (intersection for AND, union for OR) can be done with a single linear merge, the same way you'd merge two sorted arrays.

How Lucene and Elasticsearch Actually Store This

A dictionary of dictionaries is fine for eight documents in a Python process. Lucene, the search library underneath both Elasticsearch and Solr, has to make this work for indexes with hundreds of millions of documents and stay fast, so a few real engineering decisions sit on top of the basic idea:

• Postings lists are stored as sorted arrays of integers, delta-encoded. Instead of storing raw document IDs like 1055, 1080, 1240, Lucene stores the gaps between them — 1055, 25, 160 — because small numbers compress far better than large ones, and IDs in a postings list are already sorted so the gaps are always non-negative.
• Postings lists are broken into blocks with skip pointers. If a postings list for a common word has ten million entries and you're intersecting it with a postings list of a hundred entries for a rare word, you don't want to walk it one entry at a time. Lucene stores periodic "skip" markers so it can jump ahead in large blocks and only fall back to a linear scan near the target.
• The index is split into immutable segments. Lucene never edits a postings list in place. New documents go into a brand-new segment; segments are periodically merged in the background; and "deleting" a document just marks it in a bitset without touching the segment's data until the next merge. This is why a delete in Elasticsearch doesn't shrink disk usage immediately.
• Text goes through an analyzer before it's indexed. Tokenizing on whitespace isn't enough — you also lowercase, strip punctuation, remove stopwords ("a", "the", "is") for some fields, and often stem or lemmatize so that "running" and "ran" map to the same index term. This analysis chain runs identically at index time and at query time, which is exactly why a query for "ran" can still match a document containing only "running."

None of this changes the core idea from the previous section. It's still term → postings list. It's just engineered to stay fast at a scale where a Python dict would fall over.

BM25: The Formula Elasticsearch Actually Uses to Rank

An inverted index tells you which documents contain your query terms. It says nothing about which of those documents is the best match. For that you need a scoring function, and the one Lucene (and therefore Elasticsearch and Solr) has used as its default since 2015 is BM25 ("Best Matching 25"), a refinement of the older TF-IDF idea.

For a query term t and document D, BM25 scores as:

score(D, t) = IDF(t) * ( tf(t,D) * (k1 + 1) ) / ( tf(t,D) + k1 * (1 - b + b * |D| / avgdl) )

where tf(t,D) is how many times the term appears in the document, |D| is the document's length in tokens, avgdl is the average document length across the whole index, and IDF(t) is a measure of how rare the term is across all documents (rarer terms score higher, because matching on "elasticsearch" tells you a lot more than matching on "is"). k1 and b are tuning constants — Lucene defaults to k1 = 1.2 (we'll use the also-common 1.5) and b = 0.75.

The part that actually distinguishes BM25 from plain TF-IDF is the denominator. Plain TF-IDF lets a term's contribution grow linearly forever with repetition — a document that repeats "python" fifty times scores fifty times higher on that term than one that mentions it once, which is a bad proxy for relevance. BM25's tf(t,D) + k1 * (...) denominator makes each additional occurrence of a word matter less and less (it saturates), and the |D| / avgdl term inside it penalizes documents that are long simply because they're long, not because they're more relevant.

import math

N = len(docs)                                    # total documents
avgdl = sum(doc_lengths.values()) / N            # average doc length
k1, b = 1.5, 0.75

def idf(term):
    df = len(inverted_index.get(term, {}))       # doc frequency of the term
    return math.log((N - df + 0.5) / (df + 0.5) + 1)

def bm25_score(doc_id, query_terms):
    total = 0.0
    dl = doc_lengths[doc_id]
    for term in query_terms:
        tf = inverted_index.get(term, {}).get(doc_id, 0)
        if tf == 0:
            continue
        denom = tf + k1 * (1 - b + b * dl / avgdl)
        total += idf(term) * (tf * (k1 + 1)) / denom
    return total

Running a Real Query, End to End

Query the eight-document corpus for python search index. The candidate set — the only documents BM25 even has to look at — comes straight from the union of the three postings lists shown earlier: {1, 3, 7} ∪ {5, 6, 8} ∪ {6, 8} = {1, 3, 5, 6, 7, 8}. Documents 2 and 4 are never touched, because neither "python", "search", nor "index" appears in their postings lists at all.

With N = 8 and avgdl = 10.625 tokens, this is the actual, unedited output of running the scorer above against every candidate:

doc 8  score=2.1906  "A search engine ranks documents using an inverted index and scoring"
    term='search' tf=1 idf=0.9445 contributes=0.9297
    term='index'  tf=1 idf=1.2809 contributes=1.2609

doc 6  score=2.1029  "Lucene is a Java library that implements a full text search index"
    term='search' tf=1 idf=0.9445 contributes=0.8925
    term='index'  tf=1 idf=1.2809 contributes=1.2104

doc 7  score=1.0143  "Students learning Python often start with simple coding exercises"
    term='python' tf=1 idf=0.9445 contributes=1.0143

doc 1  score=0.9701  "Python is a popular language for beginners learning to code"
    term='python' tf=1 idf=0.9445 contributes=0.9701

doc 5  score=0.9701  "Elasticsearch is a search engine built on top of Lucene"
    term='search' tf=1 idf=0.9445 contributes=0.9701

doc 3  score=0.9297  "Python and Java are both used to teach programming to students"
    term='python' tf=1 idf=0.9445 contributes=0.9297

Notice what actually decided the ranking. Documents 8 and 6 both matched two of the three query terms ("search" and "index"), so they beat everything that matched only one term — that part is intuitive. But doc 8 (11 tokens long) edged out doc 6 (12 tokens long) even though both matched the exact same terms with the exact same term frequency: BM25's length normalization very slightly penalized the longer document, exactly as the |D| / avgdl term is designed to do. The term "index" also contributed more than "search" in both documents (1.28 vs 0.94 IDF) because "index" appears in only 2 of the 8 documents while "search" appears in 3 — the rarer term is worth more, which is the IDF half of BM25 doing exactly its job.

Where This Layer Ends and Ranking Begins

It's worth being precise about what this post covered and what it didn't, because "search" gets used to mean a few different layers stacked on top of each other. This post is about the retrieval and scoring layer: turning raw text into an inverted index, and using a text-similarity function (BM25) to rank matches within that index. That's exactly what Elasticsearch and Lucene do under the hood when you send them a query.

What this post deliberately did not cover is the ranking-signals layer that sits on top of this for something like a web search engine — using the link structure between documents (PageRank-style relevance scoring) as an additional signal beyond text similarity. That's a genuinely separate topic, and it's covered in depth in How Search Engines Rank Pages, which also walks through a hand-computed TF-IDF example if you want to see that scoring function specifically.

One more practical note: you do not need Elasticsearch to get value from an inverted index. PostgreSQL's built-in full-text search (tsvector/tsquery) builds and queries an inverted index internally and is often enough for tens of thousands to low millions of documents without adding a separate service to your infrastructure. Reach for Elasticsearch when you need things a database's built-in search doesn't do well — fuzzy/typo-tolerant matching at scale, faceted search across many fields, or horizontal scaling of the index itself across a cluster.

Frequently Asked Questions