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

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

accelerated query by leveraging metadata in DRAM, and (3) a log-based hierarchical overflow buffer structure tailored to PM
characteristics to optimize writing performance. The results show that, compared with the existing persistent memory indexes (APEX,
FPTree, uTree, NBTree, and DPTree), PLTree achieves significantly better performance in index construction 1.9× to 34× across various
datasets. In single-threaded scenarios, PLTree exhibits an average query and insertion performance improvement of 1.26× to 4.45× and
2.63× to 6.83×, respectively. In multi-threaded scenarios, PLTree surpasses the baseline by up to 10.2× and 23.7× in query and insertion
performance, respectively.
Key words: learning index; persistent memory (PM); persistent memory index; database

随着数据规模的快速增长, 现代数据库受到 DRAM 高成本和低容量的限制 [1] . 持久化内存 (persistent memory,
[2]
PM) 的出现为解决这一问题提供了新的解决思路. 同时, PM 自身的特性也给基于 PM 的数据库研发带来了新的
挑战. 例如, 在目前唯一商用的 PM 产品 Optane DCPMM 上进行应用开发时需要考虑以下因素 [3] : 不对称的读写
延时 (写入较慢); 有限的读写带宽资源; CPU 缓存行的访问粒度 (64 B) 与 3D-XPoint 的存储介质访问粒度 (256 B)
不匹配导致的读写放大; 持久化操作开销等. 近年来, 研究者针对 PM 特性优化了数据库索引结构, 涵盖了基于树
结构 [4−14] 和哈希结构 [15−20] 等多种类型的持久化内存索引技术. 然而, 这些基于传统数据结构的研究在设计持久化
内存索引时未充分考虑数据的分布模式, 导致索引的性能不佳. 例如, 在基于 B+树结构的持久化内存索引中, 为了
匹配 PM 介质的访问粒度, 叶节点通常设置为固定大小 (如 256 B). 索引高度与数据规模及叶节点大小有关, 由于
未充分利用数据分布特点, 随着数据量的增加, 叶节点数量也随之增加, 这导致需要构建更高的树来完成数据索
引, 导致性能下降.
最近提出的学习索引技术 [21] 能够根据数据分布特征构建更为扁平的索引结构, 从而显著降低搜索成本. 其性
能优势主要体现在两方面 [22] : 一方面, 学习索引相比传统 B+树能创建更大的数据节点, 容纳更多数据, 进而减少
索引层级和查询路径长度; 另一方面, 学习索引通过内部模型预测键值大概的存储位置, 在节点内查找时只需在预
测位置附近查找, 相比于遍历整个节点产生的开销, 利用简单模型定位的计算开销要小得多. 因此, 在 PM 上构建
基于数据分布的学习索引成为进一步提升基于 PM 的数据库索引性能的研究方向之一. 然而, 当前主流学习索引
多基于 DRAM 设计, 直接应用于 PM 时会产生额外开销 [23] . 最近的工作 [1,24,25] 针对这一问题进行了探索, 对学习索
引结构进行了调整以适应 PM 特性, 实现学习索引的持久化, 依据数据分布特点建立更扁平的索引结构, 借助模型
搜索来减少不必要的 PM 访问. 然而, 这些尝试尚未完全解决移植后索引存在的性能问题:
首先, 学习索引的性能与数据分布特征密切相关, 在真实负载上读写性能较差. 有研究 [26] 指出, 当从合成数据
集切换到真实数据集时, 学习索引的性能显著下降. 因为真实数据集通常具有非平滑和非线性的特性, 可能导致叶
[1]
节点内数据冲突增加, 即不同键值可能定位到同一位置. 为解决此问题, APEX 和 PLIN [24] 在叶节点无法容纳冲突
时需要采用溢出缓存结构存储冲突数据, 但这会带来额外的访问开销, 例如查找时不论目标键是否存在于叶节点,
都必须先在叶节点访问至少 1 个 PM 块 (256 B), 然后决定是否继续搜索溢出缓存. 当目标键不存在时, 需要完整
遍历叶节点预测位置和对应的溢出缓存区域, 导致读性能的下降. 同样, 在插入操作中, 也需要在叶节点和溢出缓
存中进行键的唯一性检查, 最坏情况下需完整遍历预测位置和缓存区域, 影响写入性能.
其次, 由于模型预测误差引起的局部搜索也会引起额外的 PM 访问. 学习索引中的局部搜索是指在查找时, 由
于模型预测不一定能完美给出准确的预测位置, 需要在预测位置的附近再进行一次搜索. 以 PLIN 为例, 其构建内
部节点时使用的分段线性逼近算法 (OptimalPLR) [27] 基于固定误差对索引各层数据进行分段, 索引内部节点中的模
型存在预测误差, 需要在误差范围内进行局部查找来定位下一层的子节点, 这一操作增加了内存的访问. 而 APEX
和 APLI [25] 采用自顶向下的方法构建索引, 内部节点中没有局部搜索问题, 但是无法保证叶节点中模型的误差上
限. 另外, 在面对难以用简单模型拟合的局部键空间时, 可能会导致更长的查找路径.
由于 PM 的访问开销比 DRAM 大, 在 PM 中, 上述问题对性能的影响会被放大, 并最终影响持久化学习索引
的读写性能. 为此, 本文提出了持久化学习索引 PLTree. 它针对 PM 的特性进行设计, 确保崩溃一致性、支持索引
恢复, 优化了面对真实数据时的读写性能. 本文的主要贡献如下: (1) 优化局部搜索, 减少 PM 访问次数. PLTree 采
用两阶段索引构建方法, 在索引构建过程中消除了由于内部节点中模型预测误差导致的局部搜索, 减少了 PM 访