FINEdex: A Fine-grained Learned Index Scheme for Scalable and Co(3)

1)可伸缩性有限。可伸缩性要求学习的索引能够有效地处理插入，并在运行时调整到新的数据分布，以及扩展到多个线程以获得高并发性能。然而，现有方案的可扩展性有限，因为它们不能同时满足所有这些要求，包括并发读、写和再培训。例如，fit -tree、ALEX和PGM-index在多核系统中不考虑数据一致性问题，同时对模型进行再训练。XIndex将数据存储到不同的数据结构中，因此为了高效的范围查询性能，不会对所有数据进行排序。
2)管理费用高。由于严重的数据依赖性，现有方案所采用的策略产生了很高的开销。具体来说，XIndex和拟合树句柄通过delta缓冲区插入，这是一种基于树的结构(例如，B -树或Masstree)，并且在遍历树时对内部节点具有高度依赖性。此外，XIndex表明，当delta- buffer变大时，由于在每次索引操作中检查这两种不同的结构，性能下降了大约3倍。ALEX和PGM-index在训练好的数据数组中保留空槽来处理插入。当扩展到多个线程时，会发生许多线程冲突，因为不同的线程在插入时需要将数据放入同一个插槽，这降低了并发性能。

值得注意的是，上述模型被解释为预测误差有界的线性回归ML模型，预测键的位置。为了确保系统中没有数据丢失，有界预测误差由距离中心函数最远的数据确定。我们使用多个小模型来学习数据分布，而不是一个复杂的模型，因为多个小模型对于系统的可伸缩性来说是灵活和高效的。
2 BACKGROUND AND MOTIVATION2.1 New Perspectives on Indexes 从机器学习的角度来看，范围索引结构被视为回归模型[37]，预测给定键的位置，如图1a所示。在B -树中，通过遍历树来找到数据。学习索引将此过程视为预测，并支持范围查询，这需要对数据进行排序，从而促进高效的数据访问。[pred - max_error,pred max_error]之间的记录类似于B -树中的叶节点。[pred - max_error,pred max_error]的长度相关的查询性能。我们把这个长度称为预测粒度。