A ternary search trie modified to support autocompletion suggestions.
It's kind of like a binary search tree with lexical ordering. Best case O(log n) lookups, and space requirements not significantly greater than the array of completions itself.
Construct with an array of strings:
const Completer = require('trie-completer');
let completer = new Completer([
'a', 'aa', 'aaab', 'abc', 'def'
]);
Then you can get the completions for a prefix via completer.getCompletions(prefix)
Completions will be sorted in ascending lexical order.
See Sedgewick & Wayne, Algorithms, 4th edition, Section 5.2