索引结构是用来提高数据访问性能的重要工具,但其采用的数据结构没有考虑真实数据的分布特征。而机器学习的本质是从数据中发掘隐藏的模式,这些从数据中发掘的模式反映了数据的内在联系和分布规律。因此机器学习为建立数据索引提供全新的解决思路。此外,机器学习模型存储空间小、并行度高、查询速度快的特点可以有效地提高索引的查询性能,降低索引带来的空间开销。然而目前基于机器学习的索引结构(简称学习索引)存在着以下不足:1)从多个维度构建主键索引时,学习索引带来的误差范围很高,查询开销急剧增长;2)只适用于聚簇索引,不能应用于二级索引的场景。本文针对学习索引存在的不足,对基于机器学习的数据索引技术进行深入研究。首先,针对学习索引在多维数据上误差范围过大的问题,通过深入分析索引问题的特点和需求,本文提出了一种递归提升模型索引结构Recursive Boosting Model Index(简称B-RMI)。在模型分层结构的设计下,本文通过三个方面进行结构的优化:自顶向下拟合预测残差来充分利用非叶子模型的拟合效果、权重更新来提高对离群数据的关注度和预设阈值进行数据剪枝,从而提高整体索引结构的预测准确度。其次,针对学习索引不适用于二级索引的局限性问题,本文提出了一种两阶段二级索引模型结构。其中第一阶段通过二分类模型和Bloom Filter进行两步筛选,将数据划分成唯一键值和非唯一键值,并保有一定的误判率。然后在第二阶段根据两类数据的特点,分别构建索引模型进行处理,从而满足二级索引的查询要求。最后,基于上述两个理论成果,本文先通过合成数据和Open Street Map真实地点数据对B-RMI、RMI和B-Tree结构性能进行比较分析,表明B-RMI结构在多维数据上的预测准确度有显著提升。然后通过开源NYC出租车数据、基准测试工具TPC-D生成的不同倾斜度订单数据和Instacart商店数据,对两阶段二级索引结构和B-Tree二级索引性能进行比较分析,表明该结构在提高查询效率和降低内存开销上的优势。最终验证了本文研究工作的可行性和有效性。
暂无评论