Autocomplete is, of course, available out of the box with Elasticsearch, but I’ll indulge Xu here, who dedicates vol. 1, ch. 13. to autocomplete.
Basically, you need a Prefix tree (Trie), and you need some strategy for updating it and reading from it.
- Your trie is going to get huge if you let it, so you need to impose some limits on how long the prefixes can get.
- You can cache the top N complete results at higher nodes in the tree so that you don’t need to traverse to the bottom.