Search and the Inverted Index: From Token to Postings

Overview

Ask a relational database for rows containing “error” anywhere in a million-row log table and it will run WHERE msg LIKE '%error%' — a full scan, because no B+tree can index inside a string’s middle. Ask a search engine the same question and it answers in microseconds from a data structure built for exactly this: the inverted index, which maps each analyzed term to the list of documents containing it. The two systems also disagree philosophically: a transactional database promises that a committed row is immediately visible to the next query under ACID; a search engine embraces near-real-time visibility — writes become searchable after a refresh lag measured in seconds — in exchange for write throughput and immutable, mergeable segments. Understanding search therefore means holding two connections at once: the similarity between inverted indexes and database indexes (both are sorted structures over keys that turn linear scans into seeks), and the divergence (relevance scoring instead of exact matching, immutable segments instead of in-place MVCC, eventual visibility instead of commit points).

This page walks the full pipeline — analyzer to term dictionary to postings to scoring to segment model to query cache — and then maps it against the transactional-DB world the reader likely met first. The mapping is a senior-interview staple (“why is Elasticsearch not a database?”, “why can’t Postgres just index this?”), and the honest answer is a boundary, not a slogan: inverted indexes and B+trees share the seek-don’t-scan principle, share even the sorted-merge join shape of query evaluation, and diverge exactly where relevance replaces correctness as the contract. Where the two worlds can meet — GIN indexes, full-text extensions inside relational engines — is itself a lesson in what each side pays for the other’s strengths.

The Subsystems, Independently

The analyzer. Text is not indexed as written; it is analyzed: character filters normalize (strip HTML), a tokenizer splits into tokens (on whitespace, punctuation, or language-aware rules), and token filters transform (lowercase, stopword removal, stemming, synonym expansion). The analyzed form is what lands in the index — and because the query string goes through its own analysis at query time, analyzer mismatches (stemming at index but not at query) silently produce zero results. Analysis is where “search quality” begins: the index is only as smart as the transformation that fed it, and it is also where language enters the data structure (CJK languages without spaces need different tokenizers entirely; see ../../dbms/sql/full-text-search.md).

The inverted index: term dictionary + postings. The index maps each term to a postings list: the documents (by internal ID) containing that term, usually with term frequency per document and positions when phrase or proximity queries matter. The term dictionary is kept sorted so terms can be binary-searched — in Lucene, compressed into an FST (a finite-state transducer that shares prefixes and suffixes across terms, small enough to memory-map), so term lookup is a pointer walk, not a hash probe. Query evaluation is set algebra over sorted integer lists: an AND is a merge-intersection of postings (skip lists let it jump past non-overlapping runs), an OR is a merge-union, a NOT is subtraction against the doc-id universe. Doc IDs are assigned at index time and delta-encoded, so postings compress well and scan at memory speed (see ../../dbms/nosql/search-engine-internals.md for the engine-level detail).

Scoring: TF-IDF and BM25. Matching is cheap; ranking is the product. Classic TF-IDF scores a term by its frequency in the document times its rarity in the corpus. BM25 refines this with two empirically tuned curves: term frequency saturates (the 10th occurrence adds much less than the 1st — the k1 parameter), and document length is normalized against the corpus average (the b parameter, 0 = no length effect, 1 = full normalization): score = IDF × tf·(k1+1) / (tf + k1·(1 − b + b·dl/avgdl)). The point for this page’s connection: scoring needs corpus statistics (document frequency, average length) that live at the segment level — another reason segments are the unit of search, and another divergence from exact-match indexing.

The segment model: near-real-time search. Writes go into an in-memory buffer plus a durable transaction log (the WAL pattern of ./event-sourcing-wal.md); a refresh (default ~1 s in Elasticsearch) converts the buffer into a new immutable segment that is instantly searchable — no fsync required for visibility, only for durability. Deletes are tombstone bitmaps over segment doc IDs (the doc stays until a merge compacts it away); updates are delete-plus-reinsert. Merges are the LSM-style background cost (../../dbms/internals/lsm-trees.md): they bound segment count, reclaim deleted space, and are throttled precisely because they compete with indexing I/O. Immutability is what buys everything else: segments can be memory-mapped, shared across queries, and cached safely (see ../../dbms/internals/compaction.md for the merge-policy mathematics).

Query caching. Because segments never change, per-segment filter results (the doc-ID set matching a filter clause) are cacheable until the segment is merged away — a cache whose keys are invalidated by physical events (merges), not logical ones. This is the cleanest possible instance of the invalidate-only-what-changed model in ./incremental-computation.md, and it explains a counterintuitive production fact: heavy merge activity degrades read latency too, by flushing the filter cache. Postgres-side analogues cache plans and buffer pages (../../dbms/caching/query-cache.md), but the segment-local cache is unique to the immutable-segment design.

The Shared Principle

An inverted index is a B+tree-shaped idea transposed from values to terms: a sorted key structure (term dictionary) whose entries point to row-ID lists (postings), turning “scan everything” into “seek the term, merge the lists.” The DB secondary index and the search postings list are the same animal — sorted key → row IDs — which is why database engines can host search (Postgres GIN is literally an inverted index; see ../../dbms/indexing/gin.md), and why the db-indexes page’s medium-shapes-structure argument (./db-indexes-data-structures.md) predicts the term dictionary’s FST just as it predicted the B+tree: a read-mostly, scan-heavy, memory-mapped workload wants prefix compression and sequential access, not mutable pages.

The divergence is a contract difference, and it is the senior-level content: a DB index answers membership queries with exact, transactionally-consistent truth; a search index answers ranked queries over a slightly stale, eventually-consistent view. That contract difference drives every structural divergence — immutable segments instead of in-place updates (updates are O(document) delete+reinsert, not O(entry) in-place), refresh lag instead of commit visibility, segment-level statistics instead of global ones, scoring functions instead of equality predicates. When someone asks “why not just put it all in Postgres with a GIN index?”, the honest answer prices both sides: GIN gives you transactions and one less system, and costs you BM25-grade ranking, horizontal read scale, and merge-managed segment compaction — see ../followup-tree/database-indexes.md for the index-choice escalation tree.

Where the Coupling HOLDS and BREAKS

A Concrete Worked Example

Why LIKE '%error%' scans and the inverted index does not, with numbers. A 10 M-row log table, 200-byte messages, on a B+tree keyed by timestamp. msg LIKE 'error%' can use an index (prefix is seekable); LIKE '%error%' cannot — the engine must read all ~2 GB of rows, matching in each: minutes of I/O at disk speed, seconds even fully cached. The inverted index path: analyze “error” to one term, seek the term dictionary (an FST walk of ~5 pointer hops), fetch its postings — say 400,000 doc IDs, delta-encoded at ~1–2 bytes each ≈ 0.6 MB — and merge with the time-range filter’s set. Total work: kilobytes of seek plus a linear merge over the result candidate set. The ratio (~10³–10⁴×) is exactly the seek-versus-scan gap from ./db-indexes-data-structures.md — the same physics, applied to a different key type (terms instead of values). The cost side of the ledger: building that index required analyzing and posting every token of every row — roughly 5–10× the storage of the raw text — which is why search indexes are built for read-heavy workloads and why transactional systems resist paying that write amplification for substring queries they rarely run.

Refresh lag and its failure signature. An indexing pipeline writes a document at t=0; the transaction log holds it durably at t=0.01 s; refresh at t=0.8 s makes it searchable; a user searching at t=0.3 s sees nothing, at t=1.0 s sees it. At 50,000 docs/s and 1 s refresh, each refresh segment holds ~50,000 docs; the “did we lose the order?” support ticket that resolves itself a second later is this mechanism, not a bug. The failure signature to teach: search says no, the database says yes — and the reconciliation rule is architectural: the database is the truth, search is the view, and any “find my order” flow that treats search absence as nonexistence has inverted that relationship (see ../../dbms/advanced/membership-filters.md for the probabilistic version of “probably absent” and what Bloom filters do and do not promise).

When This Connection Is Useful

• Problem-solving heuristics. Given a “find things by text” requirement, decide along the connection’s axes: exact prefix match → DB index (LIKE 'x%' is seekable); substring/relevance/fuzzy/multi-field → inverted index; transactions over the same data → keep the DB authoritative and replicate to search; ranking quality → analyzer + BM25 tuning before infrastructure changes. Diagnose slow search queries by postings size first (which terms are huge?), merge pressure second (is the filter cache churning?), and segment count third.
• Interview answers. “Why is Elasticsearch fast for search but a bad primary store?” is answered by the contract divergence — NRT visibility, no multi-document ACID, updates as delete+reinsert, scoring instead of exactness — each priced concretely. “What do an inverted index and a B+tree share?” is the seek-don’t-scan principle plus sorted-merge evaluation; “where do they diverge?” is relevance versus consistency. “How would you add search to an existing Postgres application?” is the GIN-versus-external-engine decision with CDC in the middle.
• Engineering decisions. Match index-time and query-time analyzers in tests, not hope; size refresh intervals to the product’s staleness tolerance, not to a default; monitor merge I/O as a read-latency cost; treat search as a derived, rebuildable view (reindex from source of truth is your backup plan); and use bitmap postings and Bloom-filtered term lookups (see ../../dbms/advanced/roaring-bitmaps.md) where filter-heavy workloads dominate.

Interview Questions

1. Walk a query token from user input to ranked results through the full pipeline — analyzer, term dictionary, postings, scoring, segments. At which step do most “zero results” bugs live, and why?
2. Why can LIKE 'error%' use an index while LIKE '%error%' cannot, and what does the inverted index change about that physics? Price both sides of the change (query speed versus write/storage cost).
3. Explain BM25’s two parameters in terms of retrieval behavior: what does k1 saturation prevent, and what does b normalization trade off? Why must corpus statistics live at segment granularity in this design?
4. Contrast search-engine visibility (refresh) with database commit visibility. What is the correct architectural relationship between the two systems, and what bug class does dual-writing create?
5. A search cluster’s p99 read latency rises during heavy indexing. Give the mechanism that couples the two (merges and the filter cache) and two mitigations with their costs.

Key Takeaways

• The inverted index transposes the B+tree idea from values to terms: sorted term dictionary (FST) → postings lists → merge-based set algebra; LIKE '%x%' scans because no sorted structure keys on substrings — search indexes are the answer to a different key type.
• Analysis is the contract: what is indexed is the analyzed token, so index-time and query-time analysis must match; search quality is decided before the data structure is touched.
• BM25 prices relevance with saturation (k1) and length normalization (b) over segment-local statistics; ranking, not correctness, is the search index’s contract — the core divergence from transactional indexes.
• Immutable segments + translog + refresh give near-real-time search: visibility in ~1 s, durability decoupled; deletes are tombstones reclaimed by merges, which couple write background load to read cache health.
• Search should be a derived view over the transactional source of truth (CDC-fed), never dual-written; “search says no, database says yes” is a designed-in property, not a bug.

Cross-References

• ./db-indexes-data-structures.md — DB Indexes and Data Structures — the storage-medium-shapes-structure argument the term dictionary instantiates.
• ../followup-tree/database-indexes.md — Database Indexes Follow-up — the index-choice escalation tree for when search requirements meet relational constraints.
• ./event-sourcing-wal.md — Event Sourcing and WAL — the translog, CDC sync, and state-as-a-fold behind search/DB integration.
• ./incremental-computation.md — Incremental Computation — segment-immutable caches and invalidate-only-what-changed.
• ./virtual-memory-caching.md — Virtual Memory and Caching — where memory-mapped segments and their caches sit in the hierarchy.
• ../../dbms/nosql/search-engine-internals.md — Search Engine Internals — engine-level segment, merge, and shard mechanics.
• ../../dbms/sql/full-text-search.md — SQL Full-Text Search — text search inside relational engines.
• ../../dbms/indexing/gin.md — GIN Indexes — the inverted index living inside Postgres.
• ../../dbms/internals/lsm-trees.md — LSM Trees — the segment/merge lineage search shares with write-optimized stores.
• ../../dbms/internals/compaction.md — Compaction — merge policy and its I/O budget in full.
• ../../dbms/advanced/roaring-bitmaps.md — Roaring Bitmaps — compressed doc-ID sets behind filters and facets.
• ../../dbms/advanced/membership-filters.md — Membership Filters — Bloom filters and the probabilistic “absent” answer.
• ../../dbms/caching/query-cache.md — Query Cache — the relational side of cached query results.