A trie, also called a prefix tree, stores a set of strings by their characters rather than by comparing whole keys. Each edge of the tree corresponds to one character, and the path from the root down to a node spells out a prefix. A complete stored key is marked at the node where its spelling ends, so strings that share a common prefix also share the same upper portion of the tree.
The structure was introduced by Edward Fredkin in 1960 in “Trie Memory,” published in Communications of the ACM, volume 3, issue 9, pages 490 to 499. Fredkin described it as a method of storing and retrieving information, naming it from the middle of the word “retrieval.” Knuth later places digital searching of this kind alongside comparison-based searching in the Sorting and Searching volume of The Art of Computer Programming.
Because navigation follows the characters of the key, a lookup takes time proportional to the length of the key being searched, independent of how many keys are stored. This also makes the trie naturally suited to prefix queries: starting from the node that spells a given prefix, every key beneath it shares that prefix, so all completions can be enumerated directly.
These strengths make tries a common choice for autocomplete suggestions, spell-checkers, and dictionary lookups, as well as for longest-prefix matching in IP routing tables. The trade-off is space, since a trie can use many nodes for sparse character sets, which has led to compressed variants that merge chains of single-child nodes.