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
Synthetic postings sheet · segment 07 · 1,200 documents
Two terms · five postings each · one phrase query
bounding boxes
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
Postings for two terms
| Doc | Positions | Gap |
|---|---|---|
| 41 | 12, 88 | — |
| 57 | 5 | +16 |
| 88 | 41 | +31 |
| 132 | 7 | +44 |
| 205 | 22 | +73 |
| Doc | Positions | Gap |
|---|---|---|
| 41 | 13, 203 | — |
| 57 | 9 | +16 |
| 88 | 42 | +31 |
| 205 | 3 | +117 |
| 301 | 60 | +96 |
| Doc | refund | window | Adjacent |
|---|---|---|---|
| 41 | 12 | 13 | yes |
| 57 | 5 | 9 | no |
| 88 | 41 | 42 | yes |
| 205 | 22 | 3 | no |
10 postings · 4 candidates · 2 hits · 1 tombstone · 0 full scans
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.
- Assign every document a stable internal id, because postings reference ids and reassignment invalidates them.
- Tokenize and normalise each document, then emit one posting per term occurrence with the document id and position.
- Sort postings by document id and delta-encode the gaps so the list compresses well.
- Intersect or union postings for multi-term queries, using skip pointers to jump past non-matching blocks.
- Use stored positions to verify phrase and proximity constraints after the candidate set is reduced.
- Handle deletes with tombstones and periodic segment merges rather than rewriting the whole structure per edit.
Trade-offs
| Choice | Good for | Cost | Fails when |
|---|---|---|---|
| Positional index | Phrase and proximity queries | Several times the storage of a term-only index | The corpus is large and only bag-of-words queries are needed |
| Immutable segments with merges | Fast writes and compressed reads | Background merge load and temporary space amplification | Ingest rate is high and disk headroom is thin |
| Tombstone deletes | Cheap removal at write time | Dead entries still consume space until merge | Churn is high and merges are infrequent |
| In-memory postings | Lowest query latency | Memory cost and slow restart | The corpus outgrows available RAM |
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
- The corpus is large and only bag-of-words queries are needed
- Ingest rate is high and disk headroom is thin
- Churn is high and merges are infrequent
- 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
- Manning, Raghavan & Schütze, Introduction to Information Retrieval — postings lists, compression, skip pointers and phrase queries.
- PostgreSQL, GIN indexes — an inverted index implemented inside a general database.
- Apache Lucene core documentation — segments, postings and merge behaviour in a widely used engine.