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

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

据计算每个叶数组模型参数及其置信区间; 最后, 基于模型驱动的插入方式将每个叶子节点数据插入到其对应位
置, 并根据新叶子节点中的数据量动态分配缓冲区的大小. 至此, 分裂操作结束. 完成分裂操作后, 重新定位到插入
键 k 所属叶子节点 leaf, 在新的叶子节点 leaf 中重新执行插入操作, 确定插入位置 pos, 完成插入操作.
算法复杂度分析. 假设忽略节点的合并和拆分操作, 插入操作的时间复杂度由遍历到叶子节点操作主导, 其时
间复杂度为 O(H), 其中 H 表示索引树的高度. 一旦找到插入键 k 所属的叶子节点 leaf, 就可以使用定位插入键所
属段操作快速找到插入键 k 所属的更新缓冲区的段 S i , 该操作的时间复杂度为 O(N seg ), 其中 N se 是叶子节点 leaf
g
对应的更新缓冲区中段的数量. 然后, 可以在 O(1) 的时间内将键 k 插入到段的末尾. 因此, 插入操作的总体时间复
杂度为 O(H+N seg ).

3 查询处理过程

本节以点查询的过程为基础, 介绍基于上述索引结构与优化算法的点查询处理过程. 范围查询可转化成双点
查询及简单的计算过程来计算, 所以本文只关注点查询.
给定查询键 k, 点查询返回查询键 k 对应的有效载荷, 即 point(k)={p|pos p =pos k }. 算法 2 概述了点查询的处理
过程, 包含 3 个步骤, 每个步骤的具体过程如下.

算法 2. 点查询.
输入: 查询键 k;
输出: 查询键 k 对应的有效载荷.

1. cur_node ← 根节点; /* 从根节点开始遍历 */
2. while true do
3. child_ID ← predict(k); /* 预测键 k 所属子节点 ID */
4. if cur_node ← (cur_node.child[child_ID]) 是叶节点 then
5. leaf ← cur_node; break;
6. pos 0 = leaf → search_leaf(k); /* 获取键 k 在叶数组中的位置 */
7. if pos 0 == −1 then /* 未在叶数组中找到键 k */
8. pos 1 = leaf → search_buffer(k); /* 获取键 k 在更新缓冲区中的位置 */
9. if pos 1 == −1 then /* 在更新缓冲区未找到键 k */
10. return −1;
11. else
12. return leaf B → payload[pos 1 ]; /* 返回更新缓冲区中键 k 对应的有效载荷 */
13. else
14. return leaf A → payload[pos 0 ]; /* 返回叶数组中键 k 对应的有效载荷 */

(1) 遍历到叶子节点 (第 1–6 行). 自上而下迭代到包含查询键的叶子节点, 即从根节点 cur_node 开始向下遍
历, 使用在构建过程中获得的内部节点分割模型确定查询键 k 所属的节点 ID, 即 child_ID.

(13)
child_ID = cur_node a ×k +cur_node b
新找到的子节点 cur_node.children[child_ID] 被视为新的父节点 cur_node, 并继续向下遍历, 直到到达叶子节
点, 即为查询键 k 所属的叶子节点 leaf.
(2) 指数搜索叶子节点 (第 7 行). 在叶数组中利用指数搜索查找键 k. 由于数据可能存储在叶子节点的叶数组
和更新缓冲区中, 当找到包含查询键 k 的叶子节点 leaf 时, 首先在叶数组中执行指数搜索, 并使用叶子节点模型预
测查询键 k 在数组中的位置 pos 0 .