How does an Inverted Index work?

Q: Should we remove stop words when building an inverted index?

It is optional. Stop words like the, is, on, and and appear in almost every document and carry very little meaning for search, so many systems remove them to save space. However, modern systems often keep them. Stemming, which reduces words like running and runs to run, is also optional and depends on our use case.

An inverted index is a data structure that maps each word to the list of documents that contain it, like the index at the back of a book, making search almost instant.

In this blog, we will learn about how an inverted index works. We will also see why search engines need it, how it is built step by step, how a search query uses it, how it handles multiple words and phrases, and where it is used in the real world.

We will cover the following:

What is an inverted index?
The problem: searching without an index
The forward index
Why we flip it: the inverted index
How an inverted index is built step by step
How a search query uses the inverted index
Handling multiple words in a search
Storing positions for phrase search
Why the inverted index is so fast
Real-world use of the inverted index

I am Amit Shekhar, Founder @ Outcome School, I have taught and mentored many developers, and their efforts landed them high-paying tech jobs, helped many tech companies in solving their unique problems, and created many open-source libraries being used by top companies. I am passionate about sharing knowledge through open-source, blogs, and videos.

I teach AI and Machine Learning at Outcome School.

Let's get started.

What is an inverted index?

An inverted index is a data structure that maps each word to the list of documents that contain that word.

In simple words, it is like the index at the back of a book.

Let's say we open a thick book on cooking. At the very end of the book, there is an index. It is a list of words in alphabetical order. Next to each word, there are page numbers.

So, if we want to find the word tomato, we look at the index. It says tomato is on pages 12, 45, and 78. We go straight to those pages. We do not read the whole book.

That is exactly what an inverted index does for a computer.

A document is just a piece of text. It can be a web page, a product description, an email, or a single sentence.

So, an inverted index takes a word and gives us the list of documents that contain that word. This is at the heart of how search engines find results so fast.

Now, let's understand the name. The usual way of storing text goes from a document to its words. We invert it, which means we flip it, so that it goes from a word to its documents. That is why it is called an inverted index.

The problem: searching without an index

The best way to learn this is by taking an example.

Suppose we have three documents. Let's keep them very short so they are easy to follow.

Document 1: the cat sat on the mat
Document 2: the dog sat on the log
Document 3: the cat and the dog played

Now, a user comes and searches for the word cat.

How do we find which documents contain cat?

The naive way is simple. We open Document 1 and read every word. We check if any word is cat. Then we open Document 2 and read every word. Then we open Document 3 and read every word.

This works, but it does not scale.

We have only 3 documents here. A real search engine has millions, sometimes billions, of documents. Reading every word of every document for every single search is far too slow.

Let's say there are one million documents, and each document has one thousand words. To answer one search, we would read one billion words. And we would do this again for the next search, and the next one.

We need a better way.

So, here comes the inverted index to the rescue.

The forward index

Before we build the inverted index, we must first understand the forward index, because the inverted index is built by flipping it.

A forward index maps each document to the list of words it contains.

It is the natural way we store text. Each document points to its own words.

For our three documents, the forward index looks like below:

Document 1  ->  the, cat, sat, on, the, mat
Document 2  ->  the, dog, sat, on, the, log
Document 3  ->  the, cat, and, the, dog, played

Here, we can see that the arrow goes from a document to its words. We start with a document number, and we get the words inside it.

This is great if we already know the document and we want to read it. But it is bad for search.

Why is it bad for search?

Because when a user searches for cat, we still have to look inside every document to check if cat is present. The forward index does not directly tell us which documents have cat. We are back to the slow problem.

So, the forward index answers the question "what words are in this document". But, search asks the opposite question: "which documents contain this word".

The forward index points the wrong way for search. Let's flip it.

Why we flip it: the inverted index

Now, we take the forward index and we turn the arrows around.

Instead of going from a document to its words, we go from a word to its documents.

Let's see the flip as below:

   Forward index                      Inverted index
   (document -> words)                (word -> documents)

   Document 1 -> cat, mat             cat -> Doc 1, Doc 3
   Document 2 -> dog, log    flip     dog -> Doc 2, Doc 3
   Document 3 -> cat, dog  ------->   mat -> Doc 1
                                      log -> Doc 2

Here, we can see that on the left the arrow goes from a document to its words, and on the right the arrow is turned around, going from a word to the documents that contain it.

The inverted index for our three documents looks like below:

the     ->  Document 1, Document 2, Document 3
cat     ->  Document 1, Document 3
sat     ->  Document 1, Document 2
on      ->  Document 1, Document 2
mat     ->  Document 1
dog     ->  Document 2, Document 3
log     ->  Document 2
and     ->  Document 3
played  ->  Document 3

Here, we can see that the arrow now goes from a word to the documents that contain it.

So, when a user searches for cat, we look up the word cat in this list. It immediately tells us: Document 1 and Document 3.

We did not read any document word by word. We just looked up one word and got the answer.

The list of documents next to each word has a special name. It is called the posting list.

So, the posting list for cat is Document 1 and Document 3.

The problem of slow searching is solved.

Planning your move into AI?

No matter which tech domain you work in today, with your effort, you can transition to these roles:

AI Engineer
Forward Deployed Engineer
AI Agent Engineer
Harness Engineer
Voice AI Engineer
AI Architect
LLM Engineer
LLM Inference Engineer
Gen AI Engineer
MLOps Engineer
ML Engineer
Deep Learning Engineer

Our AI and Machine Learning Program at Outcome School takes you there.

How an inverted index is built step by step

Now, let's understand how a computer builds this inverted index from raw text. We will go step by step, and each step has a simple job.

Step 1: We collect the documents.

First, we gather all the documents we want to search through. In our example, these are Document 1, Document 2, and Document 3.

Step 2: We tokenize the text.

Tokenization means breaking a piece of text into individual words. Each single word is called a token.

For example, the text the cat sat on the mat becomes the tokens: the, cat, sat, on, the, mat.

We can see the full build pipeline as below:

   "The Cat Sat"
         |
         | tokenize
         ↓
   [The] [Cat] [Sat]
         |
         | normalize
         ↓
   [the] [cat] [sat]
         |
         | build posting lists
         ↓
   the -> Doc 1
   cat -> Doc 1
   sat -> Doc 1

Here, we can see that the raw text first becomes separate tokens, then the tokens are cleaned up into a common form, and finally each word is added to its posting list. We will now look at the normalization step in detail.

Step 3: We normalize the tokens.

Normalization means cleaning up the tokens so that different forms of the same word are treated as one word.

For example, the word Cat, CAT, and cat all mean the same thing. So, we convert every word to lowercase. Now they all become cat.

If a user searches for cat in lowercase, but the document stored Cat with a capital C, then without normalization we would miss it. Normalization makes sure the search still works.

Two more common normalization steps are worth knowing.

Stop word removal: Some words appear in almost every document, for example the, is, on, and and. These are called stop words. They carry very little meaning for search. Many systems remove them to save space. This is optional, and modern systems often keep them.

Stemming: Stemming means cutting a word down to its root form. For example, running and runs can both be reduced to the root run. So, a search for run can also match running. This is also optional and depends on our use case.

Step 4: We build the posting lists.

Now, we go through each document. For every token in the document, we add that document to the word's posting list.

Let's walk through it.

We start with Document 1. Its words are the, cat, sat, on, the, mat.

We see the. We add Document 1 to the posting list of the.
We see cat. We add Document 1 to the posting list of cat.
We see sat. We add Document 1 to the posting list of sat.
We see on. We add Document 1 to the posting list of on.
We see the again. It is already there for Document 1, so we do not add it twice.
We see mat. We add Document 1 to the posting list of mat.

Then we do the same for Document 2 and Document 3.

After we finish all documents, we have the complete inverted index that we saw earlier. This is how the inverted index is built.

A quick note for you

No matter which tech domain you work in, get familiar with these topics:

LLM
RAG
MCP
Agent
Fine-tuning
Quantization

We put it all together in one video:

AI Engineering Explained: LLM, RAG, MCP, Agent, Fine-Tuning, and Quantization

No need to stop reading - bookmark it and watch later when you get time. Future you will thank you.

Now, let's get back to the topic.

How a search query uses the inverted index

Now that we have built the index, let's see how a search actually uses it.

A user types a search word. We call this the query.

Suppose the query is dog.

Step 1: We take the query word dog and normalize it the same way we normalized the documents. So, we lowercase it. It stays dog.

It is very important that we normalize the query in the exact same way we normalized the documents. If documents are lowercased but the query is not, they will not match.

Step 2: We look up dog in the inverted index.

Step 3: The posting list for dog is Document 2 and Document 3. We return these as the search results.

One lookup gives us the answer.

Here, we can notice that the speed does not depend on reading all the documents. It depends on looking up one word and reading its posting list.

Handling multiple words in a search

In real life, people search for more than one word at a time. Let's say the user searches for cat dog.

Now, the question is: what should we return?

Most search engines treat this as "find documents that contain both words". So, we want documents that have cat and dog.

First, we look up cat. Its posting list is Document 1 and Document 3.

Then, we look up dog. Its posting list is Document 2 and Document 3.

Now, we need documents that appear in both posting lists. We find the common documents between the two lists.

Document 1 is only in the cat list.
Document 2 is only in the dog list.
Document 3 is in both lists.

So, the result is Document 3. It is the only document that contains both cat and dog.

Let's see this intersection as below:

   cat    -> Doc 1, Doc 3
   dog    -> Doc 2, Doc 3
   common -> Doc 3

Here, we can see that we line up both posting lists and keep only the document that appears in both. Document 3 is present in the cat list and in the dog list, so it is the only match.

This step of finding common documents between two posting lists is called an intersection.

There is a trick here. If we keep each posting list sorted by document number, then finding the common documents becomes very fast. We can walk through both sorted lists together and pick out the matches quickly.

So, sorting the posting lists makes the search faster.

Stay updated: Subscribe to our newsletter to get our latest AI and Machine Learning blogs straight to your inbox.

Storing positions for phrase search

Now, let's go one step deeper.

Sometimes a user does not just want documents that contain two words. They want the two words to appear next to each other, in order. This is called a phrase search.

For example, the user searches for the exact phrase cat sat. They want cat immediately followed by sat, not just both words appearing anywhere in the document.

Our current inverted index only tells us which documents contain a word. It does not tell us where in the document the word appears. So, it cannot answer a phrase search yet.

So, here comes a small upgrade to the rescue.

We store the position of each word inside the document. The position is just the place of the word, for example the first word, the second word, and so on.

Let's see the upgraded posting lists for Document 1, where the words are the at position 1, cat at position 2, sat at position 3, on at position 4, the at position 5, mat at position 6.

cat  ->  Document 1 (position 2)
sat  ->  Document 1 (position 3)

Here, we can see that the posting list now stores not only the document, but also the position of the word inside that document.

Now, for the phrase cat sat, we do the following. We find cat at position 2 in Document 1. We find sat at position 3 in Document 1. The position of sat is exactly one more than the position of cat. So, the two words are next to each other, in the right order.

So, Document 1 matches the phrase cat sat. It works perfectly.

This is how search engines support exact phrase matching. The positions give us the extra detail we need.

Why the inverted index is so fast

Let's pause and understand clearly why this approach is so fast.

Without an inverted index, to find a word we must read through every document. The work grows with the total amount of text. More documents means more reading. This becomes very slow at large scale.

With an inverted index, we do one lookup of the word, and we immediately get the list of documents. The work does not depend on the total amount of text. It depends on looking up one word and reading its posting list.

So, we do the hard work once, while building the index. After that, every search is just a quick lookup. We pay the cost upfront so that every future search is cheap.

Real-world use of the inverted index

Now, let's see where the inverted index is used in the real world.

Search engines: Tools like Google use inverted indexes to find web pages that contain our search words. When we search for something and get results in a fraction of a second, an inverted index is doing most of the work.

Search libraries and databases: Search systems like Apache Lucene and Elasticsearch are built on inverted indexes. Many applications use them to add fast search to their products.

Search by exact words like this is called keyword search, and we have a detailed blog on Hybrid Search that explains how it is combined with Semantic Search, which finds documents by meaning.

E-commerce search: When we search for a product on a shopping website, an inverted index helps find all the products whose titles or descriptions contain our words. This is how we get instant results from a huge product catalog.

Email and document search: When we search inside our emails or files, an inverted index quickly finds the messages and documents that contain our words.

Code search: Tools that let us search through large codebases also use inverted indexes to find files containing a particular function name or keyword.

Now we must have understood how an inverted index works, how it is built, and how it makes search fast.

If we want to go deep into how retrieval works in RAG and Vector Databases, our AI and Machine Learning Program at Outcome School covers them end to end.

Frequently Asked Questions

What is a posting list in an inverted index?

A posting list is the list of documents stored next to a word in an inverted index. For example, if the word cat appears in Document 1 and Document 3, then its posting list is Document 1 and Document 3. To support phrase search, the posting list can also store the position of the word inside each document.

Do we need to normalize the search query too?

Yes. We must normalize the query in the exact same way we normalized the documents. If the documents are lowercased but the query is not, the words will not match. Normalizing both sides the same way makes sure that Cat, CAT, and cat all match.

Should we remove stop words when building an inverted index?

It is optional. Stop words like the, is, on, and and appear in almost every document and carry very little meaning for search, so many systems remove them to save space. However, modern systems often keep them. Stemming, which reduces words like running and runs to run, is also optional and depends on our use case.

Why are posting lists kept sorted by document number?

Sorted posting lists make multi-word search faster. To find documents that contain all the query words, we need the common documents between the posting lists, which is called an intersection. When each list is sorted by document number, we can walk through both lists together and pick out the matches quickly.

Is Elasticsearch built on an inverted index?

Yes. Search systems like Apache Lucene and Elasticsearch are built on inverted indexes. Many applications use them to add fast search to their products. When we search and get results in a fraction of a second, an inverted index is doing most of the work.

That's it for now.

Thanks

Amit Shekhar
Founder @ Outcome School

You can connect with me on:

Follow Outcome School on:

Read all of our high-quality blogs here.