缓存无关搜索树

模型、接口与目标 ​

在缓存无关模型公理库缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。中，数据以块大小 (B) 在慢存与容量 (M) 的快存之间传输，但算法代码不读取 (B) 或 (M)。静态有序字典支持 search、predecessor 和 successor；动态版本还需 insert、delete 与区间扫描。

对 (N) 个键，静态搜索的目标是 [ O(1+\log_B N) ] 次 I/O，同时做 (O(\log N)) 次比较。分析采用 ideal-cache：块自动调入，缓存全相联，并以最优替换衡量 misses。递归算法常在 (M=\Omega(B^{1+\delta})) 的 tall-cache 条件下证明批量更新或扫描界；具体结论若无需该条件，也应单独说明，而不是把所有操作共享一个模糊假设。

静态树的 vEB 递归布局 ​

先构造一棵平衡二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。，再按van Emde Boas 布局公理库van Emde Boas 布局van Emde Boas layout · vEB layout递归切分树高并连续摆放上下子树，使根叶路径对未知块大小保持局部性。存入连续数组。对高度 (h) 的树，在中间高度切开：递归摆放 top tree，然后按从左到右的边界次序递归摆放各棵 bottom subtree。

搜索仍按比较结果从根走向叶，变化的是节点地址。布局递归没有一层写着“每块放 (B) 个节点”；它同时让许多高度尺度的子树连续，因此可在分析时针对真实 (B) 选择恰当尺度。

块传输界的不变量 ​

固定任意 (B)，观察递归分解中规模首次落入 (\Theta(B)) 到 (B^{O(1)}) 的子树。一个这种子树由常数个连续片段构成，并覆盖根叶路径上的 (\Theta(\log B)) 层。高度 (O(\log N)) 的路径至多穿过 [ O!\left(\frac{\log N}{\log B}\right)=O(\log_B N) ] 个这样的路径片段。

每个片段只引起常数次块传输，得到搜索界。证明重心是“某个合适尺度的递归子树连续”，并非笼统的“递归会有局部性”。若节点由普通堆分配器逐个随机放置，逻辑递归关系不再带来地址连续性，论证也随之消失。

查询 11 的可追踪例子 ​

把键 (1,\ldots,15) 排成完美平衡树，根为 8；右子树根为 12，其左孩子为 10，10 的右孩子为 11。查询 11 的比较路径为 [ 8\rightarrow12\rightarrow10\rightarrow11. ] 层序数组会把 8、12、10、11 放在下标 1、3、6、13 附近，越到深层距离越大。vEB 布局先连续递归放上半树，再放下半子树；对于能容纳约四个节点的块，路径中的相邻若干层会被同一个递归片段覆盖。

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

predecessor 与扫描 ​

predecessor 搜索记录路径上最后一个小于查询键的候选，访问的仍是一条根叶路径，因此继承相同 I/O 界。successor 对称。

区间扫描需要额外的叶序结构。若布局把中序叶或记录区连续存储，定位首键后可用 (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 集合。

适用边界 ​

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

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

参考资料

• Harald Prokop, Cache-Oblivious Algorithms, MIT Master's Thesis, 1999.
• Michael A. Bender, Erik D. Demaine and Martin Farach-Colton, Cache-Oblivious B-Trees, SIAM Journal on Computing, 2005.
• Matteo Frigo, Charles E. Leiserson, Harald Prokop and Sridhar Ramachandran, Cache-Oblivious Algorithms, ACM Transactions on Algorithms, 2012.