Fusion Tree

模型、接口与保证 ​

设静态集合 $S\subseteq [0,2^w)$ 含 $n$ 个互异的 $w$ bit 整数。采用 Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。：一个键、地址和若干打包字段能装进常数个 $w$ bit 字，随机访存、加减、布尔运算、移位和字乘法均为最坏 $O(1)$。若模型不提供乘法或常数次位提取，下面的 fusion node 不能直接按同一时间界实现。

Fusion tree 是分支度

$$B=\lfloor w^{1/5}\rfloor$$

量级的多路搜索树。每个内部节点保存至多 $B-1$ 个分隔键以及一个 fusion node；树高为

$$O({\log }_{B}n)=O\left(\frac{\log n}{\log w}\right)=O({\log }_{w}n).$$

因此静态前驱查询最坏用 $O({\log }_{w}n)$ 次字操作，结构占 $O(n)$ 个字。若 $w=\mathrm{\Theta }(\log n)$，这就是 $O(\log n/\log \log n)$。这里的结论针对一字整数键；任意比较对象仍受比较模型的对数决策树约束。

重要位与保序 sketch ​

设一个节点的有序分隔键为

$$k_0<k_1<\cdots <k_{t-1},t<B.$$

把这些键放入二进制 trie。每个真正发生分叉的位称为重要位；$t$ 个叶的压缩 trie 至多有 $t-1$ 个分叉，所以重要位数 $b<t<B$。若重要位从高到低为 $i_1>\cdots >i_b$，定义

$$\mathrm{sketch}(x)=x[i_1]x[i_2]\cdots x[i_b].$$

对节点内任意两个键 $k_a<k_c$，它们最高的不同位必是压缩 trie 的某个分叉位，而且也出现在 sketch 中。更高重要位相同、这一位上前者为 $0$ 后者为 $1$，故

$$k_a<k_c⟺\mathrm{sketch}(k_a)<\mathrm{sketch}(k_c).$$

这条保序性质是核心不变量。Sketch 不是一般哈希：它可以丢掉大量位，却绝不能打乱当前节点键的相对次序。

一字中的并行比较 ​

把节点键的 sketches 按递增顺序打包为

$$W_{\mathrm{node}}=1\mathrm{sketch}(k_0)1\mathrm{sketch}(k_1)\cdots 1\mathrm{sketch}(k_{t-1}),$$

每个字段前放一个保护位并留出足够间隔。预处理掩码和乘法常数可以在 $O(1)$ 个字操作内同时抽取全部重要位；另一乘法把查询 sketch 复制到 $t$ 个字段。一次打包减法后，各字段保护位便同时指出

$$\mathrm{sketch}(k_j)\le \mathrm{sketch}(x)$$

是否成立，再由最高置位定位 sketch rank。经典选择 $B=w^{1/5}$ 为抽位、复制、字段间隔和中间乘积预留足够 bit，使所有量仍装在常数个字中；指数 $1/5$ 来自这套打包预算，不是 B 树高度本身要求的神秘常数。

查询 $x$ 可能与某个节点键具有相同 sketch，却在被删除的非重要位上不同。因此 sketch rank 只先给出相邻候选。Fusion node 再比较 $x$ 与该候选的最高不同位，构造把剩余低位全置 $0$ 或全置 $1$ 的修正查询，做第二次并行比较，最终得到真实 predecessor 所在子区间。忽略这一步会把“节点键之间保序”误写成“任意查询也由 sketch 唯一排序”。

具体例子：四个键的三个分叉位 ​

考虑八位键

$$00000000,00100000,00101000,10101000.$$

压缩 trie 只在从高到低的第 $7,5,3$ 位分叉。抽取这三位得到

$$000,010,011,111,$$

顺序与原键完全相同。查询 $00101100$ 的 sketch 也是 $011$，与第三个键碰撞；实际比较发现它大于 $00101000$。这不是哈希冲突造成的错误，而是候选修正步骤要处理的非重要位差异。

在每个树节点重复同样过程，一次 fusion-node 搜索决定一个多路子树，经过 $O({\log }_{B}n)$ 层便找到全局前驱。

失败边界与近邻结构 ​

B 树公理库B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。也用高分支度降低树高，但节点内通常仍做比较或块内搜索；Fusion tree 的额外收益来自把多个整数比较压进一个字操作。若键跨越许多机器字、比较器要执行昂贵语义，或 $w$ 小到不能容纳打包字段，这份收益消失。

比较排序的 $\mathrm{\Omega }(n\log n)$ 下界只允许二元键比较。Fusion tree 每步读取并组合多个键的位，因此没有违反该下界。它也不是 vEB 递归：vEB 以宇宙分解换取 $O(\log w)$，fusion tree 则以节点并行比较得到 $O({\log }_{w}n)$，两者依赖的参数和空间权衡不同。

本页给出经典静态主线。动态 fusion tree 需要维护重要位、打包常数和节点分裂，原论文有更复杂方案；不能仅把普通 B 树插入代码接到静态 fusion node 后便宣称同样的最坏更新界。

参考资料

• Michael L. Fredman and Dan E. Willard, “Surpassing the Information Theoretic Bound with Fusion Trees,” Journal of Computer and System Sciences 47(3), 1993, 424–436.
• Erik D. Demaine, Advanced Data Structures, MIT 6.851 lecture notes, integer data structures and fusion trees.
• Peter Bro Miltersen, “Cell Probe Complexity — A Survey,” for the predecessor-model and lower-bound context.