✅原文：
ALEX: An Updatable Adaptive Learned Index
https://doi.org/10.1145/3318464.3389711

简介

learned indexes的关键思想在于：认为索引可以被认为是预测数据集中位置的一种模型
最初的工作是Kraska所提出的，但是Kraska的工作的问题在于只支持只读静态的工作负载：遇到改动则要重新训练
ALEX的成果：比B+树速度4.1x，索引大小缩小为1/2000

引入

What to do?

Kraska的工作：给定一个key，中间节点是用来预测要使用的子模型的（叶子结点）的，然后叶子结点用来预测位置

How to do?

1. 针对模型的特点对存储结构进行了优化，基本和B+树相似也是以树为主，但是允许节点以不同的速率增长和收缩【个人理解：层数可能不同，可以这样】
   
2. 在1的基础上，使用了gaped array，具有间隔的array【老生常谈了】，可以实现
   1. 分摊插入的时候的移动key的成本
   2. 允许使用基于模型的插入来更准确的存放数据【即在插入的时候也使用模型，插入到使用模型预测的位置，那么取出的时候肯定预测准确率更高
   3. gap用相邻的key填充→提升命中率【预测到一大段的gap里面也算预测对了】
3. 如果预测没那么准，从预测位置开始进行搜索【老生常谈】
4. 使用节点扩展和节点分裂，来确定模型的再训练机制

背景介绍

传统B+树

遍历过程：

1. 遍历至叶子结点
2. 在叶子结点内搜索
   缺点：当B+树很深的时候，比较和分支【than,if】数量很大，在节点搜索速度快但是在叶子结点内部搜索使用的是二进制搜索，速度很慢，效率低
   优点：动态结构

目前【主要是Kraska】的learned index【文中也称为RMI】

1. 索引可以变成模型→可以使用累积分布函数【cdf】来做预测
2. cdf较为复杂→整体上使用单个cdf可能会不够准确→引入递归模型索引【RMI】→每个节点使用的模型不完全相同
3. 有时候叶子结点对于最终位置的预测可能没那么准，但是只要中间节点预测对了叶节点，在叶节点内部查找也会快些【可能说明相对于B+树叶子结点没那么大，并且预测位置就算错了也不会差太多】
4. RMI【resurisive model index，递归模型索引】的根可以调整：
   1. 使用线性模型：简单；使用神经网络模型：准确
   2. 但是非根节点为了降低开支和时间损耗使用线性模型
5. RMI使用的节点的【树的】级别较少【树高较低】，一般只有2-3层
6. 缺点：静态，不支持插入更新和删除→本文重点改进的部分

ALEX的介绍

目标

1. 插入时间应该要比B+树更具有竞争力
2. 查找时间应该比B+树和learned index更快【后面learned index一般指kraska那篇论文里面介绍的方法】
3. 存储索引所需的空间应该小于B+和learned index

设计全览

间隔【gapped array】阵列布局

1. 使用间隔array布局
2. 在叶节点级别使用指数搜索来查找关键字，找到大概位置再用二进制查找
   【证明这样比How to do?这里的图里面的，预测到大概位置再二进制搜索要快（预测误差可以更大了）】
3. ALEX在模型预测位置插入节点【作为对比learned index新生成RMI】

节点设置

• ALEX的节点设置类似于B+树
• 叶子节点存储数据记录
• 根节点存储线性回归模型和包含指向子节点的指针的数组
• 同一个子节点可以被多个上级节点的数组内元素所指
• 
• 还有一个特点，如上图，同一层级可能有两种类型的节点，有数据节点也有中间节点
• 这样就可以通过更准确的分配【读者思考：也许是为了如果有些数据经常被命中或者经常被混淆，可以通过增加一层节点的方式再进行更细微的区分，有助于区分开这些比较容易混淆的节点】

算法描述

查找和范围查找

• 方式：从根节点开始一路迭代模型计算指针数组中的位置【也就是类似于learned index】
  • 可以基本保证预测到正确的叶子节点
  • 在叶子节点内部从预测的结点开始先使用指数查找再使用二进制查找

插入到非满的节点

• 寻找插入位置的算法和之前相同，如果是gap则直接插入，否则移动一下再插入
• 
• 指数搜索 – 知乎 (zhihu.com)

插入到已经“满了”的节点

• 实际上ALEX里没有完全满的节点（正常情况下），如果满了则使用扩展和拆分节点的方式建立新的节点
• 注意内部节点一般也用了gapped array【纠错：本文里内部节点和中间节点都是指的一个东西】
• 使用gapped array的节点具有一个属性：“满度”【大概意思，或者叫密度】
• 默认设置下，dl（density lower）=0.6，du（density upper）=0.8【所以da（density average）≈0.7】
• 也就是说当节点满度到了0.8，就要开始考虑扩展或者分裂了
• 节点扩展：分配给这个节点一个更大的gapped array，使得d=dl，这样的好处是没有在父节点上增加新的指针
• 
• 节点分裂：如果父节点内部还没达到最大的节点大小，我们可以用新的数据节点的指针替换冗余指针，拆分向各个节点
• 三种拆分方式👇
  1. 
  2. 
  3. 

代价成本

• ALEX使用两个数据作为预期成本：
  1. 指数搜索的迭代的平均次数
  2. 插入的平均位移次数【要让多少key移动】
• 查找与1.相关，插入与1.2.相关
• 每当查找和插入一次，计算一次真实成本，如果真实成本和预期成本偏离过大，说明预测可能有问题了
• 这时候按理说可以选择
  1. 扩展节点并且重新训练模型
  2. 横向拆分数据节点【上面的2.】
  3. 向下拆分数据节点【上面的3.】
• ALEX使用了2.【作者通过实验认为大多数情况下2.最佳，但是真的如此吗，读者存疑，可能和数据类型有关？】

删除，更新和其他操作

删除

删除直接删除，不会导致节点向上合并

更新

只修改payload，对于整个内容没啥影响

批量载入

使用成本模型和贪婪算法插入，使用贪婪算法判断时应该作为叶子节点还是中间节点

效果分析

复杂度分析

• m是最大数据节点的size
• 搜索：命中了就是O(1)，最差情况可以到O(m)，大多数小于O(logm)
• 插入：命中了就是O(1)，最差情况可以到O(m * log(m,p))向上取整)【仅在插入的时候正好要分裂的时候发生，p是要分裂成几块】

评估（实验）

概述

• 在只读工作负载上，ALEX 的吞吐量比 B+Tree、Learned Index、Model B+ 高出 4.1×、2.2×、2.9×、3.0×，索引大小 800×、15×、160×、8000×倍【比较对象分别是B+，learned index，model B+ tree，ART】
• 在读写工作负载上，ALEX 的吞吐量分别比 B+Tree、模型 B+Tree 和 ART 高 4.0×、2.7×、2.7×，索引大小分别小 2000×、475×、36000×【B+ tree, model B+ tree, ART】
• ALEX 具有具有竞争力的批量加载时间，并且在扩展到更大的数据集以及由于数据倾斜而导致分布变化时，保持优于其他索引的优势。

实验

• C++实现 ALEX。在配备 Intel Core i9-9900K 3.6GHz CPU 和 64GB RAM 的 Ubuntu Linux 机器上通过单线程实验进行评估。 ALEX 与四个baseline进行比较。
  1. 标准B+ tree
  2. 作者对于Learned index的尽力实现【应该是最好的实现？】
  3. Model B+ tree，在每个节点中维护一个线性模型的B+ tree
  4. Adaptive Radix Tree(ART)，一种针对内存优化的索引，用C实现
• 数据集：使用来自某些数据集的 8 字节key和随机生成的固定大小的有效负载来运行所有实验。
• 工作负载：(1) 只读工作负载，(2) 具有 95% 读取和 5% 插入的读密集型工作负载，(3) 具有 50% 读取和 50% 插入的写密集型工作负载， (4) 具有 95% 读取和 5% 插入的短范围查询工作负载，以及 (5) 只写工作负载

结果

• 
• Read-Only: 在更均匀分布的数据集上的效果会更好
• Read-Write：工作负载越偏向写入，ALEX相对baseline的性能优势就会降低，因为在拆分/扩展节点时所有索引都必须付出复制成本
• 短范围查询：ALEX 在混合插入、点查找和短范围查询的工作负载上继续优于其他索引
• 批量加载：平均而言，ALEX 的批量加载时间仅比 B+Tree 多花 50%，并且在最坏的情况下仅比 B+Tree 慢 2 倍【看来这个还是不如B+ tree，但是感觉批量加载用的不多所以应该不是大问题】
•  

其他

作者发现搜索时间与错误大小的对数成比例增加，而二分搜索方法花费恒定的时间，而与错误大小无关，这是因为二分查找必须始终在其误差范围内开始搜索，并且无法利用误差较小的情况。也就是说如果ALEX 中 RMI 模型的预测误差较小，指数搜索应该优于二分搜索。【这个还蛮重要的，知乎那个也是详细说了这个问题】

结论

这是一种新的可更新学习索引，它有效地将学习索引的核心见解与经过验证的存储和索引技术结合起来。具体来说，我们提出了一种间隙数组节点布局，它使用基于模型的插入和指数搜索，结合简单成本模型驱动的自适应 RMI 结构，以在动态工作负载上实现高性能和低内存占用。