Page 339 - 《软件学报》2026年第5期

2218 软件学报 2026 年第 37 卷第 5 期

11. node_depth ← compute_level()
12. node_model ← pretrained_model
13. node_fanout ← 1 ≪ node_depth
14. node_children ← allocate_node(node_fanout)
15. 实例化所有子节点并递归
16. NUGC_LI ← internal_node
17. 更新 keys_remaining
18. else /*其他情况下节点设置为叶子节点*/
19. num_leaf_nodes ++
20. leaf_node_bulkload()
21. NUGC_LI ← leaf_node
22. 更新 keys_remaining
23. return 基于当前数据构建的学习索引 NUGC_LI

在算法 2 中, 学习索引从根节点开始依次向下构建, 在每个节点根据所需存储的数据趋势判断该节点是内部
节点还是叶子节点, 其中内部节点的孩子节点数需保持为 2 的幂次方, 且判断时引入代价模型, 防止因为数据的非
线性特点导致划分区间过小, 单一子树层度过深; 或者因为数据的线性特点导致划分空间过大, 单一数据节点存储
数据量过多, 从而影响索引的查询效率. 在判断完节点类型后, 如果该节点是叶子节点, 则将数据放入该节点, 如果
是内部节点, 则指向两个孩子节点, 并将数据按照线性特点划分为两部分, 分别放入两个孩子节点对应的数据节点
中, 如此循环往复, 直到所有的数据都被放入索引模型中.
对于构建好的学习索引 NUGC_LI, 从模型的根节点开始查询该键值, 迭代地使用模型来计算在指针数组中的
位置, 然后根据指针节点得到下一层中的孩子节点, 循环往复直到选择到一个数据节点, 中间节点有极高的准确性
且没有搜索代价. 使用叶子节点中的模型来预测查询键在键数组中的位置, 然后使用二分查找来寻找键值的实际
位置. 如果键值被找到, 就根据键值找到查询内容并返回查询结果, 否则返回未查找到结果.
4.4 非均匀网格索引插入机制
移动对象数据随着物体位置的变换会不断更新, 产生大量动态数据, 因此为了满足移动对象数据处理的实时
性, 学习索引应具备高效插入新键值且保持预测精度不受影响的能力, 因此对 NUGC_LI 索引设计了不同情况下
的数据插入机制, 结合索引结构中的若干变量与数据结构开展不同情况下的数据插入工作.
因为学习索引的本质是根据输入查询键预测到数据存储的位置, 所以在进行数据插入时, 首先将待插入数据
作为查询键输入 NUGC_LI 索引模型中, 通过模型预测得到该数据应插入的位置, 根据待插入位置节点的不同情
况做出对应数据插入机制的选择. 较为理想的情况是, 插入数据时, 索引的叶子节点未满, 当前位置恰好为空元素,
则可以直接插入, 同步更新键值数组与 bitmap 数组; 若当前预测位置已有元素, 则需要对叶子节点上的数据进行
移动. 如图 7 所示, 首先查找到距离当前预测位置最近的一个空元素位置 EmptyPos, 然后将该 EmptyPos 与预测位
置相比较, 若 EmptyPos 在当前预测位置的后面, 则将预测位置到 EmptyPos 之间所有键值元素往后平移一位, 然后
将新键值插入到预测位置; 反之若 EmptyPos 在当前预测位置的前面, 则将 EmptyPos 到预测位置前一位的所有键
值元素往前平移一位, 然后将新键值插入到预测位置的前一位.
若待插入叶子节点的数据已满, 则需要对叶子节点进行扩展分裂操作, 值得注意的是因为需要为叶子节点中
的数据预留数据移动的空间, 所以不能直至叶子节点中的数组全部被填满时才进行扩展操作, 设置了节点阈值
NodeTHR, 当该节点中的数据量达到阈值时即认为该节点已满, 需要进行扩展分裂操作. 扩展分裂操作分为两种类
型, 一种是保持原有结构不变, 在叶子节点中构造一个容量更大的键值数组和数据指针数组, 将原有数组中的元素
转存入这个更大的键值数组和数据指针数组中, 使得扩展后的数组密度值为预先设定的扩展密度值, 这就使得节