Indexing & the Inverted Index

Overview

A row in a database is just data until something turns it into a structure a query can search quickly. That structure is the inverted index: a mapping from term → the list of documents containing it (a “postings list”), instead of a document → its terms (a “forward index,” which is exactly what a normal database table already gives you). The whole reason query serving can answer in milliseconds instead of scanning every row is that this inversion already happened ahead of time, off in a separate pipeline from the database itself.

Getting Documents Into the Index

Assume the documents themselves already exist as rows in a database — a documents or tickets or listings table, whatever the product is. The question this subsystem exists to answer is: how do those rows become calls into the indexer, and stay in sync as rows are inserted, edited, or deleted?

• Batch reindex — periodically SELECT * FROM documents and bulk-index the results. Simple, but the index is only ever as fresh as the last run.
• Dual writes — the application writes to the database and to the search index in the same request path. Cheap to build, but not atomic: a crash or timeout between the two writes leaves them silently inconsistent, and there’s no log to replay to catch it later. Rarely the right answer past a prototype.
• Change Data Capture (CDC) — a tool (e.g., Debezium) tails the database’s own write-ahead log or binlog (Postgres WAL, MySQL binlog) and emits an event for every insert/update/delete, typically onto a Kafka topic. A consumer applies each event to the search index via a bulk API. This is the production-grade answer: the database stays the single source of truth, indexing becomes an asynchronous projection off its change stream instead of a second write the application has to remember to make, and — because it reads committed changes off the log rather than intercepting application code — nothing is missed even if a row is changed by a bulk SQL script that never goes through the app at all.

Database (Postgres/MySQL) ──▶ WAL/binlog ──▶ CDC (Debezium) ──▶ Kafka topic ──▶ Indexer consumer ──▶ Bulk API ──▶ Segments

Two details matter once CDC is in the picture: index writes must be idempotent (upsert keyed by the same doc_id the database uses as primary key, since Kafka delivery is at-least-once and events can replay), and a full reindex path has to exist independently of the stream — to seed a brand-new index, or to recover if the index and database ever drift — by replaying the entire table through the same consumer logic rather than treating the stream as the only way data gets in.

Everything below — from the single-machine toy version up through how Lucene actually stores a segment — is about what happens after a document arrives at the indexer. It applies unchanged regardless of which of the three paths above delivered it.

API Design

Indexing is an internal pipeline, not something a client calls directly:

Indexer.process(doc_id, content) -> void  -- tokenizes, scores, writes postings
Indexer.reindex(doc_id) -> void           -- re-processes a single doc (e.g., after a CDC update event)
Indexer.delete(doc_id) -> void            -- removes a doc's postings (e.g., after a CDC delete event)

Indexer.process is the whole subsystem in one call: parse the content, tokenize into terms, compute a per-term relevance signal, and merge the result into the term’s postings list. Everything else in this page is about how that one operation is made fast and durable at scale.

Database Schema

Conceptual shape — one postings list per term:

term:"search"  → [ (doc_id: 41, tf: 3, positions: [12, 88, 140]),
                    (doc_id: 7,  tf: 1, positions: [4]),
                    ... ]

-- source of truth, owned by the application — not the index itself
CREATE TABLE documents (
  doc_id      BIGINT PRIMARY KEY,
  title       TEXT,
  body        TEXT NOT NULL,
  updated_at  TIMESTAMPTZ NOT NULL
);

Storing positions (where in the document each occurrence falls) is what later lets query serving support phrase queries (“machine learning” as an exact phrase, not just both words present anywhere) — worth mentioning explicitly, since it’s the detail that connects this schema choice to a feature two subsystems away.

Basic Approach — Single-Machine, Build-From-Scratch

How it works

Hold the entire index as an in-memory hash map (term → postings list) on one machine. On a batch cadence, reprocess every document in the table from scratch and rebuild the map.

Documents (DB) ──▶ Tokenize ──▶ In-Memory Map (term → postings)

Tradeoffs

• Pro: Simplest possible design — a hash map is all the data structure you need.
• Con: The whole index has to fit in one machine’s memory, which caps out long before the document count gets large.
• Con: Rebuilding from scratch means the index is only ever as fresh as the last full rebuild — there’s no notion of incrementally adding one new document.

Scaled Approach — Distributed Build (MapReduce-Style)

How it works

Split index construction into a map phase (each worker tokenizes a shard of documents into (term, doc_id, positions) tuples) and a reduce phase (tuples for the same term, wherever they came from, get grouped and merged into that term’s final postings list). This is the same shape as a classic MapReduce word count, just emitting positions instead of counts.

Docs (sharded) ──▶ Map: (term, doc_id, positions) ──▶ Shuffle by term ──▶ Reduce: merge into postings list

Tradeoffs

• Pro: Both tokenization and merging parallelize across many machines — index build time scales with cluster size, not corpus size on one box.
• Pro: The output — one postings list per term — is naturally shardable across serving nodes afterward (see Sharding & the Distributed Index).
• Con: Still fundamentally a batch process — a row written after a build starts won’t appear in the index until the next full run.
• Con: The shuffle-by-term step moves a large volume of intermediate data across the network, which becomes the actual bottleneck at scale.

Advanced Approach — Incremental Segments, Compression, and Ranking Signals

How it works

Three refinements on top of the batch build:

• Segment-based incremental indexing: instead of rebuilding one giant index, write each new batch of documents as its own small immutable “segment” (its own mini inverted index), and merge small segments into larger ones in the background over time. A query then searches across all live segments and merges results — new or updated documents become searchable within minutes (or seconds), not on the next full rebuild. This is what makes CDC-driven indexing actually near-real-time instead of just “batch, but with smaller batches.”
• Compression: postings lists are dominated by long lists of monotonically increasing doc IDs — store them as delta-encoded, variable-byte integers (the gap since the previous ID, using only as many bytes as the value needs) instead of raw fixed-width integers, cutting index size dramatically.
• Precomputed ranking signals: attach a static relevance signal per document at index time (e.g., BM25 term-frequency scoring) so query serving can rank quickly using precomputed numbers instead of computing relevance from raw text on every query.

New/Updated Docs ──▶ New Segment (own mini-index) ──┐
                                                     ├─▶ Query merges across all live segments
Older Segments ──▶ Background Merge ─────────────────┘

Tradeoffs

• Pro: Freshness improves from “next full rebuild” to “next segment flush,” without touching how the rest of the index is stored.
• Pro: Delta + variable-byte encoding routinely shrinks postings lists by an order of magnitude, which matters enormously once the index has to be held in memory across many serving nodes.
• Con: More segments means each query does more merging work across segments — the background merge process has to keep segment count bounded, which is itself an ongoing operational cost (this is the same tradeoff Lucene-based engines like Elasticsearch make explicitly).
• Con: Precomputed signals go stale the moment something changes (a document’s popularity or related metadata shifts) — they’re a deliberate freshness/speed tradeoff, not free accuracy.

How Lucene / Elasticsearch Actually Build This

The “Advanced Approach” above — immutable segments, delta-encoded postings, precomputed scores — isn’t a simplification of what Lucene does; it’s a description of what Lucene does. Elasticsearch (and OpenSearch, Solr) are both a distributed coordination layer wrapped around Lucene, which is the actual indexing engine underneath. Worth being precise about, since it is not a hash map built over rows in a SQL table — that mental model breaks down in two ways: a SQL table gives you row → columns (a forward index), which is the opposite of what a query needs, and a plain hash map can’t do anything but exact-match lookups (no prefix/range queries, no sorted iteration), which is more than a term dictionary needs to support.

1. Analysis — text becomes terms. Every field goes through an Analyzer: a tokenizer (split on whitespace/punctuation) followed by a chain of token filters (lowercase, stemming — “running” → “run”, stop-word removal, synonym expansion). This is the step that turns "The Quick Foxes" into the term stream [quick, fox], and it’s what Indexer.process above is glossing over with the word “tokenizes.”

2. Each segment is a small set of immutable files, not one hash map:

• Term dictionary — the sorted set of unique terms in that segment, stored as a finite state transducer (FST), not a hash table. An FST shares common prefixes across terms (so run, runner, running share storage) and — critically — supports ordered traversal and prefix lookups, which a hash table structurally cannot do; that’s what makes wildcard and range queries possible at all.
• Postings lists — per term, the doc IDs (and positions, for phrase queries) that contain it, delta + variable-byte compressed as described above.
• Doc values — a separate columnar (forward-index) store per field, built specifically for sorting and aggregations, since the postings list only answers “which docs have this term,” never “what’s this doc’s price field.”
• Stored fields — a compressed row-oriented copy of the original field values, kept only so a matched document’s contents can be returned in results.

A segment, once written, is never mutated — an update (including one delivered by a CDC event) is a delete-marker on the old doc ID plus an insert into a new segment, reconciled at merge time. That immutability is why the FST and compressed postings are safe to hold read-only in memory: nothing is ever appended to them in place.

3. Elasticsearch’s contribution is distribution and near-real-time writes, not the indexing algorithm itself. An Elasticsearch index is just several Lucene indices (shards) behind a routing layer. A write lands in an in-memory buffer and a translog (write-ahead log, for durability if the node crashes before the buffer is flushed); a periodic refresh (every 1s by default) opens that buffer as a new tiny, searchable segment — this is the “near” in near-real-time, distinct from the heavier fsync commit that makes a segment durable on disk. The background merge process from the Advanced Approach section is Lucene’s TieredMergePolicy doing exactly what’s described above.

Tech Choices

• MapReduce / Spark — the standard model for building an inverted index in parallel across a document corpus.
• BM25 — a precomputed, well-understood term-relevance scoring function, the default starting point before any learned ranking model.
• Delta + variable-byte encoding — the standard compression scheme for postings lists of monotonically increasing doc IDs.
• Lucene-style segments — the production-proven pattern for incremental, near-real-time indexing without full rebuilds. The term dictionary within each segment is an FST, not a hash map — that’s what enables prefix and range queries alongside exact lookups.
• Change Data Capture (Debezium + Kafka) — the standard way to keep a search index in sync with a database of record without dual writes.

How to Vocalize This in an Interview

Introduce the inverted index by contrasting it with the forward index a database table already gives you — “a document → its words” is what the documents table naturally stores, but a query needs the reverse. Name the sync problem explicitly and early (“the database is the source of truth, the index is a derived, eventually-consistent projection of it”) and land on CDC over dual writes as the answer — that’s the detail that signals you’ve actually run this in production, not just read about inverted indexes. Build up from a single-machine hash map to MapReduce only once “what if the index doesn’t fit on one machine” comes up naturally, and bring up segments/incremental indexing as the direct answer to “how fresh is this index, really” rather than a fact recited on its own.