Tries and prefix search
A trie stores strings by shared prefix, so finding everything that starts with "ca" is a short walk plus a scan of one subtree. It serves typeahead and prefix lookups, and its memory cost decides whether it fits.
What it is
A trie, also called a prefix tree, is a search tree for a set of strings. Each link between nodes carries a single character, so a node's position spells out a prefix, the root stands for the empty string, and each child extends its parent's prefix by one character. Looking up a key means following one link per character, so the work grows with the length of the key rather than with the number of keys stored. There is no hash function and no collisions, and walking the tree in order lists the keys sorted.
Prefix search is the operation the structure is built for: walk down the characters of the prefix, and the subtree under the node you reach holds exactly the keys that begin with it. For typeahead, our advice is to keep a short, ranked list of completions on each node, refreshed when weights change, so a query returns after the walk and does not scan the subtree. The cost moves to writes and memory, which is the right trade when reads outnumber updates by a wide margin.
Memory is the catch. In a basic implementation each node carries one link per character of the alphabet, 128 for ASCII, and most of those links are empty. A radix tree (compact prefix tree) fixes the worst of it by merging each node that has no siblings into its parent, so an edge can carry a whole substring such as ard instead of one character. That pays off most when the keys are long or share long runs, which is why radix trees appear in IP routing tables and in the term dictionaries of inverted indexes.
Search engines take the idea further. Lucene's suggesters compile the completion values into a finite state transducer, a compact automaton that answers the same prefix walk. Elastic's engineers describe the older approach of loading the values and building that automaton in memory at search time as slow and resource intensive, with a rebuild needed each time the index changed; Elasticsearch's completion suggester instead builds one automaton per index segment while indexing.
When to use it
Reach for a trie, or a product that wraps one, when the query is "everything that starts with this" and latency has to keep up with a person typing: search box suggestions, command palettes, tag and username completion, route lookup by longest matching prefix. The set should fit in memory on the node that answers, or be split so that each shard holds a range of prefixes.
In a system design round you can name a product instead of building the trie. Elastic's own guide to autocomplete recommends the completion suggester for query suggestions in a search bar, the kind an e-commerce or hotel site shows, and especially when the suggestions come from an outside source such as search analytics. Suggestions are indexed as a field of their own, each with an optional weight that ranks it, and a request names the prefix to complete. Name it, and then say what you'd store in it and how often you'd rebuild it.
When the set is modest and you already run Redis, a sorted set gives you the same query with no new component. ZRANGEBYLEX, available since Redis 2.8.9 and since 6.2 written as ZRANGE with the BYLEX option, returns the members whose strings fall between a min and a max, compared byte by byte, in O(log N + M) for N members and M results. It is defined for the case where all members were added with the same score; with mixed scores the result is unspecified. Load each term with score 0, ask for the range from the typed prefix up to just past it, and cap the answer with LIMIT.
When not to
The data already sits in a relational table. PostgreSQL 18 can use an ordinary B-tree index for LIKE when the pattern is a constant anchored at the start, such as name LIKE 'ca%'; a database not running in the C locale needs the index built with a special operator class for pattern matching. For a few hundred thousand names on an admin screen, that index is the whole design, and a separate in-memory structure is a second copy to keep in sync, worth adding when the index can't meet the latency or the load.
The data lives on disk. A trie touches one node per character, and when those nodes are on storage with slow random access the trie loses to a hash table or a B-tree. Keep tries for sets that fit in memory.
The query is not a prefix. Matching in the middle of a word (%phone%), tolerating typos, or searching across words in any order is the job of an inverted index with analyzers, or of edit-distance search. PostgreSQL's note on B-tree indexes makes the same point for patterns that start with a wildcard: the index does not help them. A trie answers that query by walking the whole tree, which is a full scan with extra pointers.
The set is small. A sorted array and binary search find the first key with a given prefix and then read forward. For a dropdown of fifty countries, that is the right amount of engineering.
Compared
| Option | How it finds a prefix | Pick it when | The weaker choice when |
|---|---|---|---|
Trie or radix tree in memory | Walk one link per character, then read the subtree or a stored top list | You own the service, the set fits in RAM, and you need to control ranking and rebuilds | The data is on disk, or you'd be writing a component a database or search engine already provides |
B-tree index with anchored LIKE | Range scan from the prefix to the first key past it | The strings are already in a relational table and the query is a left-anchored pattern | You need ranking by popularity, typo tolerance, or the pattern starts with a wildcard |
Redis sorted set, lexicographic range | Members share one score; ZRANGEBYLEX scans a string range in O(log N + M) | You already run Redis and the term list is modest and flat | You need per-term weights with the prefix match, or the set outgrows one node's memory |
Elasticsearch completion suggester | Finite state transducer built per segment at index time | You already run a search cluster and have a weighted list of suggestions, for example from search analytics | A lone prefix lookup is all you need and you don't run a search cluster |
In a picture
Step 1 of 3
Insert car and cat
Each key is a path from the root. The two words share the path for c and a, then split on the third character. A marker on car and cat records that a key ends there.