Fusion Tree | Codeboy's Blog

形式陈述

模型、接口与保证

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

Fusion tree 沿用B 树式的分隔区间与平衡多路骨架，分支度取

B=\max\{2,\lfloor w^{1/5}\rfloor\}

这个数量级。位打包论证针对足够大的 $w$ ；较小字长采用常数分支的普通节点。每个内部节点保存至多 $B-1$ 个分隔键以及一个 fusion node；树高为

O(1+\log_B(n+1))=O\!\left(1+\frac{\log(n+1)}{\log w}\right).

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

重要位与保序 sketch

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

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

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

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

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

k_a<k_c \Longleftrightarrow \operatorname{sketch}(k_a)<\operatorname{sketch}(k_c).

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

一字中的并行比较

把节点键的 sketches 按从高字段到低字段递减的次序打包为

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

每个字段前放一个初值为0的保护位并留出足够间隔。预处理掩码和乘法常数把重要位抽取或散布为保序的短字段；复制查询 sketch 得到每个字段都为 $1\,\operatorname{sketch}(x)$ 的字 $Q$ 。计算 $Q-W_{\mathrm{node}}$ ：每个字段先有高位1，减去高位0的节点 sketch，因此不会向邻字段借位；结果的保护位为1恰好表示

\operatorname{sketch}(k_j)\le \operatorname{sketch}(x)

成立。节点 sketches 的顺序使这些1形成低端连续的字段区，再由最高置位及字段位置解码取得 sketch rank。常数时间抽位、最高置位定位和字段解码都是 fusion node 的字级实现内容，不能把逐位扫描当作一个免费步骤。经典选择 $B=w^{1/5}$ 为抽位、复制、字段间隔和中间乘积预留足够 bit，使所有量仍装在常数个字中；指数 $1/5$ 来自这套打包预算，不是 B 树高度本身要求的神秘常数。

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

直觉

一个多路节点中的键只在少数真正分叉位上需要彼此区分。Fusion node 抽取这些位，把所有分隔键的短 sketch 放进一个机器字，并用带保护位的算术同时比较查询；树高因高分支度下降，而每层仍只花常数字操作。

下图从左到右按 $k_0,k_1,\ldots$ 的逻辑键序列出字段，省略保护位；在上面的整数打包式中，大键字段位于更高位，因而应按相反方向读取字段位置。

四个八位键抽取三个重要位形成保序 sketch，并在一个字中同时比较查询 — Fusion Tree 的重要位与并行 sketch 比较

例子与边界

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

考虑八位键

00000000,\quad00100000,\quad00101000,\quad10101000.

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

000,\quad010,\quad011,\quad111,

顺序与原键完全相同。图中八位只是便于展示键的位模式；实际机器字还要容纳多个字段和保护位，并受上面的分支预算限制。查询 $00101100$ 的 sketch 也是 $011$ ，与第三个键碰撞；实际比较发现它大于 $00101000$ 。这不是哈希冲突造成的错误，而是候选修正步骤要处理的非重要位差异。

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

失败边界与近邻结构

B 树也用高分支度降低树高，但节点内通常仍做比较或块内搜索；Fusion tree 的额外收益来自把多个整数比较压进一个字操作。若键跨越许多机器字、比较器要执行昂贵语义，或 $w$ 小到不能容纳打包字段，这份收益消失。

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

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

推论与应用

Fusion Tree 把多个关键位压入一个机器字并并行比较，核心依赖四俄罗斯方法与字级并行式的表查与字内并行。允许的乘法、移位和字长假设是时间界的一部分。

Fusion tree 给整数 predecessor、整数排序子程序和 Word-RAM 上的次对数搜索提供基本构件，也展示了为何比较模型下界不能直接约束字级并行。动态版本、跨字键和弱操作集需要独立结构，不能从静态 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，MIT 6.851 Advanced Data Structures, Lecture 12，Spring 2012：Fusion Trees、sketch、并行比较与最高置位定位。
Peter Bro Miltersen, “Cell Probe Complexity—A Survey,” in Advances in Data Structural Query Processing, American Mathematical Society, 2000, pp. 183–217.

形式陈述 ​

模型、接口与保证 ​

重要位与保序 sketch ​

一字中的并行比较 ​

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