Inverted Index + TF-IDF/BM25

The Search Bar's Problem

Every lesson so far in this section attacked one shape of the B-tree's blind spot. The sketches took Route B — trade a little exactness for enormous space savings. This lesson takes the other road, Route A: change the geometry, stay exact, and pay in space and structure. And it does it for the query you use a hundred times a day without thinking: text search.

Type "search engine" into a search bar over a billion documents and two things have to happen in milliseconds. First, find every document that contains those words. Second, rank them so the best ones come first. A B-tree — the workhorse index of every earlier lesson — is useless here. A B-tree sorts scalar keys so it can return a contiguous slice, but a document isn't a scalar, and "documents containing this word" isn't a range — it's a set scattered anywhere in the corpus. Scanning every document for the word is O(N) over the whole collection: hopeless at scale.

The fix is to flip the map. What you store naturally is a forward index: each document points to the words it contains. Transpose it, and you get the inverted index: each word points to the list of documents that contain it — its posting list. Now "which documents contain this word?" is a single dictionary lookup that hands back a ready-made list, no scan required. A multi-word query becomes a few lookups and a merge: for "search engine," look up search → docs {2, 3, 5} and engine → docs {2, 3}, intersect them, and you have docs {2, 3} in two lookups. This flip is the structure behind every search bar, from Google to your IDE's find-in-files.

How a search engine finds the documents containing your words without scanning them all: the inverted index. A forward index stores what you have naturally — each document mapped to the words it contains. Flip, or transpose, that mapping and you get an inverted index: each word mapped to the list of documents that contain it, called a posting list. Now the question which documents contain this word is a single dictionary lookup that returns a ready-made list, instead of a scan through every document. To answer a multi-word query like search engine, you look up the posting list for each term — search is in documents 2, 3, and 5; engine is in 2 and 3 — and intersect them, giving documents 2 and 3 in just two lookups and no scan. This flip, from document-to-words into word-to-documents, is the structure behind every search bar.

From Text to Terms: the Analysis Pipeline

Before a word can go into a posting list, it has to be turned into a term — and the rules for doing that are quietly responsible for search feeling smart. The step is called analysis (or tokenization), and it runs a short pipeline:

Tokenize + lowercase — split the text into words and drop the case, so Search and search are the same term.
Drop stopwords — extremely common words like the, a, are carry almost no signal and would bloat every posting list, so they're removed.
Stem — reduce each word to its root: engines → engin, running → run, documents → document. Now singular and plural, verb and gerund, all collapse to one term.

So "The Search Engines are Running" becomes just three terms: search, engin, run. The detail that makes this powerful is that the exact same analysis runs at index time and at query time. Index a document containing "Engines" and it's stored under engin; later, search for "engine" and your query is also analyzed to engin — so it matches, even though the surface words differ in case and number. This isn't hand-waving: PostgreSQL's to_tsvector('english', …) really does stem engines → engin and running → run, drop the and are, and record each term's positions. Analysis is why a search for "running shoe" finds a page titled "Shoes for Runners" — and, when it's tuned wrong, why it sometimes doesn't.

The text analysis pipeline that turns raw words into index terms, and why searching for one word finds its variants. Raw text is first lowercased and split into tokens, so The Search Engines are Running becomes the, search, engines, are, running. Next, very common stopwords that carry little meaning — here the and are — are dropped. Finally each remaining token is stemmed to its root: engines becomes engin and running becomes run, while search stays search, so the index stores three terms: search, engin, and run. The crucial point is that the identical analysis runs both when a document is indexed and when a query is issued, so a search for engine and a document containing Engines both normalize to engin and match, regardless of case or plural. This is real behavior: PostgreSQL to_tsvector stems engines to engin and running to run and drops the and are.

Answering a Query: Posting Lists and the Boolean Merge

With terms in hand, answering a boolean query is a merge. A posting list is kept as a sorted list of document ids (that ordering is the whole trick), so the boolean operators become list operations:

AND → intersect the two posting lists,
OR → union them,
AND NOT → difference.

The intersection is a classic two-pointer walk. Put a pointer at the head of each sorted list, compare the two document ids, and advance the pointer on the smaller one; whenever the two ids are equal, you've found a document in both lists — emit it and advance both. Walking search = [1, 4, 7, 9, 12] against engine = [2, 4, 5, 9, 11]: 1 < 2 advance the first; 4 = 4 match, emit 4; 7 > 5 advance the second; … 9 = 9 match, emit 9. The answer to search AND engine is docs [4, 9]. Because both lists are sorted, this is a single linear O(|A| + |B|) pass — never the quadratic cross-product of comparing every pair. And when one list is huge and the other tiny, skip pointers let the walk jump ahead over long stretches that can't contain a match, which is exactly the kind of structure the next lesson is about. (Posting lists are also compressed — stored as gaps between ids with variable-length encoding — so a list of millions of doc ids costs only a few bits each.)

How a search engine answers a multi-word AND query by intersecting posting lists. Each term's posting list is a sorted list of document ids — here search is in documents 1, 4, 7, 9, 12 and engine is in 2, 4, 5, 9, 11. To find documents containing both, you walk the two lists with a pair of pointers: compare the two current ids, advance the pointer on the smaller one, and whenever they are equal emit a match. Stepping through: 1 is less than 2 so advance the first list; 4 equals 4, emit document 4; 7 is greater than 5 so advance the second list; and 9 equals 9, another match. The result of search AND engine is documents 4 and 9. Because the posting lists are kept sorted, this is a single linear pass costing on the order of the sum of the two list lengths, never a quadratic cross-product, and skip pointers let long lists jump over gaps to go even faster.

Finding Isn't Ranking: TF-IDF and Its Flaw

Finding the matching documents is only half the job. A query might match thousands of documents; the art is putting the best ones first. The classic answer is TF-IDF, and it combines two intuitions:

Term frequency (TF) — a document that uses the query word more is probably more about it.
Inverse document frequency (IDF) — a word that appears in few documents is more discriminating than one that appears everywhere. IDF is log(N / df), where df is the number of documents containing the term: a word in every document has IDF near zero, a rare word has high IDF. (This is why matching "the" tells you nothing but matching "defenestration" tells you a lot.)

The score of a document is the sum over the query terms of tf × idf. It's a huge improvement over counting raw matches — but it has a flaw that keyword-stuffers love. Term frequency enters linearly and without bound: a document that repeats a word 20 times scores 20× the term-frequency contribution of a document that uses it once. On our corpus, ranking the query "search engine" by TF-IDF crowns a spam document that stuffs "search" five times with a score of 4.56, far above a clean, focused document at 1.79 — even though the focused one is obviously the better result. Two problems are tangled together here: raw TF over-rewards repetition, and nothing properly discounts a long document that accumulates matches just by being long. Fixing both is what makes the next ranker the one everybody actually uses.

BM25: Saturation and Length Normalization

BM25 ("Best Match 25," from Stephen Robertson and Karen Spärck Jones's Okapi system in the 1990s) is the ranking function behind modern search — the default in Lucene since version 6, and therefore in Elasticsearch, OpenSearch, and Solr. It keeps TF-IDF's two intuitions and fixes both flaws with two ideas. Here's the score of a document D for query Q, summed over the query terms:

score(D, Q) = Σ idf(qᵢ) · [ f · (k1 + 1) ] / [ f + k1 · (1 − b + b · |D| / avgdl) ]

where f is the term's frequency in D, |D| is the document's length, avgdl is the average document length, and idf is ln(1 + (N − n + 0.5)/(n + 0.5)) (the +1 keeps it non-negative even for very common terms). Two knobs carry the whole idea:

k1 — term-frequency saturation (default 1.2). Look at the f·(k1+1)/(f+k1·…) factor: as f grows it doesn't rise forever, it flattens toward a ceiling of idf·(k1+1). The first occurrence of a word matters a lot; the fifth matters a little; the twentieth barely registers. Measured on our term, the BM25 weight goes 0.69 → 1.23 → 1.44 at term frequencies of 1, 5, and 20, while raw TF-IDF marches linearly to 0.69 → 3.47 → 13.86. Repetition stops paying.
b — length normalization (default 0.75). The (1 − b + b·|D|/avgdl) term divides longer documents down, so a match in a 10-word title counts for more than a match buried in a 10,000-word page. Set b = 0 and length is ignored entirely.

Together they flip the ranking. That spam document that beat the focused one under TF-IDF (4.56 vs 1.79)? Under BM25, saturation caps its five repetitions and length-normalization penalizes its padding, so the focused document wins, 1.99 to 1.89. Try it in the lab below: type queries, toggle BM25 vs TF-IDF and watch the order flip, and drag k1 and b to feel each knob — dropping b to 0 hands the win right back to the keyword-stuffer, which is the cleanest proof that length normalization is doing real work.

A live mini search engine over six documents. Type any query — it tokenizes, lights up the matching posting lists of a real inverted index, and ranks the documents by score. Flip between BM25, TF·IDF, and raw count and watch the ranking reorder: under TF·IDF the keyword-stuffed document (five copies of a word) jumps to the top, while BM25 pushes the short focused document above it. Drag k1 to change how fast term frequency saturates, and b to change how hard long documents are penalized — set b to 0 and the stuffed document wins again, proving length normalization is what flips the result. Real inverted-index and BM25 math, in your hands.

Why BM25 ranks documents better than raw TF-IDF, shown as a curve of a term's weight against how many times it appears in a document. Raw TF-IDF is a straight line: weight grows linearly and without bound with term frequency, so a keyword-stuffed page keeps gaining score and wins. BM25 instead saturates — its term-frequency factor rises fast for the first few occurrences and then flattens toward a ceiling of idf times k1 plus one, so extra copies count for less and less. In real numbers the BM25 weight for the search term goes 0.69 at one occurrence, 1.23 at five, and only 1.44 at twenty, while raw TF-IDF climbs to 0.69, 3.47, and 13.86 over the same counts. Two parameters tune it: k1 controls how fast the saturation kicks in and b controls how strongly long documents are normalized down. The payoff is that a document stuffing a word five times can no longer beat a short focused document — BM25 scores the focused one higher, 1.99 versus 1.89.

Where It Runs, and the Two Roads

This one structure runs almost everywhere text is searched. Lucene and its descendants Elasticsearch, OpenSearch, and Solr are inverted indexes with BM25 scoring and pluggable analyzers. PostgreSQL has full-text search built in: to_tsvector and to_tsquery, matched with @@, backed by a GIN index — a Generalized Inverted Index, an inverted index built right into the database — and ranked with ts_rank. (One sharp caveat worth knowing: Postgres's ts_rank is not BM25 and doesn't saturate — on our corpus it happily ranks the spam document 0.3974 above the focused one at 0.0991, so for true BM25 in Postgres you reach for an extension like rum or ParadeDB.) SQLite ships FTS5, a virtual table that is an inverted index with a built-in bm25() function. Under all of them the query planner really uses the index: ask Postgres for inverted & index and its plan is a Bitmap Index Scan on the GIN index, not a sequential scan.

It's worth naming the boundary. Everything here is lexical search — it matches the exact terms of your query (after stemming). Search "car" and you'll find "cars," but not "automobile": the inverted index has no idea they're related. Semantic search answers that by embedding text as vectors and matching on meaning with nearest-neighbor search — but it needs a model, it's fuzzier, and it's heavier. The modern answer is hybrid: run BM25 and vector search together and fuse the rankings (e.g. reciprocal rank fusion), taking BM25's precision and the vectors' recall. BM25 is decades old and still the baseline that's hard to beat.

Step back and the whole of §8 resolves into two roads out of the B-tree's blind spot. Route A — spatial curves, spatial trees, and this inverted index — changes the geometry to keep every answer exact, and pays for it in space and structure. Route B — Bloom, Cuckoo, HyperLogLog, Count-Min, MinHash — trades exactness for space, keeping a tiny summary and accepting a bounded error. Two structures remain in this section, and they're both about integrity and speed within an ordered set: skip lists, which make a linked list searchable in logarithmic time (the grown-up version of the skip pointers we just met), and Merkle trees, which let you verify that two large datasets are identical by comparing a single hash. That's the next lesson.