Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Search, Geo and Specialized Data Structures

System Design HLD-15.01

Inverted indexes and full-text search

How search engines work: tokenizing and stemming, posting lists, TF-IDF and BM25 ranking, and how Elasticsearch shards and refreshes its index.

Intermediate 14 min Last reviewed

The big idea

A user types "running shoes waterproof" into your store's search box. A database query like WHERE description LIKE '%running%' must scan every row, cannot match "run" or "runs", and has no idea which of 40,000 matching products is the best answer. Search needs a different index, built around words rather than rows.

An inverted indexA mapping from each term to the list of documents (and often positions) that contain it, the core data structure of full-text search. flips the data around: instead of "document to its words", it stores "word to the documents that contain it", like the index at the back of a book. Finding documents with "running" becomes one lookup. Combining terms is intersecting short lists. Then a ranking formula such as BM25 orders the matches so the most relevant come first.

Think of a library card catalog that lists, for every subject word, the shelf numbers of every book about it. You never walk the shelves; you look up a few words and get a short list to compare.

How it works

Step 1: Analysis: from text to terms

From documents to tokens to posting lists to ranked results Three documents pass through an analyzer that lowercases, removes stopwords and stems words, producing terms. The terms feed an inverted index where each term has a posting list of document ids, glowing for the query terms run and databas. A query is analyzed the same way, its posting lists are combined, and BM25 produces a ranked result list. Documents Running databases ... Query run a database Analyzer lowercase, stopwords, stem Inverted index run: [5, 14] databas: [5, 6, 14] Ranked results BM25: #14, #5, #6 Figure 1. Documents and queries go through the same analyzer, so 'Running databases' and 'run a database' both become run and databas. The index maps each term to its posting list; the query's lists are combined and scored with BM25.

Before indexing, text goes through an analyzer:

  • Tokenize: split into words (harder than it sounds for languages without spaces, hyphenated words and product codes).
  • Normalize: lowercase, strip accents.
  • Remove stopwords (optional): very common words such as "the" and "of" that carry little meaning.
  • Stem or lemmatize: reduce words to a root so "running", "runs" and "ran" can match "run".

Queries go through the same analyzer, so both sides agree on the terms. Mismatched analysis, such as stemming documents but not queries, is a classic source of "search cannot find something that is obviously there".

Step 2: Posting lists

For each term, the index stores a posting listThe sorted list of document ids (and often term frequencies and positions) that contain a given term in an inverted index.: the sorted ids of documents containing it, usually with how often the term appears and where (positions enable phrase queries such as "load balancer"). A query for two terms intersects (AND) or unions (OR) their lists. Lists are sorted and compressed (storing gaps between ids), so even lists of millions of entries are scanned quickly.

Step 3: Ranking with TF-IDF and BM25

Matching is easy; ordering is the hard part. Two intuitions:

  • Term frequency (TF): a document that mentions "database" five times is probably more about databases than one that mentions it once.
  • Inverse document frequency (IDF): a match on a rare term ("BM25") says more than a match on a common one ("data").

BM25 combines them and fixes TF-IDF's weak spots: each extra occurrence of a term adds less than the previous one (saturation, controlled by k1, typically about 1.2), and long documents are normalized so they do not win just by containing more words (controlled by b, typically 0.75):

Here is how often term appears in document , is the document's length and avgdl is the average length. With 20 documents, a term in 2 of them gets an IDF of ln(1 + 18.5/2.5), about 2.1; a term in 10 gets about 0.69. A match on the rare term counts three times as much.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Search "running the database cache" with stopwords and stemming. "the" disappears, "running" becomes "run" and "database" matches "databases". Switch to raw words and watch matches vanish.
  2. Compare BM25 with plain term count for "replication of data". Which document wins under each, and why does the rare term matter under BM25?
  3. Search "the rare terms" with raw words, then with stopwords removed. The posting list for "the" covers half the collection, and its idf is tiny.

Going deeper

Elasticsearch and OpenSearch at scale

Elasticsearch and OpenSearch build on Apache Lucene. An index is split into primary shards, each a complete Lucene index on a subset of documents, with replica shards for availability and read throughput ( Partitioning and sharding ). A query is sent to one copy of every shard, each returns its top results, and a coordinating node merges them, a scatter-gather pattern. Within a shard, new documents are written to small immutable segments that are merged in the background, much like an LSM-tree ( Storage engines: B-tree vs LSM-tree ).

Near-real-time, not real-time

New documents become searchable when the shard is refreshed and a new segment opened, by default about once a second. So search is near-real-time: a just-saved product may not appear for a second. Systems usually keep the database as the source of truth and feed the search index asynchronously, often via change data capture ( Transactional outbox and change data capture ), accepting brief lag.

Beyond keyword matching

Production relevance mixes BM25 with business signals (popularity, stock, margin), personalization, typo tolerance, synonyms, and increasingly semantic vector search ( Vector search in system design ) in hybrid ranking.

Trade-offs

OptionWins whenLoses when
SQL LIKE / basic text search Tiny datasets and exact substring matches Full scans, no stemming, no relevance ranking
Database full-text features (e.g. PostgreSQL) Moderate search needs without another system to run Fewer relevance and scaling features than a dedicated engine
Dedicated search engine (Elasticsearch, OpenSearch, Solr) Large corpora, relevance tuning, facets, scale-out Another system to operate; index lag behind the source of truth

Common mistakes

  • Analyzing documents and queries differently, so obvious matches are missed.
  • Using the search index as the primary database instead of a derived, rebuildable copy.
  • Expecting writes to be searchable instantly.
  • Choosing far too many or too few shards up front; resharding requires reindexing.
  • Ranking purely by term matches and ignoring business signals and user behavior.

In the wild

Elasticsearch, OpenSearch and Apache Solr, all built on Apache Lucene, power search for e-commerce sites, logs and documentation across the industry, and their default ranking is BM25. Large web search engines use the same core idea, inverted indexes sharded across many machines, combined with many more ranking signals.

Check yourself

  1. What does an inverted index map?

    Show answer

    B. Each term to the list of documents containing it It inverts document-to-words into word-to-documents, like a book's index.

  2. Why does BM25 give more weight to a match on a rare term?

    Show answer

    B. Its IDF factor is higher for terms that appear in few documents, so they are more informative Matching a word almost every document has tells you little about relevance.

  3. Documents are stemmed at indexing but queries are not. What happens to a search for 'running'?

    Show answer

    B. It may find nothing, because the index holds 'run' while the query looks for 'running' Both sides must be analyzed the same way to produce matching terms.

  4. A product saved a moment ago does not appear in search. Most likely reason?

    Show answer

    B. The index has not refreshed yet; search is near-real-time New documents become searchable at the next refresh, typically within about a second.

Recap

  • Full-text search uses an inverted index: each term points to a posting list of documents.
  • Analyzers tokenize, normalize, remove stopwords and stem, identically for documents and queries.
  • BM25 ranks by term frequency with saturation, inverse document frequency and length normalization.
  • Search engines shard and replicate the index, query shards in parallel and merge results.
  • Indexes are near-real-time derived copies, usually fed asynchronously from the source of truth.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy