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

2334 软件学报 2025 年第 36 卷第 5 期

佳的性能. 这得益于 PLTree 写入优化的溢出缓存以及 DRAM 元数据的合理利用, 避免不必要的 PM 访问, 减小
了 PM 带宽的争用, 降低了同步的开销. 另外, 实验结果显示 APEX 在真实数据集上的混合负载性能表现不佳,
如图 11(b)、图 12(a)–图 12(b)、图 13(a)–图 13(d) 所示, 在 osm 和 face 数据集上, APEX 的混合负载吞吐量要低
于 NBTree, 这是因为 osm 和 face 数据集非线性程度较高、较难拟合, APEX 叶节点中冲突较多, 大量的数据被
插入溢出缓存 stash 中导致了 PM 写放大. 此外, 频繁访问 stash 还降低了 CPU 缓存利用率, 抵消了学习索引模
型搜索带来的优势.
50 50 50 50 60 PLTree
吞吐量 (MOPS) 40 40 40 40 40 APEX
30
30
30
30
uTree
20
20
20
20
20
FPTree
10
10
10
10
0
0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 NBTree
(a) osm (b) face (c) genome (d) planet (e) uniform
图 10 多线程删除操作吞吐量, 横坐标为线程数, 纵坐标为吞吐量

60 60 60 60 100 PLTree
吞吐量 (MOPS) 40 40 40 40 80 DPtree
60
APEX
40
uTree
20
20
20
20
20
0
0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 FPTree
NBTree
(a) osm (b) face (c) genome (d) planet (e) uniform
图 11 多线程读重负载吞吐量, 横坐标为线程数, 纵坐标为吞吐量

60 60 60 50 80 PLTree
吞吐量 (MOPS) 40 40 40 40 60 DPtree
30
APEX
40
20
uTree
20
20
20
20
10
0
0
0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 10 20 30 FPTree
NBTree
(a) osm (b) face (c) genome (d) planet (e) uniform
图 12 多线程读写平衡负载吞吐量, 横坐标为线程数, 纵坐标为吞吐量

40 50 PLTree
吞吐量 (MOPS) 30 40 40 30 60 DPtree
30
40
20
30
APEX
20
20
20
uTree
10
20
10
10
10
0
0
0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 0 10 20 30 0 10 20 30 FPTree
NBTree
(a) osm (b) face (c) genome (d) planet (e) uniform
图 13 多线程写重负载吞吐量, 横坐标为线程数, 纵坐标为吞吐量

图 14 展示了在 28 线程下索引运行倾斜负载的性能. 实验使用 4 个真实数据集在不同的 zipfian 倾斜度
(0.2–0.99) 下进行了 1 亿次点查询的吞吐量测试. 实验结果表明, 除了 FPTree 之外, 其他索引在倾斜度增加时吞吐
量都表现出增高的趋势, 且 PLTree 在不同倾斜度下的查找性能优于其他索引. 较高的倾斜度意味着只有一小部分
热门键被频繁访问, 而大多数键很少被访问. 这说明 PLTree/DPtree/APEX/uTree/NBTree 能够有效利用 CPU 缓存
来加速热点数据的访问. 通过横向对比 4 个数据集中每个索引的吞吐量 (图 14(a)–图 14(d)), 我们可以发现 APEX
的性能容易受到不同数据集分布的影响, 而 PLTree 和 B+树结构的索引查询吞吐量的变化不大. 这说明 PLTree 的
设计能够很好地适应不同的访问模式, 并且性能受数据集分布的影响较小.