Page 427 - 《软件学报》2025年第5期

张志国 等: PLTree: 一个高性能持久化内存学习索引 2327

块元数据存储在 DRAM 中, 以 64 B 地址对齐的方式组织成数组. 每个块元数据的大小为 32 B, 其中包含以下字
段: (1) 字段 next (6 B) 存储了指向缓存元数据的地址. (2) 字段 lock (1 bit) 和字段 version (31 bits) 用于实现索引的乐
观读写并发控制. (3) 字段 v (1 B) 存储了当前元数据的版本用于索引恢复时元数据的重建. (4) 字段 num (1 B) 用于记
录叶节点中对应 block 中存储的键值对数量. 当 block 中插入一个新的键值对时, num 原子加 1; 当 block 中的数据被
清空时, num 原子置为 0. (5) 字段 ptr (5 B) 用于存储指向 PM 中缓存结构的地址 (由于缓存结构地址按 256 B 对齐,
地址的低 8 位为 0, 因此 ptr 只需使用 5 B 存储地址). (6) 剩余的空间 (15 B) 用于存储块数据中键的指纹信息.
与溢出缓存一样, 缓存元数据只有在产生数据溢出时才会被创建, 根据溢出数据的多少动态创建元数据层.
每一层的缓存元数据以 64 B 地址对齐的方式组织成 meta 数组, 每个 meta 的大小为 64 B. 其中包含以下字段:
entryPtr (8 B) 存储了溢出缓存中的对应 entry 的持久化内存地址, next (8 B) 存储了指向下一层的元数据的指针,
剩余的 48 B 用于存储溢出缓存中对应 entry 中键的指纹信息.

3 索引操作

3.1 索引的构建
为了消除内部节点中的局部搜索, 受到 DLIL 和 PGM 的启发, PLTree 采用结合自底向上和自顶向下方法构
建索引. 首先, 通过自底向上的方法构建索引布局, 根据完整的数据集划分累积分布函数, 能够更好地根据数据分
布划分内部节点, 内部节点展开分支数量按照键的局部分布特点合理设置. 其次, 采用算法复杂度为 O(n) 的分段
算法 FSW [38] 进行键空间的分段划分, 通过设定合理的分段误差, 可以在保证索引布局合理性的同时, 加快索引的
构建速度. 最后, 结合了自顶向下的方法构建索引, 消除了内部节点中由局部搜索导致的额外 PM 访问开销.
具体的做法是: (1) 采用自底向上的方法根据数据分布获得索引的布局 (每一层分段的键集合和每个分段范围包
含的子节点数), 在索引每一层使用 FSW 算法对关键字升序排列的键空间进行分段. FSW 算法是一个时间序列分段
算法, 具有线性的时间复杂度和常量的空间开销, 它使用贪心思想在满足误差的前提下划分键空间, 使每个分段内的
数据点可以被近似为一条直线, 并且尽可能包含更多的数据点. (2) 得到索引布局后使用自顶向下的方法进行索引构
建, 在内部节点中根据索引布局得到的分支数将节点范围平均划分为若干个槽位, 每个槽位的两个分段端点代表了其
指向的子节点的数据范围, 然后采用线性插值的方法计算每个子节点线性模型参数: 通过槽位的两个分段端点
(minkey 和 maxkey) 与分支数 n 来计算下层子节点的线性模型的斜率 slope=n/(maxkey – minkey). 在下层子节点中,
每个槽位的范围为 (minkey+k/slope, minkey+(k+1)/slope], 其中 k 为槽位的序号且 n > k ⩾ 0 . 因此在内部节点中查找
键 key 时可以通过线性模型 pos=⌊(key – minkey)·slope⌋ 预测节点中槽位的准确位置来定位下层子节点, 而无需在节
点中进行横向的局部搜索, 避免了额外的 PM 访问. 其中该线性模型的斜率为 slope, 截距为 – minkey·slope.
图 3 是索引操作步骤, 为方便展示, 叶节点每个数据块大小设置为 3, M(a, b) 代表第 a 层的第 b 个节点的模型.

图 3 索引操作步骤