1 基础原理

xarray¹主要由 xarray 结点组成，xarray 结点主要由槽位（即指针）、父节点指针等组成。xarray 根据整型索引组织 xarray 结点实现对目标值的高效存、查、删操作。

此文以

• 存查删等流程对应源码²
• 具体实例 —— xarray 结点槽位数 64，索引及目标值对(0, $y_0$)、(1, $y_1$)、(4095, $y_{4095}$)
  方式体会 xarray 基础原理。

1.1 存查删

在一个空 xarray 中依次新增 (0,$y_0$)、(1,$y_1$) 得如下图示。

索引 0 和 1 对应目标值分别由同一结点的 0 和 1 槽位指向。体会源码中规律，范围索引 [0…63] 对应目标值都将由该结点依次指向，此时 xarray 层级高度为 1，只有叶子结点。

续增 (4095, $y_{4095}$) 图示如下。

通过续增 (4095, $y_{4095}$) 后可得出 xarray 新增元素大概分以下几步

• 根据索引计算层级高度，若新索引对应层级高度超过原层级高度，则分配新顶层结点，并建立与原顶层结点的父子关系
• 分配子结点并与其上层结点建立父子关系，直到在叶子结点上将目标值映射到相应槽位上

4095 是层级高度为 2 的 xarray 能容纳的最大索引 —— 当新增 (64, $y_{64}$)时，xarray 的层级高度就会被扩展为 2。

根据索引查询目标值与新增过程遵循相同规则。如查询索引 4095, 64 对应目标值的流程分别为如下图示。

现将上文根据源码结合特殊例子对 xarray 的体会加以总结。此文认为 xarray 根据索引映射目标值涉及以下要点

• xarray 结点层级高度
• 索引在 xarray 各层级结点的槽位号

即对于任意整型索引 $inde{x}_x$ 与 xarray 结点层级高度 $levels$ 和在各层槽位号 $slo{t}_{ofCurrentXNode}$ 的规则为

• $$levels=lo{g}_{slots}max(inde{x}_x,inde{x}_{MaxofXarray})$$
• $$slo{t}_{ofCurrentXNode}=(inde{x}_x>>(lo{g}_{2}slots\ast levelofCurrentXNode))modslots$$

其中的 $slots$ 为 xarray 结点槽位数，这便是 xarray 根据索引值映射目标值的基础规则。

最后来看看删除，xarray 删除可以看作由查询和收缩两个流程组成。收缩指删除某目标值后尝试释放 xarray 结点的过程 —— 让 xarray 恢复到插入该目标值前的样子。

以删除上文索引 4095 为例作如下图示。

删除索引 4095 后，整个 xarray 恢复到了插入索引 4095 前即插入索引 [0…1] 之后的样子。

结点删除条件为

• 结点（包括顶层结点）槽位全为空闲
• 顶层结点只有 0 槽位非空闲

1.2 多索引

xarray 的多索引是指能用多个索引映射同一个目标值。其基础原理是：索引以“多索引数”向下对齐。如选择多索引数为 $2^{order}$ 时，则任意索引 $inde{x}_x$ 在各结点上所将映射槽位号为
$$slo{t}_{ofCurrentXNode}=((inde{x}_{x}mod{2}^{order})>>(lo{g}_{2}slots\ast levelofCurrentXNode))modslots$$

1.3 新遍历

遍历是指逐一迭代出所有叶子结点上目标值的过程。从顶层结点开始逐一遍历子 xarray 是一个比较直观的实现方法，该方法是一个递归过程。

考虑具体实现的简单性，此文提倡

• 找到 xarray 最大索引 $inde{x}_m$
• 查询索引范围 [0, $inde{x}_m$] 对应目标值
  来实现遍历 —— 如此遍历就复用了查询流程。

以 xarray 各层级结点最右侧有值槽位向下层索引子结点方式可找到 xarray 中的最大索引。

寻找最大索引所需遍历最大次数将趋近等于层级高度乘以槽位数。如 xarray 结点槽位为 64，层级高度为 5 时，最大索引遍历次数趋近为 320 = 5 * 64³。

得到 xarray 中的最大索引后，遍历就变成了对范围索引 $[0,inde{x}_m]$ 的连续查询。

2 优劣浅析

• 对聚集型索引，xarray 比诸如哈希或二叉树更具缓存友好性⁴，动态扩展比动态数组具更高效率⁵
• xarray 有多叉树特色，容纳相同数据量时层级高度比二叉树低，所以其增、查、删的平均效率比二叉树高⁶，另外 xarray 的增、删操作的内部自平衡比二叉树内部自平衡简单
• xarray 结点更可能⁷比二叉树结点复杂，由此容纳相同数据量时可能会占用更多内存
• xarray 应用场景不如二叉树丰富，其适用于具（连续）整型索引场景

如果其中优劣在实际中不是问题，则可忽略随意选择。

3 简易实现

如何有效发现上述篇幅描述是否有误呢⁸？ —— 按照以上描述简易实现一个 xarray，正好内核版本中 xarray 源码不能直接拷贝到用户空间使用⁹

• xarray.c
• xarray.h

除 xarray 基础原理相关代码外，此文还为其编码了结点缓存相关代码，用于加持 xarray 的快速性。

• pageca.c
• pageca.h
• memca.c
• memca.h

---

1. xarray 是 Linux radix tree 的替代者 ↩︎

2. linux-6.14/lib/xarray.c ↩︎

3. 实际遍历最大次数应当是第 5 层第一个索引出现时即 318 = 3 * 64 + 2 * 63，可忽略，大多数情况无需处理到如此细腻层次 ↩︎

4. 相邻索引操作涉及访问 xarray 相同结点，而 hash/rbtree 尤其是hash 往往不具该特色 ↩︎

5. xarray 不用丢掉旧内存而把旧值复制到新值上，MMU 地址映射关系也不用全部更新 ↩︎

6. 如当 xarray 结点槽位数为 64，存 2GiB 数据时，xarray 层级高度为 5，二叉树层级高度为 30 ↩︎

7. xarray 能容纳其他功能，所以可能需要结点中包含更多的成员来支撑；如果能够精简 xarray 结点的实现，xarray 结点也不一定比二叉树结点复杂 ↩︎

8. 夸夸其谈半天好像已经懂完了一样 ↩︎

9. 最大的阻碍应该是内核使用 xarray 结点地址低 2 位用作了判断该结点是否位中间结点等用途 —— 内核可保证低所分配地址以 4 字节对齐，而用户程序中的内存分配不能保证。 ↩︎