Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Patricia binary routing: compress chains without losing prefix matches

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A Patricia-style binary routing trie stores only branching and route-bearing prefixes rather than one node for every address bit. Each node holds the full bit prefix it represents, an optional destination, and up to two children keyed by the next bit. Insertion compares a new network prefix against a child edge and splits that edge at the first differing bit or where the new prefix ends. A lookup follows only edges whose complete compressed span matches the address, retaining the last destination seen. That last stored route is the longest matching prefix. Prefix bits are compared, not just numeric network values, because two routes with the same initial bits may diverge within a compressed edge. This example fixes addresses at eight bits and supports insertion and destination replacement, not deletion or address-family expansion.

Operational case

Insert a default route, then prefixes 176/5 and 184/5, followed by their shorter regional ancestor 160/3. The late ancestor insertion splits an existing compressed path and preserves both longer routes. Address 178 selects north-depot, 190 selects south-depot, 171 selects regional-gateway, and 132 falls through to default-gateway. Replacing 176/5 with north-backup changes only addresses with that longest match. The actual prefix represented by 176/5 is its first five bits, so low bits of the network argument do not identify a separate route at that prefix length.

Working Python program

python
class RouteNode:
    def __init__(self, prefix, destination=None):
        self.prefix = prefix
        self.destination = destination
        self.children = {}


class PatriciaRouteIndex:
    def __init__(self, width=8):
        if width < 1:
            raise ValueError("positive bit width required")
        self.width = width
        self.root = RouteNode("")

    def _bits(self, address):
        if not 0 <= address < 1 << self.width:
            raise ValueError("address outside configured width")
        return format(address, f"0{self.width}b")

    def insert(self, network, prefix_length, destination):
        if not 0 <= prefix_length <= self.width:
            raise ValueError("invalid prefix length")
        target = self._bits(network)[:prefix_length]
        node = self.root
        while True:
            if node.prefix == target:
                node.destination = destination
                return
            branch = target[len(node.prefix)]
            child = node.children.get(branch)
            if child is None:
                node.children[branch] = RouteNode(target, destination)
                return
            common = len(node.prefix)
            while common < min(len(child.prefix), len(target)) and child.prefix[common] == target[common]:
                common += 1
            if common == len(child.prefix):
                node = child
                continue
            split = RouteNode(target[:common])
            node.children[branch] = split
            split.children[child.prefix[common]] = child
            if common == len(target):
                split.destination = destination
            else:
                split.children[target[common]] = RouteNode(target, destination)
            return

    def longest_match(self, address):
        bits = self._bits(address)
        node = self.root
        answer = node.destination
        while len(node.prefix) < self.width:
            child = node.children.get(bits[len(node.prefix)])
            if child is None or bits[len(node.prefix):len(child.prefix)] != child.prefix[len(node.prefix):]:
                break
            node = child
            if node.destination is not None:
                answer = node.destination
        return answer


routes = PatriciaRouteIndex()
routes.insert(0, 0, "default-gateway")
routes.insert(176, 5, "north-depot")
routes.insert(184, 5, "south-depot")
routes.insert(160, 3, "regional-gateway")
print(routes.longest_match(178), routes.longest_match(190))
print(routes.longest_match(171), routes.longest_match(132))
routes.insert(176, 5, "north-backup")
print(routes.longest_match(178))

Output

Output
north-depot south-depot
regional-gateway default-gateway
north-backup

Time, space, and tradeoff

With width W bits, insertion and lookup compare at most W bit positions across the traversed compressed edges, taking O(W) time in this string-based model. A newly inserted route adds at most one leaf and one split node; stored full-prefix strings can cost O(PW) total characters for P routes, while the node count is O(P). A full binary radix trie may spend a node per traversed bit and can be simpler to update. Here compression helps sparse routing tables but does not provide deletion, concurrent publication, or a real packet-forwarding benchmark. The eight-bit example is a correctness model, not a network stack.

Common Mistakes

  • Do not match a child after only its first branch bit; check its whole compressed span.
  • Do not overwrite a longer route when inserting a shorter ancestor.
  • Do not return the deepest visited node unless it actually stores a destination.
  • Do not treat an eight-bit demonstration as an IPv4 or IPv6 implementation.

Connected lessons

Compare this operation boundary with Persistent subarray ranks: subtract prefix frequency trees, Maximum-subarray segment trees: preserve the crossing burst, Li Chao interval offers: limit each line to its valid minutes, All-one frequency buckets: increment, decrement, and read both extremes, then complete the audit project and decision quiz.

data structures
range-query-structures
Storage details