Inverted Indexing Explained: From Documents to Millisecond Search

The core inversion

A normal document store answers “what words are in document 42?” An inverted index answers the opposite question: “which documents contain this word?” That reversal moves the expensive work from query time to indexing time. Instead of scanning every document for “search engine”, the query performs two dictionary lookups and intersects two already-sorted lists.

The vocabulary on the right is the term dictionary. Each term points to a postings list—a sorted list of matching document IDs plus optional evidence. Search is fast because work is proportional to the matching lists, not the entire corpus.

Anatomy of an inverted index

A production posting stores more than a document ID. The engine may keep term frequency for ranking, positions for phrase/proximity queries, offsets for highlighting, payloads for custom scoring, and per-document field-length norms. Every optional feature costs disk and indexing time.

• Term dictionary: a sorted vocabulary, commonly represented with a finite-state transducer so shared prefixes are compressed.
• Postings: monotonically increasing document IDs, usually delta-encoded in blocks.
• Term vectors: optional per-document term information; useful for “more like this,” expensive to store.
• Stored fields: values returned to the caller. They are not the inverted index and need not be searchable.
• Doc values: column-oriented values used for sorting, aggregations and scripting—the reverse access pattern of postings.

The analysis pipeline decides what can be found

The engine never indexes prose directly. An analyzer converts text into a token stream. The same compatible analysis must run on the query, or the query and index speak different vocabularies.

input: "The runners are RUNNING quickly"

term      position   offsets
runner       1        4..11
run          3       16..23
quick        4       24..31

# "the" and "are" were removed; runners/running were stemmed.

Index-time and query-time analysis

They are often similar, not necessarily identical. Index-time synonym expansion can multiply postings forever; query-time expansion costs CPU per request but is easy to update. Exact identifiers, SKUs and tags should usually be keyword values, not language-analyzed text.

How to build one

1. Assign each document a compact internal document ID.
2. Extract indexed fields and run each field’s analyzer.
3. Emit tuples such as (term, docID, position, offsets).
4. Sort by term and document ID; aggregate repeated terms into one posting.
5. Encode the dictionary, postings, stored fields and columnar doc values into an immutable segment.
6. Publish the new segment so searches can see it.

type Posting = { tf: number; positions: number[] };
const index = new Map<string, Map<number, Posting>>();

for (const doc of documents) {
  const tokens = analyze(doc.body);
  for (const token of tokens) {
    let list = index.get(token.term);
    if (!list) index.set(token.term, (list = new Map()));
    let posting = list.get(doc.id);
    if (!posting) list.set(doc.id, (posting = { tf: 0, positions: [] }));
    posting.tf += 1;
    posting.positions.push(token.position);
  }
}

The toy map is useful for understanding, but it is not a durable search engine. Real construction uses bounded RAM, sorted runs, block encodings, checksums, write-ahead durability, immutable files and background merging.

Boolean, prefix and phrase queries

AND is a sorted-list intersection

Because postings are sorted by document ID, search AND engine needs a linear merge, not a hash set. Compare both cursors; when IDs match, emit the document. Otherwise advance the smaller ID. Complexity is O(m+n), with skip data allowing larger jumps.

OR, NOT and filters

• OR merges the union and combines scores.
• NOT subtracts a postings set, but a pure negative query may still require visiting many documents.
• Filters produce a yes/no bitset and skip scoring; repeated filters can be cached.
• Prefix/wildcard queries first enumerate matching dictionary terms. A leading wildcard can enumerate an enormous vocabulary.

Phrase queries need positions

“search engine” first intersects the two document lists. Inside each surviving document, it checks whether an engine position is exactly one greater than a search position. Slop broadens the allowed distance and order.

Ranking: why matching is only half the job

A Boolean index tells us what matches. Ranking decides what deserves the first page. BM25 rewards a term appearing repeatedly in a document, rewards rare terms more than common ones, and normalizes for field length so a short title is not drowned by a long body.

score(q, d) = Σ IDF(t) × [ tf(t,d) × (k₁ + 1) ]
                         ─────────────────────────────
                         tf(t,d) + k₁ × (1 - b + b × |d| / avgdl)

IDF(t) ≈ log(1 + (N - df(t) + 0.5) / (df(t) + 0.5))

N      = documents in the collection
_df(t) = documents containing term t
|d|    = field length; avgdl = average field length

Distributed BM25 introduces a subtlety: each shard can estimate rarity from local statistics. DFS-style querying can collect global statistics first, but costs another round trip. Large, balanced shards usually make local estimates acceptable.

Compression, blocks and skip data

Postings lists are large but unusually compressible. Document IDs increase monotonically, so the engine stores gaps: [100, 104, 107, 140] becomes [100, 4, 3, 33]. Small gaps need few bits. Block-based encodings pack many gaps using one bit width and support fast SIMD decoding.

• Variable-byte encoding: simple and compact for small integers.
• Frame-of-reference / bit packing: excellent throughput for blocks with similar magnitudes.
• Skip pointers: jump over ranges that cannot intersect the other list.
• Impact ordering / block maxima: skip blocks that cannot enter the current top-k results.

Updates, deletes and immutable segments

Editing a term in-place would shift compressed bytes and rewrite large files. Lucene-style engines avoid that: segments are immutable. New documents go to a buffer, a refresh publishes a new searchable segment, deletes set bits in a live-docs bitmap, and background merges compact segments while physically dropping deleted versions.

Aggressive refreshing creates many tiny segments; aggressive merging steals I/O from queries and indexing. The right policy balances freshness, write throughput, query fan-out and disk reclamation.

Distributed inverted indexes

At scale, the corpus is split into shards and each shard owns a complete local inverted index. A coordinating node sends the query to one copy of every relevant shard. Each shard returns its local top-k document IDs and scores; the coordinator merges them, then fetches only the winners.

• More primary shards increase parallelism and capacity, but every query has more coordination and queueing overhead.
• Replicas provide failover and extra read throughput; they do not increase write capacity for the same documents.
• Routing by tenant or entity can reduce fan-out, but a bad routing key creates hot shards.
• Deep pagination forces each shard to retain many candidates. Prefer search_after plus a stable tiebreaker.

Designing a search system around the index

Keep the transactional database as the source of truth and treat the search index as a derived read model. Publish changes through an outbox or change-data-capture stream, transform them into search documents, and make consumers idempotent. Search may be briefly stale; writes must remain correct.

Capacity questions to answer

• How many documents, indexed characters and distinct terms exist now and in one year?
• Which fields need positions, offsets, sorting, aggregations or source storage?
• What freshness SLA is required: seconds, minutes or daily batches?
• What are peak indexing QPS, query QPS, top-k, concurrency and latency percentiles?
• Can users tolerate stale results, partial shard failures or approximate counts?

index_bytes ≈ source_bytes
            + postings_bytes
            + positions_and_offsets
            + doc_values
            + stored_fields
            + segment_and_merge_headroom

plan 1.5–2× disk headroom for merges, replicas separately,
and benchmark with the real analyzer and field mapping.

Failure modes that appear in production

A strong interview answer

“I would keep the database as source of truth and asynchronously build a denormalized search document through an outbox or CDC pipeline. The index analyzer emits normalized terms into a compressed term dictionary and sorted postings lists containing document IDs, frequencies and positions. AND queries intersect postings; phrase queries verify adjacent positions; BM25 ranks survivors. Writes create immutable segments, deletes use tombstones, and background merges reclaim space. At scale, documents are sharded, queries scatter to shards, and a coordinator merges local top-k results. I would explicitly choose the freshness SLA, analyzer, stored features, shard strategy and relevance metrics before sizing.”

Continue with Elasticsearch Explained for the surrounding distributed engine, or follow the HLD learning roadmap to practise placing search inside a complete system design.