Dabble

Kraska 等人提出使用机器学习模型代替传统的 B 树索引，并在真实数据集上取得了不错的效果，但其提出的模型假设工作负载是静态的、只读的，对于索引更新问题没有提出很好的解决办法。提出了基于中间层的可扩展的学习索引模型 Dabble，用来解决索引更新引发的模型重训练问题。首先，Dabble 模型利用 K-Means 聚类算法将数据集划分为 K 个区域，并训练 K 个神经网络分别学习不同区域的数据分布。在模型训练阶段，创新性地把数据的访问热点信息融入到神经网络中，从而提高模型对热点数据的预测精度。在数据插入时，借鉴了 LSM 树延迟更新的思想，提高了数据 写入速度。在索引更新阶段，提出一种基于中间层的机制将模型解耦，从而缓解由于数据插入带来的模型更新问题。

例子

如果我们想要建立一个数据库存储和查询 100M 个以连续整数作为键值的记录，我们可以将键视为偏移量，从而将查询的时间复杂度由 B 树的 O(logN)降低到为 O(1)；同时，索引的内存占用也从 O(N)减少到 O(1)。

学习型索引的不足

作者认为当前学习索引有两大不足：
可扩展性较差，体现在不能更新数据。某个数据的插入会引发大量数据的位置变化,这也导致了模型之间的依赖度较高.一旦有某个模型需要重新训练,为了维持模型的准确性,所有的模型都要重新训练;
模型复杂，RMI 要遍历多个模型，增加延迟。

RMI 建立 了一个层次化的模型,下一层的数据划分取决于上一层模型的预测.第 1 层给出一个 0 到 N 的预测,假设第 2 层 有 K 个模型,那么第 1 层预测在范围(0,N/K)的记录将交给第 2 层的模型 1 进一步预测,落在(N/K+1,2×N/K)的记 录将由第 2 层的模型 2 进一步预测,以此类推.