RadixSpline: A Single-Pass Learned Index (2020) [video]

Merge operation over different levels of log structured merge trees allows one to build hierarchical index. My work used uniform splitting of indices, e.g., each 1024 samples at some level we add one sample at level above, but it is quite possible to have different splitting criteria. One such example criteria would be "how good is linear approximation of data" and another can be "how long is common prefix of the keys stored".

This "single pass learned index" is essential feature of log structured merge trees, basically, you can (ab)use it for your fun and profit.

What is more, this approach is not confined to "short integers" - one can use it for keys of any size.

And, finally, LSM trees provide you with the solution of insertion problem authors of video mentioned - just write your new data next to old data and merge them when time has come. Even when you do not write anything new, you can merge two data levels into one when you found you perform merging on reading too much.

Here is the pdf[0].

[0]: https://dl.acm.org/doi/pdf/10.1145/3401071.3401659