有序文件维护与 Packed Memory Array

两个问题层 ​

Order maintenance 只需比较列表中两元素的相对次序，可用标签完成；ordered file maintenance 还要求元素按序物理存于数组并留空隙。Packed Memory Array 是后者的分层密度实现，使二分搜索和范围扫描保有数组局部性。

密度不变量 ​

把容量 $N$ 的数组按幂次窗口组织。插入先在目标邻近空隙放置；若叶窗口过密，就逐层扩大到第一个密度未越上界的窗口，再把其中元素均匀摊开。越高层允许的密度区间越窄/按设计变化；删除对称使用下界并回收空隙，顶层越界时全局扩缩。

摊还图像 ​

一次重平衡长度 $L$ 的窗口移动 $\mathrm{\Theta }(L)$ 个元素，但其密度从阈值恢复到留有裕量的状态；在再次触发同层前必须有 $\mathrm{\Omega }(L)$ 次集中更新，故成本可向这些更新收费。层数 $O(\log N)$，具体移动/I/O 界取决于阈值梯度和 cache-aware/oblivious 版本，不能只写“摊还对数”而省略模型。

时间线插入例子 ​

按时间有序保存事件时，在上午记录间插入迟到事件。普通紧密数组移动整个后缀；PMA 若局部窗口有空位只移动附近记录，持续集中插入才逐层扩大重平衡，范围扫描仍沿连续数组读取。

边界 ​

单次对抗插入可触发大窗口重排，低尾延迟需去摊还化公理库去摊还化Deamortization把偶发的大工作拆成有预算的增量步骤，使逐操作延迟获得最坏界。。墓碑删除若不计入密度会让扫描充满空洞。标签顺序与物理地址不是同一保证；仅有 order-maintenance 标签不能推出连续范围扫描。

阈值层级为何要分离 ​

若所有层使用同一上界，局部重平衡后可能只留常数个空位，连续几次插入就再次触发同样大窗口，收费失败。标准设计让窗口越大越接近全局目标密度，并在相邻层阈值间留出与层高相关的 slack；重平衡后要积累足够更新才再次越界。

去摊还化可同时维护旧/新布局和迁移游标，每次操作搬固定预算元素。查询在迁移期间须检查两位置或由 forwarding map 定位；只把搬移动作拆开而不维护可见顺序，会出现重复或漏读。

插入如何寻找重排窗口 ​

在逻辑位置 $i$ 插入时，先尝试附近常数槽；若已满，就从最小叶段开始逐级扩大窗口，直到窗口加入新元素后的密度不超过该层上阈值。随后把窗口内元素按顺序均匀撒回槽位。逻辑次序保持不变，改变的只是物理空隙分布。

阈值不能每层相同。常用设计让大窗口允许的密度更低、下阈值与上阈值之间留有滞回：一次大范围重排后，必须经历足够多次局部更新才会再次触发同级重排。按“元素跨过的层级”收费，可得 $O({\log }^{2}N)$ 摊还移动；配合更精细调度可改善，但需要新的去摊还证明。

例如容量 16 的窗口已有 12 项，若该层上阈值为 $3/4$，再插一项就必须扩到父窗口，而不是仍在 16 槽中强塞。删除对称地检查下阈值；若只在插入时维护密度，连续删除会留下过稀布局并破坏空间保证。

参考资料

• Alon Itai, Alan Konheim, Michael Rodeh, A Sparse Table Implementation of Priority Queues, ICALP, 1981.
• Michael Bender et al., Cache-Oblivious B-Trees, SIAM J. Comput., 2005.
• Michael Bender et al., Two Simplified Algorithms for Maintaining Order in a List, ESA, 2002.