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

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

100 100 100 100 PLTree
吞吐量 (MOPS) 50 50 50 50 DPtree
APEX
uTree
0
0
0
0
0.2 0.4 0.6 0.8 0.99 0.2 0.4 0.6 0.8 0.99 0.2 0.4 0.6 0.8 0.99 0.2 0.4 0.6 0.8 0.99 FPTree
NBTree
zipfian zipfian zipfian zipfian
(a) osm (b) face (c) genome (d) planet
图 14 在 28 线程不同倾斜负载设置下 4 个真实数据集上的查找操作吞吐量

4.5 索引加载时间
本节实验对 6 个索引的加载时间进行了评估, 我们使用了 1 亿个键来构建索引, 并记录了构建索引所需的时
间. 由于 DPtree、FPTree、uTree 和 NBTree 没有实现批量加载功能, 因此我们使用它们的插入函数来进行索引构
建. 图 15 显示了在 6 个数据集上构建索引所需的时间. 实验结果表明, 在所有数据集上, PLTree 的加载时间最短
(5.3–12.6 s), 其次是 APEX (8.6–26.2 s). 相比之下, 传统的 B+树结构索引则需要更长加载时间, 平均约 94–324 s. 由
于 PLTree 采用了 O(n) 复杂度的分段算法来构建索引, 因此具有最快的加载速度. 即使在较难拟合的 face 数据集
上只需约 12 s, DPtree/APEX/uTree/FPTree/NBTree 的加载时间分别是 PLTree 加载时间的 7.4 倍/2.0 倍/
26.6 倍/13.0 倍/8.5 倍, 进一步证明了 PLTree 在索引构建方面表现出的高性能.

300 PLTree PLTree PLTree-local
批量加载时间 (s) 200 APEX 延时 (ns) 100
DPtree
uTree
50
100
FPTree
0
osm face genome planet uniform NBTree 0
图 15 不同数据集上索引的加载时间 图 16 不同数据集上内部节点查找的平均延时
此外, 实验结果还显示 PLTree 和 APEX 的索引加载时间受数据分布的影响. 数据集的非线性程度越高, 索引
的加载时间越长. 例如, 线性分布的 uniform 数据集所需的加载时间最短 (PLTree 为 5.3 s, APEX 为 8.6 s). 而在真
实数据集上, APEX 相比 PLTree 的加载所需时间更长. 在 osm 数据集上, APEX 的索引加载时间约为 PLTree 加载
时间的 2.1 倍. 这是因为 APEX 在加载键时需要同时计算成本模型估计索引的查找/插入平均延时, 并选择合适的
分割数量, 从而导致更多的计算开销. 因此, APEX 在加载真实数据集时比 PLTree 需要更多时间.

4.6 索引设计对性能影响

4.6.1 两阶段构建索引
PLTree 采用了两阶段的方法构建, 通过消除内部节点中的局部查找来提高性能. 我们首先对比了表 1 中所示
的 5 个索引, 在不同数据集上进行 1 亿次查询时, 内部节点遍历的平均访问延时 (由于 DPTree 采用了分层树的结
构, 所以没有被纳入比较范围).

表 1 内部节点平均查找延时 (ns)

数据集 PLTree APEX uTree FPTree NBTree
osm 3.03 26.60 482.67 853.44 315.68
face 3.01 17.71 483.70 852.56 315.92
genome 3.01 9.10 486.01 854.58 315.32
planet 3.00 13.84 482.19 858.37 315.81
uniform 3.03 6.73 481.69 848.67 315.87

从表 1 的结果来看, PLTree 在所有测试数据集上的平均查找延时均低于其他索引, 最低仅为 3 ns. 并且内部节
点遍历的平均延时几乎不受数据分布的影响. 原因在于 PLTree 消除了内部节点中的局部查找, 每层只需访问一