How Inverted Indexes Power Every Search Engine You Use

If you've ever wondered how search engines like Google, Elastic-search, or even the search feature in your favourite app work so fast, the answer lies in a fundamental data structure called the inverted index.

In this post, We'll break down:

• What inverted indexes are and why they matter

• How they're built and stored

• Key optimisations that make them efficient

• Why they're the backbone of modern search engines

The Problem: Searching Without an Index

Imagine you have a set of documents (called a corpus), and you want to find all documents containing the word "fish." A naive approach would be:

1. Scan each document one by one.

2. Check if it contains "fish."

3. Add matching documents to your results.

This linear scan works for small datasets but becomes painfully slow as your corpus grows.

Enter: The Inverted Index

Instead of scanning documents repeatedly, an inverted index flips the approach:

• It maps each term (word) to a list of documents where it appears (called a posting list).

• The collection of all terms is called the dictionary or vocabulary.

Example:

Given these documents:

1. "So long and thanks for the fish"

2. "Nobody loves a pig wearing lipstick on the wall"

The inverted index would look like:

Now, searching for "fish" is as simple as looking up the term in the dictionary and retrieving its posting list—O(1) or O(log n) time instead of O(n).

How an Inverted Index is Built

Constructing an inverted index involves several preprocessing steps:

1. Tokenisation

Breaking text into words (tokens). Simple approaches split on whitespace; advanced ones handle punctuation, contractions, and special cases.

2. Normalisation

• Lowercasing: "Fish" → "fish"

• Stemming: Reducing words to root form (e.g., "housing" → "house")

• Lemmatisation: More sophisticated than stemming—produces grammatically correct roots (e.g., "better" → "good")

3. Stop Word Removal

Common words like "the," "is," and "and" are often removed since they appear in almost every document and don’t help differentiate results.

4. Building the Index

For each term, we store:

• Document IDs (the posting list)

• Term frequency (how often the word appears in each doc)

• Positions & offsets (for phrase searches and highlighting)

Example enriched posting list for "fish":

{
  "fish": [
    { "doc_id": 1, "frequency": 1, "positions": [6], "offsets": [28] },
    { "doc_id": 5, "frequency": 1, "positions": [1], "offsets": [0] }
  ]
}

Why This Matters for Search Engines

Fast Query Processing

A query like fish AND wall becomes:

1. Fetch posting list for "fish" → [1, 5]

2. Fetch posting list for "wall" → [2, 5]

3. Intersect the lists → [5]

4. Return document 5

This is orders of magnitude faster than scanning every document.

Proximity Searches

Storing positions lets you rank documents where terms appear close together higher (e.g., "fish climbing" vs. "fish... [100 words later] climbing").

Snippet Generation & Highlighting

Offsets help generate previews with matched terms highlighted.

Optimisations for Real-World Use

1. Sorted Posting Lists

• Enables efficient merging (O(n) for intersection).

• Unsorted lists would require O(n²) operations.

2. Compression

• Delta encoding: Store differences between doc IDs (e.g., [5, 10, 12] → [5, +5, +2]).

• Variable-length encoding: Use fewer bits for smaller numbers.

3. Tiered Indexing (Champion Lists)

• Keep frequently accessed documents in memory.

• Store the full index on disk.

4. n-gram Indexes

Index word sequences (e.g., bigrams, trigrams) for better phrase search.

Build Your Own Search Engine

Want to try this yourself? Here’s how:

1. Get a dataset: Wikipedia dumps work great (~30-40GB compressed).

2. Implement tokenization & normalization.

3. Build the inverted index (start simple, then add term frequencies/positions).

4. Add query processing (Boolean AND/OR, phrase search).

5. Implement ranking (TF-IDF or BM25).

Key Takeaways

• Inverted indexes map terms → documents, enabling fast search.

• They store additional data (positions, frequencies) for ranking and highlighting.

• Optimizations like compression and tiered indexing make them scalable.

• Every major search engine (Elasticsearch, Solr, Lucene) uses them under the hood.

If you're working with search, understanding inverted indexes is non-negotiable. Try building one yourself—it’s the best way to learn!

Further Exploring:

• TF-IDF Explained

• How Phonetic Search Works

---