Adaptive radix trees: grow byte-edge nodes as incident codes branch

Last updated: 5 Oct 20269 min read

tutorial

An adaptive radix tree indexes byte-string keys by common prefixes and grows a node's child representation as its fanout rises. This model stores a compressed prefix in each node, then uses Node4 or Node16 parallel label and child arrays, a Node48 label-to-child-position array, or a direct Node256 child array. A new key can split an existing compressed prefix at the first mismatching byte, creating a parent for the common run and two separate branches. A value may live at an internal node when one complete code prefixes longer codes. Promotion changes only the local child representation; it must preserve every outgoing byte and child. The program supports insertion with replacement and exact lookup of byte strings. It does not delete keys, shrink tiers, or persist nodes to disk. Python objects make this an operation model, not a measured compact-memory implementation.

Operational case

Nineteen codes start with rack and end in distinct byte values from zero through eighteen. Their shared rack prefix lives across the root edge r and a compressed ack run. The ack node has nineteen children, so it has promoted past Node4 and Node16 into the Node48 representation. A value of 83 is then stored on the shorter key rack, while rack followed by byte eighteen returns 4718; byte nineteen is absent. Splitting rack from a longer code must preserve the existing children. An empty byte string is also a valid key in this implementation, and zero is a valid stored value; a missing lookup is represented by None, so callers should avoid using None as a meaningful value.

Working Python program

class RadixNode:
    def __init__(self, prefix=b"", value=None):
        self.prefix = prefix
        self.value = value
        self.tier = 4
        self.labels = []
        self.children = []
        self.index = None
        self.count = 0

    def items(self):
        if self.tier <= 16:
            return list(zip(self.labels, self.children))
        if self.tier == 48:
            return [(label, self.children[position]) for label, position in enumerate(self.index)
                    if position != -1]
        return [(label, child) for label, child in enumerate(self.children) if child is not None]

    def get(self, label):
        if self.tier <= 16:
            return self.children[self.labels.index(label)] if label in self.labels else None
        if self.tier == 48:
            position = self.index[label]
            return None if position == -1 else self.children[position]
        return self.children[label]

    def put(self, label, child):
        if self.get(label) is not None:
            if self.tier <= 16:
                self.children[self.labels.index(label)] = child
            elif self.tier == 48:
                self.children[self.index[label]] = child
            else:
                self.children[label] = child
            return
        if self.count == self.tier and self.tier < 256:
            old = self.items()
            self.tier = {4: 16, 16: 48, 48: 256}[self.tier]
            self.labels = []
            self.children = [] if self.tier < 256 else [None] * 256
            self.index = [-1] * 256 if self.tier == 48 else None
            self.count = 0
            for old_label, old_child in old:
                self.put(old_label, old_child)
        if self.tier <= 16:
            self.labels.append(label)
            self.children.append(child)
        elif self.tier == 48:
            self.index[label] = len(self.children)
            self.children.append(child)
        else:
            self.children[label] = child
        self.count += 1


class AdaptiveIncidentCodes:
    def __init__(self):
        self.root = RadixNode()

    def insert(self, code, incident_id):
        if not isinstance(code, bytes):
            raise TypeError("incident code must be bytes")

        def place(node, suffix):
            common = 0
            while common < min(len(node.prefix), len(suffix)) and node.prefix[common] == suffix[common]:
                common += 1
            if common < len(node.prefix):
                parent = RadixNode(node.prefix[:common])
                old_label = node.prefix[common]
                node.prefix = node.prefix[common + 1:]
                parent.put(old_label, node)
                if common == len(suffix):
                    parent.value = incident_id
                else:
                    parent.put(suffix[common], RadixNode(suffix[common + 1:], incident_id))
                return parent
            suffix = suffix[common:]
            if not suffix:
                node.value = incident_id
            else:
                label = suffix[0]
                child = node.get(label)
                node.put(label, RadixNode(suffix[1:], incident_id) if child is None
                         else place(child, suffix[1:]))
            return node

        self.root = place(self.root, code)

    def lookup(self, code):
        if not isinstance(code, bytes):
            raise TypeError("incident code must be bytes")
        node, suffix = self.root, code
        while node is not None:
            if not suffix.startswith(node.prefix):
                return None
            suffix = suffix[len(node.prefix):]
            if not suffix:
                return node.value
            node = node.get(suffix[0])
            suffix = suffix[1:]
        return None


if __name__ == "__main__":
    index = AdaptiveIncidentCodes()
    for number in range(19):
        index.insert(b"rack" + bytes([number]), 4700 + number)
    index.insert(b"rack", 83)
    print(index.lookup(b"rack"), index.lookup(b"rack\x12"), index.lookup(b"rack\x13"))
    rack_node = index.root.get(ord("r"))
    print(rack_node.prefix, rack_node.tier, rack_node.count)

Output

83 4718 None
b'ack' 48 19

Time, space, and tradeoff

For a key of L bytes, traversal compares at most L prefix bytes and performs one child lookup per branch, giving O(L) time with a fixed 256-byte alphabet. Node4 and Node16 linearly scan at most their tier capacities; Node48 and Node256 use indexed access. A promotion copies the node's current children and allocates its new representation, bounded by 256 slots but visible as a single-operation cost. Storage is O(S + N) for S retained key-prefix bytes and N nodes in this Python model, with substantial list and object overhead. Prefix splitting copies byte substrings. Unlike the prior static double-array trie, this one accepts new keys without rebuilding the whole dictionary, but lookup order and node identity are not stable after edits.

Common Mistakes

Do not discard the old child when splitting a compressed prefix.
Do not confuse a prefix node's stored value with all descendant values.
Do not call Python list tiers a verified compact native layout.
Do not promise deletion or tier shrinkage that the model does not implement.

Connected lessons

Compare this operation boundary with Bit-sliced indexes: filter and sum fixed-width sensor readings, SimHash bands: find near-duplicate incident fingerprints, Minimal acyclic dictionaries: merge equivalent word suffix states, then complete the audit project and decision quiz.

data structures

range-query-structures