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

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

f
f
a
a
I = I |I = I .
即
1 2 1 2
证明: 内部节点模型的计算如下:

1
a = × I i f (4)
I max_key − I min_key
i i
b = −a× I min_key (5)
i
由于本文构建的索引结构是一个区间分割树, 一个非叶节点的所有孩子节点均分其范围. 换言之, 已知父节
点 R 的最大值、最小值与扇出, 所有属于同一父节点 R 的子节点 I 1 ,I 2 ,…,I Z 有相同的数据范围, 即:
I max_key − I min_key = R max_key −R min_key (6)
i i
R f
对于同层的内部节点, 其模型参数计算过程如公式 (4)、(5), 由区间分割树的特性及公式 (6) 可知, 节点 I 1 , I 2
的数据范围 I 1 max_key –I 1 min_key =I 2 max_key –I 2 min_key 相同. 因此, 当节点 I 1 , I 2 具有相同的扇出 f, 即 I = I 时, I = I . 证毕.
f
f
a
a
1 2 1 2
由定理 1 可知, 属于同一父节点且具有相同扇出的内部节点, 其斜率完全相同. 由公式 (4)、(5) 可知, 内部节
点的斜率、截距均可由其存储的其他参数计算. 因此, 不在每个内部节点中存储模型参数, 而是在执行查找时根据
其扇出、最大值和最小值计算, 从而实现无损参数压缩 (lossless parameter compression, LLPC). 算法只在内部节点
使用 LLPC, 这种方法显著减少了索引内部结构的内存消耗, 在一定程度上平衡了叶数组中的间隙所导致的内存
开销, 且内部节点模型只用于数据分区不存在预测误差, 其压缩后对查询性能影响较小. 此外, 由于扇出总是在离
散空间中探索, 叶子节点的父亲节点扇出通常相同. 因此, 并不在每一个内部节点存储扇出值, 而是使用一个扇出
表进行记录. 具体来说, 统计同一层扇出相同的相邻内部节点, 直至从某一节点开始扇出值不同, 扇出表存储扇出
值相同的第 1 个节点编号、扇出值以及最后一个扇出值相同的节点编号.
例 3: 如后文图 4 所示, 假设当前数据 key 值分布在 N 的范围是 [0,1000], 扇出
0
[0,1000] 区间内, 则根节点
0
fanout=40. 首先根据区间分割树的思想确定每一内部节点对应的键值区间, 并根据开销模型确定每一个内部节点
的扇出. 经计算, 区间大小均为 25, 且 N 和N 39 的扇出均为 2; N – N 38 的扇出均为 4; N , N , N , N 39 的最小值分
0
1
38
1
0
1 1 1 1 1 1 1 1
别为 0, 25, 950, 975. 由于 N 和 N 39 具有相同的父节点 N 与相同的扇出 fanout=2, 由定理 2 可知, N 和 N 39 共享相
0
0
0
1 1 0 1 1
同的斜率为 0.08. 同理可得, N 和N 38 共享相同的斜率为 0.16. 使用公式 (4) 计算内部节点的模型斜率, N 和N 39 的
0
1
1 1 1 1
模型斜率为 0.08; N 和N 38 的模型斜率的确为 0.16. 斜率的压缩是无损的. 由公式 (5) 可知, 模型的截距是根据模型
1
1 1
斜率与该节点的最小值计算, 而模型斜率的压缩是无损的且节点的最小值均已知, 因此根据斜率与最小值计算的
1 38 的扇出均为 4, 压缩后的扇出表并不存储 个扇出值, 而是存储
内部节点模型截距同样是无损的. 由于 N – N 40
1 1
1
0
N 和N 39 的扇出值 2, N – N 38 的相同扇出值 4, 以及节点的起始编号 1 和 38.
1 1 1 1

2.1.3.2 有损参数压缩策略 LPC
考虑到 DRAMA 的叶子节点采用最小二乘法拟合数据分布作为叶子节点模型, 而不是采用内部节点的线性
插值函数用于数据分区, 因此叶子节点并不满足上述定理, 无法利用无损参数压缩策略进一步压缩叶子节点模型
的内存占用. 对于叶子节点采用可调节的有损压缩 (lossy parameter compression, LPC) 策略, 以牺牲一部分查询性
能为代价, 进一步降低索引结构的内存占用. 具体过程如下: 首先使用线性插值方式计算每个叶子节点 leaf i 的模
型参数 (斜率或截距) 长度非零的区间 [leaf i .min, leaf i .max]; 然后根据区间的最小值 leaf i .min, 对所有区间进行排序;
最后将相似的区间进行合并. 在合并后的参数区间内随机选值, 作为共享的模型参数, 并用两个参数映射表分别存
储合并后的斜率与截距. 本文用区间重叠度 θ 来衡量模型参数区间的相似程度.
定义 1 (区间重叠度 θ). 若两个叶子节点 leaf i 和 leaf j 的参数区间 [leaf i .min, leaf i .max] 与 [leaf j .min, leaf j .max]
存在重叠的区域 (leaf i .min≤leaf j .min<leaf i .max≤leaf j .max), 则重叠的区间为 [leaf j .min, leaf i .max]. 用重叠区间长度与
整个区间长度的比, 即 (leaf i .max–leaf j .min)/(leaf j .max–leaf i .min) 作为 θ 的值, 那么 θ∈(0,1).
定义 2 (有损压缩系数 ε). 有损压缩系数 ε 是用来控制有损压缩程度的参数值, 其取值范围是 [0,1]. 当对叶子
节点的模型进行有损参数压缩时, 仅在区间重叠度 θ >1–ε 的模型参数区间才进行合并.