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

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

PLTree-ff 3 PLTree 50
吞吐量 (MOPS) 4 3 2 1 0 100 0 2 1 0 40 0
5
150
30
20
50
10
osm
face
osm
face
osm
face
planet
planet
planet
planet
genome
genome
genome
(a) 查找操作 (1 线程) uniform (b) 查找操作 (28 线程) uniform osm face genome uniform (d) 插入操作 (28 线程) uniform
(c) 插入操作 (1 线程)
图 18 对比不同溢出缓存设计在不同数据集上查找操作和插入操作的吞吐量

4.7 空间开销测试
在本节中我们首先对比了两个持久化学习索引 PLTree 和 APEX 分别在合成数据集和真实数据集上写入 2 亿
个键值对后的 DRAM 和 PM 的空间开销, 实验结果显示在合成数据集上 PLTree 的存储空间开销要比 APEX 低.
在真实数据集上 PLTree 的 DRAM 空间开销比 APEX 低, 但是 PM 空间开销要比 APEX 要高, 详见表 2.

表 2 PLTree 和 APEX 存储开销 (GB)

索引 uniform (DRAM/PM) face (DRAM/PM)
PLTree 0.495/4.391 0.859/8.934
APEX 0.571/5.379 1.544/5.494

为进一步探究 PLTree 中重复数据写入时存储空间的消耗情况, 我们在真实数据集 face 上构建了一个包含
200M 个 (即 2 亿个) 键值对的索引, 并进行了不同比例的重复数据随机插入实验. 如表 3 所示, 我们分别向索引随
机插入原数据集中 10% 至 50% 的键重复的数据, 即分别对应了额外插入 20M/40M/60M/80M/100M 个重复键值
对. 表 3 的实验结果显示, 随着重复数据写入比例的增加, PLTree 在 PM 上的空间开销相对于原始状态分别增长
了约 4.17%、6.91%、9.33%、11.66% 和 13.95%, 而在 DRAM 中的空间开销也相应增加了约 3.51%、5.82%、
7.87%、9.85% 及 11.81%. 每增加 10% 的重复数据, PM 和 DRAM 空间开销的增量平均约为 2.45% 和 2.08%.

表 3 不同比例重复数据写入 PLTree 时存储空间的消耗情况

存储空间开销增量 10% 20% 30% 40% 50%
PM空间开销增量 (%) 4.17 6.91 9.33 11.66 13.95
DRAM空间开销增量 (%) 3.51 5.82 7.87 9.85 11.81

以上实验结果表明, 在真实数据分布下, PLTree 牺牲了一定的空间存储空间以换取更高的读写性能, 本文提
出的索引设计方案能够一定程度上减轻由于冗余数据导致的空间开销增大问题.

4.8 索引信息统计分析
本节首先分析了加载 1 亿条数据时, PLTree 和 APEX 在不同数据集上的索引高度和叶节点数, 结果如表 4 所
示. PLTree 在大部分数据集上能够构建较少的叶节点, 并且是一棵平衡树, 索引的最大最小高度相同. APEX 是一
颗非平衡树, 在难以拟合的局部键空间可能需要构建更长的遍历路径, 因此查询性能更易受数据分布的影响.

表 4 PLTree 和 APEX 索引高度和叶节点数统计 (最小高度/最大高度/叶节点数)

索引 osm face genome planet uniform
PLTree 4/4/77 941 3/3/126 140 3/3/21 007 4/4/51 814 3/3/683
APEX 2/6/80 524 2/6/113 839 2/6/22 485 2/4/59 713 3/4/16 384

表 5 展示了在索引加载 1 亿个数据时, 不同数据集上 block 总数、溢出缓存总数以及其占 block 总数的比例,
结果显示在 osm/face/genome/planet/uniform 上溢出缓存占比分别 11.87%/12.22%/16.64%/11.83%/0.001 3‰. 这表
明溢出缓存的数量与数据的分布特点有关, 分布越均匀, 溢出缓存的数据量越少. 在此基础上, 我们进一步统计了