Search Indexing - Complete Deep Dive

Prerequisites: Database Indexing, Caching Used in: Web Crawler, Search Autocomplete, Zomato, Q&A Forum

What is a Search Index?

A search index is a data structure that answers “which documents contain these words, and which of them are most relevant?” A database index answers “where is the row with this key?” Those are different questions, and the second one is much easier.

The structure that does the work is the inverted index: instead of mapping a document to its words, map every word to the documents that contain it. Everything else on this page is either how you decide what counts as a word, or how you order the results.

Real-world analogy: The index at the back of a textbook. Nobody builds it by listing each page’s contents. You list each concept once and record every page it appears on. Looking up “binary search” is then a single lookup instead of 600 page reads. A search engine does the same thing over a billion pages, and additionally tells you which page is most about binary search.

Why LIKE ‘%term%’ Is Not Search

SELECT * FROM articles WHERE body LIKE '%distributed cache%';

This query is not slow search. It is not search.

No index can serve it. A B-tree index on body is sorted by the full string value, so it can answer a left-anchored LIKE 'distributed%' and nothing else. A leading wildcard forces a full table scan: read every row, run a substring match on every body. At 10M articles averaging 2KB that is 20GB of I/O per query, every query.

No ranking. The result is a set, not a ranked list. A document with the phrase once in a footer is indistinguishable from one with it forty times in the opening paragraph. The ORDER BY you reach for next sorts on a column - date, votes - because there is no relevance to sort on.

No tokenisation. '%cache%' matches “cached” and “caches”, which you wanted, and also “cachet” and “apache”, which you did not. It is substring matching, not word matching. Search for “distributed caches” and you get nothing from a document that says “caching in distributed systems” - different order, different inflection, zero results.

Nothing else either. No typo tolerance, no synonyms, no phrase proximity, no weighting title above body, no faceting.

To be fair to databases: Postgres tsvector with a GIN index fixes most of this. It tokenises, applies stop words and stemming, and ranks with ts_rank. It is the correct choice far more often than people admit. The real gap is in two steps - from LIKE to tsvector, which is enormous, and from tsvector to a Lucene engine, which is about BM25 with query-time field boosts, faceting, sharding past one machine, and as-you-type matching.

The Inverted Index

Three tiny documents, run all the way through:

Documents
  D1: "the cat sat on the mat"
  D2: "the dog sat on the cat"
  D3: "cats and dogs"

Forward index - what a row store has
  D1 -> [the, cat, sat, on, the, mat]
  D2 -> [the, dog, sat, on, the, cat]
  D3 -> [cats, and, dogs]

Inverted index - after stop words and stemming
  term   posting list as docId, termFreq, positions
  -----  ------------------------------------------
  cat    (D1, 1, [1])  (D2, 1, [5])  (D3, 1, [0])
  dog    (D2, 1, [1])  (D3, 1, [2])
  mat    (D1, 1, [5])
  sat    (D1, 1, [2])  (D2, 1, [2])

“cats” and “dogs” stemmed to cat and dog, so a search for “dog” finds D3 even though D3 never contains that exact string. The words the, on, and and were dropped as stop words. Positions are recorded from the original token stream, which is what makes the next trick possible.

Query: cat sat
  posting list for cat -> {D1, D2, D3}
  posting list for sat -> {D1, D2}
  intersect              -> {D1, D2}

Phrase query: "cat sat"
  D1: cat at 1, sat at 2  -> adjacent, match
  D2: cat at 5, sat at 2  -> not adjacent, reject
  result -> {D1}

Two properties make this fast at scale. Posting lists are stored sorted by document ID, so an intersection is a linear merge rather than a hash join. And each list carries skip pointers, so merging a two-term query costs roughly the length of the shorter list - which is why adding a rare term to a query makes it faster, not slower.

Posting lists also compress extremely well. Store gaps between document IDs instead of the IDs themselves - delta encoding - then variable-byte or Frame-of-Reference encode the gaps. A dense posting list over 10M documents routinely shrinks to a few bits per entry.

The Analysis Pipeline

Analysis turns a blob of text into terms. Whatever it produces is your vocabulary - if analysis drops a word, no query can ever find it.

flowchart LR
    DOC["Incoming document"]:::client
    AN["Analysis chain<br/>tokenise fold stem"]:::service
    BUF["In memory buffer<br/>not yet searchable"]:::service
    SEG[("Segment<br/>immutable mini index")]:::data
    MRG[("Merged segment")]:::data

    DOC -->|"1. Index request"| AN
    AN -->|"2. Terms and positions"| BUF
    BUF -->|"3. Refresh makes it visible"| SEG
    SEG -->|"4. Background merge"| MRG

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#60a5fa,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef async fill:#3b1f5e,stroke:#c084fc,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Tokenisation splits text into tokens. It sounds trivial and it is where most search quality bugs actually live. A naive split on non-letters destroys C++, wi-fi, user@example.com, 192.168.1.1, and ERR_CONN_REFUSED. Chinese and Japanese have no spaces at all and need a dictionary-based segmenter. Pick the tokeniser that matches your content, then test it against your weirdest real documents.

Case folding lowercases everything so “Cat” and “cat” are one term. Cheap, almost always right, and it quietly destroys acronyms - “IT” becomes “it”, which the next stage then discards as a stop word.

Stop words are the extremely common terms: the, a, of, is. They were historically dropped because “the” appears in nearly every document, so its posting list is almost the entire corpus while contributing nothing to discrimination. Modern engines mostly keep them, for two reasons: BM25’s IDF already drives their contribution to near zero, and dropping them breaks phrase search - “to be or not to be” analyses to an empty query.

Stemming versus lemmatisation both reduce inflections, differently.

Stemming producing non-words is not a problem, because the query goes through the same stemmer. Both sides meet at cach and match. It becomes a problem when it conflates unrelated words, and you only find out when a user complains that searching for “universal” returns university rankings.

N-grams index substrings so partial input can hit a term. Edge n-grams expand “cache” to c, ca, cac, cach, cache, which turns as-you-type matching into an ordinary term lookup instead of a wildcard scan. Full n-grams expand it to cac, ach, che and give you infix matching. Both inflate the index substantially - roughly by the average term length for edge n-grams - so apply them to one field, not to everything.
💡 For typo tolerance specifically, n-grams are the wrong tool. Lucene’s fuzzy query walks the term dictionary with a Levenshtein automaton, which finds edit-distance neighbours without multiplying the index.

The most common production search bug: the index-time analyser and the query-time analyser drift apart. Index with a stemmer, query without one, and “running” will never match “run”. If a field returns nothing for queries you are certain should match, compare the two analysers before anything else.

Ranking: From Term Frequency to BM25

Retrieval finds candidates. Ranking decides the order, and the order is the product.

Term frequency alone

Score a document by how many times the query term appears in it. Three failures, all immediate. A 10,000-word document outranks a 50-word one on volume alone. The word “the” dominates every score it touches. And repeating a word fifty times in a hidden div is rewarded, which is how SEO spam worked for a decade.

TF-IDF

Weight each term by how rare it is across the corpus. Inverse document frequency is roughly log(N / df) - total documents over the number containing the term.

The intuition is the useful part: rarity is evidence. A term in 5 of 10M documents tells you almost everything about those 5 documents. A term in 9M of them tells you nearly nothing. “the” has df close to N, so its IDF collapses to about zero and it stops mattering without anyone having to blacklist it. “zookeeper” has a tiny df, so a single occurrence is strong signal.

Multiply TF by IDF, divide by document length to stop long documents winning on volume, and you have a ranker that was state of the art for twenty years and is still a reasonable baseline.

Two things it gets wrong. Term frequency enters linearly, so a document with 100 occurrences of “cache” scores ten times one with 10 occurrences - and it is plainly not ten times more about caching. Past a handful of mentions, each extra mention carries almost no new information. And the length normalisation is a flat divide with no way to tune how much length should matter for your particular corpus.

BM25

Okapi BM25, from Robertson and Spärck Jones, keeps the IDF intuition and fixes both problems. It is the default in Lucene, Elasticsearch, OpenSearch, Solr, Vespa, and essentially every lexical engine shipped in the last decade.

Term-frequency saturation. TF enters through a function that rises steeply and then flattens towards a ceiling. One occurrence to two moves the score a lot. Twenty to forty barely moves it at all. Keyword stuffing stops paying.

Tunable document-length normalisation. A document’s length is compared against the average length in the corpus rather than against an absolute. “Long” becomes relative to your data, so a 2,000-word document is unremarkable in a corpus of legal filings and suspicious in a corpus of tweets.

Score contribution of one query term

  ^
  |              ...........................  ceiling, set by k1
  |         .....
  |      ...
  |    ..
  |   .
  |  .
  | .
  +--------------------------------------->  occurrences in this document
    1   2   3    5        10          20

Steep from 1 to 3. Almost flat past 10.
Multiply the whole curve by the term's IDF.
Then shift it by how far this document's length sits from the corpus average.

Two parameters, and you should be able to say what each does in plain words:

• k1 sets how quickly saturation arrives - how much an additional occurrence is still worth. Push it towards 0 and the score depends almost entirely on whether the term is present at all, not how often. Push it high and you are back to linear TF. Lucene defaults to 1.2; 1.2 to 2.0 is the usual range.
• b sets how much document length matters, from 0 for ignore-length-entirely to 1 for full normalisation against the average. Default 0.75. Lower it when long documents are genuinely more informative - manuals, legal text, documentation. Raise it when long documents are usually padding.

The final score sums the per-term contributions, so a document matching three query terms generally beats one matching a single term very strongly. That is intentional and it is usually what users want.

One honest caveat: BM25 is the retrieval layer, not the whole ranker. Production systems use it to pull a cheap candidate set of maybe 1,000 documents, then rerank the top 100 with a model that can afford to be expensive. See hybrid search and reranking.

Segments, Updates, and the Refresh Interval

A segment is a complete, immutable mini-index: its own term dictionary, its own posting lists, its own doc values. An index is just the set of its segments, and a query runs against all of them and merges the results. Lucene writes segments and never modifies them, which is the same immutability bargain an LSM tree makes, for the same reasons.

Immutability means there is no such thing as updating a document. An update is a delete plus an insert:

1. The new version is analysed and written into the current in-memory buffer.
2. Whichever segment holds the old version records that document’s internal ID in a deletion bitset.
3. Queries consult the bitset and skip deleted IDs.
4. The old copy’s bytes stay on disk until a merge rewrites that segment without them.

Which means a heavily updated index carries a lot of garbage, and - a detail that bites people - deleted-but-unmerged documents still count toward that segment’s document frequency, so they still influence IDF and therefore scores.

Segment merging combines small segments into larger ones, physically dropping deleted documents and rebuilding the term dictionary. The tradeoff is identical to LSM compaction: merge aggressively for fewer segments and faster queries at the cost of I/O, or merge lazily and watch query latency drift upward.

The refresh interval is why search is near-real-time, not real-time. An indexed document is not searchable the instant it is accepted. It sits in the in-memory buffer until a refresh turns that buffer into a new searchable segment. Elasticsearch refreshes every 1s by default. Refresh more often and you pay in segment churn and merge pressure; set it to 30s for a bulk load and indexing throughput improves several times over.

Durability is a separate mechanism and worth keeping separate in your head. Every indexing operation is appended to a translog and fsynced, so an unrefreshed buffer survives a crash.
💡 Refresh makes a document visible. Flush makes it durable. They are different operations with different intervals, and conflating them is a classic interview stumble.

Distributed Search: Sharding and Scatter-Gather

Split documents across shards by hashing the document ID. Each shard holds a disjoint subset of documents and a complete inverted index over just those documents. This is document partitioning, and the alternative - partitioning by term - makes every multi-term query a cross-shard coordination problem, which is why nobody ships it.

flowchart LR
    Q["Search query"]:::client
    CO["Coordinator"]:::edge
    S1[("Shard 1<br/>local inverted index")]:::data
    S2[("Shard 2<br/>local inverted index")]:::data
    S3[("Shard 3<br/>local inverted index")]:::data
    TOP["Merge and return top K"]:::service

    Q -->|"1. One query"| CO
    CO -->|"2. Fan out to all shards"| S1
    CO -->|"2. Fan out to all shards"| S2
    CO -->|"2. Fan out to all shards"| S3
    S1 -->|"3. Local top K with scores"| TOP
    S2 -->|"3. Local top K with scores"| TOP
    S3 -->|"3. Local top K with scores"| TOP

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef edge fill:#1e3a5f,stroke:#60a5fa,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef async fill:#3b1f5e,stroke:#c084fc,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Three consequences fall out of that picture.

Your P99 is the slowest shard, not the average shard. Twenty shards each with a 1% chance of a slow response gives roughly an 18% chance that any given query is slow, because a query needs all of them. More shards buys parallelism and costs tail latency. This is the single best reason to not over-shard a small index.

Deep pagination is brutal. Page 500 at 20 results per page means every shard must return its own top 10,000 so the coordinator can merge them and slice out the final 20. Cost grows with offset multiplied by shard count. Use a cursor - search-after, or a keyset on a tiebreaker field - and cap the page depth in the API.

Distributed scoring is approximate. IDF needs a corpus-wide document frequency, but each shard computes df over only its own documents. A term that is globally rare but happens to be common in shard 7 gets a lower IDF there, so two identically-matching documents score differently purely because of where they landed. Across millions of evenly-routed documents the error is noise you will never see. With a small corpus, or with custom routing that deliberately co-locates a tenant’s documents, it visibly reorders results. The fix is a two-pass query that gathers global term statistics before scoring - dfs_query_then_fetch in Elasticsearch - and it costs you an extra round trip on every search.

Lexical Versus Vector Search

Lexical retrieval matches tokens. If the query’s terms are not in the document, the score is zero - no partial credit for meaning. That sounds like a weakness and is also precisely its strength: SKU-44812, ERR_CONN_REFUSED, a surname, a part number. IDF makes rare exact tokens the strongest possible signal, results are explainable, and an update is visible in a second.

Vector retrieval embeds query and document into the same space and returns nearest neighbours by cosine distance. It matches meaning, so “how do I stop my app from crashing” can retrieve a document titled “handling unhandled exceptions” with no shared terms at all. It is weak exactly where lexical is strong - an embedding model blurs a rare identifier into the neighbourhood of similar-looking strings, which is the opposite of what you want when someone pastes an error code.

Hybrid retrieval runs both, fuses the two result lists with reciprocal rank fusion, and reranks the fused top ~100 with a cross-encoder. It wins when the query distribution is mixed, and for a real product it always is - the same users type SKU-44812 and “something cheap for a rainy day” into the same box. The details of fusion and reranking are in hybrid search and reranking, and the index structures behind nearest-neighbour search are in vector databases.

Comparison Table

Common Interview Questions

Q: “Postgres full-text search or Elasticsearch?” A: Start with Postgres. tsvector plus a GIN index gives you tokenising, stop words, stemming, and ts_rank relevance inside the database you already run, with no sync pipeline and no second on-call rotation, and it holds up to a few million documents. Move to a Lucene engine when you need BM25 with per-field boosts tuned at query time, aggregations and facets over result sets, sharding past one machine, as-you-type or fuzzy matching, or sub-50ms at thousands of QPS. “Just use tsvector” is frequently the senior answer, and saying so demonstrates you have priced the alternative.

Q: “How do you keep the search index in sync with the database?” A: Not with dual writes. Write the row and then call the index in the same request handler, and you get silent divergence the first time the second call fails. Turn committed database changes into a stream with change data capture or the outbox pattern, and have an indexer consume that stream and bulk-index. Under 3 seconds of lag is fine for a catalogue. Make the indexer idempotent - key on document ID and carry the row version, so a replayed event overwrites instead of duplicating.

Q: “A user creates a product and immediately cannot find it in search. What is happening?” A: The refresh interval. The document is durable - it is in the translog - but it is not yet in a searchable segment, so it is invisible for up to one second by default. Do not fix this by forcing a refresh per write; that produces a tiny segment per document and the merge load will take the cluster down. Read the just-created item from the primary database by ID on the confirmation screen, and let search catch up a beat later.

Q: “Why does the same query return a different order on two clusters holding the same documents?” A: Per-shard IDF, mostly. Document frequency is computed within a shard, so term statistics differ with document placement, and two clusters with different shard counts or routing will score identical matches differently. Deleted-but-unmerged documents compound it, because they still count toward their segment’s document frequency until a merge removes them. If exact reproducibility matters, use the global-statistics query mode and pay the extra round trip.

Q: “How would you build as-you-type search?” A: Push the work to index time. Edge n-grams turn “cache” into c, ca, cac, cach, cache, so a two-character query becomes an ordinary term lookup rather than a leading-wildcard scan. The price is index size, roughly multiplied by average term length, so apply it to one field. For a bounded suggestion set - popular queries rather than arbitrary documents - a trie or FST held in memory is faster still, which is the route the autocomplete design takes.

Q: “The user’s words never appear in the matching document. Now what?” A: That is the lexical ceiling and BM25 honestly scores it zero. Synonym expansion at query time covers the cases you can enumerate. Vector retrieval covers the ones you cannot. Run both, fuse the lists, rerank the top 100 with a cross-encoder, and measure whether the hybrid actually beats BM25 on your own query log - sometimes it does not, and that is worth knowing before you buy a second cluster.

When NOT to Use a Dedicated Search Index

• Small datasets. Under a few hundred thousand documents, Postgres tsvector with a GIN index does tokenising, stemming, and ranking with zero sync lag. A separate search cluster buys you a sync pipeline, a reindex runbook, and a new failure domain, in exchange for relevance tuning you probably are not doing yet.
• Strict-consistency reads. The refresh interval makes a search index eventually consistent by construction. Never read one to authorise an action, check inventory before capturing payment, or compute a balance. Those reads go to the system of record.
• Purely structured filtering. status = 'active' AND created_at > X with no text component is a composite-index job. A search engine will answer it, and your database will answer it faster and inside a transaction.
• Primary storage. A Lucene index is a derived artifact. Keep the system of record in something you can restore from backup and treat the index as rebuildable, because sooner or later a mapping change will force you to rebuild it from scratch.
• Tiny corpora where ranking must be exact. A few thousand documents across several shards is where per-shard IDF skew is large enough to visibly reorder results, and it is also the size where you did not need sharding at all.

Related Concepts

• Database Indexing → — B-trees and GIN, and why a B-tree cannot answer a leading wildcard
• LSM Trees and SSTables → — the same immutable-segment-plus-merge bargain Lucene makes
• Change Data Capture → — how committed database writes reach the index without dual writes
• Outbox Pattern → — the application-level alternative for feeding the indexer
• Caching → — query-result caching in front of search, where a stale hit is cheap and a slow miss is not

Where This Shows Up

This concept is load-bearing in these designs - each link goes straight to the design that leans on it:

• Design a Web Crawler and Search Engine - a document-sharded inverted index over 10B pages with a scatter-gather query aggregator
• Design Search Autocomplete - where a trie beats an inverted index outright, and exactly why
• Design Zomato - Elasticsearch fed by CDC, blending BM25 relevance with geo distance in a single query
• Design a Q&A Forum - BM25 over questions with tag facets, kept as a separate failure domain from reading
• Design a News Aggregator - relevance combined with time decay over a million articles a day