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

王撷阳 等: 基于数据分布的移动对象学习索引及查询算法 2219

点的密度小于节点阈值, 符合新数据插入的基本条件. 但是, 因为数组容量的变更导致新数组无法与已训练的线性
回归模型相匹配, 所以需要对当前的线性回归模型重新进行训练. 将新数组创建时间、数组元素移动时间、线性
回归模型重训练时间和当前节点中键查询的平均时间之和作为此次节点扩展的时间代价. 另一种则是对节点的分
裂, 将当前已经超出阈值的叶子节点分裂为两个相同大小的新叶子节点, 这种情况下需要判断, 当前叶子节点的父
节点是否已经存在两个孩子节点, 若不存在, 则新增叶子节点直接作为兄弟节点与当前父节点相连, 更新与相邻叶
子节点间的顺序连接关系; 若存在, 则当前叶子节点转化为一个内部节点下分支两个叶子节点. 分裂操作后的两个
叶子节点平均分配原有键值和数据指针, 将创建节点时间、线性回归模型重训练时间和当前节点中键查询的平均
时间之和作为此次节点分裂的时间代价. 在实际选择扩展分裂操作类型时, 优先使用时间代价较小的方式. 这样的
插入机制使得插入键值并不总是存储在缓冲区或某一特定位置, 而是每次都插入在预测位置的附近, 不必因插入
新数据而重新训练模型, 因为数据总在模型预测的误差范围之内, 有效保证了索引预测的准确性. 新数据始终插入
模型预测位置附近, 而非全局重分布. 这一机制保证了插入操作的时间复杂度与节点内数据量线性相关而非全局
重建, 单次插入的均摊代价较低, 适合高频增量场景. 通过 NodeTHR 阈值提前触发节点扩展或分裂而非等待节点
完全填满, 预留插入空间以缓冲突发负载. 此外, 扩展与分裂策略优先选择时间代价较小的操作, 进一步减少高频
插入的累积开销. 由于插入位置严格限制在模型预测误差范围内, 数据分布不会因高频更新剧烈偏移, 避免了频繁
的模型重训练, 仅在节点扩展或分裂时触发局部模型更新, 确保了长期预测精度. 若插入频率极高且数据分布持续
突变, 如节点频繁分裂, 可能导致分裂操作的时间代价累积. 节点扩展或分裂的代价包含创建节点时间、线性回归
模型重训练时间和当前节点中键查询的平均时间, 此类操作的时间代价虽通过阈值控制得到减小, 但仍可能成为
极端场景下的性能瓶颈.

预测位置 最近的EmptyPos
Insert
12 18 23 34 45 76 12 18 23 34 key 45 76
元素移动前 元素移动后

(a) EmptyPos在预测位置之后
最近的EmptyPos 预测位置
Insert
12 18 23 34 45 76 12 18 23 key 34 45 76
元素移动前 元素移动后
(b) EmptyPos在预测位置之前
图 7 叶子节点未满时的索引数据插入机制示意图

4.5 非均匀网格索引删除及更新
因移动对象具有随时间快速变化位置的特点, 在实际的应用场景下, 会造成数据库中索引记录的频繁更新. 对
于时间跨度较久、存储价值较低的数据记录和不再追踪的移动对象, 数据库均需删除其对应的索引数据. 在
NUGC_LI 学习索引中, 删除一个索引键的操作, 就是通过查询得到该键所在的位置, 然后将它和对应的数据记录
的指针从索引数组和数据存储中同步删除. 这一删除操作应同时更新与之相关联的 bitmap, 以确保 bitmap 能够准
确反映当前索引结构的状态. 如果该位置之前在 bitmap 中被标记为 1, 则在删除后需要将其更新为 0, 有助于后续
插入操作准确判断该位置是否可用, 从而避免出现数据覆盖或混乱的问题. 删除操作仅是将数组中该位置的元素
信息清空, 该位置的清空并不会导致学习模型中对于其他查询键位置预测准确性的影响, 因此索引不需要像插入
操作时那样, 对于数组中其他已有的键值进行位置的移动, 操作十分简单快速. 但是, 若该键值删除后, 叶子节点中
的键值数组和数据指针数组为空数组, 则需要进行节点删除工作, 即在父节点中删除指向该节点的指针, 并将该节
点与相邻叶子节点间的双向指针断开, 将这两个相邻节点相互联结, 最后释放当前空的数据节点, 这一操作是为了
降低索引的空间占用, 也能避免后续在范围查询等操作时因空叶子节点的存在造成冗余的遍历时间.