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

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

地被写入下一层, 从而降低吞吐量. 另一方面, 当 entry 过大时, 缓存元数据需要维护更多的指纹信息. 这会增加在
访问溢出缓存时缓存未命中的概率. 因此根据实验结果, 我们将 block 大小设置为 256 B, entry 大小设置 768 B.
3.5 2.5 3.5 2.5 osm
吞吐量 (MOPS) 2.5 2.0 2.5 2.0 face

genome
planet
1.5
256
1 280
512
768
512
768
1 280
256
block大小 (B) 768 1.5 block大小 (B) 768 1.5 256 entry大小 (B) 1.5 256 entry大小 (B)
(a) 点查找操作 (b) 插入操作 (c) 点查找操作 (d) 插入操作
图 5 在不同 block 大小和不同 entry 大小设置下进行查找和插入操作的吞吐量

4.3 单线程测试
本节中, 我们对索引进行了单线程实验, 并且使用 5 个不同的数据集分别进行了 1 亿次的点查找/插入/范围查
找/删除操作的性能测试. 如图 6(a) 所示 PLTree 和 APEX 的点查找在所有的数据集上的性能均优于 B+树结构的
索引, 这是因为学习索引根据数据的分布特点构建索引, 能够创建更大的数据节点, 因此具有更扁平的索引结构,
而传统 B+树的结构的索引构建与数据集的分布无关, 叶节点的数量和树的高度随着数据量的增加而增加, 因此查
找遍历时会产生更多的缓存未命中. 相比于其他 4 个真实数据集, PLTree 和 APEX 在合成数据集 uniform 上所有
操作的吞吐量最高, 这是因为在该数据集上键分布均匀且易于模型拟合, 索引高度最低, 此外在叶节点中所产生的
冲突也是最小的, 大部分的键值对存储在叶节点中, 无需频繁访问溢出缓存结构.

PLTree 3 DPtree APEX 1.5 uTree FPTree 4 NBTree
吞吐量 (MOPS) 3 0 2 1 0 1.0 0 2 0
6
0.5

osm
face
planet
planet
planet
planet
genome
(b) 插入操作
(d) 删除操作
(a) 点查找操作 uniform osm face genome uniform osm face genome uniform osm face genome uniform
(c) 范围查找操作
图 6 在 5 个数据集上进行单线程的点查找/插入/范围查找/删除的吞吐量

如图 6(a) 和图 6(d) 所示, 在 4 个真实数据集上进行点查找和删除操作时, PLTree 相比其他索引结构表现更优
异. 以线性模型较难拟合的 face 数据集为例, PLTree 点查找性能分别比 DPtree/APEX/uTree/FPTree/NBTree 提升
了 2.6 倍/1.8 倍/2.3 倍/3.7 倍/2.2 倍. PLTree 在性能上优于 APEX 的原因是, 真实数据集中的键呈非线性特征, 导
致学习型索引中有较多数据需要存储在溢出缓存中. 而 PLTree 通过块元数据结构提高了查找性能, 可以在访问叶
节点之前先通过访问块元数据判断叶节中键是否存在, 若不存在则可直接跳过叶节点的访问, 从而避免了额外的
PM 访问. 相比之下, APEX 使用的 probe-and-stash 技术需要先在叶节点中进行线性探测来判断键是否存在, 然后
才会在溢出缓存 (stash) 中查找键, 从而产生了不必要的 PM 访问. 此外, 在查找溢出缓存中的键时, PLTree 的缓存
元数据结构中每个缓存行可以存储 48 个指纹信息, 而 APEX 的元数据结构中每 2 个缓存行只存储了 15 个指纹信
息, 因此 APEX 比 PLTree 更容易产生更多的缓存行访问. 在合成数据集 uniform 上 PLTree 的删除操作的吞吐量
与 APEX 相当, 点查询的吞吐量接近于 APEX, 这是因为 uniform 数据集中的数据是线性分布的, 大部分的数据都
存储在叶节点中, PLTree 在访问叶节点之前需要额外先访问块元数据, 产生了一定的性能损失.
如图 6(b) 和图 6(c) 所示, PLTree 在所有数据集上的插入和范围查找性能都优于其他索引. 以插入操作为例,
在 uniform 数据集上, 相对于 DPtree/APEX/uTree/FPTree/NBTree, PLTree 的性能提高了 3.2 倍/2.2 倍/8.4 倍/6.5 倍/
3.6 倍. 这是因为: (1) PLTree 避免了在溢出缓存中进行键的唯一性检查, 从而缩短了插入操作的查找路径; (2) 每次
插入和更新操作只发生在叶节点, 减少了冲突严重时将新插入的数据写入溢出缓存的频率; (3) PLTree 采用了写
优化的溢出缓存结构, 当叶节点 block 满时, 采用批量写入的方式将数据移入下一层, 从而减小了 PM 的写放大.