PHASE 1Beginner ~20 min· topic 2 of 9

Topic 1.2

The Inverted Index

In one line

An inverted index stores, for every term, the list of documents that contain it. A query then reads a few short lists instead of every document, which is why search stays fast as the collection grows.

Think of it like this

The index at the back of a textbook. To find every page that mentions "photosynthesis" you do not read the whole book; you look up the word in the index and it lists the page numbers. The book is organised by page; the index flips it around so it is organised by word. That flip is why it is called an inverted index.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Inverted index: A map from each term to the documents that contain it.
Postings list: The list of document ids stored for one term.
Dictionary (vocabulary): The set of all distinct terms in the index.
AND query: Matches documents containing every query term (intersection of postings lists).
OR query: Matches documents containing at least one query term (union of postings lists).
Full scan: Reading every document to answer a query. Simple, but cost grows with the collection.

Step by step

01Step 1: the slow way

To find passages with the word helmet, loop over every passage and check. Seven passages is nothing; seven million is too slow for every keystroke. Count the words you had to read: that is the cost.

scan.pywhole filepython

hits = [doc_id for doc_id, text in HANDBOOK if "helmet" in tokenize(text)]

02Step 2: flip the table

Instead of document to words, store word to documents. Go through each document once, and for every distinct word append the document id to that word's list. The dictionary is built in one pass.

build.pywhole filepython

index = {}
for doc_id, text in HANDBOOK:
    for word in dict.fromkeys(tokenize(text)):   # distinct words, in order
        index.setdefault(word, []).append(doc_id)

Step 2: flip the tablediagram

Rendering diagram…

03Step 3: read a postings list

Look at the first lines the example prints. minutes appears in D3 D6 D8, pass only in D8, scooter nowhere. A rare word has a short list, and that is what makes the next step cheap.

04Step 4: AND is an intersection

Take the first term's list and keep only ids that are also in every other list. monthly AND pass keeps D8. pass AND helmet keeps nothing, because no passage contains both. Put the rarest term first in real engines so the working list is tiny from the start.

05Step 5: OR is a union

Collect every id that appears in any list. pass OR helmet gives D4 and D8. OR returns more results, so it needs ranking to be useful (Topic 1.3).

06Step 6: compare the work

The last two lines print the cost. The full scan reads 123 words. The index reads 2 postings to answer monthly AND pass. Scale the collection a thousand times and the scan grows a thousand times, while the index still reads two (slightly longer) lists.

Try it yourself

1
Predict a list
Before running, write down the postings of bike and rides. Then add print(index["bike"], index["rides"]) and compare.
2
Three-word AND
Run match_all(["minutes", "the", "late"]). Which passage is it, and which of the three lists was the shortest? Start from that list: why is that faster?
3
Add a document
Append ("D10", "A flat tyre can be fixed free at any shop.") to HANDBOOK, rebuild, and look at the postings for shop. Which lists changed? How many lists does one new document touch?

Code & diagrams

An inverted index over seven passages New tab

Seven handbook passages (D1 to D9 without D5 and D7) keep the output short. Postings keep handbook order.

Expected output

words in the index: 91
postings for 'the': D3 D6 D8 D9
postings for 'minutes': D3 D6 D8
postings for 'pass': D8
postings for 'helmet': D4
postings for 'scooter': (none)
monthly AND pass:   D8
pass AND helmet:    (none)
pass OR helmet:     D4 D8
words read by a full scan: 123
postings read by the index: 2

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

AND that behaves like OR

In the Python tab, in match_all, change found &= set(index.get(word, [])) to found |= set(index.get(word, [])) and run.

terminal

$ Run

── what you'll see ──

monthly AND pass: D8

pass AND helmet: D4 D8

pass OR helmet: D4 D8

Myth vs fact

Myth

A bigger index makes every query slower.

Fact

Query cost depends mostly on the lengths of the postings lists of the query's terms, not on the total number of documents. Common words have long lists; rare words short ones.

Myth

Search engines read the documents when you search.

Fact

They read the index. The documents are only opened afterwards, to show snippets for the few results.

Myth

AND is always the right operator.

Fact

AND is precise but returns nothing when one word is missing or misspelt. OR with ranking (the next topics) forgives a missing word and still puts the best match first.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Real postings lists are stored sorted by document id and compressed (delta encoding: store the gaps between ids, which are small numbers). Sorted lists let AND walk two lists side by side in a single pass, and skip pointers let the walker jump over ranges.
▸
Intersect shortest list first. If monthly has 3 postings and the has 3 million, checking the 3 candidates against the long list is far cheaper than walking the long list. Engines estimate list sizes from the dictionary for exactly this reason.
▸
Updating one huge sorted list in place is slow, so engines (Lucene and everything built on it) write immutable segments: new documents go to a small new segment, deletes are marked, and segments are merged in the background. Searches read all segments and combine results.

Remember this

1
Why this exists. The simplest search reads every document and checks whether it contains the query words. That is fine for twelve passages and hopeless for twelve million, because the work grows with the size of the collection on every single query. Search engines need the cost of a query to depend on how many documents *match*, not on how many documents *exist*.
2
The structure. An inverted index is a dictionary from each term to its postings list: the ids of the documents that contain that term, usually kept sorted. Building it is one pass over the data: analyse each document, and for each distinct term append the document's id to that term's list. In the example, pass maps to just D8, while the very common the maps to four documents.
3
Answering a query. For the query monthly pass, look up the postings of each term and combine them. An AND query keeps only documents present in every list (an *intersection*): monthly AND pass gives D8. An OR query keeps documents present in any list (a *union*): pass OR helmet gives D4 and D8. Terms missing from the dictionary (scooter) simply have an empty list.
4
Why the lookup is fast. Finding a term in the dictionary is a hash lookup (or a binary search in a sorted file), and a postings list is short for rare terms. In the example the full scan reads 123 words to answer one question, while the index reads 2 postings. With real data the gap is millions to thousands, and real engines also use skip pointers and compression to move through long lists quickly.
5
What an index costs. It is extra data that must be built and kept in step with the documents. Adding a document touches one list per term in it. Removing or changing one means finding that document in many lists (the playbook, Topic 1.9, does this). Real engines write small immutable index segments and merge them in the background instead of editing lists in place.
6
What the index can and cannot say. A basic postings list only says *which* documents contain a term. It does not say how often, where, or how important. Topic 1.3 adds counts so documents can be ranked, and Topic 1.5 adds positions so phrases can be matched. An AND/OR result is an unordered set, which is rarely what a user wants: they want the best match first.

Explain it without notes

What is an inverted index, and why does it make search faster than scanning?

How do AND and OR queries use postings lists?

Why is the work of an indexed query roughly independent of the total number of documents?

Practice

Build the index for the three passages below and print the postings of late and minutes: ("A", "Bikes returned late are charged 2 dollars"), ("B", "Late fee 2 dollars every 15 minutes"), ("C", "Pass holders ride 45 minutes").

Write match_any(index, words) that returns the sorted list of ids matching at least one word. Print the result for ["late", "holders"].

Trade-offs

↔
Index vs scan: the index makes queries fast and costs memory and update work; a scan needs nothing extra and is fine for a few hundred short texts.
↔
Sorted compressed lists vs simple lists: much smaller and faster at scale, much more code to write. Use an engine (Topic 1.7) rather than writing your own for real data.
↔
AND vs OR: AND is precise and brittle, OR is forgiving and needs ranking.

Done when you can

Done when you can draw the inverted index of three short documents on paper.
Done when you can explain why a query on a rare word is fast regardless of collection size.
Done when you can write AND and OR over postings lists and say which list to start with.
Done when you can name what a basic postings list does not tell you (counts, positions).

Command Palette

Words you'll meet

Step by step

01Step 1: the slow way

02Step 2: flip the table

03Step 3: read a postings list

04Step 4: AND is an intersection

05Step 5: OR is a union

06Step 6: compare the work

Try it yourself

Predict a list

Three-word AND

Add a document

Code & diagrams

Break it on purpose

AND that behaves like OR

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can