Loading...
System Design and AI Engineering, by Roni Das. 980 interactive lessons.
Start LearningIntermediate · Database Types & Storage
A map from each word to the list of documents that contain it, like the index at the back of a book. Search engines such as Elasticsearch use it to find words without reading every document.
In short
An inverted index is a map from each word to the documents that contain it. It works like the index at the back of a book. To search for 'kafka log', the engine reads the list for 'kafka' and the list for 'log'. It keeps the documents on both lists, and never reads every document. Elasticsearch, Lucene and most full-text search engines are built on it. A forward index is the opposite direction: from each document to the words it contains.
In short
An inverted index is a map from each word to the documents that contain it. It works like the index at the back of a book. To search for 'kafka log', the engine reads the list for 'kafka' and the list for 'log'. It keeps the documents on both lists, and never reads every document. Elasticsearch, Lucene and most full-text search engines are built on it. A forward index is the opposite direction: from each document to the words it contains.
Learn it in the course
This page is the free part.
₹1,777 in India$49 everywhere elseonce, for the whole course
The System Design course covers Inverted Index across a run of lessons, not one page. These 3 alone are about 75 minutes of step-by-step reading, every one with a quiz.
The data structure powering every search engine, mapping words to the documents that contain them.
Design a web search engine - crawling, inverted indexes, PageRank, query processing, and caching at global scale.
What a forward index stores and how search engines use it with the inverted index for BM25 scoring. Also shows how Lucene and Elasticsearch store it.
all part of
System Design Masterclass
770 lessons · about 283 hours · 18 free to read
₹1,777in India, by UPI
$49everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Inverted Indexpay once,
yours for life
Imagine 10 million product descriptions in a database, and a user types 'red running shoes'. The simple way is to read every description and check whether it contains those words. That is a full scan, and it gets slower with every new product. A normal database index on the description column does not help, because it is sorted by the whole text, not by the words inside it.
Think of a thick textbook. To find every page about 'photosynthesis', you do not read the whole book. You turn to the index at the back, find the word in alphabetical order, and it tells you the page numbers. An inverted index is exactly that, for a computer: for every word, the list of documents (and sometimes the positions) where it appears.
Building it has two steps. First, text analysis: each document is broken into words, called tokens, and each token is made standard, for example lower case, so that 'Kafka' and 'kafka' become the same term. Elastic's documentation calls these steps tokenization and normalization, and the same rules are applied to the search query, so the words in the query match the words in the index. Second, for every term, the engine adds the document's id to that term's list. This list is called a posting list.
Searching reads the index instead of the documents. The terms are kept sorted, so the engine finds a term quickly. For an AND search, it takes the documents that are on every term's list (the intersection). For an OR search, it takes the documents on any of the lists (the union). Then it ranks the results, using how often each word appears and how rare it is across all documents.
inverted_index.py (scripts/labs/guides/inverted_index_1023.py)
import re
from collections import defaultdict
docs = {
1: "Kafka keeps messages in a log",
2: "Redis keeps data in memory",
3: "A log is read in order by Kafka consumers",
}
def tokens(text): # analysis: lower-case, split into words
return re.findall(r"[a-z0-9]+", text.lower())
index = defaultdict(set) # term -> posting list (ids of docs that contain it)
for doc_id, text in docs.items():
for term in tokens(text):
index[term].add(doc_id)
def search(query): # AND query: intersect the posting lists
lists = [index.get(t, set()) for t in tokens(query)]
return sorted(set.intersection(*lists)) if lists else []
print("keeps ->", sorted(index["keeps"]))
print("log ->", sorted(index["log"]))
print("kafka log ->", search("Kafka log"))
print("keeps memory ->", search("keeps memory"))
print("terms in the index:", len(index))Output, captured 2026-10-23
keeps -> [1, 2]
log -> [1, 3]
kafka log -> [1, 3]
keeps memory -> [2]
terms in the index: 14
Document 3 writes 'Kafka' with a capital letter and is still found for 'kafka', because the same analysis (lower case, split into words) ran on the documents and on the query. 'keeps memory' finds only document 2, because only document 2 is on both lists.
A forward index goes the other way: for each document, the list of words it contains. It is the natural shape of the data as it arrives, and it is useful when you already have a document and need its words, for example to show a snippet, to highlight matches, or to rebuild the inverted index. It is useless for finding which documents contain a word, because you would have to read every entry.
Search engines usually keep both. The inverted index answers 'which documents contain these words?', and a forward store holds each document's own fields to show the results. The inverted index lesson and the forward index lesson cover each in depth, with diagrams and exercises.
In a system design interview, the inverted index is the answer to every 'search' box: product search, log search, searching your own email, or typeahead over titles. See it used in the Elasticsearch design guide, the Google Search design guide and the per-user mail search in the email service design guide.
Elasticsearch
Built on Lucene's inverted index, stored in immutable segments that are merged in the background.
Apache Lucene
The search library that defines segments, posting lists and the deletion file used by Elasticsearch, OpenSearch and Solr.
PostgreSQL
Offers full-text search with a GIN index, which is an inverted index over the words in a text column.
It is like the index at the back of a book. For every word, it keeps a list of the documents where the word appears, and sometimes the positions. So a search reads a few short lists, not every document.
Because it turns the natural direction around. Documents naturally list their words (document to words, a forward index). The inverted index lists, for each word, its documents (word to documents).
A forward index maps each document to the words it contains; it is good for showing or highlighting one document. An inverted index maps each word to the documents that contain it; it is what makes word search fast. Search engines keep both.
Yes. Elasticsearch stores text fields in Lucene's inverted index. Text is split into terms and normalized. Each term points to the documents that contain it. The index lives in segments that never change and are merged over time.
It looks up both words' posting lists. For an AND search, it keeps the documents on both lists (the intersection). For an OR search, it keeps the documents on either list (the union). Then it ranks them.
Checked against these on .
Elasticsearch
A distributed search and analytics engine built on Apache Lucene. Powers full-text search, log analysis, and real-time analytics at scale.
Index
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
B-Tree
A self-balancing search tree in which each node is a page holding many sorted keys, so it stays wide and shallow. Most database indexes use it: finding one key among millions takes only a few page reads.
LSM Tree
Log-Structured Merge Tree: a write-optimized data structure that buffers writes in memory and periodically flushes sorted runs to disk. Used by Cassandra, RocksDB, and LevelDB.
Semantic Search
Search that matches meaning instead of exact words. Text is turned into embeddings, and the results are the documents whose embeddings sit closest to the query's.
Redis
An in-memory data store used as a cache, message broker, and database. Blazing fast because everything lives in RAM.
This page explains the idea. The "Inverted Index" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Inverted Index lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Inverted Index in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
