Radix (Patricia) Tree, in depth: path compression, edge splits and merges, prefix search, longest-prefix match and where radix trees run

From trie to radix tree

Start from a trie and apply path compression. Every chain of nodes in which each node has one child and marks no key collapses into a single edge labelled with the concatenated characters. After compression the structure satisfies one invariant: every node other than the root either ends a stored key or has at least two children. Two consequences follow. A tree storing n keys has at most n key-ending nodes and at most n - 1 branching nodes that end no key, so it has O(n) nodes regardless of key length. And the children of a node are distinguished by the first character of their edge labels, because two edges sharing a first character would have been merged into a common prefix edge.

The diagram stores seven words with total length 48 characters. The plain trie needs 28 nodes, one per distinct prefix; the radix tree needs 14. The saving grows with key length and with how much keys share: URLs, file paths, and token sequences are close to the best case.

Radix, PATRICIA, crit-bit: the names

The names are used loosely, so it helps to separate them. A compressed trie or radix tree is the character-level structure above, usually with byte or character edges. The name PATRICIA comes from Donald Morrison's 1968 paper in the Journal of the ACM, Practical Algorithm To Retrieve Information Coded in Alphanumeric. It works on bits: keys are bit strings, every internal node has exactly two children, and each node stores the index of the bit where its subtrees first differ rather than the skipped bits themselves. A lookup tests only those bit positions on the way down and then compares the full key once at the leaf, because skipped bits were never checked. The crit-bit tree popularised by Daniel J. Bernstein is the same idea. A radix-2^r tree such as the Linux kernel's branches on r bits at a time with fixed-size child arrays; it compresses less but indexes children directly.

Insert and lookup

Each node holds a map from the first character of an edge to the pair (label, child), a flag saying whether the node ends a key, and the stored value. Insert walks down consuming labels. It meets one of three cases: no edge starts with the next character, so a leaf is attached with the whole remaining suffix; the edge label is fully a prefix of the remaining key, so it descends; or the label and the key diverge partway, so the edge is split at the divergence point by inserting a new middle node.

class Node:
    __slots__ = ("children", "value", "is_key")
    def __init__(self):
        self.children = {}      # first char of edge label -> (label, Node)
        self.value = None
        self.is_key = False

def common_prefix_len(a, b):
    n, i = min(len(a), len(b)), 0
    while i < n and a[i] == b[i]:
        i += 1
    return i

class RadixTree:
    def __init__(self):
        self.root, self.size = Node(), 0

    def insert(self, key, value=None):
        node, i = self.root, 0
        while i < len(key):
            edge = node.children.get(key[i])
            if edge is None:                       # case 1: attach a leaf
                leaf = Node()
                leaf.is_key, leaf.value = True, value
                node.children[key[i]] = (key[i:], leaf)
                self.size += 1
                return
            label, child = edge
            k = common_prefix_len(label, key[i:])
            if k == len(label):                    # case 2: consume the edge
                node, i = child, i + k
                continue
            mid = Node()                           # case 3: split the edge at k
            mid.children[label[k]] = (label[k:], child)
            node.children[key[i]] = (label[:k], mid)
            node, i = mid, i + k
        if not node.is_key:
            self.size += 1
        node.is_key, node.value = True, value

    def _find(self, key):
        node, i = self.root, 0
        while i < len(key):
            edge = node.children.get(key[i])
            if edge is None or not key.startswith(edge[0], i):
                return None
            i, node = i + len(edge[0]), edge[1]
        return node

    def get(self, key, default=None):
        node = self._find(key)
        return node.value if node is not None and node.is_key else default

Notice that case 3 does not finish the insert: after the split, the loop continues from the middle node. If the key ends exactly at the split point, the middle node becomes the key; otherwise the next iteration attaches the rest of the key as a second child. Inserting romanus into a tree holding only romane splits the edge romane at index 5 into roman, then attaches e and us below it.

Prefix search and longest-prefix match

Prefix enumeration walks down until the query prefix is exhausted, which may happen in the middle of an edge, then traverses the subtree. Longest-prefix match walks down the text and remembers the last key-ending node passed, the operation routers perform for every packet.

    def items_with_prefix(self, prefix):
        node, i, acc = self.root, 0, ""
        while i < len(prefix):
            edge = node.children.get(prefix[i])
            if edge is None:
                return
            label, child = edge
            rest = prefix[i:]
            if label.startswith(rest):             # prefix ends inside this edge
                acc, node, i = acc + label, child, len(prefix)
                break
            if not rest.startswith(label):
                return
            acc, node, i = acc + label, child, i + len(label)
        stack = [(node, acc)]
        while stack:                               # sorted order: push in reverse
            n, s = stack.pop()
            if n.is_key:
                yield s, n.value
            for label, child in sorted(n.children.values(), key=lambda e: e[0], reverse=True):
                stack.append((child, s + label))

    def longest_prefix(self, text):
        node, i = self.root, 0
        best = ("", node.value) if node.is_key else None
        while i < len(text):
            edge = node.children.get(text[i])
            if edge is None or not text.startswith(edge[0], i):
                break
            i, node = i + len(edge[0]), edge[1]
            if node.is_key:
                best = (text[:i], node.value)
        return best

Delete and merge

Deletion must restore the invariant. Clearing the key flag can leave a node that ends no key and has fewer than two children. A leaf is removed outright, which may leave its parent as a one-child pass-through; a node with a single remaining child is merged with that child by concatenating labels. At most one merge is needed per delete, because only the deleted node and its parent can change shape.

    def delete(self, key):
        path, node, i = [], self.root, 0           # (parent, first_char) per edge
        while i < len(key):
            edge = node.children.get(key[i])
            if edge is None or not key.startswith(edge[0], i):
                return False
            path.append((node, key[i]))
            i, node = i + len(edge[0]), edge[1]
        if not node.is_key:
            return False
        node.is_key, node.value = False, None
        self.size -= 1
        if path:
            parent, c = path[-1]
            if not node.children:                  # leaf: drop the edge
                del parent.children[c]
                if len(path) > 1:                  # parent may be a pass-through now
                    self._merge(*path[-2])
            elif len(node.children) == 1:          # one child: merge it upward
                self._merge(parent, c)
        return True

    def _merge(self, parent, c):
        label, child = parent.children[c]
        if child.is_key or len(child.children) != 1:
            return
        (sub, grandchild), = child.children.values()
        parent.children[c] = (label + sub, grandchild)

This listing was fuzz-tested against a Python dictionary: thousands of random insert, delete and lookup sequences, checking every query result and the invariant after each step. Do the same for any variant you write; edge splitting and merging are where off-by-one errors live.

Worked example: a routing table

A routing table maps bit-string prefixes to next hops. Store 10 to hop A, 1011 to hop B and 101101 to hop C. The tree has a root, an edge 10 to a key node A, an edge 11 to a key node B, and an edge 01 to a key node C. Looking up the address 10110011 descends 10 (A is a candidate), then 11 (B replaces it), then tries the edge 01 against the remaining 0011 and fails on the second bit. The answer is B, the longest stored prefix. Address 1011010 reaches C. Address 10111111 also returns B: the walk stops at the child keyed 1 because no edge starts with it under B.

Production routers use the bit-level form with stride tricks, such as multibit nodes or level compression, to cut the number of memory accesses per lookup, since a lookup that touches 20 nodes is 20 potential cache misses.

Complexity and memory layout

Lookup, insert and delete take O(k) character comparisons for a key of length k, independent of n, plus the cost of finding the child at each node. Depth is at most min(k, n). Space is O(n) nodes, but the labels add up to the total length of the distinct suffixes, so production implementations avoid copying strings: an edge stores an offset and length into a stored key, or the node stores a small inline prefix as Redis rax and ART-style trees do.

The child map dominates constants. A dictionary per node is flexible but heavy; a sorted small array with linear or binary search suits sparse nodes; a 256-entry array suits dense ones. The Adaptive Radix Tree of Leis, Kemper and Neumann (ICDE 2013) switches between node types sized for 4, 16, 48 and 256 children as a node fills, which made radix trees competitive with hash tables as in-memory database indexes. For disk-resident ordered indexes, B-trees remain the usual choice.

Where radix trees run

Since Linux 4.20 the kernel's radix tree API has been implemented on top of the XArray, which indexes page-cache pages by file offset. Redis implements a radix tree called rax, which backs Streams. HTTP routers such as Go's httprouter match paths against a radix tree, giving lookup cost proportional to path length rather than route count. Ethereum's state is stored in a modified Merkle Patricia trie whose nodes are hashed so the root commits to the whole state.

LLM serving uses the same structure over tokens. SGLang's RadixAttention keeps cached attention keys and values in a radix tree keyed by token sequences: a new request walks the tree to find the longest cached prefix, reuses those KV blocks, and only computes the rest. Edge splits happen when two prompts diverge mid-edge, and eviction removes least recently used leaves, which is the delete-and-merge logic above at GPU memory scale; see prefix caching on GPUs. Suffix trees are radix trees over all suffixes of a text; the suffix tree deep dive covers their linear-time construction.

Pitfalls

Trade-offs

Choose a radix tree when you need prefix queries, ordered iteration or longest-prefix matching on keys that share long prefixes. Choose a hash map when you only need exact lookups: it is simpler, and the per-node pointer chasing of any trie costs cache misses. Choose a sorted array or B-tree when the data is mostly static or disk-resident. The radix tree's weak spot is random, high-entropy keys, where compression saves little and the branching nodes add overhead.

What to do next

1. Implement the listing above and fuzz it against a dictionary, including the invariant check.
2. Replace per-node dictionaries with sorted arrays and measure the memory change.
3. Switch labels to (offset, length) references into stored keys.
4. Build a bit-level longest-prefix-match table for a few IPv4 prefixes and test edge cases such as the default route.
5. Read how ART adapts node sizes, and how SGLang evicts KV-cache leaves.
6. Profile against a hash map on your real keys before adopting either.