Y-Fast Tries

Suppose you have a sorted set of integers, all drawn from the universe $\{0, 1, \ldots, U-1\}$, and you want to answer predecessor queries: given a key $x$, find the largest stored integer that is $\leq x$.

A balanced binary search tree does this in $O(\log n)$ time. A van Emde Boas tree does it in $O(\log \log U)$ — doubly-logarithmic — but it needs $O(U)$ space, which is ruinous when $U = 2^{64}$.

In 1983, Dan Willard invented the y-fast trie, which achieves both goals at once: predecessor in $O(\log \log U)$ time and $O(n)$ space — linear in the number of stored elements, not the universe size. It is van Emde Boas speed without the astronomical memory price.

The trick is a two-layer design. The top layer is a compact x-fast trie that stores only $O(n / \log U)$ representative elements. The bottom layer holds $O(n)$ total elements spread across small balanced BSTs (one per representative). A query first locates the right cluster in $O(\log \log U)$, then searches within a cluster of size $O(\log U)$ in $O(\log \log U)$ — both layers contribute the same bound.

The demo below keeps a dynamic set of integers in the range $[0, 255]$ (so $U = 256$, $\log U = 8$, $\log \log U = 3$). Insert or delete values, then ask for the predecessor of any key.

<p class="hint">{{hint}}</p>
<div class="controls">
  <div class="row">
    <input id="valInput" type="number" min="0" max="255" placeholder="0–255" />
    <button id="btnInsert" type="button">{{btn_insert}}</button>
    <button id="btnDelete" type="button">{{btn_delete}}</button>
  </div>
  <div class="row">
    <input id="predInput" type="number" min="0" max="255" placeholder="{{placeholder_query}}" />
    <button id="btnPred" type="button">{{btn_pred}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="status" class="status"></div>
<div id="trace" class="trace"></div>
<div id="visual" class="visual"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; flex-direction: column; gap: .45rem; margin-bottom: .7rem; }
.row { display: flex; gap: .45rem; flex-wrap: wrap; align-items: center; }
input[type=number] { width: 90px; padding: .38rem .5rem; border: 1px solid #bbb;
  border-radius: 6px; font-size: 14px; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .8rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-weight: 600; font-size: .95rem; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.trace { font-size: .82rem; color: #555; background: #f4f6f8; border-radius: 6px;
         padding: .5rem .7rem; min-height: 2.4em; margin-bottom: .6rem;
         font-family: ui-monospace, monospace; line-height: 1.6; white-space: pre-wrap; }
.visual { display: flex; flex-direction: column; gap: .4rem; }
.cluster-row { display: flex; align-items: center; gap: .35rem; flex-wrap: wrap; }
.cluster-label { font-size: .75rem; color: #777; width: 54px; text-align: right;
                 font-family: ui-monospace, monospace; flex-shrink: 0; }
.chip { display: inline-flex; align-items: center; justify-content: center;
        width: 32px; height: 28px; border-radius: 5px; font: 600 12px ui-monospace, monospace;
        border: 1px solid #cdd9e3; background: #e8eef3; color: #1d3557; }
.chip.rep { border-color: #457b9d; background: #d0e4f0; }
.chip.hi { background: #e63946; border-color: #c92f3c; color: #fff; }
.chip.pred-chip { background: #2a9d8f; border-color: #1d7a6f; color: #fff; }
.empty-row { font-size: .8rem; color: #aaa; font-style: italic; margin-left: 60px; }

// Code not found

Notice how the search never scans the whole sorted list. It first narrows down to the right cluster using a hash-table lookup on the representative keys — that is the x-fast trie layer. Then it does a tiny local search within a cluster that holds at most $O(\log U) = 8$ elements. Compare that with a binary search over all $n$ elements: here the cluster size is bounded by a constant of the universe, not by $n$.

How do y-fast tries hit $O(\log \log U)$ with only $O(n)$ space? The proof uses two ingredients.

The x-fast trie (top layer). Store only $O(n / \log U)$ representative keys — one per cluster — in a hash table keyed on binary prefixes. A predecessor query on the representatives takes $O(\log \log U)$ time via binary search on the $O(\log U)$ levels of the trie, each level checked in $O(1)$ with a hash table. The total space for the representatives is $O(n / \log U \cdot \log U) = O(n)$.

The balanced BST clusters (bottom layer). Each cluster holds $\Theta(\log U)$ consecutive elements. There are $O(n / \log U)$ clusters, so the total number of elements across all clusters is $O(n)$. A predecessor within a cluster of size $\Theta(\log U)$ takes $O(\log \log U)$ time.

Insertions and deletions cost $O(\log \log U)$ amortized: when a cluster grows beyond $2 \log U$ elements, it splits; when it shrinks below $\frac{1}{2} \log U$, it merges with a neighbor. Split/merge cost $O(\log U)$ but happen so rarely that the amortized cost per operation is $O(\log \log U)$.

The lower bound. Any comparison-based structure on $n$ integers from a universe of size $U$ requires $\Omega(\log \log U)$ time per predecessor query in the worst case (proven by Fredman and Willard). So y-fast tries are optimal in this model.

This puts y-fast tries in a small club of data structures that are simultaneously time-optimal and space-optimal, beating the binary-search baseline of $O(\log n)$ whenever $\log n \gg \log \log U$ — which happens whenever $n \gg \log U$. For comparison, see sorting lower bounds and van Emde Boas / P vs NP for why such tight bounds matter.

The predecessor query is more fundamental than it first appears. Many real systems reduce to exactly this problem on large integer universes:

• IP routing: a router classifies packets by finding the longest-matching prefix in a 32- or 128-bit address space. Y-fast tries (and related structures) enable sub-microsecond lookup at line rate.
• Event-driven simulation: the next event to fire is the predecessor of "now" in a priority queue keyed by timestamp. O(log log U) extraction keeps simulation throughput high.
• Database range queries: B-trees answer range queries in $O(\log n + k)$. When keys are dense integers, a y-fast trie beats the $O(\log n)$ first step.
• Competitive programming: problems that require a dynamic sorted set on integers with large universe size ($2^{30}$ or more) often accept an $O(n \log \log U)$ solution where $O(n \log n)$ times out.
• Succinct data structures: the ideas behind y-fast tries — universe decomposition and clustered representation — appear in modern compressed indexes for genomic data and inverted indexes for search engines.

Whenever you have integers, a bounded universe, and repeated predecessor/successor queries, the y-fast trie is the go-to structure — the same ideas power the data structures inside every modern database and router.

Y-fast tries deliver a theorem that feels almost too good to be true: predecessor queries in $O(\log \log U)$ time using only $O(n)$ space — no compromise on either axis.

The key insight is separation of concerns: a tiny top layer of representatives handles universe navigation, while cheap bottom-layer clusters handle local search. Each layer does exactly what it is good at, and the costs multiply down to $O(\log \log U)$.

The next time you see a sorted set of integers and someone reaches for a balanced BST, remember Willard's 1983 result: if the universe is bounded, you can do doubly logarithmically better, and you don't have to pay a byte extra for it. See also sorting lower bounds for why no integer structure can do better.