Inverted Indexes: Fast Lookup

The Instant Search in Your Pocket

Open any large WhatsApp group you have been part of for a couple of years — a family group, a class group, a society notice board — and it will easily hold tens of thousands of messages. Now tap the search icon and type a single word, say syllabus. Before you have even lifted your finger off the last letter, every message containing that word appears in front of you, highlighted, in the correct order. The app did not just scroll through years of conversation while you typed. It could not have — checking tens of thousands of messages character by character, for every keystroke, from every user, all day long, would grind any phone or server to a halt.

The same thing happens when you search on Google, when you use the search box inside a shopping app, or when you look something up in a PDF reader across a four-hundred-page textbook. In every one of these situations, the software already knew, before you typed anything, which items contain which words. Your search did not trigger a scan — it triggered a lookup. That distinction, between scanning and looking up, is the subject of this chapter, and the data structure that makes the lookup possible is called an inverted index.

By the end of this chapter you will build a working inverted index in Python, trace by hand exactly how a search engine answers a two-word query in a handful of steps instead of scanning every document, and see precisely why this one design decision is what makes fast search possible at any scale — from a WhatsApp group to the World Wide Web.

Why "Just Scan Everything" Breaks Down

Say you have a small folder of text files and you want to find every file that mentions the word Bumrah. The most direct approach is to open every file and check whether the word appears in it — this is exactly what the Unix command grep does, and what your browser does when you press Ctrl+F on a single web page: it walks through the text from the beginning, comparing as it goes. This approach is called a linear scan, and it works perfectly well for a single page or a small folder.

Now scale it up. Suppose you have N documents, each with roughly L words on average. Answering one query by scanning everything costs on the order of N × L word comparisons — you touch every word of every document, every single time, even the documents that have nothing to do with your query. For six short headlines this is over before you notice it. For fifty thousand chat messages, checked on every keystroke of every search, for every user of an app, the cost adds up fast. For a search engine indexing a meaningful fraction of the web, a fresh scan per query is not merely slow — it is impossible within the time any human is willing to wait.

The way out is to stop scanning at query time altogether. If you are willing to do some work once, in advance, before anyone types a single query, you can precompute the answer to "which documents contain this word?" for every word that appears anywhere in your collection, and simply store those answers. A query then becomes nothing more than looking up an answer that already exists, no matter how large the collection has grown. That precomputed structure is the inverted index, and building it once is exactly what happens when an app "indexes" your messages or when a search engine "crawls and indexes" the web.

Flipping the Index: From Documents-to-Words to Words-to-Documents

You already know a data structure that does something similar: the index at the back of a printed textbook. To find every page that discusses "Photosynthesis," you do not flip through all four hundred pages — you jump straight to the alphabetically sorted back index, find the entry Photosynthesis, and read off the exact page numbers listed beside it. The book's index maps a term to the list of locations where it occurs. That is precisely the shape of the data structure this chapter is about, with "page number" replaced by "document ID."

To see why it is called inverted, contrast it with the structure you start with. Every document collection naturally gives you what is called a forward index: a mapping from each document to the list of terms it contains — document 1 contains these words, document 2 contains those words, and so on. That is just the documents themselves, read left to right. An inverted index flips that relationship around: instead of document → terms, it stores term → documents. For every distinct word anywhere in the collection, it keeps a list of every document that contains that word. That list is called a postings list (or simply the postings for that term), and each individual entry in it — typically a document ID — is called a posting. The complete set of distinct terms being tracked across the whole collection is often called the dictionary or the vocabulary.

Once this term-to-postings mapping is built, answering "which documents contain the word Bumrah?" no longer means touching every document. It means looking up one key, bumrah, and reading off its postings list directly — the same speed whether the collection holds six documents or six billion.

Building the Index, One Headline at a Time

Suppose a small sports news aggregator has indexed the following six sample headlines, given document IDs 1 through 6:

• D1: "Kohli scores century in Mumbai"
• D2: "Rohit and Kohli open the innings in Chennai"
• D3: "Bumrah takes five wickets in Mumbai"
• D4: "India wins the match in Chennai"
• D5: "Kohli and Bumrah shine in the World Cup"
• D6: "Rohit scores century in the World Cup final"

Before any indexing happens, each document is broken down into searchable units through tokenization — splitting text on spaces and punctuation, and lowercasing everything so that Kohli and kohli are treated as the same term. Most systems also strip out stopwords: extremely common words like the, in, and and that appear in nearly every document and therefore do almost nothing to distinguish one document from another, while bloating every postings list they touch. We will drop the stopwords {in, and, the} from our index.

Build the index by processing documents one at a time, adding the document's ID to the postings list of every term it contains. After D1 ("kohli scores century mumbai" once stopwords are gone), the index has four entries, each pointing only at document 1:

kohli    -> {1}
scores   -> {1}
century  -> {1}
mumbai   -> {1}

D2 contributes the tokens rohit, kohli, open, innings, chennai. Notice that kohli already exists in the index from D1 — a new entry is not created, its existing postings list is simply extended:

kohli    -> {1, 2}
scores   -> {1}
century  -> {1}
mumbai   -> {1}
rohit    -> {2}
open     -> {2}
innings  -> {2}
chennai  -> {2}

Continue this for all six documents and the complete inverted index looks like this:

bumrah   -> {3, 5}
century  -> {1, 6}
chennai  -> {2, 4}
cup      -> {5, 6}
final    -> {6}
five     -> {3}
india    -> {4}
innings  -> {2}
kohli    -> {1, 2, 5}
match    -> {4}
mumbai   -> {1, 3}
open     -> {2}
rohit    -> {2, 6}
scores   -> {1, 6}
shine    -> {5}
takes    -> {3}
wickets  -> {3}
wins     -> {4}
world    -> {5, 6}

Every postings list here is kept sorted by document ID. That is a deliberate design choice, not an accident — the next section shows exactly why it matters.

Answering a Query: Merging Two Postings Lists

Someone now searches for kohli AND century — every document mentioning both words is wanted. Looking up the two postings lists directly from the index gives:

kohli   -> [1, 2, 5]
century -> [1, 6]

The query is now a pure list problem: find every document ID present in both lists. The naive way is a nested loop — for each of the 3 entries in kohli's list, check it against each of the 2 entries in century's list, which is 3 × 2 = 6 comparisons for lists this size, and grows to n × m comparisons for lists of length n and m.

Because both lists are sorted, there is a much better way: walk through both lists at once with two pointers, moving forward only as needed. Start a pointer i at the beginning of the kohli list and a pointer j at the beginning of the century list:

• Step 1 — compare kohli[0] = 1 with century[0] = 1. They are equal, so document 1 is added to the result, and both pointers move forward.
• Step 2 — compare kohli[1] = 2 with century[1] = 6. Since both lists are sorted and 2 is smaller than 6, nothing still ahead in century's list can equal 2 — so only the kohli pointer advances.
• Step 3 — compare kohli[2] = 5 with century[1] = 6. Again 5 is smaller, so only the kohli pointer advances.
• The kohli pointer has now moved past the end of its list (length 3), so the merge stops.

The result is [1] — document 1 is the only headline containing both "Kohli" and "century," which matches the actual text of D1. This merge-based intersection took exactly 3 comparisons, not 6, and the saving grows with the size of the lists: for two postings lists of 1,000 entries each, the merge needs at most 2,000 steps against 1,000,000 for the nested-loop version — five hundred times fewer. This is exactly why postings lists are stored in sorted order: it is what makes the cheap merge possible in the first place. That exact process translates into a short function:

def intersect_sorted(list1, list2):
    result = []
    i, j = 0, 0
    while i < len(list1) and j < len(list2):
        if list1[i] == list2[j]:
            result.append(list1[i])
            i += 1
            j += 1
        elif list1[i] < list2[j]:
            i += 1
        else:
            j += 1
    return result

Calling intersect_sorted([1, 2, 5], [1, 6]) runs exactly the three steps traced above and returns [1].

From Pencil-and-Paper to Python

The whole process — tokenize, build the index, answer a query by intersecting postings — translates directly into a short, complete Python program:

import re

documents = {
    1: "Kohli scores century in Mumbai",
    2: "Rohit and Kohli open the innings in Chennai",
    3: "Bumrah takes five wickets in Mumbai",
    4: "India wins the match in Chennai",
    5: "Kohli and Bumrah shine in the World Cup",
    6: "Rohit scores century in the World Cup final",
}

STOPWORDS = {"in", "and", "the"}

def tokenize(text):
    words = re.findall(r"[a-zA-Z]+", text.lower())
    return [w for w in words if w not in STOPWORDS]

def build_inverted_index(docs):
    index = {}
    for doc_id, text in docs.items():
        for term in tokenize(text):
            index.setdefault(term, set()).add(doc_id)
    return index

inverted_index = build_inverted_index(documents)

def and_query(index, *terms):
    result = None
    for term in terms:
        postings = index.get(term, set())
        result = postings if result is None else result & postings
    return sorted(result)

print(and_query(inverted_index, "kohli", "century"))  # [1]
print(and_query(inverted_index, "kohli", "bumrah"))    # [5]
print(and_query(inverted_index, "rohit", "century"))   # [6]

tokenize lowercases the text, pulls out runs of letters with a regular expression, and drops stopwords. build_inverted_index loops over every document exactly once, and for every term it meets, adds the current document ID to that term's set using setdefault, which creates an empty set the first time a term is seen and reuses it afterward. and_query accepts any number of terms and repeatedly intersects their postings sets with Python's built-in & operator — the same idea as the two-pointer merge, expressed at a higher level. Running this program prints [1], [5], and [6]; each result can be checked by hand against the six headlines above.

Notice what did not happen: at no point during and_query did the program re-read the text of any document. All the expensive reading happened exactly once, inside build_inverted_index. Every query afterward, however many times it runs, only touches the small postings lists of the specific words asked for.

OR, NOT, and Exact Phrases

Combining postings lists with the operators AND, OR, and NOT is known as Boolean retrieval, and the same postings lists answer far more than just AND queries. An OR query — documents containing either word — is the union of the two postings lists rather than their intersection (in Python, the | operator instead of &). A NOT query — documents that do not contain a word — is the set of all document IDs in the collection with that word's postings list removed from it.

A trickier case is an exact phrase, such as "World Cup" as a single unit rather than the two words appearing anywhere in the same document. A plain postings list cannot tell the difference between a document that says "World Cup" and one that happens to mention "world" in one sentence and "cup" in another, unrelated one. The fix is to store more than just a document ID in each posting — also store the positions at which the term occurs within the document, giving a positional index. For the two documents that mention both words:

world -> {5: [3], 6: [3]}
cup   -> {5: [4], 6: [4]}

Document 5's token sequence after stopword removal is kohli, bumrah, shine, world, cup, so world sits at position 3 and cup at position 4. To confirm the phrase "world cup," the query checks whether cup occurs at exactly one position after world in the same document. Here 4 = 3 + 1 in both D5 and D6, so both count as genuine phrase matches. Without positions, this distinction could not be made from the postings lists alone.

How This Scales to Billions of Pages

Real search engines apply the same ideas covered here, plus two refinements that matter once a collection grows from six headlines to billions of documents. First, when a query has more than two terms, it pays to intersect the shortest postings lists first. The length of a term's postings list is called its document frequency, and starting with the rarest terms shrinks the intermediate result as early as possible. For a three-word query like kohli AND century AND mumbai, century and mumbai each have a postings list of length 2, while kohli's has length 3; intersecting the two shorter lists first, then intersecting that small result with kohli's list, does less total work than starting with the longest list.

Second, storage matters at scale: a postings list for a common word can hold billions of document IDs, and storing each one as a full number is wasteful. A standard trick is gap encoding — instead of storing the absolute document IDs [1, 2, 5, 9, 15], store the gaps between consecutive entries: [1, 1, 3, 4, 6]. Because the sorted document IDs in a postings list tend to be close together, the gaps are usually much smaller numbers than the IDs themselves, and smaller numbers take fewer bits to store — across billions of postings, this adds up to enormous savings in memory and disk space.

These are not just theoretical ideas. Apache Lucene, the open-source search library that underlies both Elasticsearch and Apache Solr, builds its search capability directly on an inverted index. SQLite, the lightweight database engine bundled inside a huge share of mobile apps, ships a full-text search extension that is documented as being built on an inverted index. Whatever the exact private engineering behind any single app's search bar, the instant results it returns — from a search engine answering billions of queries a day to an app searching years of your own messages — are only possible because of some form of this one core idea: do the expensive reading once, and turn every future lookup into a cheap one.

Back to Your Chat Search

Return to that WhatsApp group with tens of thousands of messages. Typing syllabus into the search box is, structurally, exactly the query and_query(inverted_index, "syllabus") from the code above — a single lookup into a postings list that was built once, quietly, as messages arrived, rather than a fresh scan triggered by your keystroke. The result appears before you finish typing not because phones have become impossibly fast at reading text, but because the hard work of reading was already done in advance, trading it for a lookup. That trade — precompute once, so that every future question is cheap to answer — is the idea this chapter has been about, and it reappears throughout computer science under different names: a cache, a database index, a hash table. The inverted index is simply the version of that idea built specifically for one of the oldest and most common questions in computing: which of these documents contain this word?

Think About It

Think about this: How would you explain inverted indexes: fast lookup to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where inverted indexes: fast lookup is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting inverted indexes: fast lookup to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind inverted indexes: fast lookup, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.