Maple TreeMaple Tree
以多路树组织不重叠的整数索引区间。
- 核心约束
- 节点通过范围边界把索引空间分配给孩子。
- 适用问题
- VMA 等区间索引及区间迭代。
- 边界与取舍
- 节点类型、区间修改与并发访问规则复杂。
常见操作#
n 为树中记录的范围数，h 为树高，k 为操作涉及的范围数；成本针对 Linux 6.12。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 按索引查找范围 | 沿多路树下降；节点内部槽位数由内核实现固定。 | |
| 插入 / 覆盖范围 | 与树高、覆盖范围数及拆分有关 | 宽区间更新可能影响多个已有范围，不能统一写成一次 。 |
| 删除一个已存在范围 | 与定位、合并和重平衡有关 | 可能触发节点分配或释放；RCU 回收成本另计。 |
| 范围迭代 | 与访问节点及输出范围数有关 | 使用 mas_state 延续遍历状态，避免每次从根重新找起点。 |
| 寻找空隙 | 由空隙元数据和搜索范围决定 | 仅相应分配树配置维护 gap 信息。 |
时间与空间#
- 时间复杂度
- 点查找随树高增长；范围修改按实际影响范围计费
- 存储空间
固定节点容量下按节点与范围计存储；预分配、并发锁和 RCU 生命周期另计。
工程中的应用#
1 个案例 · 附源码Linux 用 Maple Tree 管理进程的 VMA，将虚拟地址区间关联到映射对象。
附源码片段 · 内存管理
基础原理参考资料
Linux 6.12 · Maple Tree范围映射、常规 API、advanced API、预分配和 gap 查找。