Y-Fast Trie, in depth: predecessor search in O(log log u) with linear space, built from the x-fast trie and measured

The predecessor problem and the bounds to beat

Predecessor search is the core of many lookups: which interval does a timestamp fall into, which routing prefix covers an address, which shard owns a key range, what is the next scheduled event. Sorting-based structures solve it in O(log n) comparisons. When keys are integers, you can do better by treating a key as a string of w bits and searching on its bits instead of comparing whole keys.

The word expected matters: both tries rely on hash tables, so their bounds hold in expectation over the hash function, and the y-fast update bound is amortised as well.

Step one: the x-fast trie

Picture the binary trie of all w-bit keys: the root is the empty prefix, each level adds one bit, and the leaves are the keys. An x-fast trie stores only the prefixes that actually occur, with one hash table per level mapping each present prefix to the smallest and largest key below it. The leaves are also linked in sorted order.

The key observation is monotonicity: if a prefix of x of length k is present, every shorter prefix is present too. So the length of the longest present prefix of x can be found by binary search over levels, with one hash lookup per probe: O(log w) probes. Once that node is found, x's path leaves the trie there, so every key below the node lies entirely on one side of x. If x would branch right, all of them are smaller and the node's maximum is the predecessor. If x would branch left, all of them are larger, the node's minimum is the successor, and one step back in the leaf list gives the predecessor.

Worked example. Take w = 4 and keys {2, 5, 9, 12}, that is 0010, 0101, 1001 and 1100. Query x = 7 (0111). The binary search probes length 2: prefix 01 is present (key 5 lives there), so go longer. It probes length 3: prefix 011 is absent, so the longest present prefix is 01. The next bit of x is 1, so x branches right of everything under 01, and the predecessor is that node's maximum, 5. Now query x = 8 (1000). Prefixes 1, 10 and 100 are present (each contains 9), 1000 is not. The next bit of x is 0, so everything under 100 is larger; the node's minimum is 9 and one step back in the leaf list gives 5. Two or three hash probes, no key comparisons along a path.

The weakness is updates and space. Inserting a key touches all w + 1 levels, and a set of n keys can occupy up to n(w + 1) table entries.

Step two: indirection through buckets

The y-fast trie fixes both problems with indirection. Split the sorted keys into buckets of Θ(w) consecutive keys. Store each bucket in a balanced binary search tree, and store one separator per bucket in an x-fast trie. There are about n/w separators, so the x-fast trie now costs O(n/w × w) = O(n) space, and the buckets hold n keys in total.

A query finds the right separator in the x-fast trie in O(log w), then searches a bucket of size O(w) in O(log w). An insert finds its bucket the same way and inserts into the tree in O(log w). Only when a bucket grows past 2w does it split, which adds one separator to the x-fast trie at O(w) cost. Because a freshly split bucket needs Θ(w) more inserts before it can split again, that cost amortises to O(1) per insert. Deletes are symmetric: a bucket that shrinks below w/4 merges into its neighbour and removes one separator, re-splitting if the merged bucket is too large.

The implementation below uses separators rather than bucket minimums. A separator r owns the keys in [r, next separator). A sentinel separator at 0 means every key has a bucket, separators never change when keys are deleted, and a query needs to look at no more than two buckets: the bucket of r = pred(x), and, if every key there exceeds x, the maximum of the bucket before it.

A tested implementation

Sorted Python lists stand in for the balanced bucket trees to keep the code short. They make bucket inserts O(w) rather than O(log w), which does not change correctness or the number of x-fast updates; swap in a treap or red-black tree for the real bound.

from bisect import bisect_right

class XFastTrie:
    def __init__(self, w):
        self.w = w
        self.levels = [dict() for _ in range(w + 1)]   # prefix -> (min, max) below it
        self.prv, self.nxt = {}, {}                     # sorted leaf list

    def _lcp_level(self, x):            # longest present prefix: O(log w) probes
        lo, hi = 0, self.w
        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 pred(self, x):                  # largest key <= x, or None
        if not self.levels[0]:
            return None
        lv = self._lcp_level(x)
        if lv == self.w:
            return x
        mn, mx = self.levels[lv][x >> (self.w - lv)]
        if (x >> (self.w - lv - 1)) & 1:
            return mx                   # subtree lies left of x
        return self.prv.get(mn)         # subtree lies right of x

    def insert(self, x):
        if x in self.levels[self.w]:
            return
        p = self.pred(x)
        s = self.nxt[p] if p is not None else (
            self.levels[0][0][0] if self.levels[0] else None)
        self.prv[x], self.nxt[x] = p, s
        if p is not None: self.nxt[p] = x
        if s is not None: self.prv[s] = x
        for lv in range(self.w + 1):    # O(w) table updates
            key = x >> (self.w - lv)
            mn, mx = self.levels[lv].get(key, (x, x))
            self.levels[lv][key] = (min(mn, x), max(mx, x))

    def delete(self, x):
        if x not in self.levels[self.w]:
            return
        p, s = self.prv.pop(x), self.nxt.pop(x)
        for lv in range(self.w + 1):
            key = x >> (self.w - lv)
            mn, mx = self.levels[lv][key]
            if mn == mx:
                del self.levels[lv][key]
            else:
                self.levels[lv][key] = (s if mn == x else mn, p if mx == x else mx)
        if p is not None: self.nxt[p] = s
        if s is not None: self.prv[s] = p

class YFastTrie:
    def __init__(self, w):
        self.w, self.top = w, XFastTrie(w)
        self.top.insert(0)              # sentinel separator
        self.buckets = {0: []}

    def pred(self, x):
        r = self.top.pred(x)
        b = self.buckets[r]
        i = bisect_right(b, x)
        if i:
            return b[i - 1]
        if r == 0:
            return None
        prev = self.buckets[self.top.pred(r - 1)]
        return prev[-1] if prev else None

    def insert(self, x):
        b = self.buckets[self.top.pred(x)]
        i = bisect_right(b, x)
        if i and b[i - 1] == x:
            return
        b.insert(i, x)
        if len(b) > 2 * self.w:
            self._split(b)

    def delete(self, x):
        r = self.top.pred(x)
        b = self.buckets[r]
        i = bisect_right(b, x)
        if not (i and b[i - 1] == x):
            return
        del b[i - 1]
        if r != 0 and len(b) < self.w // 4:
            left = self.buckets[self.top.pred(r - 1)]
            left.extend(self.buckets.pop(r))    # all left keys < r <= these keys
            self.top.delete(r)
            if len(left) > 2 * self.w:
                self._split(left)

    def _split(self, b):
        m = b[len(b) // 2]              # new separator: an existing key
        self.buckets[m] = b[len(b) // 2:]
        del b[len(b) // 2:]
        self.top.insert(m)

Both classes were checked against a sorted list with bisect over 300 random sequences of inserts, deletes and queries at w between 4 and 12, and 200 delete-heavy runs at w = 16 that force merges. Every answer matched.

Measured run: 100,000 keys

Inserting 100,000 distinct random 32-bit keys into the y-fast trie caused 2,253 bucket splits, leaving 2,254 buckets and 51,290 entries across the x-fast level tables. Inserting the same keys into a plain x-fast trie produced 1,650,497 entries, about 32 times more: that is the O(n w) versus O(n) difference made concrete. Only 2.3 percent of inserts touched the x-fast trie at all.

Deleting 95,000 of those keys caused 1,886 merges and left 368 buckets. The non-sentinel buckets then held between 8 and 30 keys, inside the w/4 to 2w band, and 20,000 random predecessor queries on the 5,000 survivors all matched the reference.

Where it sits in practice and theory

The y-fast trie is a theoretical landmark more than a production workhorse. Each hash probe is likely a cache miss, and a query makes about log w of them plus a tree search, while a B-tree over a million keys visits three or four nodes and does its comparisons inside them. For in-memory sets of ordinary size, a B-tree, a sorted array with binary search, or a radix tree usually wins on wall-clock time.

The ideas travel further than the structure. Binary search on prefix length with one hash table per length is the basis of a well-known IP routing lookup scheme by Waldvogel and colleagues (SIGCOMM 1997). Bucketing to cut the cost of an expensive top structure is the same move used in many succinct and external-memory designs. On the theory side, fusion trees achieve O(log n / log w), and Pătraşcu and Thorup showed that the best possible predecessor bound depends on n, w and space together, with van Emde Boas-style bounds optimal in part of that range.

Failure modes

• Adversarial keys and weak hashing. The level tables are hash tables. A predictable hash lets an attacker who chooses keys force collisions and destroy the expected bounds; use a seeded hash when keys come from outside.
• Keys outside the universe. A key with more than w bits silently aliases another prefix. Validate the range on insert.
• Signed integers. Two's-complement order differs from unsigned order. Flip the sign bit on the way in and out.
• Merge without a guard. Merging a small bucket into a large neighbour can create a bucket far above 2w; re-split after merging, as the code does.
• Constant factors in high-level languages. In Python each table entry is a dictionary slot with boxed integers, so the memory advantage holds in ratio but absolute memory is large.

Operational guidance

• Benchmark against a sorted array and a B-tree at your real n and key width before adopting it; the asymptotic win needs large n and large w to show.
• Size buckets around w and measure: larger buckets mean fewer separators and slower bucket searches.
• Track splits and merges per thousand updates; a sudden rise signals a change in the key distribution or churn pattern.
• Keep successor queries symmetric to predecessor; most bugs live in the asymmetric boundary cases (first bucket, empty sentinel).

Trade-offs

Choose a y-fast trie when keys are integers from a large universe, n is large, predecessor queries dominate, and you need linear space with doubly logarithmic query time in theory. Choose a van Emde Boas tree for small universes where O(u) space is fine and worst-case rather than expected bounds matter. Choose a B-tree or sorted array when cache behaviour dominates, which on real hardware is most of the time. Choose a radix tree when keys share long prefixes and you also need ordered iteration with cheap updates.

What to do next

1. Run the code above against bisect on your own key distribution, then count splits and table entries as in the measured run.
2. Replace the bucket lists with a treap and confirm the update cost per operation.
3. Read the van Emde Boas tree deep dive to see the same log log u bound reached by recursion instead of hashing.
4. Compare with a B-tree and a radix tree on wall-clock query time at 10 million keys.
5. Review how the level tables would behave under hostile input with the hash table guide.