van Emde Boas 布局

布局递归 ​

对高度 $h$ 的完整二叉树，在约 $h/2$ 层切开：上半形成高度 $\lceil h/2\rceil$ 的 top tree，下方有若干高度 $\lfloor h/2\rfloor$ 的 bottom subtrees。内存中先递归布局 top tree，再按其叶次序递归布局各 bottom subtree。布局算法不读取缓存参数 $B,M$。

路径 I/O 分析 ​

固定任意块大小 $B$，选择递归层级使子问题大小介于 $B$ 与 $B^2$ 的常数幂范围。一个这样大小的连续子树占 $O(1)$ 块，而根叶路径每穿过它就跨越 $\mathrm{\Theta }(\log B)$ 层；高度 $\mathrm{\Theta }(\log N)$ 的路径于是访问

$$O({\log }_{B}N)$$

个块，与知道 $B$ 后设计的 B-tree 路径量级一致。分析是在事后选择观察尺度，算法本身仍 cache-oblivious。

与层序布局对照 ​

层序数组把同深节点放一起，根附近局部性好，但路径到深层后相邻父子可能相距指数远；不同 $B$ 下频繁换块。vEB 布局让多种高度尺度的子树都连续，适合静态搜索树的根叶遍历。

名称与失效边界 ​

本页递归的是树高，与vEB 整数树公理库van Emde Boas 树van Emde Boas tree · vEB tree按平方根宇宙递归分簇，以双对数时间支持整数前驱和动态集合操作。递归键宇宙不是同一结构。证明依赖平衡/完整树及连续布局；普通指针逐节点随机分配不享受界。动态插入会移动布局或产生碎片，需要 packed-memory/cache-oblivious B-tree 等额外技术。路径 I/O 好也不自动保证扫描或更新最优。

搜索树应用 ​

对静态平衡 BST，比较过程走一条根叶路径，vEB 布局因此给 $O({\log }_{B}N)$ 次未知块大小下的传输；CPU 比较仍为 $O(\log N)$。区间扫描还需叶按键序邻接或额外链接，布局的递归次序本身不保证叶序连续。

Cache-oblivious 分析通常采用理想缓存和最优替换，并可能要求 tall-cache；现实多级缓存、TLB 和硬件预取会影响常数。结论是对每个层级同时渐近良好，不是“完全不需要知道记录大小或缓存行为”。

路径为何只碰对数个块 ​

把高度 $h$ 的树在中间切成高度约 $h/2$ 的顶部树和若干底部树，递归连续存放。对任意块大小 $B$，取最小递归层使一个子树含 $\mathrm{\Theta }(B)$ 个节点；它占常数个连续块。根到叶路径穿过的此类子树数量为 $O(h/\log B)$，故平衡搜索树得到 $O({\log }_{B}N)$ 次块传输。

布局本身按固定静态形状计算，不读取运行时的 $B$，这才是 cache-oblivious。若节点带可变长记录、指针对象被分配器分散到堆上，数组下标的连续性不再等于物理局部性；需要紧凑序列化或显式索引才能继承分析。

更新导致旋转时，大段布局位置可能失效。把 vEB layout 用于静态搜索树与把 vEB tree 用于整数前驱是两个独立思想，名字相同不代表接口或复杂度可以互换。

参考资料

• Harald Prokop, Cache-Oblivious Algorithms, MIT thesis, 1999.
• Matteo Frigo et al., Cache-Oblivious Algorithms, FOCS, 1999.
• Michael Bender, Erik Demaine, Martin Farach-Colton, Cache-Oblivious B-Trees, SIAM J. Comput., 2005.