How Search Works: The Inverted Index

Building an inverted index by hand

Three products:

Doc 1: "Red running shoes for men"Doc 2: "Blue running jacket"Doc 3: "Men's red leather shoes"

Step 1: Analyse the text. Break it into words (called tokens), make them lowercase, and cut each word down to a simple form (for example, "running" becomes "run"):

Doc 1: red, running→run, shoes→shoe, for, menDoc 2: blue, running→run, jacketDoc 3: men's→men, red, leather, shoes→shoe

Step 2: Build the index. A term is one cleaned-up word stored in the index. For each term, list the documents (and the positions) where it appears. That list is called a posting list:

Step 3: Search. For the query "red shoes":

• Analyse it the same way: red, shoe.
• Look up each term: red → {1, 3}, shoe → {1, 3}.
• AND them together. This means you keep only the documents that are in both lists (an intersection): {1, 3}.
• Rank the results (explained below). Both documents match. Doc 1 might rank higher if it is more relevant.

You do not scan every document. You only do a few quick lookups, even across millions of documents.

Text analysis: making search forgiving

The analyser is the part that turns raw text into index terms. Much of search quality comes from it. It must treat documents (when you index them) and queries (when you search) in the same way. These are its steps:

• Tokenisation: split text into words. "Men's red-leather shoes" → men's, red, leather, shoes.
• Lowercasing: Shoes = shoes.
• Stop words: you can choose to drop very common words ("the", "for", "a"). They say little about the topic.
• Stemming or lemmatisation: cut a word down to its root. Stemming chops off word endings with simple rules (running, runs → run; shoes → shoe). Lemmatisation uses a dictionary, so it can also turn ran into run. Now "running shoe" matches "run shoes".
• Synonyms: words with the same meaning are treated as equal: sneakers ↔ trainers ↔ running shoes, and TV ↔ television.
• N-grams / edge n-grams: an n-gram is a short piece of a word. Edge n-grams are pieces from the start of the word (sho, shoe, shoes). You index these pieces for autocomplete (suggestions while the user types) and partial matches.
• Fuzzy matching: match words that are only a few edits apart. An edit is adding, removing or changing one letter. So runing still finds running. This handles typos.
• Language-specific rules for Hindi, Japanese, German compound words (long words made from several words) and so on.

Ranking: which results come first?

Finding matches is half the job. Putting them in a good order (ranking) is the other half. Ranking gives each match a score. The best scores come first.

TF-IDF is a classic scoring formula. It multiplies two ideas:

• TF (term frequency): how often the word appears in one document. A document that mentions "shoes" many times is probably more about shoes.
• IDF (inverse document frequency): how rare the word is across all documents. Rare words matter more. Matching "leather" (in few documents) says more than matching "for" (in almost all).

BM25 is a ranking formula that improves on TF-IDF. It is the default in Elasticsearch, OpenSearch and Lucene. It stops giving too much credit for repeated words. It also adjusts for document length. So a short title that matches well beats a long page that mentions the word once.

Real products then add business signals (facts about your business that change the order):

• popularity, ratings and sales,
• recency (for news),
• user location or personalisation,
• boosting fields (boosting means giving one field more weight: a match in the title counts more than a match in the description),
• and, more and more, machine-learning ranking models (models that learn the best order from past clicks).

Filters and facets

Search pages usually combine text search with structured filters: "red shoes" + size 9 + price under ₹3,000 + brand = Nike. A facet is a count of results for each value of a field. For example, "Nike (120), Adidas (95), Puma (40)" in the sidebar. Search engines compute facets for you. They store these structured fields in formats that are fast for filtering and counting.

Search at scale: distributed search

One machine cannot hold the index for billions of documents. It also cannot answer thousands of queries per second. So search engines split the index into parts:

• Shards: a shard is one slice of the data. Each shard holds part of the documents and their index.
• Replicas: copies of each shard. They keep search working if a machine fails (availability). They also let more queries run at the same time.
• Scatter-gather: a coordinator (the node that receives the query) sends the query to all shards. Each shard returns its best results. The coordinator merges them into a final top 10.

This connects to Lesson 8 on latency. A search that fans out to many shards is exposed to tail latency (the rare slow responses). The slowest shard decides the response time.

Near-real-time: new documents do not become searchable at once. They become searchable after a short refresh interval. In Elasticsearch the default is 1 second.

Keeping search in sync with your database

The search index is usually a copy of your data. The "source of truth" (the place where the correct data lives) is your main database. How do you keep the two in sync?

1. Dual writes. The app writes to the database and to the search engine.

• It is simple. But if one write fails, the two systems disagree. This is easy to get wrong without noticing.

2. Queue or events (recommended). The app writes to the database and sends an event (a short message such as "product 991 updated") to a queue. A worker reads the event and updates the search index.

3. Change Data Capture (CDC). CDC is a method that reads the database's change log (the file where the database records every change) and sends each change to the indexer. This happens automatically, so no app code can forget to do it.

An important rule: treat the search index as derived, rebuildable data. If it gets damaged, or you change the analyser, you can re-index (build the index again) from the database. Never make the search engine the only place where important data lives.

Beyond keywords: semantic (vector) search

Keyword search matches words. But "cheap flights to Goa" and "budget air tickets to Goa" mean the same thing in different words. A keyword search may miss that.

Vector search finds results by meaning. A machine-learning model turns text (or images) into a list of numbers called an embedding. Similar meanings get lists that are close to each other. The search engine then finds the "nearest" lists. It uses approximate nearest neighbour (ANN) algorithms. These find close neighbours quickly, but not always the exact closest ones.

Many systems now use hybrid search. It combines keyword results (BM25) with vector results and then ranks them again. Many AI assistants also use search to find relevant documents before they answer a question. This is called retrieval-augmented generation, or RAG.

Popular tools