- aiDM@sigmod’22 学习型二级索引
论文题目：LSI: A Learned Secondary Index Structure
背景介绍
本文是基于学习索引做出的一个二级索引场景下的demo。
在二级索引场景下，不再是以往的一个key对应一个value，二级索引中保存的是非主键到主键的映射关系，因此会出现一个key对应多个value的情况，并且这些数据条目在底层存储设备上也不保持有序性，这就会导致学习索引不能直接拿来构建二级索引结构。
整体架构介绍
这篇文章的设计部分很简单。通过建立多层级的映射层，把底层的无序数据转换成最上层的有序数据从而构建学习索引。
- learned index层采用了PLEX设计
- fingerprint vector:通过哈希函数计算出的一个哈希值，只选取了固定长度的几位保存，用来进行相等判断。
- permutation vector:保存了底层数据的位置信息，相比于直接保存key要更节约空间，同时也可以对该vector进行数据压缩来时间换取空间。
测试
首先测试了索引建立时间，LSI相比于常见的art有着更短的建立时间。
随后分别测试了空间开销，查询延迟以及permutation vector的空间开销等等，LSI均取得了不错的表现。
总结
学习索引的研究总是基于数据的有序性，如何把一些无序的数据转换成有序的是一个难题，此外，如何寻找这种二级索引应用场景也是每一个学习索引研究者需要思考的问题。