X-Fast Trie, in depth: binary search on prefix length, descendant pointers, a tested implementation and the space it really costs

The structure: level tables, leaf list and descendant pointers

Start from the complete binary trie over w-bit keys: the root is the empty prefix, a node at depth d is a d-bit prefix, and its children append a 0 or a 1. The x-fast trie stores only the nodes that lie on the path of some present key, and it stores them in w + 1 hash tables, one per depth, keyed by the prefix value. Three more ingredients complete it.

• Leaf list. The leaves (the keys themselves, at depth w) are threaded into a sorted doubly linked list, so once you have one neighbour of x the other is one pointer away.
• Child flags. Each internal node records which of its two children exist.
• Descendant pointers. A node with only a left child points to the largest leaf in its subtree; a node with only a right child points to the smallest. A node with both children needs no pointer.

The figure shows the trie for u = 16 and keys {2, 5, 6, 13}. The node 1 has only a right child, so its pointer goes to 13, the smallest key beginning with 1. The node 00 has only a right child, so its pointer goes to 2. Only 4 + 4 + 3 + 2 + 1 = 14 of the 31 possible nodes exist.

Why binary search on length works

The key property is prefix closure: if a prefix of length d is present, every shorter prefix of it is present too, because a node exists only if some key passes through it. So for a query x, the predicate "the length-d prefix of x is in table d" is true for d = 0, stays true up to some depth D, and is false beyond it. A monotone predicate over 0..w can be binary-searched in about log2(w + 1) probes. That finds D, the depth at which x leaves the trie.

If D = w, x is a key. Otherwise the node at depth D has no child in x's direction, by the definition of D, but it has at least one child, so it has exactly one and its descendant pointer is set. If x would have gone right, the existing subtree is on the left and the pointer is its maximum, which is pred(x). If x would have gone left, the pointer is the minimum of the right subtree, which is succ(x), and the predecessor is one step back along the leaf list. Either way, one comparison and at most one list step finish the query.

Worked example: pred(11) with 11 = 1011. The search starts with lo = 0, hi = 4. It probes depth 2, prefix 10, which is absent, so hi = 1. It probes depth 1, prefix 1, which is present, so lo = 1 and the search stops after two probes. Node 1 points at 13, which is greater than 11, so the answer is 13's list predecessor, 6. The same walk gives succ(11) = 13.

A tested implementation: queries

class Leaf:
    __slots__ = ("key", "prev", "next")
    def __init__(self, key):
        self.key, self.prev, self.next = key, None, None

class Node:
    __slots__ = ("left", "right", "desc")
    def __init__(self):
        self.left = self.right = False
        self.desc = None                      # set only when exactly one child exists

class XFastTrie:
    def __init__(self, w):
        self.w = w
        self.levels = [dict() for _ in range(w + 1)]   # levels[w] maps key -> Leaf

    def _deepest(self, x):
        lo, hi = 0, self.w                    # prefix of length lo is present
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if (x >> (self.w - mid)) in self.levels[mid]:
                lo = mid
            else:
                hi = mid - 1
        return lo

    def predecessor(self, x):                 # largest key <= x, or None
        if not self.levels[0]:
            return None
        d = self._deepest(x)
        if d == self.w:
            return x
        leaf = self.levels[d][x >> (self.w - d)].desc
        if leaf.key > x:
            leaf = leaf.prev
        return leaf.key if leaf else None

    def successor(self, x):                   # smallest key >= x, or None
        if not self.levels[0]:
            return None
        d = self._deepest(x)
        if d == self.w:
            return x
        leaf = self.levels[d][x >> (self.w - d)].desc
        if leaf.key < x:
            leaf = leaf.next
        return leaf.key if leaf else None

Insert and delete: maintaining the pointers

Insertion first finds the neighbours with two queries, splices the new leaf into the list, and then walks the path bottom-up, creating missing nodes, setting the child flag on each, and fixing descendant pointers. A node that now has both children drops its pointer. A node with only a left subtree keeps the larger of its old pointer and the new leaf; a node with only a right subtree keeps the smaller.

    def insert(self, x):
        w, L = self.w, self.levels
        if x in L[w]:
            return
        leaf = Leaf(x)
        p, s = self.predecessor(x), self.successor(x)
        leaf.prev = L[w][p] if p is not None else None
        leaf.next = L[w][s] if s is not None else None
        if leaf.prev: leaf.prev.next = leaf
        if leaf.next: leaf.next.prev = leaf
        L[w][x] = leaf
        for d in range(w - 1, -1, -1):
            pre, bit = x >> (w - d), (x >> (w - d - 1)) & 1
            node = L[d].setdefault(pre, Node())
            if bit: node.right = True
            else:   node.left = True
            if node.left and node.right:
                node.desc = None
            elif node.left:                   # max of the left subtree
                if node.desc is None or node.desc.key < x: node.desc = leaf
            else:                             # min of the right subtree
                if node.desc is None or node.desc.key > x: node.desc = leaf

    def delete(self, x):
        w, L = self.w, self.levels
        leaf = L[w].pop(x, None)
        if leaf is None:
            return
        pl, sl = leaf.prev, leaf.next
        if pl: pl.next = sl
        if sl: sl.prev = pl
        child_gone = True
        for d in range(w - 1, -1, -1):
            pre, bit = x >> (w - d), (x >> (w - d - 1)) & 1
            node = L[d][pre]
            if child_gone:
                if bit: node.right = False
                else:   node.left = False
            if not (node.left or node.right):
                del L[d][pre]                 # keep the tables prefix closed
                continue
            child_gone = False
            if node.left and node.right:
                node.desc = None
            elif node.left and (node.desc is None or node.desc is leaf):
                node.desc = pl                # new max of the left subtree
            elif node.right and (node.desc is None or node.desc is leaf):
                node.desc = sl                # new min of the right subtree

Deletion is the mirror image. The subtle step is choosing the replacement pointer. If the deleted leaf was the maximum of a node's left subtree and that subtree is not empty, its new maximum is the deleted key's list predecessor: everything between them would have to live in the same subtree. The same argument gives the successor for right subtrees, and it also covers a node that just lost its whole right child and now has only a left one. Both operations touch w tables, so they cost O(w) expected time; the two neighbour queries add O(log w).

This code was tested against Python's bisect on 400 random tries with w from 1 to 16, including the keys 0 and u - 1 and the empty trie, checking predecessor and successor after every insert and after interleaved deletes. A structural check also confirmed that every one-child node's pointer is the true maximum or minimum of its subtree.

Measured probes and the space bill

Prefix closure is also what costs memory. Each key contributes up to w + 1 entries, shared only where keys share prefixes. With random keys, the top levels are shared and the bottom ones are private, so the count is roughly n * (w - log2 n) plus a little. A measured run with w = 32 and 100,000 random keys (seed 42) gave:

Scale that to 64-bit keys and a million of them and the estimate is about 45 entries per key, 45 million in total. With a general-purpose hash map, where an entry often costs a few tens of bytes once pointers and load-factor slack are counted, that is gigabytes to index eight megabytes of keys. The y-fast trie exists to fix exactly this: it puts only one representative per bucket of about w keys into the x-fast trie, bringing space down to O(n).

Hashing, hardware and a networking cousin

The O(log log u) bound counts hash probes, and each probe on a large trie is typically a cache miss into a different table. Seven dependent cache misses is not obviously faster than a B-tree whose upper levels stay in cache, and Python timings say nothing about either, so none are quoted here. The x-fast trie wins when the universe is bounded, the workload is query-heavy, and the key count is large enough that log n clearly exceeds log w.

The hash tables decide the guarantees. With ordinary chaining or open addressing the query bound is expected time. With a worst-case constant lookup structure such as cuckoo hashing or dynamic perfect hashing, queries become worst-case O(log w) while updates stay expected or amortized. For a static key set, building every level with a perfect hash gives compact tables with no collision handling.

The same idea appears in IP routing. Waldvogel, Varghese, Turner and Plattner's SIGCOMM 1997 paper on scalable lookups keeps one hash table per prefix length and binary-searches over lengths to find the longest matching prefix. A routing table is not prefix closed, though: a /24 route does not imply a /16 one. Their fix is markers, extra entries inserted on the search path so that the monotone predicate holds again, each carrying the best matching real prefix so far. Seeing why markers are needed there is the clearest way to see why the x-fast trie needs none.

For the fully deterministic alternative with the same bound, compare the van Emde Boas tree, which recurses on the square root of the universe instead of hashing prefixes. For string keys with no fixed width, an ordinary trie is the better starting point.

Failure modes

• Stale nodes after delete. Leaving an empty node in its table breaks prefix closure in the other direction: the binary search believes x continues deeper than it does and lands on a node with no children and no pointer.
• Stale descendant pointers. A pointer to a deleted leaf returns a key that no longer exists. The structural check above is cheap to run in tests.
• Off-by-one on the search bounds. The invariant is that depth lo is present; mid must round up, or the loop never ends when hi = lo + 1.
• Keys outside the universe. A key of u or more, or a negative number in a language with arithmetic shifts, produces prefixes that collide with real ones. Validate on insert and on query.
• Empty trie. With no keys the root is absent and every query must return none before any lookup.
• Memory surprise. Capacity plans that budget n entries instead of about n * (w - log2 n) run out of memory long before they run out of keys.

Trade-offs

What to do next

1. Implement the trie above and test it against bisect with keys 0 and u - 1, single-key tries and interleaved deletes.
2. Add the structural check for descendant pointers and run it after every update in tests.
3. Count hash probes per query for w = 16, 32 and 64 and confirm they track log2(w + 1).
4. Measure table entries for your real key distribution; clustered keys share far more prefixes than random ones.
5. Swap the per-level dictionaries for a worst-case structure and note which bounds change.
6. Build the y-fast trie on top and compare memory for the same key set.
7. Benchmark against a sorted array and a B-tree in a compiled language before choosing it for production.