A customer opens Tiffin's search box and types "p". Before they type the next letter, the app should already suggest "pizza", "paneer tikka" and "pasta". They type "i" and the list changes to "pizza", "pizzeria", "pita". Every keystroke is a new query, and each one has to come back in well under 100 milliseconds.
You could run SELECT name FROM menu_items WHERE name LIKE 'pi%' ORDER BY orders DESC LIMIT 3 on every keystroke. With an index on name it even works, for a while. But at dinner time, with thousands of people typing, you are sending a database query for every letter anyone types. The data structure built for exactly this job is the trie, and its compact cousin, the FST, is what search engines actually ship.
What a trie is
A trie (from retrieval, usually said "try") is a tree where each edge is one character. A word is the path from the root down to a node marked "end of word". Words that share a prefix share the top of their path.
Here is a trie for five Tiffin dishes. Each letter is a node, and the path from the root to it spells the prefix that node represents. The right-hand column marks the nodes where a word ends, with its order count:
root
└─ p
├─ i
│ ├─ z ─ z ─ a pizza (900)
│ │ └─ e ─ r ─ i ─ a pizzeria (120)
│ └─ t ─ a pita (60)
└─ a
├─ s ─ t ─ a pasta (400)
└─ n ─ e ─ e ─ r paneer (700)
Two things fall out of this shape:
- Looking up a prefix costs the length of the prefix, not the number of words. Finding "piz" takes three steps whether the trie holds 5 dishes or 5 million.
- Everything under a node shares its prefix. Once you reach the "pi" node, every word below it starts with "pi". Autocomplete becomes "walk down, then collect what is underneath".