An inverted index over seven passages
Seven handbook passages (D1 to D9 without D5 and D7) keep the output short. Postings keep handbook order.
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.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 5 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
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"].
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?
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