Lesson 0004 · Internals

The inverted index

The data structure under every search — and why term lookup is fast.

~10 minWarm-up + quiz + labCheat sheet: here

Warm-up — recall from 0003

From memory: analysis turns a text value into what, and where do those go? — Into terms, written to the inverted index. This lesson opens that box. By the end you'll trace a full-text query end-to-end and see the two numbers BM25 needed in 0002 come straight off this structure.

What it is: a book index, inverted

A normal (forward) index maps document → its words. An inverted index flips that: it maps term → the documents that contain it. — Definitive Guide: Inverted index It has two parts:

Term dictionary — the sorted list of every unique term in the field.
Postings list — for each term, the sorted list of doc IDs containing it.

Index two text docs — 1: "the quick brown fox" and 2: "the lazy brown dog" — and (after analysis lowercases them) the field's inverted index is just:

Term (sorted)	Postings → doc IDs	doc freq
brown	[1, 2]	2
dog	[2]	1
fox	[1]	1
lazy	[2]	1
quick	[1]	1
the	[1, 2]	2

Why lookup is fast

To answer “which docs contain brown?” the engine does not scan documents. Because the term dictionary is sorted, it finds the term by binary search — sub-linear in the number of terms — then reads its postings list directly. — Definitive Guide: Inverted index

Multi-term queries stay cheap because postings are sorted doc-ID lists. To AND two terms (brown AND the → find docs in both), the engine merge-walks the two sorted lists in one pass — the same idea as a merge join. No per-document work, no full scan.

This is exactly where BM25's inputs live

Remember from 0002: IDF needed n = docs containing the term. That's just the length of the term's postings list — its document frequency. And f(t,D) (term frequency) plus the field-length norm are computed and stored at index time, riding along in the postings. — Definitive Guide: Scoring theory The inverted index isn't just where we search — it's where the scoring numbers come from.

The whole pipeline, assembled

You now hold every piece. A match: "Brown Foxes" on a text field runs:

"Brown Foxes"→ analyse (0003)→ brownfox→ seek term dictionary→ read + merge postings→ candidate docs→ BM25 (0002)→ ranked hits

That single line — analysis → inverted index → BM25 scoring — is the backbone answer to “how does a full-text query become a ranked result set?” (Shard aggregation is the last piece, coming in 0005.) Being able to say it unprompted is a core goal of this course.

The interview edge: sorted order cuts both ways

Why quic* is fast but *ick is slow

A trailing wildcard / prefix query (quic*) is cheap: sorted terms mean all matches sit in one contiguous range of the dictionary. A leading wildcard (*ick) can't use the sort order at all — matching terms are scattered everywhere — so the engine must scan the entire term dictionary. Same reason range queries on sorted terms are efficient. When someone asks why leading wildcards are discouraged, this is the answer.

One inverted index per field

Each field has its own inverted index — title and body don't share one. That's why field-length norm and term stats are per-field, and why the same word can have different IDF in different fields. — Scoring theory

Check yourself

From memory — effortful recall is the point. Feedback is immediate.

An inverted index maps each term to:

The postings list is that list of doc IDs. The count (document frequency) is just its length; the score is computed later by BM25.

The term dictionary is kept sorted mainly to enable:

Sorted order lets the engine binary-search a term (and scan prefix ranges). Scoring is BM25's job; segments are immutable, so terms aren't deleted in place.

A term's document frequency equals:

Document frequency = how many docs contain the term = the number of doc IDs in its postings list. This is IDF's n from lesson 0002.

A leading wildcard like *ick is slow because sorted order:

Matches for a leading wildcard are scattered across the dictionary, so the sort gives no contiguous range to jump to — the whole term dictionary must be scanned.

Term frequency and field-length norm are computed:

Both are calculated and stored at index time, riding in the inverted index, so scoring at query time just reads them.

Hands-on: read the postings' statistics directly

The _termvectors API exposes the per-term numbers stored in the inverted index — including doc_freq (the postings length = IDF's n). Seed a tiny index:

PUT /lab_ii/_doc/1
{ "title": "the quick brown fox" }
PUT /lab_ii/_doc/2
{ "title": "the lazy brown dog" }

1 · Inspect a document's terms and the collection stats

GET /lab_ii/_termvectors/1
{
  "fields": ["title"],
  "term_statistics": true,       // per-term df / ttf across the index
  "field_statistics": true        // doc_count, sums for the field
}

In the response, each term shows term_freq (TF for this doc) and doc_freq (how many docs contain it). Confirm brown reports doc_freq: 2 and fox reports doc_freq: 1 — that's the postings-list length, straight off the diagram above.

2 · Predict, then verify, an IDF ordering

Which single term is rarer across the index — brown or fox? Predict which would earn a higher IDF, then run GET /lab_ii/_search {"query":{"match":{"title":"brown fox"}}} with ?explain=true and read the idf sub-scores to confirm. Then DELETE /lab_ii. Bring any mismatch to your teacher.

Primary source — read this next

Elasticsearch: The Definitive Guide — “Inverted Index” (and the short follow-on “What Is Relevance?”). Legacy 2.x, but the clearest conceptual treatment of this structure. ⚠️ Trust the concepts here; verify any API/settings syntax against current docs.

Where this goes next

One question is now unavoidable: the term dictionary and postings are described as if fixed — but documents keep arriving. How does an immutable inverted index absorb new docs? That's segments and the merge process — Lesson 0005 — and it's where shards, refresh, and the “why is my index slowly getting slower” story live.

← Lesson 0003 Inverted index cheat sheet → Glossary → All lessons

Want to trace one of your own queries through analysis → postings → BM25, or see why a wildcard query is timing out? Bring me the query and a _termvectors dump and we'll walk it together.