Art of Codeartofcode
Lesson 1 of 15

19. Search and Inverted Indexes

1
The picture to keep in your head
2
19.1 Why doesn't `LIKE '%word%'` scale?
3
19.2 How do you tokenise and normalise text?
4
19.3 What is an inverted index?
5
19.4 How does ranking work (TF-IDF, BM25 in brief)?
6
19.5 How do prefix search and tries work?
7
19.6 How do you keep the search index in sync with the database?
8
19.7 Where does Elasticsearch fit in the big picture?
9
19.8 How do you shard a search index?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
19. Search and Inverted Indexes

The picture to keep in your head

3 min read+10 XP

Every question below is answered twice: first in the library, so you can picture it, then in the system, so you know exactly how it works. Each answer ends with a memory code to lock it in.

The picture to keep in your head

An old library has a wooden cabinet of subject cards. Each card is one subject, like "Cooking", and lists every book that covers it, with shelf numbers. You want books on cooking? You don't walk the shelves opening every book. You pull one card.

The librarian keeps it useful in a few ways. Everyone files under the same spelling ("Cooking", not "cooking", "COOKING" or "cookery"). If you want "cooking and Kerala", you lay two cards side by side and pick the books on both. The librarian hands you the best books first, not just any book that mentions the word. And when new books arrive, someone updates the cards, or the cabinet slowly lies to you.

That's an inverted index: instead of "book → its words", keep "word → the books it appears in".

Our running example: the bookstore's catalogue search. The catalogue has about 2 million titles (an assumption for practice), each with a title and a description, and customers type things like "database internals" or "kerala recipes" and expect good results in a fraction of a second.

In the libraryIn the system
Opening every book on every shelfLIKE '%word%', a full table scan
Everyone filing under the same spellingThe analyzer: lowercase, split, stop words, stemming
A card per subject listing the booksThe inverted index: term → document IDs
Laying two cards side by sideIntersecting posting lists (AND queries)
The librarian's "best ones first"Ranking: TF-IDF, BM25
The drawer of cards starting "Coo..."Prefix search and tries (autocomplete)
Updating cards when books arriveKeeping the index in sync with the database
Several cabinets, one per wingSharding a search index

the library cards mapped to LIKE scans, analyzers, inverted indexes, ranking and sync.

Figure: keep a card per word that lists where it appears.