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

3774 软件学报 2025 年第 36 卷第 8 期

根据公式 (3) 计算模型的斜率和截距 slope=0.463 和 intercept=−0.315; 然后根据数据量 K.size() 和节点容量对斜率
和截距进行缩放: slope×=capacity/K.size()=0.648, intercept×=capacity/K.size()=−0.441; 最后, 根据斜率和截距计算
键 k 的插入位置 pos. 对于数据集中的每个键, 它们在叶数组中的位置分别为 0, 1, 2, 4, 6.

① 1/52 2/30 4/12 8/20 ① fanout/cost
−
N ij N ij
N ij N ij
② S i : unordered
… …
叶数组
更新缓冲区

段
步骤1: 选择最佳 fanout
以第2段为例

y=0.648x−0.441 1 2 5 7 10 1 2 5 7 10
Bulk loading Insert 4, 6, 9, 12 4 − − 6 9 − −
12

步骤2: 计算模型并缩放 步骤3: 模型驱动插入 步骤4: 更新缓冲区模型

图 3 索引的构建及更新过程

2.1.2 分段策略
使用开销模型确定索引结构后, 需要实例化每一个节点. 内部节点是一个区间分割的过程, 并不存储真实数据.
每个叶子节点由一个叶数组和一个更新缓冲区组成, 其中, 叶数组有序, 其存储的数据根据模型驱动的方式插入, 更
新缓冲区则存储所有新插入的数据. 对于更新缓冲区, 一个简单的方法是使其无序从而可以在 O(logn) 的时间内完
成插入操作, 但查询性能会急剧下降; 若令更新缓冲区完全有序, 查询性能则会大幅提高, 但会导致插入性能下降.
因此, 为了均衡更新缓冲区的查询与插入效率, 采用了段间有序、段内无序的分段策略. 其中, 更新缓冲区中
的段的数量根据其对应的叶数组确定, 叶数组中数据量增加, 更新缓冲区中的段的数量也随之增加. 因此, 当进行
查询操作时, 首先定位到查询键所属的段, 然后遍历该段.
例 2: 如图 3 所示, 在上例的基础上, 第 1 个叶子节点的更新缓冲区大小为 7, 假设更新缓冲区中根据键 k 是否
大于 5 进行分段, 分别为: S 1 、S 2 . 其中, 段 S 1 的容量为 3, 包含 2 个键 4、6; 段 S 2 的容量为 4, 包含 2 个键 9、12.
由于本文采用了段间有序、段内无序的分段策略, 由图可知, 当前段 S 1 的最大值 S max =6 总是小于其后续段 S 2 的
1
最小值 S min = 8. 换言之, 对于∀i<j, 则有 (key i ∈s i )<(key j ∈s j ). 而对于每一单独的段 S i , 其内部键是无序的.
2
2.1.3 混合压缩策略 HPC
数据库中索引往往是多级的, 如果索引过多或过大, 会导致内存不足, 进而影响查询的速度和响应时间. 通过
减少索引内存占用, 可以保持更多的数据和查询操作在内存中, 从而提高整体性能. 考虑到部分应用对内存占用的
限制比较苛刻, 本文针对所提索引结构的特点, 提出了无损压缩和有损压缩叠用的混合压缩策略.

2.1.3.1 无损参数压缩策略 LLPC
构建无预测误差的内部节点过程通常为一个区间分割树的划分过程. 若利用线性回归模型实现无预测误差的
内部节点, 则要求该无预测误差的内部节点的所有孩子节点有相同的数据范围. 基于上述动机与观察, 可以得出如
下定理.
定理 1. 假设 Z 个内部节点 I 1 ,I 2 ,…,I Z 都属于同一个父节点 R, 每个内部节点 I 有 m 种可能的扇出方式, 表示
为 f 0 , f 1 ,…, f m . 基于内部节点模型的定义, 可得具有相同父节点和相同扇出的内部节点也完全共享相同的斜率 a,