XArrayXArray

将无符号整数索引映射到条目，支持稀疏存储与有序遍历。

核心约束: 按索引的位段分层定位条目。
适用问题: 页缓存等按整数索引管理的稀疏对象。
边界与取舍: 不适合把任意键直接哈希后作为索引；需遵守锁与条目规则。

常见操作#

h 为索引树层数，k 为返回的槽位数；索引为 unsigned long，层数受机器字宽限制。

操作	时间复杂度	条件与说明
按整数索引加载	$O(h)$	沿固定扇出的 radix 路径查找；不要把固定字宽界混作与 n 无关的工程零成本。
存入 / 删除槽位	$O(h)$	可能创建或回收路径节点；内存分配、锁竞争与 RCU 回收另计。
查找下一个存在 / 带标记的条目	与跳过子树和访问节点数有关	标记可帮助跳过子树，不能保证任意稀疏分布下每个结果只需一次访存。
区间迭代	与节点扫描和输出 k 个条目有关	支持保留 xa_state 的遍历接口；多索引条目还需区分范围与别名。

时间与空间#

时间复杂度: 点操作 $O(h)$ ，h 受索引位宽限制
存储空间: 与分配节点和有效槽位数有关

稀疏整数索引的节点开销取决于索引分布；多索引条目不等于每个索引独立存值。

工程中的应用#

1 个案例 · 附源码

Linux Kernel·页缓存v6.12

按文件偏移查找页缓存

页缓存用 XArray 把文件页索引映射到 folio，支持稀疏条目和多页 folio。

附源码片段 · 缓存与复用

基础原理参考资料

Linux 6.12 · XArray整数索引、普通和高级接口、标记与多索引条目。