19.3 What is an inverted index?

In the library: The subject card cabinet. One card per subject, each listing every book that covers it. "Cooking and Kerala" means taking both cards and finding the books on both lists.

In the system: A normal (forward) view is document → words. An inverted index flips it: term → list of documents containing it. Each list is called a posting list.

Figure: finding a word becomes one lookup; AND becomes intersecting two lists.

How queries work:

• One word: look up the term, return its posting list.
• AND ("design systems"): look up both lists and intersect them. Start with the shortest list, the rarest word, and check the others against it; it's much less work.
• OR: union the lists.
• Phrases ("system design", in that order): the index also stores the position of each word in each document, so the engine can check that "system" is followed directly by "design". In the chapter's code, "designing systems" matches books 5 and 7, but the phrase "system design" matches only book 5.

What real engines add:

• Posting lists are kept sorted by document ID and compressed, so they're small and fast to intersect.
• The index is built in immutable segments: new documents go into a new small segment, and segments are merged in the background. Deletes are marked, then cleaned up on merge.
• Each posting also stores term frequency (how many times the word appears), needed for ranking.

Memory code: "Flip the book: a card per word, listing every page it's on."

---