QML:一种混合空间索引结构

摘要

为了丰富现有学习多维索引的功能并提高索引效率,提出了可以保留数据分布特征的动态数据分段算法DDSA,并结合四叉树和Z顺序曲线构建了混合空间索引(QML),在此基础上分别设计范围查询算法和KNN查询算法.这种保留数据分布特征的索引可以灵活实现快速查询和更新.实验结果表明,QML索引在实现丰富功能的前提下优化了检索效率,数据更新的时间复杂度为O(1).与R*-tree相比,QML索引存储减少约33％,更新效率提升40％～80％.查询效率与最优树形索引相近.