知识卡片

普通读书笔记卡

学习索引:用机器学习模型替代B+树的分层查找

理解等级:未标注

B+树索引本质是一种通用的、不对数据分布做任何假设的分层查找 结构:不管数据实际长什么样,都要用O(n)规模的额外空间去构建树、 每次查询都要从根节点逐层往下走到叶子节点,查询代价随数据规模 直接增长——这种”通用性”恰恰是它的代价,因为它没有利用数据本身 可能存在的规律。学习索引反过来利用这一点:如果一批键的分布 存在某种规律(哪怕是近似的),一个训练好的机器学习模型就能直接 从键”预测”出它在有序数据中的大致位置,不再需要沿着树逐层比较 下降。这个思路的关键转变是把索引问题从”如何组织一批指针”重新 定义成”如何拟合一个从键到位置的函数”:B+树用固定的树形结构 表达这个映射,学习索引用一个可训练的模型表达同一个映射,模型 越能贴合数据的实际分布,预测位置离真实位置就越近,需要的额外 校正搜索就越少。理论上这能同时降低索引占用的空间代价、提升 查询性能,但代价是这套映射高度依赖数据分布本身,数据分布一旦 发生显著变化(新数据涌入导致分布漂移),模型就需要重新训练, 这是它相对B+树”一次构建、结构稳定”的通用性所要付出的代价。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《新型数据库系统:原理、架构与实践》第3章"新型数据库 技术概述"3.1.5节"新型人工智能技术的发展"(源文件: _epub-src/EPUB/xhtml/Section0001_0005.xhtml) - 结论依据:原文明确"B+-tree索引需要借助O(n)规模的额外空间来 索引原始的数据……每次查询需要多次的间接搜索,B+-tree中的每次 查询都需要访问从树根到叶子节点路径上的所有节点……学习索引使用 机器学习模型替代传统的B+树层次索引结构,可以大幅降低传统索引 的空间代价并提高查询性能",直接对比出B+树的两个具体代价来源 及学习索引针对这两点的改进方向。 - 原始内容:MIT的研究人员Kraska等人在2018年SIGMOD会议上首次 提出了学习索引(learned index)的概念。他们将机器学习方法 应用于索引结构中,目的是降低索引空间代价,同时提升索引的 查询性能。