A plain trie
A trie stores strings as a tree where each edge carries one character and each path spells a prefix. It supports fast prefix lookups, but long unique stretches create long chains of nodes that each have a single child, wasting memory.
The radix idea
A radix tree, also called a compressed trie or patricia tree, merges any chain of single child nodes into one edge labeled with the whole substring. Branching only happens where two stored keys actually diverge.
- Edges hold strings, not single characters.
- The node count drops to roughly the number of stored keys.
Lookups and inserts
To look up a key we match its characters against edge labels, descending until the key is consumed or a mismatch occurs. Inserting a new key may split an edge where the new key diverges from an existing label, creating a fresh branch node.
Where it shines
Radix trees back IP routing tables and many key value stores, because they keep prefix sharing while removing the overhead of long single child chains.
Key idea
A radix tree compresses single child chains of a trie into edges carrying whole substrings, branching only where keys diverge to save nodes while keeping fast prefix search.