Art of Codeartofcode
Lesson 6 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

19.5 How do prefix search and tries work?

3 min read+10 XP

In the library: The card drawers are labelled "Coa–Coo", "Cop–Cyn". To find everything starting with "Coo", you open one drawer and read from there. You don't need the whole word yet.

In the system: Autocomplete ("dat" → "data", "database", "date") needs prefix search, on every keystroke, in a few milliseconds. (Chapter 34 designs a full typeahead service.)

A trie (prefix tree) stores words letter by letter: each path from the root spells a word's beginning. To complete "dat", walk d → a → t; every word below that node is a match.

walk d, a, t; everything below is a match, ranked by popularity.

Figure: follow the letters, then return the most popular few below.

In the chapter's code, with popularity counts, "dat" returns data, database, date, in that order.

At scale:

  • Store the top few suggestions at each node, so a keystroke is one walk down the tree, not a search through everything below it.
  • Build it offline from search logs and popular titles, and refresh it every few minutes or hours.
  • Cache hot prefixes (one or two letters) at the edge, and debounce keystrokes in the app.
  • Search engines also offer prefix and "search-as-you-type" features built on edge n-grams (indexing "d", "da", "dat", "data" as terms), which trade index size for speed.

Memory code: "Follow the letters; the answers are already waiting below."