Typeahead

Typeahead, or autocomplete, is the dropdown that suggests completions as you type into a search box, and it has to answer in a few tens of milliseconds on every keystroke. The usual structure is a trie, a tree where each step down adds one letter, so every prefix you’ve typed corresponds to one node. Searching all completions under a node at typing time would be too slow, so each node stores its precomputed top handful of suggestions, ranked by popularity, and the whole thing sits behind a cache. The interesting trade-off is freshness: the rankings are rebuilt from query logs in the background, so trending searches can take a while to show up unless you add a faster path.