How the Inverted Index Data Structure Works

Introduction

You might have done a Google search, found a video on YouTube, or searched for a product on Amazon. If your answer to any of those is yes — you've already used an inverted index.

These sites work with billions of pages, videos, and products. How do results appear so fast? Because these sites have already built an inverted index. Instead of reading all documents from start to end when you search, they look up a pre-built index.

What is an Inverted Index?

An inverted index data structure allows you to find information quickly and efficiently. It does this by indexing the words contained in documents, creating a mapping from words → documents.

Why is it Called "Inverted"?

In a normal document structure, we have a document that contains words — to find a word you read from start to end. An inverted index inverts this: instead of document → words, it stores words → documents. Each word points to the list of documents containing it. Hence "inverted."

Preprocessing Before Building the Index

Before inserting words into the index, we preprocess the documents. Consider these five:

Document1: My name is Ishan Upamanyu
Document2: Abhishek Upmanyu is a great comedian
Document3: I would like to name my dog as Bruno
Document4: Alexander the great.
Document5: Abhishek is studying in Delhi.

Tokenization

Break sentences into individual tokens — the smallest unit added to the index.

Stop Words

Remove common words like "a", "and", "the", "is" that carry little meaning in search. After stop word removal:

Document1: [My, name, Ishan, Upamanyu]
Document2: [Abhishek, Upmanyu, great, comedian]
Document3: [I, would, like, name, my, dog, Bruno]
Document4: [Alexander, great]
Document5: [Abhishek, studying, Delhi]

Stemming

Convert tokens to their root form. "studying" → "study". This ensures a search for "study" matches documents containing "studying".

Lemmatization

A smarter alternative to stemming — converts tokens to their meaningful base form using dictionaries. "caring" → "care" (not "car" as stemming might produce). Many systems also lowercase all tokens so "Upmanyu" matches "upmanyu".

Building the Inverted Index

After preprocessing, we build the index in two steps:

Step 1: Create a table mapping every word to the document it appeared in.

Step 2: Group identical words together, note their frequency, and collect all document IDs into a sorted list called a posting list.

The result is an inverted index with two main components:

• Dictionary — contains each term with its frequency and a pointer to its postings
• Posting List — the sorted list of document IDs containing that term

A token is raw output from splitting. A term is what actually gets stored in the index after preprocessing.

Boolean Retrieval

To find documents matching a query, we look up terms in the dictionary and operate on their posting lists.

AND Query

For ishan AND upmanyu: look up both terms, get their posting lists, and intersect them. Only documents in both lists are returned.

OR Query

For ishan OR upmanyu: look up both terms, get their posting lists, and take the union. Documents in either list are returned.

NOT Query

For NOT upmanyu: return all documents not in the posting list for "upmanyu".

Conclusion

We covered what an inverted index is, why it's called inverted, how preprocessing shapes the terms stored in the index, and how boolean retrieval uses posting lists to find matching documents efficiently.

Now that you understand how the index finds candidate documents, the natural next question is: how does a search engine rank those results? That's where the Vector Space Model comes in.