缓存无关搜索树

普通二叉搜索树的逻辑路径只有 $O(\log N)$ 个节点，但随机地址可能让每个节点各触发一次 I/O。vEB 布局把多种高度的完整子树递归地放成连续片段；无论块实际能容纳多少节点，总能在某个递归尺度上让一块覆盖路径的若干层，于是块传输数从 $\log N$ 降为 ${\log }_{B}N$。

查询 11 的可追踪例子 ​

把键 $1,\dots ,15$ 排成完美平衡树，根为 8；右子树根为 12，其左孩子为 10，10 的右孩子为 11。查询 11 的比较路径为

层序数组会把 8、12、10、11 放在下标 1、3、6、13 附近，越到深层距离越大。vEB 布局先连续递归放上半树，再放下半子树；对于能容纳约四个节点的块，路径中的相邻若干层会被同一个递归片段覆盖。

这个例子不声称四个节点必然恰落在一个对齐块内。数组起始地址可能使连续片段跨块，所以证明按常数块而非“一块”计数；渐近界不依赖幸运对齐。

predecessor 与扫描 ​

本页的 predecessor 返回不大于查询键的最大已存键：沿路径保留最后一个合适候选，比较相等时即可返回；无候选时报告无前驱。successor 对称地返回不小于查询键的最小成员。两者都只访问一条根叶路径，继承相同 I/O 界；严格前驱或严格后继则须排除相等项。

区间扫描需要额外的叶序结构。若布局把中序叶或记录区连续存储，定位首键后可用 $O(K/B+1)$ 次 I/O 输出 $K$ 个结果；仅有 vEB 形状布局并不自动保证报告记录连续。把 search 的路径界直接写成 range query 的输出界，会漏掉这一接口条件。

动态维护为何是另一项技术 ​

静态数组插入一个键可能移动大量后缀，树旋转也会破坏递归片段。动态缓存无关搜索树通常把有序记录放入 packed-memory array，以分层密度阈值控制局部重排，再用缓存无关搜索索引定位区域；更完整的 cache-oblivious B-tree 还要协调分裂、重建和扫描。

密度不变量要求每个层级区间的占用率落在相应上下界。插入先利用附近空隙；区间过密时逐级扩大重排范围。由多次局部更新摊分重排成本，而不是从静态 $O({\log }_{B}N)$ 搜索界“顺便”推出便宜更新。

与已知结构的对照 ​

传统 B-tree 明确知道 $B$，把一个节点设计成约一个块并用高扇出降低树高。缓存无关搜索树以二叉比较路径和递归地址布局适配多个未知层级，常数、重建成本与实现复杂度不同。

排序数组也有优秀的顺序扫描局部性，二分搜索却可能在每一层跳到远处；合适的 cache-oblivious 静态布局改善的是搜索路径。名称中的 vEB 指 layout，不是按整数宇宙递归、支持 predecessor 的 van Emde Boas 集合。

适用边界 ​

界依赖记录大小固定或可受控，使 $\mathrm{\Theta }(B)$ 个节点确实对应一个块尺度。可变长对象、间接指针、垃圾收集移动和并发修改都需要额外布局协议。ideal-cache 的最优替换是分析基准，不代表真实硬件会执行同一策略；硬件预取、TLB 与缓存组相联会改变常数。

因此页面级结论应分开报告：静态查找可由 vEB layout 达到 $O(1+{\log }_{B}N)$ I/O；动态更新需要额外结构及其自身假设；并发与持久化不在经典模型保证内。