Skip to content
AI Engineer Guide.

concept · concepts · intermediate · concept 3 of 57

Inverted index

0 of 57 complete

Why it matters

Scanning every document per query is linear in corpus size and unusable beyond a toy set. The inverted index inverts the storage: instead of asking what terms a document contains, it asks which documents contain a term, and intersects those lists. That inversion is what makes sub-second search over millions of documents possible, and its layout — sorted ids, delta encoding, positions — determines both query latency and how painful deletes become.

Mental model

An inverted index is the index at the back of a textbook: a term, then the page numbers where it appears. The analogy holds for lookup and breaks for maintenance, because a printed index is rebuilt in editions while a live index must absorb edits page by page.

How it works

Two postings lists, one phrase queryInteractive

Synthetic postings sheet · segment 07 · 1,200 documents

Two terms · five postings each · one phrase query

bounding boxes

Step 1/6 · Term to ids

Step 1Term to ids

The index maps a term to the documents that contain it, not to the text. The stored text lives elsewhere and is fetched only for the documents that survive ranking.

INVERTED INDEX · SEGMENT 07 · 1,200 DOCUMENTS

, running header, region 1. Select to inspect.

Postings for two terms

, title, region 2. Select to inspect.
Termsrefund · window
, form field Terms, region 3. Select to inspect.
Postings10
, form field Postings, region 4. Select to inspect.
Positionsstored
, form field Positions, region 5. Select to inspect.
POSTINGS · REFUND
DocPositionsGap
4112, 88—
575+16
8841+31
1327+44
20522+73
, table POSTINGS · REFUND, region 6. Select to inspect.
POSTINGS · WINDOW
DocPositionsGap
4113, 203—
579+16
8842+31
2053+117
30160+96
, table POSTINGS · WINDOW, region 7. Select to inspect.
PHRASE CHECK
DocrefundwindowAdjacent
411213yes
5759no
884142yes
205223no
, table PHRASE CHECK, region 8. Select to inspect.
Phrase result2 hits · docs 41, 88 · 4 candidates · 0 documents scanned
, form field Phrase result, region 9. Select to inspect.
Delete

Deleting doc 132 writes a tombstone at once. Its postings stay in segment 07 until a merge rewrites them.

, paragraph Delete, region 10. Select to inspect.

10 postings · 4 candidates · 2 hits · 1 tombstone · 0 full scans

, running footer, region 11. Select to inspect.
11 regions

Step record

Terms
2
Documents
1,200
Text in index
no

The text version summarises this figure; select a region for its full text.

Figure. The postings sheet for the terms refund and window: five entries each, sorted doc ids with the gap to the previous id, and the positions that make a phrase query possible. Four documents hold both terms, and only two hold window immediately after refund.

What to notice. Synthetic segment. Documents ids, positions and gaps are authored to show the layout; the segment holds 1,200 documents, of which these are the postings for two terms. The figure does not claim a compression ratio or a latency measurement.

Text version

A postings sheet for one 1,200-document segment. refund has five postings: doc 41 at positions 12 and 88, doc 57 at 5 with a gap of 16, doc 88 at 41 with a gap of 31, doc 132 at 7 with a gap of 44, and doc 205 at 22 with a gap of 73. window has five postings: doc 41 at 13 and 203, doc 57 at 9, doc 88 at 42, doc 205 at 3 with a gap of 117, and doc 301 at 60 with a gap of 96. A phrase check lists four candidate documents: 41 has refund at 12 and window at 13, adjacent; 57 has 5 and 9, not adjacent; 88 has 41 and 42, adjacent; 205 has 22 and 3, not adjacent. Steps mark the lists, the gaps, the intersection, the positional check, the tombstone and the stale-position failure.

  1. Assign every document a stable internal id, because postings reference ids and reassignment invalidates them.
  2. Tokenize and normalise each document, then emit one posting per term occurrence with the document id and position.
  3. Sort postings by document id and delta-encode the gaps so the list compresses well.
  4. Intersect or union postings for multi-term queries, using skip pointers to jump past non-matching blocks.
  5. Use stored positions to verify phrase and proximity constraints after the candidate set is reduced.
  6. Handle deletes with tombstones and periodic segment merges rather than rewriting the whole structure per edit.

Trade-offs

ChoiceGood forCostFails when
Positional indexPhrase and proximity queriesSeveral times the storage of a term-only indexThe corpus is large and only bag-of-words queries are needed
Immutable segments with mergesFast writes and compressed readsBackground merge load and temporary space amplificationIngest rate is high and disk headroom is thin
Tombstone deletesCheap removal at write timeDead entries still consume space until mergeChurn is high and merges are infrequent
In-memory postingsLowest query latencyMemory cost and slow restartThe corpus outgrows available RAM
Trade-off mapInteractive

Good for

Phrase and proximity queries

Cost

Several times the storage of a term-only index

Fails when

The corpus is large and only bag-of-words queries are needed

  1. The corpus is large and only bag-of-words queries are needed
  2. Ingest rate is high and disk headroom is thin
  3. Churn is high and merges are infrequent
  4. The corpus outgrows available RAM

Figure. Each choice with what it buys, what it costs, and the case where it loses.

What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.

Text version

Four trade-offs: Positional index is good for Phrase and proximity queries, costs Several times the storage of a term-only index, and fails when The corpus is large and only bag-of-words queries are needed. Immutable segments with merges is good for Fast writes and compressed reads, costs Background merge load and temporary space amplification, and fails when Ingest rate is high and disk headroom is thin. Tombstone deletes is good for Cheap removal at write time, costs Dead entries still consume space until merge, and fails when Churn is high and merges are infrequent. In-memory postings is good for Lowest query latency, costs Memory cost and slow restart, and fails when The corpus outgrows available RAM

Failure modes

  • Stale postings after deletion. A removed document still appears in results because only the tombstone was written. Debug: query for a known deleted id and confirm the postings were merged away.
  • Position drift on update. An edited document keeps old positions, so phrase queries match text that no longer exists. Debug: re-fetch the stored field and compare it with the positions used to answer the phrase query.
  • Unbounded posting lists. A very common term produces a list so long that query latency spikes. Debug: log the number of postings scanned per query and inspect the terms with the largest lists.

In production

Track index size, merge backlog and query latency per term rarity. Cap the number of postings a single query may scan, and schedule merges outside peak traffic.

Common misconceptions

People think: An inverted index stores the documents.

Actually: It stores term-to-id mappings; the text lives in a separate store and is fetched after ranking.

People think: Deleting a document removes it immediately.

Actually: Most engines mark it deleted and reclaim space during a merge, so a deleted document can remain physically present for a while.

Interview angle

Walk through the postings layout, the purpose of positions, and how deletes and merges actually work. Connect sorted ids and compression to query latency, and explain why lexical engines pay for updates. Responses that stop at words mapped to documents cannot answer how a phrase query is resolved or why removing a document is not instant.

Sources