van Emde Boas 布局

vEB 布局在许多高度尺度上同时把完整子树放成连续片段。固定任意实际块大小后，总能在递归中找到一层，使一个常数块片段覆盖根叶路径的若干层；代码无需知道 $B$，分析仍能把路径分成少量适配该块尺度的连续段。

与层序布局对照 ​

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

名称与失效边界 ​

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

布局递归地把树分成 top tree 与若干 bottom trees，是分治法公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。；每层切分不读取具体缓存参数，却保证任意根叶路径在不同块尺度上都只穿过少量连续区段。

搜索树应用 ​

对静态平衡 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 用于整数前驱是两个独立思想，名字相同不代表接口或复杂度可以互换。