15 篇按块容量 B 选择节点大小与归并路数。缓存无关算法不读取 B 和缓存容量 M，而用一种布局同时提供多个尺度的局部性。分析仍然依赖 B、M；“无关”限定算法可见的参数，不表示性能与硬件容量无关。

本篇只重排一棵静态完美二叉搜索树。逻辑键、左右孩子和查询序列保持相同，变化的是节点地址。这样能分辨缺失次数的变化来自布局，而不是树形或输入被换过。

理想缓存与实际替换策略

沿用15篇块传输单位，B个常数大小节点占一块，快存能保存M个节点。ideal-cache模型假设全相联：任何块可进入任何槽；替换时知道整个未来访问轨迹，选择离线最优策略OPT。算法不知道M和B，分析者知道。

LRU只根据过去访问淘汰最久未用块，是可以在线模拟的另一种策略。它不等于OPT。原论文把容量M的LRU与容量M/2的OPT比较，带有容量扩张；不能直接改写成“同样大小缓存中LRU至多差两倍”。要把这项比较转成同阶渐近界，还须满足所分析缺失函数对容量缩放的正规性，并保留缩放后所需的容量条件。

本篇模拟明确记录LRU。小轨迹另外与OPT参照比较，用于检查替换器；大轨迹的LRU数字不伪装成理想缓存定理的实测证明。所有节点和轨迹都在Python内存中，也没有读取CPU硬件缓存计数器。

按高度递归划分地址

树高h按根到叶的节点层数计，节点数n=2^h−1。键为0到n−1，逻辑树递归选择中点为根。普通布局按层序BFS排放；递归布局把顶部ceil(h/2)层作为一棵树，先递归排放顶部，再逐一递归排放底部子树。h为0时为空，h为1时只有一个节点。

1
2
3
h=3，键0..6，逻辑根3
BFS地址顺序：3 1 5 0 2 4 6
递归地址顺序：3 1 5 0 2 4 6

小树上两种布局可以完全相同。不能用“递归”这个名字推断每个输入都有改进。更高树会在多个尺度保留连续子树片段，而层序布局把同一深度的不同搜索分支放在一起。

这种布局常称van Emde Boas布局，简称vEB布局。它不是20篇将讨论的整数宇宙前驱数据结构；相同名字不表示相同接口或复杂度。

重排为什么不改变查找答案

搜索在逻辑树上比较目标与当前键，选择左或右孩子，直到找到相等键或空区间。布局只是键到唯一地址的双射。每次逻辑访问改成读取相应地址，比较对象与分支不变，因此答案和比较次数保持不变。

递归构造顶部及底部片段时，它们的节点集合互不相交且并为原树。由归纳可知每个节点恰出现一次，地址映射为排列。这是布局正确性义务；仅检查输出数组长度等于n不足以排除重复地址或漏节点。

为什么一条路径只穿过少量片段

分析时选取递归划分中第一次能容纳在B个节点内的片段。其父片段还超过B节点，按高度近似对半切分意味着所选片段高度为Θ(log(B+1))，除树的顶端和末端边界外，一条根到叶路径每经过一个片段就前进这个数量的层。

片段节点连续存放，长度不超过B，却不一定从块边界开始，因此可能跨两块。保守要求M≥2B，让这两块可以同时驻留。理想替换能保留当前片段需要的块，离开该片段后搜索不会返回；每个片段至多常数次装入。全树高O(log(n+1))，得到一次冷缓存搜索的最坏O(1+log_{B+1}n)块缺失上界。B大到覆盖整树时归入常数项。

该论证依赖静态、常数节点大小、常数分支以及叶同层。动态插入或旋转可能破坏地址连续性，不能把06篇AVL旋转直接接上就宣称仍保留该I/O界。教学实现也没有动态更新接口。

递归矩阵转置和funnelsort有各自的证明。所查论文的转置界使用tall-cache条件M=Ω(B²)；不能因本篇也使用递归，就给静态搜索强加同一条件，或反过来把更弱的M≥2B套到矩阵转置上。

实验应固定什么

实现位于 examples/advanced-algorithms/cache_layout.py。layout(height,veb=False)返回键到地址的列表；search_trace(n,key)返回是否命中及访问键序列；blocks(addresses,B,offset)把地址转换为块号。lru_misses与opt_misses接受块号序列和缓存块槽数，返回冷启动缺失次数。高度、地址偏移非负，B与槽数为正；非法数值抛ValueError。高度0对应空树，空轨迹缺失数为0。输入类型按整数契约使用，不是外部文本解析接口。

1
python3 examples/advanced-algorithms/check_cache_layout.py

本轮实际检查通过：529次逻辑搜索、3279组缓存轨迹与容量组合。LRU与独立列表参照对照；OPT与穷举替换选择的动态规划对照，避免仅用OPT≤LRU这个必要条件掩盖两者共同错误。还有高度3、4的精确地址排列和非法参数检查。

固定h=10、n=1023、seed=20260920生成1000次查询。每组开始为空缓存，组内跨查询保留缓存状态，容量固定为4个块槽，所以M随B变化为4B；这不是固定字节容量下单独改变块大小的实验。地址偏移单位为节点字，完整结果含offset=0与1。

B BFS缺失，offset=0 递归布局缺失，offset=0
2 8457 7838
4 7671 5815
8 6736 3524
16 5645 2037
32 4428 1248

表中是实际运行的LRU模拟计数。偏移1时，B=8的两项变为6838与3731，说明对齐也影响结果。完整JSON保存于 examples/advanced-algorithms/results/cache_layout.json。这些有限参数下递归布局缺失较少，不推出每棵树、每个查询序列或真实硬件都更快。

布局生成、轨迹生成与模拟器自身的CPU成本不计入缺失次数。逻辑搜索最坏O(log(n+1))次比较；LRU模拟器使用OrderedDict，其容器访问依赖字典成本假设。朴素OPT参照每次淘汰扫描未来，长度L、槽数C时可用O(L²C)保守CPU上界；它只是小轨迹参照，不是高效生产缓存。程序保存O(n)地址与整条轨迹，不能把缓存槽数上限说成整个Python进程的空间上限。

布局与缓存模拟契约

练习

  1. 对h=4手算两种地址排列，选一条到最左叶的搜索路径，在B=4、地址偏移0与1时分别标出块号。哪些连续片段会跨两块？
  2. 给出两槽缓存访问轨迹，使LRU与离线OPT淘汰不同块。说明为什么OPT需要知道未来，以及这不构成可直接用于实际缓存的在线实现。

参考资料