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

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

Root_model

Int_model 1.1 Int_model 1.2 Int_model 1.3 Int_model 1.4
Int_model 2.1 Int_model 2.2 Int_model 2.3 Int_model 2.4

Leaf_model 0 Leaf_model 1 Leaf_model 2 Leaf_model 3 Leaf_model 4 Leaf_model 5
图 4 NUGC_LI 结构图

第 3 部分的每个叶子节点是数据节点, 如图 5 所示存储线性回归模型、键值数组、数据指针数组和一个 64
位 bitmap, 这个线性回归模型将把一个查询键映射为一个数据存储位置. 键值数组与数据指针数组大小相同且一
一对应, 且整个数组并非完全填满的, 而是均匀分布元素, 即数组中存在均匀分布的空元素, 这是为了在插入和更
新数据阶段, 使得新插入的数据能够更大概率地插到模型预测的位置, 有利于拟合原本的数据分布, 从而提高查询
的效率. 同时, 为了能支持数据插入导致的索引更新, 叶子节点还支持扩展分裂, 因此包含一个分裂函数, 该函数的
输入参数为预计分裂的孩子节点个数, 为保证分裂过程顺利, 该输入参数必须为 2 的指数幂, 分裂后的节点视具体
情况决定是否需要生成新的内部节点.

Key数组 key i key i+1 key i+2 key i+3
Data_pointer Linear
数组 ptr i ptr i+1 ptr i+2 ptr i+3 model Leaf_model 1
Bitmap 0 1 1 0 0 1 1 0
Leaf_model 0
图 5 NUGC_LI 叶子节点图

此外, 为了使得数据节点能正常执行插入、更新等操作, 应充分避免数据节点中的键值数组和数据指针数组
被插满, 因此根据实际情况, 对数据节点设置了一个节点阈值 NodeTHR, 当数据节点中的数组元素超过该阈值时
则开始节点分裂. 叶子节点中的 bitmap 则是用来记录数组的使用情况, 逆序记录数组该位置若已有键值或数据指
针, 则该位置为 1, 否则该位置为 0.
考虑到索引的构建是为了提升查询的效率, 叶子节点除了与其父节点相连接外, 还与相邻叶子节点相连接, 便
于范围查询操作的执行, 如图 4 所示. 所以叶子节点中均包含指向前一个叶子节点和指向下一个叶子节点的两个
指针来保证节点间的顺序连接.
4.3 非均匀网格初始化建立
在明确所需搭建索引模型的各部分结构后, 就可以根据移动对象数据构建出通过学习数据分布实现精准预测
的学习索引模型, 如第 3 节所述将移动对象数据通过 NUGC 算法降至一维, 并按照编码二叉树的深度优先遍历顺
序得到有序数列, 将移动对象数据处理成为符合学习索引构建需求的数据格式. NUGC_LI 使用线性回归模型通过
最小化线性函数的平方误差对数据分布进行学习, 模型预测查询键对应的数据记录位置近似于累积分布函数
(cumulative distribution function, CDF), 用于描述变量的概率分布. 提出针对移动对象数据的累积分布函数, 给定一
个查询键 key, 定义对应的数据位置表示为:

PrePos = CDF(key)×Count(key) (18)

( )
CDF(key) = Pr random key ⩽ key , CDF(key) ∈ [0,1] (19)
其中, PrePos 表示有序数据数组中的预测位置, CDF(key) 是数据估计的累积分布函数, 该函数计算 Pr, 其值表示
任意键 random key ⩽ key 的概率, Count(key) 是键值的个数.