Designing a Search Engine: Inverted Indexes, Relevance Scoring, and Query Processing at Scale

Most engineers interact with search engines daily but never build one. When a system design interview asks you to design search, the temptation is to wave your hands at Elasticsearch and move on. That works until you need to understand why your cluster is returning garbage results, why indexing latency spiked, or why a seemingly simple query is scanning every shard. Understanding the internals changes how you operate search in production.

This guide walks through the core components: inverted index construction, tokenization and analysis, relevance scoring with TF-IDF and BM25, query parsing and execution, sharding and replication, near-real-time indexing, and faceted search. The goal is to give you a working mental model of what happens between a user typing a query and results appearing on screen.

The Inverted Index

A forward index maps documents to words: “Document 7 contains the words [search, engine, architecture].” An inverted index flips this: it maps each word to the list of documents containing it. This inversion is the single most important data structure in text search.

interface Posting {
  docId: number;
  termFrequency: number;
  positions: number[]; // for phrase queries
}

interface InvertedIndex {
  dictionary: Map<string, Posting[]>;
  docCount: number;
  docLengths: Map<number, number>; // docId -> number of tokens
  avgDocLength: number;
}

function buildIndex(documents: Array<{ id: number; text: string }>): InvertedIndex {
  const dictionary = new Map<string, Posting[]>();
  const docLengths = new Map<number, number>();
  let totalLength = 0;

  for (const doc of documents) {
    const tokens = analyze(doc.text);
    docLengths.set(doc.id, tokens.length);
    totalLength += tokens.length;

    const termPositions = new Map<string, number[]>();
    for (let i = 0; i < tokens.length; i++) {
      const token = tokens[i];
      if (!termPositions.has(token)) termPositions.set(token, []);
      termPositions.get(token)!.push(i);
    }

    for (const [term, positions] of termPositions) {
      if (!dictionary.has(term)) dictionary.set(term, []);
      dictionary.get(term)!.push({
        docId: doc.id,
        termFrequency: positions.length,
        positions,
      });
    }
  }

  return {
    dictionary,
    docCount: documents.length,
    docLengths,
    avgDocLength: totalLength / documents.length,
  };
}

The posting list for a common term like “the” might contain millions of entries. The posting list for “cryptozoological” might contain three. This asymmetry drives most of the interesting optimization decisions.

Storage format matters. In production, posting lists are stored as sorted arrays of document IDs with delta encoding and variable-byte compression. A posting list [102, 107, 243, 244] becomes deltas [102, 5, 136, 1], which compress well because small numbers dominate. Lucene uses a block-based format (PFOR-delta) that compresses 128 doc IDs at a time, enabling both compact storage and fast intersection via SIMD operations.

Tokenization and Analysis Pipelines

Raw text is useless to an inverted index. The analysis pipeline transforms text into normalized tokens. The pipeline order matters: each step feeds the next.

function analyze(text: string): string[] {
  let tokens = tokenize(text);
  tokens = lowercaseFilter(tokens);
  tokens = stopwordFilter(tokens);
  tokens = stemFilter(tokens);
  return tokens;
}

function tokenize(text: string): string[] {
  // Unicode-aware word boundary splitting
  return text.split(/[\s\p{P}]+/u).filter(Boolean);
}

function lowercaseFilter(tokens: string[]): string[] {
  return tokens.map((t) => t.toLowerCase());
}

const STOP_WORDS = new Set([
  "the", "a", "an", "is", "are", "was", "were", "in", "on", "at",
  "to", "for", "of", "and", "or", "but", "not", "with", "this",
]);

function stopwordFilter(tokens: string[]): string[] {
  return tokens.filter((t) => !STOP_WORDS.has(t));
}

function stemFilter(tokens: string[]): string[] {
  return tokens.map(porterStem); // Porter or Snowball stemmer
}

A few things trip people up in production:

The same analyzer must run at index time and query time. If you stem “running” to “run” during indexing but leave queries unstemmed, a search for “running” will miss documents that only contain “running” (because the index only has “run”). This sounds obvious, but mismatched analyzers are one of the most common causes of “I know this document exists but search cannot find it” bugs.

Tokenization is language-dependent. Whitespace splitting works for English. For Chinese, Japanese, and Korean, you need dictionary-based segmentation (like ICU or MeCab). For German compound words, you need decompounding (“Dampfschifffahrtsgesellschaft” should match searches for “Dampf” or “Schiff”).

Stopword removal is a tradeoff. Removing “the” saves index space and speeds up queries. But it breaks phrase queries for “The Who” or “To Be or Not to Be.” Many modern search systems skip stopword removal entirely and instead rely on scoring to downweight common terms.

Relevance Scoring: TF-IDF and BM25

Once you have a list of matching documents, you need to rank them. The fundamental insight behind all term-frequency-based scoring: a term that appears frequently in a document but rarely across the corpus is a strong signal that the document is relevant.

TF-IDF

Term Frequency, Inverse Document Frequency. The formula:

score(term, doc) = tf(term, doc) * idf(term)

tf(term, doc) = count of term in doc
idf(term) = log(N / df(term))

Where N is total document count and df(term) is the number of documents containing the term.

The problem with raw TF-IDF is that term frequency is unbounded. A document that mentions “kubernetes” 200 times scores 10x higher than one mentioning it 20 times, but it is not 10x more relevant. It is probably just repetitive.

BM25

BM25 (Best Matching 25) fixes this with saturation and document length normalization:

function bm25Score(
  termFreq: number,
  docFreq: number,
  docLength: number,
  avgDocLength: number,
  totalDocs: number,
  k1 = 1.2,
  b = 0.75
): number {
  const idf = Math.log(
    (totalDocs - docFreq + 0.5) / (docFreq + 0.5) + 1
  );

  const tfNorm =
    (termFreq * (k1 + 1)) /
    (termFreq + k1 * (1 - b + b * (docLength / avgDocLength)));

  return idf * tfNorm;
}

function scoreDocument(
  queryTerms: string[],
  docId: number,
  index: InvertedIndex
): number {
  let score = 0;
  const docLength = index.docLengths.get(docId) ?? 0;

  for (const term of queryTerms) {
    const postings = index.dictionary.get(term);
    if (!postings) continue;

    const posting = postings.find((p) => p.docId === docId);
    if (!posting) continue;

    score += bm25Score(
      posting.termFrequency,
      postings.length,
      docLength,
      index.avgDocLength,
      index.docCount
    );
  }

  return score;
}

The two tunable parameters carry real weight:

k1 controls term frequency saturation. At k1 = 0, term frequency is ignored entirely. At k1 = 1.2 (the common default), the score curve flattens quickly: going from 1 to 3 occurrences matters, going from 20 to 60 barely does. For short documents (tweets, product titles), a lower k1 often works better.

b controls length normalization. At b = 1, long documents are heavily penalized. At b = 0, document length is ignored. The default of 0.75 works well for heterogeneous corpora. If all your documents are roughly the same length (e.g., product descriptions), lowering b makes sense.

Query Parsing and Execution Plans

A query like "distributed systems" AND (kafka OR rabbitmq) NOT tutorial needs to be parsed into a structure the engine can execute against the inverted index.

type QueryNode =
  | { type: "term"; value: string }
  | { type: "phrase"; terms: string[] }
  | { type: "and"; children: QueryNode[] }
  | { type: "or"; children: QueryNode[] }
  | { type: "not"; child: QueryNode };

function executeQuery(node: QueryNode, index: InvertedIndex): Set<number> {
  switch (node.type) {
    case "term": {
      const postings = index.dictionary.get(node.value) ?? [];
      return new Set(postings.map((p) => p.docId));
    }

    case "phrase": {
      return executePhraseQuery(node.terms, index);
    }

    case "and": {
      const sets = node.children.map((c) => executeQuery(c, index));
      return sets.reduce((acc, s) => intersect(acc, s));
    }

    case "or": {
      const sets = node.children.map((c) => executeQuery(c, index));
      return sets.reduce((acc, s) => union(acc, s));
    }

    case "not": {
      const allDocs = new Set(index.docLengths.keys());
      const excluded = executeQuery(node.child, index);
      return difference(allDocs, excluded);
    }
  }
}

Phrase queries require position information. The posting list must store not just “term X appears in document Y” but “at positions [3, 17, 42].” A phrase “distributed systems” matches only when “distributed” and “systems” appear at consecutive positions in the same document.

function executePhraseQuery(terms: string[], index: InvertedIndex): Set<number> {
  const postingLists = terms.map((t) => index.dictionary.get(t) ?? []);
  if (postingLists.some((p) => p.length === 0)) return new Set();

  // Find documents containing all terms
  const candidates = postingLists
    .map((p) => new Set(p.map((posting) => posting.docId)))
    .reduce((acc, s) => intersect(acc, s));

  const results = new Set<number>();

  for (const docId of candidates) {
    const positionArrays = postingLists.map(
      (p) => p.find((posting) => posting.docId === docId)!.positions
    );

    // Check for consecutive positions
    for (const startPos of positionArrays[0]) {
      let match = true;
      for (let i = 1; i < positionArrays.length; i++) {
        if (!positionArrays[i].includes(startPos + i)) {
          match = false;
          break;
        }
      }
      if (match) {
        results.add(docId);
        break;
      }
    }
  }

  return results;
}

Query optimization matters. The engine should execute the rarest terms first. If you are intersecting posting lists for “the” (10 million docs) and “cryptozoological” (3 docs), start with the short list and check each doc against the long one, not the other way around. This is query planning, and production search engines build cost models for it just like relational database query optimizers.

Index Sharding and Replication

A single-node index works until it doesn’t. There are two dimensions to distribute along:

Document-based sharding (horizontal partitioning). Split the corpus across N shards. Each shard is an independent inverted index covering a subset of documents. A query goes to all shards in parallel, each returns its local top-K, and a coordinator merges the results. This is how Elasticsearch and Solr work by default.

Term-based sharding (vertical partitioning). Split the dictionary across shards, so shard 1 owns terms A-F, shard 2 owns G-L, and so on. A multi-term query now requires cross-shard coordination to intersect posting lists. This is rarely used in practice because the coordination overhead is painful.

interface SearchCluster {
  shards: ShardNode[];
  replicas: Map<number, ShardNode[]>; // shardId -> replica nodes
}

async function distributedSearch(
  query: string,
  cluster: SearchCluster,
  topK: number
): Promise<ScoredDocument[]> {
  const queryTerms = analyze(query);

  // Fan out to all shards (pick one replica per shard)
  const shardResults = await Promise.all(
    cluster.shards.map((shard, i) => {
      const replicas = cluster.replicas.get(i) ?? [shard];
      const target = replicas[Math.floor(Math.random() * replicas.length)];
      return target.search(queryTerms, topK);
    })
  );

  // Merge: re-rank across shards
  const merged = shardResults
    .flat()
    .sort((a, b) => b.score - a.score)
    .slice(0, topK);

  return merged;
}

The key tradeoff with document-based sharding: global IDF vs. local IDF. Each shard computes IDF using its local document frequency and document count. If shard distribution is uneven (say one shard has mostly technical documents), the local IDF for “algorithm” will differ across shards, and scores are not directly comparable. The fix is either to precompute global term statistics and distribute them to each shard, or to accept the slight inaccuracy (which is often negligible with enough documents per shard).

Replication is straightforward: each shard has N replicas, queries are load-balanced across them, and you can tolerate N-1 replica failures per shard. Write operations go to the primary, which replicates to followers. This is the standard primary-follower pattern.

Near-Real-Time Indexing

Batch reindexing is simple but means new documents are not searchable for minutes or hours. Production systems need near-real-time (NRT) indexing, where a document becomes searchable within seconds of ingestion.

The trick is an in-memory buffer that periodically flushes to a new immutable segment:

class NRTIndexWriter {
  private buffer: Array<{ id: number; text: string }> = [];
  private segments: InvertedIndex[] = [];
  private flushIntervalMs = 1000;

  constructor() {
    setInterval(() => this.flush(), this.flushIntervalMs);
  }

  addDocument(doc: { id: number; text: string }): void {
    this.buffer.push(doc);
  }

  private flush(): void {
    if (this.buffer.length === 0) return;
    const segment = buildIndex(this.buffer);
    this.segments.push(segment);
    this.buffer = [];
  }

  search(queryTerms: string[]): ScoredDocument[] {
    // Search all segments, merge results
    const results: ScoredDocument[] = [];
    for (const segment of this.segments) {
      results.push(...searchSegment(queryTerms, segment));
    }
    // Also search the in-memory buffer if you need sub-second visibility
    return results.sort((a, b) => b.score - a.score);
  }
}

This creates a proliferation of small segments over time, which degrades query performance (you are merging results from hundreds of segments). The solution is segment merging: a background process that periodically combines small segments into larger ones. Lucene uses a tiered merge policy where segments are grouped by size and merged when a tier accumulates enough segments. This is conceptually similar to LSM-tree compaction in databases.

Deletes in an append-only segment model work via a separate bitset per segment. When a document is deleted, its bit is set to 1, and search filters it out. The actual removal happens during segment merging.

Faceted Search

Faceted search lets users filter and count results by categories: “show me laptops under $500 with brand:Apple.” This requires a different data structure than the inverted index.

For each faceted field, you maintain a mapping from field values to document ID sets:

interface FacetIndex {
  fields: Map<string, Map<string, Set<number>>>; // field -> value -> docIds
}

function computeFacetCounts(
  matchingDocs: Set<number>,
  facetIndex: FacetIndex,
  facetField: string
): Map<string, number> {
  const fieldIndex = facetIndex.fields.get(facetField);
  if (!fieldIndex) return new Map();

  const counts = new Map<string, number>();
  for (const [value, docIds] of fieldIndex) {
    let count = 0;
    for (const docId of docIds) {
      if (matchingDocs.has(docId)) count++;
    }
    if (count > 0) counts.set(value, count);
  }

  return counts;
}

The naive intersection approach above is O(values * matchingDocs). Production systems use doc-value columns (Lucene’s column-stride storage), which store field values in document-ID order for cache-friendly sequential access. This turns facet counting into a single pass over the matching documents rather than repeated set intersections.

Numeric range facets (price ranges, date ranges) use a different structure. Lucene stores numeric fields in a BKD-tree (a variant of a k-d tree), which enables range queries without scanning the full posting list.

Precision vs. Recall: The Production Tradeoff

Precision is the fraction of returned results that are relevant. Recall is the fraction of all relevant documents that appear in results. You almost never maximize both simultaneously.

High-precision scenarios (e-commerce product search): Users expect the first few results to be exactly right. You can aggressively filter, boost exact matches, and accept missing some long-tail results. A user searching “iPhone 15 Pro Max 256GB” wants that exact product, not a page of tangentially related phone cases.

High-recall scenarios (legal document discovery, patent search): Missing a relevant document has real consequences. You use broader matching (synonyms, fuzzy matching, stemming), accept lower precision, and let users refine with filters and facets.

Practical knobs you can turn:

• Fuzzy matching adds recall at the cost of precision. Levenshtein distance 1 on query terms catches typos (“seach” matches “search”) but also introduces false positives.
• Synonym expansion broadens recall (“laptop” also matches “notebook”) but requires careful curation. Automated synonym mining from query logs helps but produces noisy results.
• Minimum-should-match on multi-term OR queries. Requiring 75% of terms to match is a middle ground between AND (high precision, low recall) and OR (low precision, high recall).
• Re-ranking with a more expensive model. Use BM25 to retrieve the top 1000 candidates (optimizing for recall), then re-rank with a learned model (optimizing for precision in the final top 10). This two-phase architecture is standard in production search systems.

Putting It Together

A production search system is a pipeline: documents flow through an analysis chain into an inverted index distributed across shards, queries flow through the same analysis chain into a query planner that fans out to shards, results merge at a coordinator, and a re-ranker produces the final ordering.

The pieces that trip teams up most often in production: analyzer mismatches between index and query time (always test both paths), shard imbalance causing hot spots (monitor per-shard latency, not just averages), segment merge storms competing with query throughput (tune merge policies and use throttling), and facet computation on high-cardinality fields blowing out memory (cap cardinality or use approximate counts).

None of these components are individually complex. The difficulty is in the interaction between them, and in tuning them for your specific data and query patterns. Start with a working BM25 index, measure what is actually wrong with your results, and optimize from there. The number of teams that skip measurement and jump to ML re-ranking before fixing basic analyzer issues is higher than you would expect.