What a Trie Is, and Why Autocomplete Doesn't Search the Whole Dictionary
A trie stores words letter by letter along shared paths, so finding every word that starts with a given prefix costs almost nothing extra once you've walked to that prefix.
Imagine a hallway that branches at every doorway, where each doorway is labeled with a single letter, and walking through a sequence of doorways spells out a word letter by letter. Two words that start the same way -- "cat" and "car" -- share the exact same first two doorways before finally branching apart at the third. A trie is a data structure built around exactly that shared-hallway idea.
Formally, a trie is a tree where each node represents a single character, and the path from the root down to a specially marked node spells out one complete word stored in the structure. The key efficiency comes from what happens when two stored words share a prefix: instead of storing "cat" and "car" as two entirely separate sequences, a trie stores "ca" once, as a single shared path, and only branches into two separate paths at the point where the words actually differ.
That shared-path structure is exactly what makes autocomplete fast: finding every stored word that starts with a given prefix means walking down from the root through that prefix's own doorways once, and then everything reachable below the node you land on is, by construction, every word sharing that prefix -- no need to scan through the entire dictionary checking each entry individually for a matching start, the way a plain list of words would require.
That's the structural reason a trie's prefix search runs in time proportional to the length of the prefix being typed, not the total number of words stored -- searching a trie holding a hundred words and one holding a million words takes the same amount of work for the same prefix, since the walk only ever depends on how many characters deep it goes, never on how many other, unrelated words happen to be stored elsewhere in the structure.
Autocomplete is the most visible use of a trie, but the same shared-prefix efficiency shows up anywhere a system needs fast prefix-based lookups against a large set of stored sequences -- spell-checkers suggesting corrections, and IP routing tables matching an address against the most specific known network prefix, both lean on the identical underlying idea: share the common path, and only branch where the sequences actually diverge.