Words stored by their beginnings
A Socratic walk-through of words stored by their beginnings — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How can looking up a word take the same time whether the dictionary holds a thousand entries or a billion?
Every lookup structure we meet first is a guessing structure. A sorted list, a search tree: you compare your word with one that is already there, learn whether you have overshot, and halve what remains. The number of guesses grows with the size of the collection, because the whole method is about narrowing down among the entries.
But consider what you actually do with a paper dictionary. You do not compare. You go to C, then to CA, then to CAT. Would that have taken you longer if the dictionary had a thousand times more words in it? And if not — what is different about it?
Reasoning it through
REASONING #The difference is in what the key is treated as. A comparison structure treats a word as an atom: an opaque thing you can hold up against another thing and ask "which is bigger?". Since the only tool is comparison, the depth of the search must scale with how many candidates need eliminating, and each comparison eliminates at best half. Hence a logarithm in the number of entries.
Now suppose you refuse to compare, and instead treat the word as a route. At the top there is a junction with one signpost per letter. You read the first letter of your word and take that turn. At the next junction you read the second letter and take that turn. Ask the question that matters: does any junction's cost depend on how many words the collection holds?
It does not. A junction offers one turn per letter of the alphabet, and the alphabet does not grow when the dictionary does. So the work is the number of turns, which is the length of your word. Adding a billion more entries adds branches out to the sides; it does not make "cat" any longer to spell.
That is the whole trick, and it is worth naming what makes it possible: the keys are not stored in the nodes at all. The key is the path. Nothing at any junction needs to be read and compared — the character selects the edge directly.
So is the claim really that lookup is independent of collection size? Nearly, and the exceptions are instructive rather than fatal.
First, that junction has to select a turn in constant time. If each node holds an array with one slot per possible symbol, it does — but a mostly-empty array of 256 slots per node is a great deal of memory. If instead each node keeps a small map of the branches it actually has, you reintroduce a factor — but a factor bounded by the alphabet size, not by the number of entries, so the independence survives.
Second, and more honestly: the number of entries does put a floor on key length. Over an alphabet of s symbols there are only s to the power L distinct strings of length L, so a billion distinct keys cannot all be four bytes long. Length is independent of collection size for a given word, but you cannot hold a huge collection of very short keys. The independence is real; it is not magic.
Third, memory again, from a different angle. A plain trie is full of long single-child chains — the tail of a word nothing else shares. Storing one node per character there is wasteful, so real implementations compress those runs into a single edge carrying a whole substring. That is a radix tree, and the depth becomes the number of characters that actually distinguish your key, which is usually far fewer than its length.
And one practical caveat that pulls the other way: every level of a trie is a pointer hop to an unpredictable address, and those hops cannot be overlapped by the processor. A hash table with a single probe often wins on the clock despite doing the same amount of asymptotic work. So why use a trie at all? Because of the questions only it can answer — every word starting with "cat", the entries in sorted order without sorting, or the longest stored prefix of an address, which is exactly what an internet router does for every packet.
The analogy
THE ANALOGY #Think of a route through signposted junctions rather than a search through drawers. At each junction there is a board with one arrow per letter; you read the next letter of your word and take that arrow. Nobody at any junction knows how many destinations exist beyond it, and nobody needs to — your word is not something to be found, it is the set of instructions for getting there.
the boards are not free — a junction must carry an arrow slot for every letter that might come next, so a naive trie spends most of its memory on arrows pointing nowhere, which is why real ones compress long unbranching stretches of road into a single signed exit.
Clarifying the model
THE MODEL #The refinement that connects the pieces: we have not beaten a lower bound, we have changed the cost model. The n log n and log n results for comparison-based structures are theorems about comparisons. A trie does not compare, so those theorems say nothing about it — much as counting sort escapes the sorting bound by looking at digits rather than pairs. Whenever a result feels dodged, check whether the assumption behind it is still in force.
The misconception to correct is that a trie is simply a faster dictionary. It is a different trade. You spend memory, and you spend cache behaviour, to buy two things: a cost that tracks the key rather than the collection, and a set of prefix questions that hashing cannot answer at all. If all you ever do is exact lookup on whole keys, a hash table is usually the better engineering choice, and saying so is not a concession.
Be precise about the sharing, too. Words with a common beginning share the path for it, so a related corpus is stored far more compactly than a list — and that shared structure is what makes autocomplete cheap, because "everything under this node" is a subtree rather than a search.
A picture of it
THE PICTURE #How to readEvery edge is one character, and a word is the sequence of characters you read on your way down from the centre — so the words are stored in the shape, not in the nodes. The hexagons mark the points where a complete word ends; notice that "car" is on the way to "card", which is why a trie can tell you a stored word is the prefix of another. Trace "cat" and count the steps: three, because the word has three letters. Adding a thousand more branches around the outside would not add a fourth.
What became clearer
WHAT CLEARED #Lookup cost is not inherently a function of collection size — that is a consequence of choosing comparison as your only tool. Treat the key as a path to be walked rather than a value to be compared, and the depth becomes a property of the key. What you pay for it is memory and cache behaviour; what you gain, besides the scaling, is the whole family of prefix questions that a hash of the entire key destroys the information to answer.
Where to go next
ONWARD #- How a radix tree's edge compression changes both depth and memory, and when it is worth it.
- Why longest-prefix match makes tries the natural structure for IP routing tables.
- What a ternary search tree trades away to shrink the per-node branching cost.
Key terms
TERMS #| Term | What it means |
|---|---|
| Trie | a tree in which the path from the root spells the key, so no key is stored in any node. |
| Radix tree | a trie with unbranching chains collapsed into single edges carrying whole substrings. |
| Prefix sharing | the property that keys with a common beginning traverse and occupy the same nodes. |
| Longest-prefix match | finding the longest stored key that begins a given input; a routing table's core operation. |
Every term the collection defines is gathered in the glossary.