【数据库研究前沿】学习型索引再审视：RMI、ALEX、PGM

2018 年 Kraska 等人在 SIGMOD 上抛出一篇题目挑衅味十足的论文——“The Case for Learned Index Structures”。他们的论断是：索引本质上是一个从 key 到 position 的函数 f(key) → pos，而这个函数可以用神经网络拟合。如果拟合得足够好，查找一条记录只需要一次前向推理 + 一次局部二分搜索，常数可能比 B+Tree 的 log(N) 级别跳转更小，内存占用也更低。

七年过去，我们已经能比较冷静地判断这条路线的边界。它没有替代 B+Tree，也没有替代 LSM-Tree；但它在只读分析场景、排序后的列存稀疏索引、以及 key 分布规则的 embedded 场景里，确实站稳了脚跟。本文上半梳理 RMI、ALEX、PGM-Index、RadixSpline 四个代表性工作；下半讨论它们为什么没有在 OLTP 上取代 B+Tree，并给出一个 50 行的最小 RMI demo。

一、把索引看成函数：RMI 的核心观察

1.1 累积分布函数视角

假设一个有序数组 A[0..N-1] 存了所有 key。对任意 key x，它在数组中的 position 就是

pos(x) = N · CDF(x)

其中 CDF 是 key 的累积分布函数（Cumulative Distribution Function）。索引查找的本质就是估计 CDF。B+Tree 用一棵树分层离散化 CDF，哈希表用随机散列把 CDF 打散成 uniform。如果我们能直接学到一个足够准的 CDF̂，就可以用

pos_est = round(N · CDF̂(x))

跳到大概位置，然后在 [pos_est - ε, pos_est + ε] 的小窗口里做局部搜索修正误差。只要 ε 明显小于 B+Tree 的叶子 fanout，总访问数就更少。

这个观察听起来平凡，但带出了一个结构性好处：B+Tree 的内部节点本身也是数据，要占内存；而一个学到的 CDF̂ 可以只占几百 KB，对大数据集压缩比极高。

进一步，如果 CDF 足够光滑，甚至连”估计 + 修正”都可以退化成一次常数查找。Kraska 等在论文里用整数 timestamp 数据做过极端实验：几百万 key，RMI 的查找时间比高度优化的 B+Tree 快 3 倍、内存占用小一个数量级。这套结果把”是否应该继续用 B+Tree”这个看似已解决的问题重新抛回桌面。

1.2 RMI：Recursive Model Index

Kraska 等人没有直接上大神经网络，因为一次 exp / tanh 的推理开销比一次 cache miss 还贵。他们提出 RMI（Recursive Model Index）：一棵固定深度（通常 2 层）的小模型树。

• 第 1 层是一个粗模型 M_root(x)，输出一个 stage-2 的 bucket id；
• 第 2 层里每个 bucket 是一个超简单的线性模型 M_i(x) = a_i · x + b_i，只用加法和乘法；
• 第 2 层输出的就是估计的 position，再在一个 bounded error 窗口里做局部搜索。

训练时自顶向下切分数据，每个叶子线性模型拟合它那一段的 CDF。推理时走两次 O(1) 运算，比 B+Tree 的 log(N) 次 cache miss 少得多。

1.3 RMI 的最大问题

RMI 的致命短板是只读。一旦插入 / 删除让 CDF 局部偏移，模型就不再准；要维持误差界要么全量重训（代价大），要么在模型外面套 delta buffer（又退化成 B+Tree 那一套）。这直接刺激了 ALEX 的出现。

二、ALEX：可更新的学习型索引

ALEX（Ding et al., SIGMOD 2020, “ALEX: An Updatable Adaptive Learned Index”）把可更新性作为一等公民。它的三个关键设计：

• Gapped Array：叶节点不存连续数组，而是在预估 position 附近留空槽。插入时如果空槽就绪，直接 O(1) 落位。
• Node Splitting：当空槽比例超过阈值，节点分裂并重训局部模型。类似 B+Tree 分裂，但触发条件是”模型误差超标”而不是”节点写满”。
• Adaptive Cost Model：内部根据访问模式动态选择”多用模型 vs 多留空槽”，对读密集和写密集自适应。

ALEX 在均匀和偏斜读写混合工作负载下都能逼近 B+Tree 的吞吐，有时因为更紧凑的内存占用反而更快。但它仍有两个前提：key 是数值、数据能全装进内存。

2.1 误差界的工程含义

学习型索引和 B+Tree 最大的工程差异是：B+Tree 的叶子定位精确，没有二次搜索；learned index 的叶子定位带误差，必须在一个固定窗口里再做一次局部 scan。所以评估一个 learned index，除了平均查找时间，还要看两个指标：

• max_error：所有 key 里最差的预测误差。决定了局部搜索窗口的大小。
• avg_error：平均误差。决定了 cache 命中率。

ALEX、PGM、RadixSpline 本质上都在用不同代价换 max_error 的下降。

2.2 Gapped Array 的实现细节

Gapped Array 是 ALEX 里值得单拎出来讲的一个数据结构。想象一段长度 N 的数组，预留 α · N 的空槽随机分散在数组里。插入时：

• 用局部线性模型预测 pos_est；
• 在 [pos_est - ε, pos_est + ε] 附近找最近的空槽；
• 把数据写进去，写入的 key 与预测位置不等，差异累积进 max_error。

要点是空槽的分布要和模型预测的误差分布匹配，否则”预测 + 找空槽”退化成线性扫描。ALEX 的解法是用模型残差分布做反 CDF 抽样，把空槽放到模型最容易出错的位置。这个设计在 LevelDB 的 skip list 里也能找到亲戚——“在难的地方多留冗余”。

三、PGM-Index：可证明误差界

PGM-Index（Ferragina & Vinciguerra, VLDB 2020, “The PGM-Index: A Fully-Dynamic Compressed Learned Index with Provable Worst-Case Bounds”）的贡献是把”带误差界的学习型索引”做成了有可证明 worst-case bound 的数据结构。

3.1 分段线性近似

PGM 的叶层是对 CDF 的 ε-分段线性近似（piecewise linear approximation, PLA）。给定误差预算 ε，算法一遍扫描 key 数组，贪心地把能被一个线性段覆盖（误差始终 ≤ ε）的连续区间合成一段。这是一个经典的计算几何问题，有 O(N) 的在线算法。

keys:   1   3   4   7   9  11  12  15  18
pos:    0   1   2   3   4   5   6   7   8
seg1: (a1, b1)  for keys [1, 9]   max err 1
seg2: (a2, b2)  for keys [11, 18] max err 1

查找时先二分找到 key 所在的段，再用段的线性公式算出 pos_est ± ε，最后在窗口内做搜索。

3.2 递归压缩

段的数量本身可能还很大。PGM 的关键 trick 是把段的 起始 key 数组 再递归做一遍 ε-PLA，一层层压上去。总空间复杂度是 O(N / ε²) 但实际上对真实数据（CDF 大体光滑）常数非常小，压到几十到几百 KB 不罕见。

3.3 动态 PGM

PGM 的动态版本叫 Dynamic PGM（DPGM），用 Log-Structured Merge 思路：多层静态 PGM + 小写入缓冲，满了就合并重建。形态上它其实非常接近 LSM-Tree，只是每一层存 learned index 而不是 SSTable。这也提示了 learned index 在 OLTP 的路径——不是替代 B+Tree，而是替代 LSM-Tree 某一层的 sparse index。

四、RadixSpline：一遍构建、无超参

RadixSpline（Kipf et al., SIGMOD 2020 aiDM workshop, “RadixSpline: A Single-Pass Learned Index”）的立场是”尽可能简单”。它直接用样条插值拟合 CDF，并用一个 radix table（高位 prefix）做第一步定位：

• 一次扫描数据，贪心地放置样条点，保证每一段的最大误差 ≤ ε。
• 用 key 的高 r 位作为 radix 索引，快速跳到对应样条段。

相比 PGM 的多层递归、ALEX 的 gapped array，RadixSpline 只有两个超参（ε 和 radix bits）、构建 O(N)、只读。它的定位是只读分析数据的稀疏索引：列存 block 的最小 key → block offset，或者排序后 primary key → row group，这类场景读路径极短，写全通过批量 rebuild。

五、四个方案的对比

要点：没有一个方案同时解决”高写入吞吐 + 可证明延迟上界 + schema 适应性”这三件事。这就是为什么 learned index 到今天还是一个”补位”技术而不是”取代”技术。

六、为什么还没替代 B+Tree 与 LSM

这是每个看到 learned index 论文的工程师都会问的问题。把分散在十几篇后续论文里的答案归并一下：

6.1 OLTP 写路径的延迟上界

B+Tree 的写路径有明确的 worst-case：最多 log(N) 次页锁获取 + 一次 WAL fsync。learned index 的写路径要么退化成 LSM 合并（延迟尖峰），要么退化成 gapped array 的节点分裂（需要重训局部模型），两者都难以给出硬上界。高并发 OLTP 场景对 p99.9 极敏感，这条线直接把 learned index 挡在门外。

6.2 字符串和复合 key

RMI 系列算法天然假设 key 是一维实数。字符串 key、复合 key、反向排序 key，都需要先做 order-preserving encoding，而好的编码本身就接近一个 B+Tree 内部节点的工作量。到 2024 年这方面仍无让人信服的通解。

6.3 数据分布漂移

生产负载的 key 分布会因为业务活动呈现时段性或季节性漂移。B+Tree 对分布完全不敏感；learned index 会伴随分布漂移误差变大，要么放大搜索窗口、要么触发重训。对一个稳定运行十年的系统来说，“永远不需要重训”本身就是一个很强的特性。

6.4 哪里确实在用

• 列存稀疏索引：Parquet / ORC 的 min-max zone map + learned row-group 定位。
• 内存 OLAP 只读副本：ClickHouse 社区的若干实验分支用 RadixSpline 替代 primary key mark。
• 字典压缩：排序字典 → 码字的映射天然只读、key 数值化，RMI / PGM 都适用。
• LSM 的 meta 层：每层 SSTable 的 key → file offset 可以用 PGM 替代原有 index block，是 RocksDB 社区讨论过多次的方向。

6.5 混合形态：learned index 作为加速层

2023 年之后有一批”混合形态”工作值得留意：B+Tree 作为正确性层、learned model 作为加速层。思路是：

• B+Tree 结构照常存在，负责正确性与并发控制；
• 在 B+Tree 上叠一个 learned model，根据 key 直接预测到叶子页的近似位置；
• 预测命中就跳过内部节点的二分查找，miss 了就退回常规遍历。

这种形态不依赖 learned model 的 max error 保证（失效就退回），也不改写入路径（B+Tree 结构不变），是一条工程上更稳妥的路线。代表工作有 BOURBON（Dai et al., OSDI 2020, 针对 LSM 的 learned 加速）和一批 industrial note。

6.6 开放问题

几个研究界还没有统一答案的问题：

• Concurrent updatable learned index：并发写入 + 局部重训的正确性如何保证？
• Variable-length keys：真正通用的字符串 learned index 存在吗？
• Cost model in LSM：把 PGM 嵌入 LSM 每层之后，compaction 策略要不要跟着改？

这些问题都属于”learned index 第二阶段”，值得持续跟踪 2026 年之后的 VLDB / SIGMOD 工作。

七、Demo：50 行实现一个最小 RMI

放在 demo/rmi_minimal.py 的脚本把第二节的想法落成可运行代码。它接收一个有序整数数组，用一个 2 层 RMI（root 线性模型 + K 个 stage-2 线性模型）拟合 CDF，然后对比直接二分搜索的查找次数。

核心训练循环：

def train_rmi(keys, K):
    N = len(keys)
    # stage-1: a single linear model mapping key -> stage2 bucket id
    xs = np.asarray(keys, dtype=np.float64)
    ys = np.arange(N, dtype=np.float64)
    a1, b1 = np.polyfit(xs, ys * K / N, 1)
    # assign keys to buckets based on stage-1 prediction
    buckets = np.clip(np.round(a1 * xs + b1).astype(int), 0, K - 1)
    # stage-2: one linear model per bucket
    stage2 = []
    for k in range(K):
        mask = buckets == k
        if mask.sum() < 2:
            stage2.append((0.0, ys[mask][0] if mask.any() else 0.0))
            continue
        a2, b2 = np.polyfit(xs[mask], ys[mask], 1)
        stage2.append((a2, b2))
    return (a1, b1), stage2

查找：

def lookup(key, rmi, keys, max_err):
    (a1, b1), stage2 = rmi
    bucket = int(np.clip(round(a1 * key + b1), 0, len(stage2) - 1))
    a2, b2 = stage2[bucket]
    pos_est = int(a2 * key + b2)
    lo = max(0, pos_est - max_err)
    hi = min(len(keys) - 1, pos_est + max_err)
    # local binary search within [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if keys[mid] == key:
            return mid
        if keys[mid] < key:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

在 1e6 条均匀 key 上，K=1024 的 RMI 的平均误差在 10 以内、max error 约 200，局部二分大约 8 次比较；标准二分需要 20 次。这个 demo 足够展示”为什么 learned index 有机会”，但也足够暴露”一次插入如何让 max error 爆炸”——这正是 ALEX / PGM / RadixSpline 要解决的后续问题。

7.1 离线可跑

demo 只依赖 numpy。完整 README 与运行说明见 demo/README.md，核心命令：

cd demo
pip install numpy==1.26.4
python rmi_minimal.py

输出包含：（1）RMI 的 avg / max error；（2）与标准二分搜索的比较次数对比；（3）注入 1% 随机插入后误差如何迅速退化。第三条的意义是：想明白了 RMI 在 writes 下为什么坏，你就理解了后续所有 learned index 论文在努力解决什么。

7.3 学习型索引在 2025 的几个非共识

综述文章通常不会讲的几条开放观点，放在这里给读者做决策参考：

• “CDF 光滑就有用”是一个强假设。真实 OLTP 的 primary key 分布往往是 time-based 或 UUID-based，CDF 反而非常光滑——但这种场景 B+Tree 也已经做得非常好。learned index 最想要 “光滑且稀疏” 的场景（例如事件时间戳 + 业务 ID 复合键），在现实工作负载里占比不高。
• 内存省下来未必是 ROI。B+Tree 占内存的”内部节点”同样是热数据，如果换成 learned index 释放出来的内存去放 row cache，ROI 更直接。这是 2023 年 MySQL / PostgreSQL 社区拒绝把 learned index 纳入主干的原因之一。
• “无需超参”只是表象。RadixSpline 的 ε 与 radix bits 本质是两个需要随数据分布重调的参数。自动选参数的论文（如 “Tuning Hyperparameters Without Grad Students”）在这里还没有令人信服的工作。
• 失效模式可观测性差。B+Tree 的 worst case 是结构性的（树高），容易监控；learned index 的 worst case 和 key 分布漂移强相关，监控它需要额外打点，大部分 DBA 没这个成本预算。

承认这些开放问题，比鼓吹”learned 系吊打经典”更接近真实 2026 年的行业共识。

7.4 与仓库其他文章的互链

• B+Tree 与 LSM 在写路径上的差异，参考 B+Tree vs LSM。
• 列存稀疏索引的 zone map 思路，参考 LSM-Tree 工程实践 中的 block-level 统计。
• 上一篇讨论的 learned query optimizer 与本篇同属 “把传统 DB 组件替换为模型” 的研究线，参考 学习型查询优化器。

八、一个被低估的视角：把 learned index 当作索引压缩

学术界常把 learned index 定位为”新的索引结构”。从工程角度有一个更朴素的视角：learned index 是一种索引压缩方法。

8.1 与 FST、Succinct Data Structure 的类比

• Finite State Transducer（FST）：把一组有序字符串压缩成 DAWG，查找依然 O(len(key))。RocksDB 6.x 引入 FST block，把 SSTable 的 index block 体积压到原来的 20–30%。
• Succinct tree / Bloom filter：用接近信息论下限的位数表达结构，查询依然 O(1) / O(log N)。
• Learned index：用一个小模型把 key → pos 函数压缩，查询 O(1)（推理） + 窗口搜索。

这三者共享的工程 DNA 是：放弃”精确结构 + 直接跳转”，换取”近似结构 + 小窗口搜索”。它们在”磁盘索引压缩”这件事上是竞争者也是合作者——RadixSpline 和 FST 可以同时出现在一个 SSTable 的 metadata 里，分别处理数值 key 和字符串 key。

8.2 “压缩视角”带来的不同选型

一旦把 learned index 视为压缩工具，选型问题就变得清晰：

• 要最低访问延迟：B+Tree 依然是赢家。
• 要最低内存占用 + 可接受小窗口搜索：learned index / FST 是赢家。
• 要最高写吞吐：LSM-Tree 依然是赢家，learned 结构只能做辅助索引。
• 要可证明的 worst case：PGM 这类带 ε 保证的方案胜出。

这个框架比”learned 是否取代 B+Tree”更能指导真实选型。事实上大多数关于 “learned index 实用不实用” 的争论，都可以在这个框架下重新翻译成 “在你的场景里，哪一轴是瓶颈？”

8.3 小结：研究意义大于替代意义

坦诚说，到 2026 年 learned index 仍然是研究意义大于替代意义。它带来的三个真正有价值的影响：

• 让数据库社区认真思考”索引结构是否一定要精确”这一前提。
• 把”分布建模”引入以前纯结构化的领域，催生了基数估计、计划搜索等一系列 learned QO 工作。
• 在特定窄场景（只读列存、内存 OLAP、SSTable 元信息）提供了真实的 10%–50% 收益。

对工程师来说，学习型索引应该被看成工具箱里一个细分工具，不是银弹。具体什么时候拿出来用，答案几乎总是 “先量清楚你的 workload 到底卡在哪”。

九、工程视角的 learned index 选型决策树

给团队一张可直接用的决策树：

问题: 当前索引方案卡在哪？

1. 内存不够？
   是 → 数据集大小？
        > 1 TB → 考虑 RocksDB + learned block index（PGM 替代 block index）
        100 GB 级 → 保留 B+Tree，优先加内存
        < 10 GB → 不是瓶颈，不换
   否 → 下一问

2. 需要写吞吐？
   OLTP 写入 > 10k/s → B+Tree 或 LSM-Tree，learned 只能做辅助
   批量 + 只读 → 可选 RadixSpline / PGM 做主索引

3. Key 类型？
   数值 / 时间戳 → learned 友好
   UUID → 分布太随机，learned 没收益
   字符串 → 当前版本不成熟，继续 B+Tree

4. 是否可接受定期 rebuild？
   可以（夜间窗口） → 静态 learned index（RMI、RadixSpline）
   不可以 → ALEX / Dynamic PGM（更复杂但可更新）

这张树隐含一个判断：多数场景的答案是”不换”。换索引结构的认知负荷与迁移成本是可观的，只有在清晰瓶颈 + 大量收益预期时才值得。

9.1 一个负面案例

2023 年某大厂内部分享过一个 learned index 的失败项目：

• 场景：亿级 primary key 列存 OLAP，key 是业务 UUID（高熵随机）。
• 动机：想用 learned index 省内存。
• 结果：UUID 的 CDF 接近 uniform + 剧烈局部抖动，learned 模型的 max error 与 N 近乎线性，退化成全表扫。
• 教训：先看 CDF 再选工具。一张 Python 脚本 5 分钟画的 CDF 图，能省几个月的项目学费。

把这种失败案例放在决策树旁边，比在论文里再堆一张准确率曲线更对工程师有价值。

十、小结：研究价值、工程价值、读者指南

写到这里，把这篇文章的立场总结一下。

研究价值：learned index 是过去十年数据库领域最有思想冲击力的研究线之一。它让我们重新思考 “索引” 的本质——不是一种具体结构，而是 “key → pos 的函数逼近”。这一视角打开了大量后续工作：learned QO、learned cardinality、learned buffer manager。即使这些具体工作都没替代传统方案，这条思路本身已经永久改变了数据库研究的地貌。

工程价值：目前只在特定窄场景落地（只读列存索引、SSTable 元信息、字典压缩）。在 OLTP 主路径上 B+Tree 仍然是默认选择。2026 年的工程决策建议很直白：默认不换，除非你能在自己数据上证明收益。

读者指南：如果你想深入这个方向，推荐读论文的顺序：

1. Kraska 2018（理解动机）→
2. Ferragina & Vinciguerra 2020 PGM（理解误差界）→
3. Ding 2020 ALEX（理解可更新）→
4. Marcus 2020 benchmark 论文（公平对比四类方法）→
5. BOURBON OSDI 2020（理解 LSM 中的加速层形态）→
6. 最新的 SIGMOD / VLDB 论文（工程化细节）。

这条路径大概需要 20 小时的论文阅读，之后你会对 learned index 的可能性与边界有非常清晰的理解，做决策不会被短视频式的”替代 B+Tree”吸引。

十、练习题：给你一个 workload 怎么做判断

最后留几个练习题，帮读者把前面的分析转成自己的决策直觉。都是真实场景简化版。

题 1：电商订单库，每天 1 千万 INSERT、1 亿 SELECT，主索引是 (tenant_id, created_at)，现在 p99 写延迟被 B+Tree 分裂拖到 20ms。你会不会上 learned index？

提示：写密集 + 主索引。答案是”不上”。继续 B+Tree，考虑的是否减少索引数量、调整 fill factor、或者引入 LSM。

题 2：广告日志分析库，全量 1 TB parquet 存在对象存储，主键是事件时间戳 + 广告 ID。最常见查询是时间范围过滤，查询响应时间 95% 在 2 秒内。你会不会上 learned index？

提示：只读 + 时间戳主键 + 大数据集 + 内存受限。答案是”可以试”。RadixSpline / PGM 对这个场景非常合适，能把 zone map + sparse index 压缩到很小的内存占用。

题 3：文档数据库，每个用户文档 UUID 作为 key，1 亿文档，点查为主。你会不会上 learned index？

提示：UUID 高熵 + 点查为主。答案是”不上”。CDF 对 uniform 分布没有结构可学，learned model 退化成线性表。

题 4：内存 OLTP 库，数据全量 50 GB 放内存，热点在最近 10% 的数据上，主键是单调递增的 long ID。你会不会上 learned index？

提示：单调 ID + 内存 + 写压力。答案是”看 ALEX 是否能撑写吞吐”，小规模 PoC 一下；大部分时候还是 B+Tree + 热数据 cache 更稳。

把这四题想明白，你对 learned index 的落地判断就接近可以上岗的程度了。

十一、对新人的几句话

如果你是刚进入数据库领域的工程师或者研究生，想做 learned index 方向，几条实用建议：

• 先建立 B+Tree 和 LSM 的肌肉记忆。没有经典基线，你看不懂 learned index 论文声称的优势到底真假。
• 从可视化 CDF 开始。任何新的学习型索引想法，都先画几条真实数据的 CDF 曲线，看它到底光滑不光滑、稀疏不稀疏。很多差的想法在这一步就能排除。
• 做可验证的 micro-benchmark。一个 10 行 Python + numpy 的原型比 10 页论文草稿信息量大得多。
• 重点不是比 B+Tree 快多少，而是在什么 workload 下稳定。稳定性是工程化的门槛。
• 读失败论文。被拒稿或者没被接收的工作里，失败案例往往比成功案例对你更有启发。

数据库是一个几十年沉淀的严谨学科，learned index 是它的新分支但不能绕开经典底座。带着对经典结构的敬意去看新论文，能读出更多。学术的兴奋容易让人忽视工程约束；工程的实用容易让人低估研究的价值。这个方向需要同时保持两种视角，才能做出好工作。

十二、一个给高年级本科或研究生的习题

在结束之前，布置一道思考题，读完本文的读者可以作为自检：

题：给你一份 1 亿条按时间排序的日志，key 是 (timestamp, host_id) 复合键。设计一个索引方案，给定 timestamp 范围 + host_id 做过滤，p95 响应时间要 < 10ms；索引占用内存越小越好。你会选 B+Tree、learned index、还是两者混合？给出具体结构。

提示方向：时间戳列 CDF 高度光滑，可以 RadixSpline；host_id 列离散，可以 B+Tree；如何组织两者的关系（先时间再 host？倒排？）决定了最终效率。这题没有唯一答案，但做完你会对本文所有概念有实战级的熟悉。

参考文献

1. T. Kraska et al., “The Case for Learned Index Structures”, SIGMOD 2018, https://dl.acm.org/doi/10.1145/3183713.3196909.

2. J. Ding et al., “ALEX: An Updatable Adaptive Learned Index”, SIGMOD 2020, https://dl.acm.org/doi/10.1145/3318464.3389711.

3. P. Ferragina and G. Vinciguerra, “The PGM-Index: A Fully-Dynamic Compressed Learned Index with Provable Worst-Case Bounds”, PVLDB 13(8), 2020, http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf.

4. A. Kipf et al., “RadixSpline: A Single-Pass Learned Index”, aiDM@SIGMOD 2020, https://arxiv.org/abs/2004.14541.

5. R. Marcus et al., “Benchmarking Learned Indexes”, PVLDB 14(1), 2020, http://www.vldb.org/pvldb/vol14/p1-marcus.pdf. 四类 learned index 的公平评测。

6. P. Ferragina, F. Lillo, G. Vinciguerra, “Why are learned indexes so effective?”, ICML 2020, https://arxiv.org/abs/2006.02473. 从 CDF 光滑性角度解释效果。

7. learnedsystems/RMI, GitHub, https://github.com/learnedsystems/RMI. Kraska 组的 RMI 参考实现。

8. microsoft/ALEX, GitHub, https://github.com/microsoft/ALEX.

9. gvinciguerra/PGM-index, GitHub, https://github.com/gvinciguerra/PGM-index.

上一篇: 学习型查询优化器：Neo、Bao、Balsa 到 LLM-CBO 下一篇: 自治数据库十年回顾：Peloton、NoisePage、OtterTune 到云原生 auto-tuning