PDF Name Tree / Number Tree：索引结构、性能与工程化用法（小众硬核）

当 PDF 需要维护一份很大的「键到对象」映射时（比如上千个命名目的地、上万条页面标签、成百上千个嵌入附件），普通字典不再合适。为兼顾可扩展性与查找效率，PDF 规范引入了两种树形索引：Name Tree 和 Number Tree。这两个结构在实际项目里很少被直接手写，却深刻影响加载速度、内存占用与兼容性。

1. 两种树到底是什么

Name Tree 以经过排序的字节序列作为键（通常是名称或字符串）；Number Tree 以整数作为键。两者本质都是分块有序表的树形索引，类似 B 树：中间节点负责范围划分，叶子节点保存成批键值对。

1.1 典型结构示意

% Name Tree（伪示例）
12 0 obj
<< /Type /Catalog
   /Names << /Dests 20 0 R /EmbeddedFiles 30 0 R >>
>> endobj

20 0 obj
<< /Type /Names
   /Kids [21 0 R 22 0 R]
   /Limits [(Chap-001) (Chap-200)]
>> endobj

21 0 obj
<< /Names [(Chap-001) 101 0 R (Chap-050) 102 0 R]
   /Limits [(Chap-001) (Chap-050)]
>> endobj

22 0 obj
<< /Names [(Chap-120) 103 0 R (Chap-200) 104 0 R]
   /Limits [(Chap-120) (Chap-200)]
>> endobj

/Limits 表示当前节点覆盖的最小键与最大键，/Names 是叶子节点的键值对。Number Tree 与此类似，只是键是整数，字段名为 /Nums。

2. 它们会出现在哪里

• /Names > /Dests：命名目的地，供内外部跳转锚点使用。
• /Names > /EmbeddedFiles：嵌入文件清单，附件面板依赖它组织与检索。
• /PageLabels（Number Tree）：页面标签映射页码到样式规则，例如 i, ii, iii, 1, 2, 3 或自定义。
• /ViewerPreferences 等扩展映射：一些实现会通过树组织大量配置或脚本标识。

3. 为什么不用普通字典

字典在键数量非常大时会出现两个问题：一是内存与解析成本线性增长；二是增量更新难以保持局部性。树结构把数据分块，阅读器可以有选择地加载，只解析命中路径上的节点，显著降低初次打开与跳转时的 I/O 与解析压力。

4. 查找与复杂度

从根沿着 /Kids 下降，根据 /Limits 判断应进入哪个子节点，最终命中叶子节点的 /Names 或 /Nums 数组。理论上查找是对数级，但受节点分块大小影响。一个合理的叶子批量通常在几十到几百对键值项之间，既减少对象数量，又避免超大数组。

5. 生成策略与参数取舍

5.1 键排序与规范化

• Name Tree 键必须按字节序排序。涉及 Unicode 时建议统一成 UTF-16BE 再比较，避免平台默认编码带来的不一致。
• Number Tree 键必须严格按升序排列，且不重复。

5.2 批量大小与多层拆分

当叶子里的 /Names 或 /Nums 超过某阈值时，拆分为若干叶子并挂到新的中间节点。阈值可以根据平均键值长度与阅读器表现微调。例如：

leaf_target = 128  % 单个叶子存放的键值对目标数量
if items > 2 * leaf_target:
    split into ceil(items / leaf_target) leaves
    create an internal node with /Kids pointing to leaves

5.3 限定范围 /Limits 的维护

每次拆分或合并后，更新节点 /Limits 的最小与最大键。很多阅读器会依赖该范围快速剪枝；错误的范围会导致查找失败或全量回退扫描。

5.4 对象复用与跨页引用

当键对应的目标对象分布很广时，尽量提前稳定对象编号与引用，降低增量更新后树的大幅改写。对于嵌入文件，可将文件规格字典与流对象固定在独立对象空间，树只改叶子数组，减少写放大。

6. 增量更新的友好做法

1. 优先选择在叶子层追加或替换，避免频繁调整中间层的 /Kids 结构。
2. 当叶子溢出阈值时，再一次性分裂；设置稍高的阈值以减少连续版本中反复分裂合并。
3. 把新增键集中写入一个新的叶子对象，通过替换父节点的 /Kids 引用实现最小改动。

7. 调试与可视化方法

• 用结构查看工具枚举树节点，核对 /Limits 是否覆盖正确边界。
• 抽样验证查找：随机选择几个键，沿节点路径手工确认命中过程与目标对象。
• 对 Name Tree 进行编码一致性检查，确保排序与比较算法一致。

# 示例：打印 PageLabels 的 Number Tree（伪命令）
qpdf --json your.pdf | jq ".objects[] | select(.value.PageLabels != null)"

8. 兼容性与阅读器差异

大多数现代引擎对两类树都有良好支持，但在以下细节上可能存在差异：

• 极端大数组：某些阅读器对超长的 /Names 或 /Nums 数组会退化为线性扫描，建议控制叶子大小。
• 边界键处理：若 /Limits 不精确，部分实现会错误跳过包含边界的叶子，表现为偶发找不到某些键。
• 编码混用：Name Tree 同时混用多种编码方式时，排序与比较存在实现差异，建议在生成端统一。

9. 典型应用的工程要点

9.1 命名目的地 Dests（Name Tree）

• 键命名规则建议「章节短码」加递增编号，避免超长键影响叶子容量。
• 目标对象尽量使用间接对象，便于增量更新。
• 与目录书签配合时，保持命名与标题映射的一致性，便于外部跳转稳定复用。

9.2 PageLabels（Number Tree）

页面标签为大规模文档提供人类友好的编号，如前言使用罗马数字，正文使用阿拉伯数字。工程上建议按「段起始页」写入稀疏映射，而非为每一页都写键值，既简化树也更直观。

% PageLabels 片段示例（稀疏定义，起始页从 0 计）
<< /PageLabels
   << /Nums [ 0 << /S /r >>   10 << /S /D /P (Chapter ) >> ] >>
>>

9.3 EmbeddedFiles（Name Tree）

• 文件名统一大小写与规范化，避免重复键。
• 附件很多时，按照首字母或哈希前缀分桶，生成多叶子结构。
• 面向检索的场景可同步维护一个可选次级索引，用于关键词到附件名映射，但注意不要让自定义结构干扰标准树。

10. 大规模场景的性能基线

当键达到数万量级时，可以设立一套简单的性能基线：

• 首次打开时间 FPV 不明显上升；
• 随机查找 100 次的平均耗时稳定；
• 增量写入 1000 个新键，引入对象数量在可控范围内（例如 < 1.5 倍叶子对象增量）。

这类基线能帮助在不同阈值配置下做 A/B 对比，找到适配项目的叶子容量与分裂策略。

11. 常见坑位与修复

1. Limits 与实际键不一致：重建父节点的边界，或在生成端统一通过程序计算边界值，严禁手写。
2. 键未排序：Name Tree 与 Number Tree 都要求严格排序，任何乱序都会触发查找失败或全量回退。
3. 增量更新孤儿叶子：替换父节点 /Kids 时遗漏旧叶子，导致树结构形成断链。修复方式是重构该分支并更新引用。

12. 实战小模板：从一组键生成 Name Tree

# 伪代码
def build_name_tree(pairs, leaf_target=128):
    # pairs: List[(name_bytes, obj_ref)] 已按字节序排序
    leaves = []
    for i in range(0, len(pairs), leaf_target):
        chunk = pairs[i:i+leaf_target]
        node = make_leaf_node(names=chunk,
                              limits=(chunk[0].key, chunk[-1].key))
        leaves.append(node)

    while len(leaves) > 1:
        parents = []
        for i in range(0, len(leaves), leaf_target):
            kids = leaves[i:i+leaf_target]
            parent = make_internal_node(kids=kids,
                                        limits=(kids[0].limits.min, kids[-1].limits.max))
            parents.append(parent)
        leaves = parents

    return leaves[0]  # root

这个模板体现了构建与逐层合并的基本思路。工程中还需要处理对象编号、间接引用、以及与现有树的合并策略。

13. 测试清单（可直接落地）

• 键集中度：极短键与极长键混合的边界表现。
• 跨编码：仅使用一种确定编码路径；验证排序与比较。
• 增量扩容：从 1 万键扩展到 5 万键的叶子分裂稳定性。
• 随机查找：命中首叶、中间叶、末叶与不存在键的回退逻辑。
• 阅读器对比：在至少三种实现上测试跳转与附件面板表现。

结语

Name Tree 与 Number Tree 是 PDF 世界里低频但关键的基础设施。它们让超大映射在体积、解析与增量写入之间取得平衡。理解其结构与生成策略，可以显著提升大型文档的可维护性与用户体验。多数项目不必手写这些树，但当你需要构建定制化的目录、海量附件索引或复杂的页面标签体系时，这两把「小众的扳手」会非常顺手。