Fusion Tree

Fusion tree is a trans-dichotomous word-RAM search tree data structure in computation and algorithms invented in 1990 (journal publication 1993) by Michael L. Fredman and Dan E. Willard. For decades prior to 1990, the information-theoretic comparison-based lower bound within computational complexity theory dictated that searching an ordered set of N items required Ω(log₂ N) comparisons and sorting required Ω(N log₂ N) comparisons—bounds achieved by balanced binary search trees (red–black tree, AA tree, scapegoat tree, splay tree) and standard B-trees.

Fredman and Willard shattered the comparison barrier on a standard w-bit word RAM (where each machine word holds w ≥ log₂ N bits and standard arithmetic, bitwise boolean, shift, and multiplication instructions execute in O(1) time). A fusion tree is a B-tree with branching factor B = Θ(w^1/5) in which every internal node compresses the distinguishing trie branching bits of all B child keys into a single w-bit machine word called a sketch node. Using word-level parallelism (SWAR / broadword techniques), a query key is compared against all B compressed sketches simultaneously in constant O(1) time, reducing tree height and search complexity to:

and yielding a deterministic integer sorting algorithm running in O(N log N / log log N) worst-case time.

Why Naive Word Packing Cannot Fit B Keys in One Word

Consider an internal B-tree node holding k = B − 1 sorted w-bit integer keys S = {x₁ < x₂ < … < x_k}, where B = w^1/5. Because each key x_i is w bits long, storing the full keys x₁, …, x_k requires k · w bits—which cannot fit into a single w-bit machine word when k ≥ 2.

To compress k keys into O(k⁴) ≪ w total bits, Fredman and Willard analyzed the binary trie T_S formed by viewing the k keys x₁, …, x_k as root-to-leaf bit strings of length w (indexed from most significant bit w − 1 down to least significant bit 0). Because T_S has k leaves, it possesses at most k − 1 internal branching nodes (bit positions where at least two keys in S diverge, one taking bit 0 and the other taking bit 1). Let the set of bit positions of these branching levels be:

For any key x, define its perfect sketch sketch(x) as the r-bit integer obtained by extracting only the bits of x at the distinguishing positions b₁, …, b_r in order of significance:

Because two keys x_i < x_j in S first diverge at some branching bit b_t ∈ I, extracting only the bits in I strictly preserves the sorted order among all keys in S:

Each sketch is at most r < B bits long, so the information needed to distinguish all k keys requires fewer than B² bits in total!

Constant-Time Approximate Sketching via Word Multiplication

Although sketch(x_i) for the static node keys can be precomputed when the node is constructed, how can the algorithm extract sketch(q) for a newly arriving w-bit query key q in O(1) word operations? Masking out all non-branching bits of q via bitwise AND (q′ = q ∧ M, where M = ∑_t=1^r 2^b_t) leaves the r branching bits scattered across w positions.

To pack those r scattered bits into a contiguous low-order block of length O(r⁴) bits using a single hardware multiplication q′ × m, Fredman and Willard proved the Collision-Free Multiplier Lemma: there exists a multiplier m = ∑_t=1^r 2^m_t such that in the product:

the r target bit positions p_t = b_t + m_t (for t = 1, …, r):

1. Are collision-free from all r² pairwise sums b_s + m_t (selected greedily because each m_t only has to avoid at most r³ forbidden congruences modulo r³),
2. Maintain strictly increasing order p₁ < p₂ < … < p_r, and
3. Span a total bit window p_r − p₁ ≤ r⁴ < B⁴ = w^4/5 bits.

Shifting right by p₁ and masking out the non-target positions p_t yields the approximate sketch approxSketch(q) of length ≤ B⁴ bits in three O(1) word operations (bitwise AND, multiply, shift + AND).

Broadword Parallel Subtraction Across B Packed Sketches

Because each approximate sketch occupies L ≤ B⁴ bits and B = w^1/5, all k < B node sketches approxSketch(x₁), …, approxSketch(x_k) fit side-by-side inside a single w-bit machine word NodeSketch (B · B⁴ = B⁵ ≤ w), separated by a 1-bit padding (sentinel) bit set to 1 immediately above each field:

Given a query key q:

1. Compute s_q = approxSketch(q) in O(1) time and replicate s_q across all k parallel lanes (with 0 in each sentinel bit) by multiplying s_q by the constant repetition mask R = ∑_i=0^k−1 2^i(L+1).
2. Perform a single w-bit integer subtraction:

In each lane i, the sentinel bit remains 1 if and only if approxSketch(x_i) ≥ approxSketch(q) (no borrow out of the sentinel bit), and flips to 0 if approxSketch(x_i) < approxSketch(q).

1. Mask the k sentinel bits of Diff, multiply by a packing constant, and count leading ones (or index a tiny lookup table) to find the exact number of node sketches less than or equal to s_q in O(1) time!

Two-Step Representative Prefix Matching

Because q may differ from the keys in S at a bit position not in the branching set I, approxSketch(q) is guaranteed to land next to the key x_i ∈ S that shares the longest common prefix (LCP) with q, though not necessarily the true predecessor of q in S. Fusion trees resolve this in O(1) additional steps:

1. Compare q against the adjacent sketch match x_i via bitwise XOR (q ⊕ x_i) and find the most significant differing bit d = ⌊log₂(q ⊕ x_i)⌋ (a standard word-RAM most-significant-bit operation implemented via fusion-style bit compression or floating-point exponent extraction).
2. The true predecessor or successor of q among S corresponds to the extreme leaf in the subtrie beneath bit d: construct a mask e that matches q down to bit d + 1, flips bit d, and fills bits d − 1 … 0 with all 0 bits (or all 1 bits).
3. Compute approxSketch(e) and perform one more parallel subtraction against NodeSketch. Because e agrees with a key in S at every branching bit above d and is extremal below d, its sketch rank gives the exact predecessor/successor child branch for q in T in O(1) total time per B-tree level!

Comparison of Word-RAM and Comparison-Based Ordered Dictionaries

Furthermore, by combining fusion trees (optimal when w is large relative to log N) with van Emde Boas trees (optimal when w is small relative to log N) at crossover w = 2^{√(log N · log log N)}, Fredman and Willard achieved O(log N / log log N) search time unconditionally for every word size w ≥ log₂ N. In 2014, Mihai Pătrașcu and Mikkel Thorup introduced dynamic fusion nodes that update the compressed trie and multiplier m in O(1) time per insertion or deletion without weight-balanced rebuilding.

1. SIMD and Broadword In-Register B-Trees: Modern database index engines (ART, Masstree, Fast Architecture Sensitive Tree) and hardware packet classifiers use the fusion-tree paradigm of extracting distinguishing trie bits and executing parallel SIMD / SWAR lane comparisons to search 16–64 child keys in a single register instruction.
2. Trans-Dichotomous Shortest Paths and Minimum Spanning Trees: Fredman and Willard applied fusion-tree priority queues to accelerate Dijkstra's algorithm to O(E + V log V / log log V) time and to develop the first deterministic linear-time O(E) minimum spanning tree algorithm on the word RAM.

Why is the branching factor of a classical fusion tree B = w^(1/5) rather than w^(1/2)?

For k < B keys, there are up to B distinguishing branching bits. Packing those B scattered bits into a contiguous window via a single multiplication without pairwise bit collisions requires spacing the multiplier exponents across a range of size O(B⁴). Storing B such approximate sketches inside one w-bit word therefore requires B × B⁴ = B⁵ ≤ w, giving B = w^1/5 (note that constant factors in log_B N = 5 log_w N do not affect O(log_w N)).

Does a fusion tree require non-standard CPU instructions?

No. A fusion tree uses only standard C/Rust integer operations available on every 64-bit processor: bitwise AND, OR, XOR, bit shifts, addition, subtraction, and integer multiplication.

1. Fredman, M. L., & Willard, D. E. (1993). "Surpassing the information theoretic bound with fusion trees." Journal of Computer and System Sciences, 47(3), 424–436. https://doi.org/10.1016/0022-0000(93)90040-490040-4)
2. Fredman, M. L., & Willard, D. E. (1994). "Trans-dichotomous algorithms for minimum spanning trees and shortest paths." Journal of Computer and System Sciences, 48(3), 533–551. https://doi.org/10.1016/S0022-0000(05)80064-980064-9)
3. Andersson, A., Miltersen, P. B., & Thorup, M. (1999). "Fusion trees can be implemented with AC⁰ instructions only." Theoretical Computer Science, 215(1–2), 337–344. https://doi.org/10.1016/S0304-3975(98)00172-800172-8)
4. Pătrașcu, M., & Thorup, M. (2014). "Dynamic integer sets with optimal rank, select, and predecessor search." Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 166–175. https://doi.org/10.1109/FOCS.2014.26