Google autocomplete functionality

Whenever you start typing your search on Google, you get a list of recommendations, and the more letters you type, the more accurate the recommendations get. If you’re like me, you’ve always wondered how this works — is the inverted index being stored, or is it something else?

The data structure that would be apt here is a Trie.

Source de l’article sur DZONE