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把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。在数据摆放上的应用。静态搜索时，键比较仍沿原树的根叶路径进行，只改变节点的物理位置。因此 CPU 比较次数为 $O(\log (N+1))$，块传输次数则为 $O(1+{\log }_{B}N)$；两种成本对应同一条逻辑路径。

这一证明依赖紧凑、定长的节点表示。若节点另含可变长记录，可把键和记录索引留在紧凑布局中，再单独计算取回记录的 I/O。范围扫描也需要自己的分析：连续输出多少条记录、如何从一片叶区间进入下一片，都是根叶搜索界之外的工作。

理想缓存模型把块传输单独计费，实际多级缓存、TLB 和预取还会影响运行常数。静态路径的局部性界只需常数个块的缓存容量；动态缓存无关搜索树则需进一步安排空位、重建和更新。