19. Search and Inverted Indexes
1
The picture to keep in your head2
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 breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab19. Search and Inverted Indexes
Memory card and where the analogy breaks
3 min read+10 XP
The memory card (tear this page out)
| # | Question | Memory code |
|---|---|---|
| 19.1 | Why LIKE '%word%' fails? | A word in the middle has nowhere to jump to |
| 19.2 | Tokenising and normalising? | Clean the words the same way going in and coming out |
| 19.3 | Inverted index? | Flip the book: a card per word, listing every page it's on |
| 19.4 | Ranking? | Rare words count more; repeating a word stops paying |
| 19.5 | Prefix search and tries? | Follow the letters; the answers are already waiting below |
| 19.6 | Keeping in sync? | The shelves are the truth; the cards follow the change log |
| 19.7 | Elasticsearch? | Lucene does the cards; Elasticsearch runs the department |
| 19.8 | Sharding search? | Ask every room for its best, then pick the best of the best |
The whole chapter in one line: Clean the words, keep a list of documents per word, rank by rare and well-placed matches, feed the index from the database's change log, and split it by document across shards.
Where the analogy breaks
- A librarian understands meaning. An inverted index only matches terms: "car" won't find "automobile" without synonyms or vector search.
- Library cards are updated by hand, rarely. A search index takes thousands of updates a second, through segments, merges and refreshes.
- A library has one copy of each card. Search clusters keep several replicas, and each shard's scores are computed from its own documents only.
Quick check
Five questions on this chapter. Pick an answer, then check it.
quiz