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

图2：The RMI structure in the learned indexes.2.3 The Limited Scalability of Existing Schemes 各种学习到的索引利用不同的策略来支持可伸缩性，包括fit -tree、ALEX、PGM-index和XIndex，但它们的可伸缩性有限，如表1所示。具体来说，在delta缓冲区中插入fit -tree和XIndex句柄。它们的区别在于XIndex使用并发增量缓冲区(即Masstree)并支持并发再训练，如图3a所示。尽管在delta- buffer中处理插入不会影响经过训练的数据，并保证插入期间的数据正确性，但由于将数据存储在两个不同的结构中，这样的设计效率很低。XIndex表明，当delta- buffer变大时，搜索性能下降了约3倍，这是由于在每个索引操作中都检查了学习的索引和delta- buffer。

此外，当扩展到多个线程时，delta- buffer的使用增加了线程冲突，因为模型覆盖的所有数据都共享。delta- buffer是一个基于树的结构，在遍历树的过程中，它在内部节点之间具有很高的依赖性。为了提高性能，XIndex提出了一种两阶段压缩(Two-Phase-Compact)技术来支持并发再训练，该技术在不阻塞系统的情况下，同时压缩学习索引中的delta缓冲区。然而，这种设计仍然存在低效的delta- buffer，它在再训练时通过构造另一个delta- buffer来处理插入。
ALEX和PGM-index在经过训练的数据数组中保留空槽，以就地处理插入。在插入期间，已训练数据数组中的现有数据将向后移动到新数据的空槽中。同时，对训练好的模型进行检查，并根据需要扩大预测误差，避免出现将部分数据移出预测范围的错误。通过这种方式，ALEX和PGM-index确保插入过程中的数据正确性，并保持所有数据的排序，以实现高范围查询性能。然而，当扩展到多个线程时，这样的设计效率很低，因为在插入期间不同的线程会竞争共享的空槽。此外，当没有足够的空槽时，ALEX和PGM-index扩展训练数据数组，将数据重新分布到新的训练数据数组中，并重新训练新的模型。在重新训练完成之前，我们不能同时插入新的数据，因为重新训练的新模型在插入过程中没有察觉到一些数据被移出预测范围的错误。为了保证数据的一致性，进行再训练的线程会长时间阻塞系统，导致并发性能显著降低。