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

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

证计算和学习的效率, 大多数学习索引通常采用多个简单模型的组合来近似 CDF.
学习索引中存在局部搜索的问题, 即模型只能预测键的大概位置, 需要在预测位置附近进行局部搜索以确定
准确位置. 在一些学习索引中 (如 APEX, ALEX, FITing-Tree [30] , ALERT [31] 等) 模型误差导致的局部搜索只存在于
叶节点, 而其他一些索引 (如 PLIN, PGM, XIndex [32] , FINEdex [33] 等) 局部搜索不仅存在于叶节点还存在于内部节
点. 为改善局部搜索性能, PGM、FITing-Tree 以及 ALERT 等工作通过设定模型误差上限, 并结合二分查找策略来
优化. ALEX 则采用指数搜索方式提升叶节点内的局部查找效率. APEX 和 PLIN 限制了叶节点内的查找距离, 从
而避免过多的 PM 访问. 此外, LIPP [34] 和 DILI [35] 提出了消除内部节点与叶节点中局部搜索的方法. LIPP 采用了最
小化冲突的模型消除局部搜索, 当同一位置产生多个键冲突时, 创建一个新的子节点来覆盖冲突的数据, 将相同位
置的键存入子节点中, 并将原先的键值对设置为指向子节点的指针, 以较长的遍历路径为代价消除局部搜索.
DILI 通过两阶段索引构建和局部优化的方法消除了内部节点和叶节点内的局部搜索.
目前, 构建学习索引主要有两种方法: (1) 自底向上法. 该方法设定一个固定的误差, 使用分割算法将有序排列
的键空间切割为若干个互不相交的有序子集, 作为叶节点中的数据分区. 在构建上层的内部节点时, 将所有叶节点
分段边界键汇总并作为新的划分对象, 递归使用分割算法将边界键划分到上层的不同内部节点中, 直到形成根节
点 [24,29] . 此外, 还可以借助叶节点边界键构建 B+树或 Radix 树来索引叶节点 [30,31] . (2) 自顶向下法. 该方法从根节
点开始, 学习整个数据集 CDF 的大致轮廓, 然后判断是否进一步向下拆分子节点. 若节点需要向下拆分, 则使用多
个子节点模型来细化分割 CDF 曲线, 拟合其局部数据分布, 并在该节点内训练一个键到子节点的模型. 递归执行
直至满足叶节点的划分条件为止, 然后训练一个模型来预测叶节点中键的位置.
例如, PGM、PLIN 等采用的是自底向上的索引构建方法. 该方法的优点在于: (1) 可以通过一次性顺序扫描数
据集快速完成数据分区与模型拟合. (2) 依据预设的误差上限来划分每个节点, 确保在最差情况下, 节点内模型的
误差仍能得到控制. (3) 能够根据完整的数据集划分 CDF, 从而更好地理解关键字的分布, 并据此合理地划分子节
点. 该方法的缺点为: 节点内的模型存在预测误差, 因此查找操作需要在内部节点中进行局部搜索才能确定下一层
节点, 增加了查找开销. 相比之下, 自顶向下方法在构建索引时, 依据预设分支数量精确划分内部节点, 因此查找子
节点时, 无需在内部节点中执行局部搜索. 但是构建索引时通常需要预先设定索引的分支数量, 不够灵活且得到的
数据分区可能会最终降低叶节点模型的准确性. 以 ALEX 和 APEX 为例, 它们采用自顶向下的方法构建索引, 通
过成本模型估计索引的查找/插入平均延时, 并选择合适的子节点分割数量, 利用均匀数据分区的方式向下分割节
点. 自顶向下的分割方法无法在学习阶段感知数据分布的整体情况. 例如, ALEX 和 APEX 在节点向下拆分的过程
中, 将子节点的数量固定为 2 的指数, 这意味着在构建索引时, 不能根据实际数据分布情况动态调整最优的分支数
量分割 CDF. 这可能会导致索引布局不能很好地近似某些特定的数据分布. 另外, 自顶向下的方法也无法确保叶
节点内预测误差的上限. 如果分区粒度过粗, 叶节点中的线性模型可能无法很好地拟合某些范围内的 CDF. 在这
种情况下, ALEX 的叶节点中可能产生更大的误差, 导致更大范围的局部搜索; 而 APEX 的叶节点中可能会引发更
多的冲突, 导致更多数据被写入溢出桶中.
为解决局部搜索的问题, DILI 采用了两阶段构建索引的策略: 首先, 在第 1 阶段, 根据数据分布使用贪心算法
自底向上计算内部节点和叶节点的搜索成本, 并在所有可能的索引布局中寻找一个既能使搜索成本最小又能有效
体现键分布特点的最优索引布局方案. 然后, 在第 2 阶段, 根据得到的索引布局, 采用自顶向下的方法构建索引. 根
据布局中每个节点的分支数量均匀地划分子节点范围, 通过自顶向下方法构建索引, 消除内部节点的局部搜索开
销. 然而, DILI 在构建索引布局时需要遍历所有可能布局以确定搜索成本最低的那一种, 这导致了较高的计算开
销. 同时, 每层使用的贪婪合并算法代价较高, 其时间复杂度为 O(nlog n) . 此外, DILI 在构建过程中, 从底层开始创
2
建线性回归模型, 并使用线性回归计算模型参数. 每次合并节点时, 都需要计算节点中所有数据 (键-位置) 之间平
方差的最小值, 以调整模型的斜率和截距. 这导致 DILI 的索引构建时间较长.

2 索引结构

PLTree 是 DRAM/PM 混合架构的持久化学习索引, 其结构如图 1 所示, 其中内部节点、叶节点以及溢出缓存