Page 350 - 《软件学报》2025年第8期

郭娜 等: DRAMA: 更新分布感知的学习型索引 3773

显著性水平为 α (定义 3). 更新缓冲区的容量由叶数组中的数据量确定, 在此基础上执行段间有序、段内无序的分
段策略. 由于在相同的叶模型下数据分布相似, 可以通过在预先计算的参数置信区间内随机选择参数来快速近似拟
合 (定义 5) 更新分布模型 (AFit). 此外, 为了减少索引的内存占用, 本文提出了一种混合内存压缩 (HPC) 策略.

索引构建 索引结构 查询过程
HPC 插入过程 分裂
(ֻ2.1.3 节) 新记录 (ֻ2.2.2节) 扩展
数据库
更新分布
① ② ① ②
开销模型 (ֻ2.1.1节) 缓冲区 ① ② ① ② 缓冲区 点查询过程
分段策略 近似拟合 数据库 (ֻ3节) 查询结果
(ֻ2.1.2节) (ֻ2.2.1节)

图 2 索引的结构框架

2.1 索引的构建过程
为了高效地执行查询操作, 一个设计良好的索引结构是必不可少的. 创建索引的过程涉及从上到下构建一个
区间分割树并根据分段策略优化更新缓冲区结构.

2.1.1 基于开销模型构建索引
基于开销模型启发式地探索为每个节点设置不同扇出参数时所对应的节点开销. 开销由两部分组成: 查询时
间与内存占用. 对于每一个未实例化的节点, 从扇出为 1 (1 代表该节点视为一个叶子节点) 开始探索, 直到从某一
扇出值开始节点开销连续增加 t 次或者扇出值达到阈值 MAXF 时, 该节点扇出即可确定.
根据上述方式递归确定每一个节点的扇出, 根据节点扇出值将数据按范围分配到其所有子节点并实例化每一
个节点, 而内部节点只用来划分区间并不存储真实数据. 为了提高索引的查询效率, 采用模型驱动的插入模式. 首
先, 根据当前叶子节点中的数据量与提前设定的密度 density (density∈(0,1)) 对数组容量进行扩充. 然后, 在索引构
建过程中, 使用最小二乘拟合叶子节点模型, 如公式 (1)–(3) 所示, 将当前叶子节点中的键插入到由模型计算预测
出的位置处.

  2
1 n ∑  
n ∑ 

l xx =   − x i   (1)
x i
 n 
i=1 i=1

  
1 n ∑  1 n ∑ 
n ∑ 
  

l xy =   − x iy i − y i   (2)

x i
 n  n 
i=1 i=1 i=1

1 n ∑ 1 n ∑ l xx
intercept = y i − slope× x i , slope = (3)
n n l xy
i=1 i=1
1 ∑ n 1 ∑ n
其中, x 和 y 分别表示键及其位置; n 表示键的数量; x i 和 y i 分别表示每个叶子节点中的键及其位置
n i=1 n i=1
的平均值; slope 和 intercept 分别表示叶子节点模型的斜率和截距.
叶数组容量与模型确定后, 开始使用模型驱动的方式执行插入. 如果某一键 k 的预测位置已经被其他键占据,
当前键 k 将按照顺序插入到距离其预测位置最近的空位置处. 当叶数组中剩余的空位置数 (叶数组容量 capacity–
当前叶数组中最大键所在位置 pos) 不大于待插入键的数量时, 将从模型驱动的方法切换为顺序插入方法来处理
剩余的键.
例 1: 如图 3 所示, 假设 t=1, 存在节点 N ij (第 i 层的第 j 个节点), 从其扇出为 1 开始计算开销: cost f=1 =52、
cost f=2 =30、cost f=4 =12、cost f=8 =20. 可以看到, cost f=8 >cost f=4 , 随着扇出值增加, 开销开始增加. 此时, 节点 N i 的扇
j
出值即可确定为 4. 若给定一个数据集 K={1,2,5,7,10}作为要插入的键值, 完整的模型驱动插入模式如下: 首先, 根
据当前数据集 K 的数量初始化叶数组容量, 即 capacity=K.size()/density (K.size()=5, density=0.7), 容量为 7; 之后,