有序文件维护与 Packed Memory Array

形式陈述

两个问题层

Order maintenance 在一个全序列表中只需比较两元素的相对次序，可用标签完成；ordered file maintenance 还要求元素按序物理存于数组并留空隙。Packed Memory Array 是后者的分层密度实现；它保持物理有序和可扫描的空隙分布，按键搜索仍须配合能处理空槽的定位规则或搜索索引。

密度不变量

用 $n$ 表示当前元素数、 $P=\Theta(n)$ 表示数组容量，避免把两者混为一谈。小规模数组直接维护；其余把数组分成 $\Theta(\log P)$ 大小的叶段，把叶段数量取为二次幂，再在其上建立隐式完美二叉树；容量按常数比例取整不改变 $P=\Theta(n)$ 。树高 $H=\Theta(\log P)$ ，每个节点对应一个连续窗口。叶段的常数系数取足够大，以吸收均匀分配的整数舍入。

设根深度为 $0$ 、叶深度为 $H$ ，可选择一组具体阈值

\rho_j=\frac14-\frac{j}{8H},\qquad \tau_j=\frac34+\frac{j}{4H}\qquad(0\le j\le H).

窗口占用率须在 $[\rho_j,\tau_j]$ 内，越靠近叶允许的区间越宽。插入或删除先定位叶段；若更新会使某个路径窗口越界，就找出路径上最高的越界窗口，再取其上方最近的、容纳更新后元素数且密度合法的祖先窗口，将其元素按序均匀分布。根越界时重新分配数组并重建层级。根的常数间隔允许采用扩倍和减半：扩倍后密度约为 $3/8$ ，减半后约为 $1/2$ ，都回到合法区间。

阈值间隔决定摊还费用

重排容量为 $L$ 的父窗口花 $O(L)$ 次扫描和移动。重排后，每个孩子的密度接近父窗口密度；它距自身上下阈值的余量为 $\Theta(1/H)$ ，并非固定常数。因此要让同一孩子再次越界，至少需要 $\Omega(L/H)$ 次净增或净减更新，整数舍入只改变常数。

把父窗口的 $O(L)$ 成本计给触发它的孩子中的这些更新，每层每次更新承担 $O(H)$ 。一次更新属于 $H+1$ 个层级，故总摊还移动为

O(H^2)=O(\log^2(n+2)).

叶段自身重排花 $O(\log P)$ ，包含在此界内；扩缩容的 $O(n)$ 成本则由自上次重建以来的 $\Omega(n)$ 次更新支付。这是摊还分析中的实际余量账本，不能把每层的更新间隔误写成 $\Omega(L)$ 后仍沿用同一阈值设计。

直觉

PMA 用分层密度而非指针维持顺序：小窗口的空隙吸收局部插入，持续热点写入才逐级扩大重排范围。相邻层阈值之间的 slack 确保一次大重排后必须积累足够更新才能再次触发，因而保留数组扫描局部性同时支付搬移成本。

局部窗口过密后扩大到首个合法父窗口并均匀恢复空隙 — PMA 的分层密度检查与窗口重排

图截取数组中的一个局部片段，child、parent 分别表示子窗口和父窗口的上阈值；四槽与八槽用于展示重排。例如取两阈值为 $15/16$ 与 $7/8$ ，就有 $4/4>15/16$ 、 $5/8\le7/8$ 。这里没有把示意窗口大小当作渐近分析中的叶段参数。

例子与边界

时间线插入例子

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

边界

单次对抗插入可触发大窗口重排，低尾延迟需去摊还化。墓碑删除若不计入密度会让扫描充满空洞。标签顺序与物理地址不是同一保证；仅有 order-maintenance 标签不能推出连续范围扫描。

阈值层级为何要分离

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

去摊还化可同时维护旧/新布局和迁移游标，每次操作搬一份预定预算的元素；预算及触发阈值还须保证迁移在新布局再次越界前完成。查询在迁移期间须检查两位置或由 forwarding map 定位；只把搬移动作拆开而不维护可见顺序，会出现重复或漏读。

推论与应用

局部重排或区间重建可能移动许多元素，摊还分析用密度阈值的层级间隔证明一个区间在再次重建前接收了足够多次插入。

插入如何寻找重排窗口

在逻辑位置 $i$ 插入时，先定位叶段，计算从该叶到根的每个窗口加入新元素后的密度。即使叶段仍合法，也要检查全部祖先。若路径全部合法，只需在叶段内移动记录；否则以最高越界窗口为起点，取其上方最近的合法祖先并均匀重排。根越界则扩容重建。逻辑次序保持不变，改变的只是物理空隙分布。

例如按上式取 $H=4$ ，容量为 $128$ ，已有 $96$ 个均匀分布的元素，每个八槽叶段有六项。插入一项后，沿途占用数依次为 $7/8,13/16,25/32,49/64,97/128$ 。前四个分别仍不超过各层上界 $1,15/16,7/8,13/16$ ，根却超过 $3/4$ ，必须扩容；只检查叶段便会漏掉这次触发。删除对称地检查整条路径的下阈值，根过稀时缩容，以维护容量与当前元素数同阶。

相邻层的阈值差以及根的扩缩滞回，正是前面 $O(\log^2(n+2))$ 摊还移动账本的条件。更快的界或更小的最坏延迟需要额外结构及相应证明。

参考资料

Alon Itai, Alan Konheim, Michael Rodeh, A Sparse Table Implementation of Priority Queues, ICALP, 1981.
Michael A. Bender, Erik D. Demaine and Martín Farach-Colton, Cache-Oblivious B-Trees, SIAM J. Comput., 2005，§2.3：叶段大小、线性密度阈值、按孩子收费的 $O(\log^2 n)$ 移动证明。
Michael Bender et al., Two Simplified Algorithms for Maintaining Order in a List, ESA, 2002.

形式陈述 ​

两个问题层 ​

密度不变量 ​

阈值间隔决定摊还费用 ​

时间线插入例子 ​

边界 ​

阈值层级为何要分离 ​

插入如何寻找重排窗口 ​