SIGMOD’18 Learned Index

References

The Case for Learned Index Structures | Proceedings of the 2018 International Conference on Management of Data

Massachusetts Institute of Technology, Cambridge, MA, USA

https://dl.acm.org/doi/10.1145/3183713.3196909

Tim Kraska, MIT, The Case for Learned Index Structures

https://www.youtube.com/watch?v=MM33CvATm_M

[文献阅读] The Case for Learned Index Structures

我们常见的索引有三种：①B树，用于范围查询；②Hash索引，用于点查询；③BitMap索引，用于存在性检测。 对于上述的索引，本质上都是给定一个key，索引给出该key对应的数据的位置。稍微不同的地方在于，B树对应的…

https://zhuanlan.zhihu.com/p/536461846

Learned index-调研和分析

Postdoc at HUST

https://emperorlu.github.io/learned_index/

Abstract

• 索引就是模型：
• B-tree 索引可以看成是一个把 key 映射到有序数组中的一条 record 的模型；
• Hash 索引就可以看成是一个把 key 映射到无序数组中的一条 record 的模型；
• BitMap 索引就可以看做是一个表示一条数据记录存在与否的模型；

• 在这篇探索性研究论文中，我们从这个前提出发，假设所有现有的索引结构都可以被其他类型的模型所取代，包括深度学习模型，我们称之为学习索引。我们理论分析在什么样的条件下学习索引会比传统索引表现得更好，然后描述设计学习索引的主要挑战。

• 我们初步的结果表明我们的学习索引相比于传统索引有巨大的优势。更重要的是，我们相信通过学习模型取代数据管理系统核心组件的想法对未来的系统设计有着深远的影响，而这项工作只是提供了可能的一瞥。

Introduction

• 无论何时我们都需要高效的数据访问，索引结构就是这个问题的答案。存在大量的方案来解决不同访问模式下的需求。比如 B-tree 是范围请求下的最好选择，HashMap 在单 Key 点查询的性能上就独孤求败，BloomFilters 则是检查数据存在与否场景下最普遍的方案。因为数据库系统的重要性，过去几十年，索引已经被广泛调优，使其更加 memory, cache, and/or CPU efficient。

• 这些索引结构在设计时保证了通用性，不会对数据分布做任何假设，也不会利用在真实世界中最常见的 patterns。
• 假设目标是构建一个高度调优的系统来存储和范围查询 在一个连续的整数 key 区间的固定长度的数据（比如键从 1 到 100M），我们不会在键上使用传统的 B-Tree 索引，因为键本身就可以用作偏移量，这使得查找任何键或键范围的开始是 O(1) 而不是 O(log n) 操作。相应的，索引占据的内存大小也可以从 O(n) 减小到 O(1)。
• 可能让人惊喜的是，对于其他数据模式而言，相似的优化也是可行的；换句话说，知道确定的数据分布可以对几乎所有数据结构做高度优化

• 当然真实场景下数据并不会严格遵守已知的分布，而且为每个 use case 构建特定的解决方案的工程代价也太高了。但是我们认识 ML 带来了新的机会，可以学习得到一个反应数据 patterns 的模型，因此能够自动生成专门的索引结构，称为学习索引，工程成本低。

• 本文中，我们探索了学习模型，包括神经网络，可以用来增强甚至取代从 B 树到 BloomFilter 的传统索引结构的程度。这似乎是违反直觉的，因为 ML 不能提供我们传统上与这些索引相关联的语义保证，而且因为最强大的 ML 模型，神经网络，传统上被认为是非常昂贵的计算。然而，我们认为，这些明显的障碍都不像它们看起来那么成问题。相反，我们使用学习模型的建议有潜在的显著好处，特别是在下一代硬件上。

• 就语义保证而言，索引在很大程度上已经是一种学习模型，因此用其他类型的 ML 模型替换它们非常简单。例如，可以将 B-Tree 视为一个模型，它以键作为输入并预测数据记录在排序集中的位置 (必须对数据进行排序以实现有效的范围请求)。Bloom 过滤器是一种二元分类器，它基于一个键来预测一个键是否存在于集合中。显然，存在着微妙但重要的差异。例如，布隆过滤器可以有假阳性，但不能有假阴性。然而，正如我们将在本文中展示的那样，可以通过新颖的学习技术和/或简单的辅助数据结构来解决这些差异。

• 在性能方面，我们观察到每个 CPU 都已经具有强大的 SIMD 功能，我们推测许多笔记本电脑和移动电话将很快拥有图形处理单元 (GPU) 或张量处理单元 (TPU)。我们也有理由推测 CPU-SIMD/GPU/TPU 将变得越来越强大，因为它比通用指令集更容易扩展神经网络使用的有限 (并行)数学运算集。因此，在未来，执行神经网络或其他 ML 模型的高成本实际上可以忽略不计。例如，英伟达和谷歌的 TPU 已经能够在一个周期内执行数千甚至数万个神经网络操作。此外，有人指出，到 2025 年，GPU 的性能将提高 1000 倍，而 CPU 的摩尔定律基本上已经失效。通过用神经网络取代重分支索引结构，数据库和其他系统可以从这些硬件趋势中受益。虽然我们看到了在专用硬件 (如 TPU) 上学习索引结构的未来，但本文完全关注 CPU，并且令人惊讶地表明，即使在这种情况下，我们也可以获得显着的优势。

• 值得注意的是，我们并不主张用学习索引完全取代传统的索引结构。相反，本文的主要贡献是概述和评估一种构建索引的新方法的潜力，它补充了现有的工作，并且可以说，为一个已有几十年历史的领域开辟了一个全新的研究方向。这是基于一个关键的观察，即许多数据结构可以分解为一个学习模型和一个辅助结构，以提供相同的语义保证。这种方法的潜在威力来自于这样一个事实，即描述数据分布的连续函数可以用来构建更有效的数据结构或算法。在对只读的分析型工作负载的合成数据集和真实数据集进行评估时，我们从经验上得到了非常符合预期的结果。然而，许多尚未解决的挑战仍然存在，例如如何处理写负载繁重的工作负载，我们概述了未来工作的许多可能方向。此外，我们相信我们可以使用相同的原理来替换(数据库)系统中常用的其他组件和操作。如果成功，将学习到的模型深度嵌入算法和数据结构的核心思想可能会导致与当前系统开发方式的彻底背离。

Range Index

• 范围索引结构，比如 B-tree，已经是模型了：给定一个键，预测 value 在对应按键排序的数据集中的位置。考虑在一个分析型的内存数据库中的为有序的主键构建的 B-tree 索引，如下所示。B-Tree 提供了一个从查询键到有序数组中位置的映射，保证这个位置上的数据对应的键是第一个等于或者大于要查询的键。数据必须有序以支持范围查询。对于二级索引也同样适用，只是对应的数据为一个由 <key,record_pointer> 组成的 list。

• 出于效率原因，不会为每个单独的数据索引一个键，而是为每 n 条记录维护一个键，比如一个 page 一个 key。因此我们可以确保在一个连续的内存区域上固定长度的记录和逻辑分页，比如单个数组，而不是分布在不同内存区域的物理页面。（后面会讨论物理页面和变长的记录）。只索引每个页面的第一个键可以显著减小键的个数，而且不会造成明显的性能损失。因此，B-tree 就是一个模型，或者用 ML 的专业术语来说，就是一个回归树 regression tree：它将键映射到具有最小误差和最大误差之间的位置(最小误差为0，最大误差为页面大小)，并保证如果该键存在，则可以在该区域找到该键。因此，我们可以用其他类型的 ML 模型(包括神经网络)替换索引，只要它们也能够提供类似的关于最小和最大误差的强保证。

• 乍一看，似乎很难为其他类型的 ML 模型提供相同的保证，但实际上它非常简单。
• 首先，B-Tree 只对存储的键提供最小和最大错误保证，而不是对所有可能的键提供最大和最小错误保证。对于新数据，B 树需要重新平衡，或者在机器学习术语中重新训练，以仍然能够提供相同的错误保证。也就是说，对于单调模型，我们唯一需要做的就是对每个键执行模型，并记住位置的最坏预测，以计算最小和最大误差。
• 其次，更重要的是，甚至不需要强错误界限。无论如何，数据必须排序以支持范围请求，因此任何错误都可以通过围绕预测的局部搜索 (例如，使用 指数搜索) 轻松纠正，因此，甚至允许非单调模型。因此，我们可以用任何其他类型的回归模型(包括线性回归或神经网络)代替 B 树(见图1(b))。

• 现在在替换 B-tree 之前有其他技术挑战需要解决。比如，B 树的插入和查找成本有限，并且特别擅长利用缓存。此外，B 树可以将键映射到没有连续映射到内存或磁盘的页面。所有这些都是有趣的挑战/研究问题，并将在本节和附录中更详细地解释，以及潜在的解决方案

• 同时，使用其他类型的模型作为索引可以提供巨大的好处。最重要的是，它有可能将 B-Tree 查找的 log N 成本转换为常数操作。例如，假设一个数据集具有 1M 条唯一键，其值从 1M 到 2M (因此值 1,000,009 存储在位置 10)。在这种情况下，由单个乘法和加法组成的简单线性模型可以完美地预测点查找或范围扫描的任何键的位置，而 B-Tree 则需要 log n 次操作。机器学习的美妙之处在于，尤其是神经网络，它们能够学习各种各样的数据分布、混合和其他数据特性和模式。挑战在于平衡模型的复杂性和准确性。

• 对于本文中的大多数讨论，我们保留了本节的简化假设：我们仅对内存中按键排序的密集数组进行索引。这可能看起来很限制，但是许多现代硬件优化的 B 树，例如 FAST，做出了完全相同的假设，并且这些索引在内存数据库系统中非常常见，因为它们比扫描或二分搜索具有更好的性能。然而，虽然我们的一些技术可以很好地转化为某些场景(例如，具有非常大块的磁盘驻留数据，例如 Bigtable 中使用的)，但对于其他场景(细粒度分页，插入繁重的工作负载等)，需要进行更多的研究。在附录 D.2 中，我们将更详细地讨论其中的一些挑战和可能的解决方案

What Model Complexity Can We Afford?

• 为了更好地理解模型的复杂性，重要的是要知道在遍历 B-Tree 所需的相同时间内可以执行多少操作，以及模型需要达到什么精度才能比 B-Tree 更有效？

• 考虑 B-Tree 索引了 100M 条记录，页面大小 100，我们可以把每个 B 树节点看作是划分空间的一种方式，减少“错误”并缩小区域以找到数据。因此，我们说页大小为 100 的 B-Tree 每个节点的精度增益 precision gain 为 1/100，我们需要遍历总共 个节点。因此，第一个节点将空间从 100M 划分到 100M/100 = 1M，第二个节点将空间从 1M 划分到 1M/100 = 10K，以此类推，直到我们找到记录。现在，用二分搜索遍历单个 B 树页面大约需要 50 个周期，并且很难并行化。尽管存在 SIMD 优化的索引结构，如 FAST，但它们只能将控制依赖转换为内存依赖。这通常比使用简单的缓存内数据依赖项的乘法要慢得多，而且正如我们的实验所显示的那样，SIMD 优化的索引结构(如 FAST) 并没有明显快得多。相反，一个现代 CPU 可以每个 cycle 里做8-16 个 SIMD 操作，因此，只要模型的精度增益优于每 50 * 8 = 400 个算术运算 1/100，它就会更快。注意，此计算仍然假设所有 B-Tree 页面都在缓存中。一次缓存缺失需要 50-100 个额外的周期，因此可以使用更复杂的模型。

• 此外，机器学习加速器正在彻底改变游戏规则。它们可以在相同的时间内运行更复杂的模型，并卸载 CPU 的计算。例如，英伟达公司最新的 Tesla V100 GPU 能够实现 120 TeraFlops 的低精度深度学习算术运算（每周期 ≈ 60,000 次运算）。假定整个学习索引都能容纳在 GPU 的内存中（我们将在第 3.7 节中说明这是一个非常合理的假设），那么只需 30 个周期，我们就能执行 100 万次神经网络运算。当然，从 GPU 传输输入和检索结果的延迟仍然要高得多，但考虑到批处理和/或最近将 CPU/GPU/TPU 更紧密集成的趋势，这个问题并非不可克服。最后，可以预见的是，GPU/TPU 的性能和每秒浮点运算/进制运算的次数将继续增加，而 CPU 在提高执行 if 语句性能方面的进展基本上停滞不前。尽管我们认为 GPU/TPU 是在实践中采用学习型索引的主要原因之一，但在本文中，我们还是将重点放在局限性更大的 CPU 上，以便更好地研究在不影响硬件变化的情况下通过机器学习替换和增强索引的意义。

Range Index Models are CDF Models

• 如本节开头所述，索引是一个以键为输入并预测记录位置的模型。而对于点查询，记录的顺序无关紧要，对于范围查询，数据必须根据查找键排序，以便可以有效地检索范围 (例如，在一个时间框架内) 中的所有数据项。这导致了一个有趣的观察结果：预测给定键在排序数组中的位置的模型有效地近似于累积分布函数 (CDF)。我们可以对数据的 CDF 建模来预测位置为 。
• 其中 p 就是预估的位置；F(Key) 就是数据的估计累积分布函数，用于估计观察到小于或等于要查询的键的可能性 P(X ≤ Key)；N 就是总的键的个数。
• 这一观察结果开辟了一系列有趣的新方向
• 首先，它意味着索引实际上需要学习数据分布。B 树通过构建回归树来学习数据分布。线性回归模型将通过最小化线性函数的(平方)误差来学习数据分布。
• 其次，估计数据集的分布是一个众所周知的问题，学习索引可以从几十年的研究中受益。
• 第三，学习 CDF 在优化其他类型的索引结构和潜在算法方面也起着关键作用，我们将在本文后面概述。
• 第四，关于理论 CDFs 与经验 CDFs 的接近程度的研究已有很长的历史，这为从理论上理解这种方法的好处提供了一个立足点。我们在附录 a 中对我们的方法进行了高层次的理论分析

A First, Naïve Learned Index

• 为了更好地理解通过学习模型替换 B 树的需求，我们使用了200M 的 web 服务器日志记录，目标是使用 Tensorflow 在时间戳上构建二级索引。我们使用 ReLU 激活函数训练了一个双层全连接神经网络，每层有 32 个神经元；时间戳是输入特征，排序数组中的位置是标签。之后，我们测量了一个随机选择的键的查找时间(忽略 first numbers 后的几次运行的平均值，即忽略前几次的数据)， Tensorflow 和 Python 作为前端。

• 在此设置中，我们实现了每秒 ≈1250 个预测，即使用 Tensorflow 执行模型需要 ≈80,000 纳秒(ns)，而不需要搜索时间(从预测位置找到实际记录的时间)。作为比较点，在相同数据上的 B 树遍历大约 ≈300ns，在整个数据上的二分搜索大约 ≈900ns。仔细一看，我们发现 naïve 方法在几个关键方面是有限的：
• (1) Tensorflow 的设计是为了有效地运行大型模型，而不是小型模型，因此，调用开销很大，特别是在 Python 作为前端时
• (2) B 树，或一般的决策树，在使用一些操作过拟合数据方面确实很好，因为它们使用简单的 if 语句递归地划分空间。相比之下，其他模型可以更有效地近似到 CDF 的一般形状，但在单个数据实例级别的准确性方面存在问题。要查看这一点，请再次考虑图 2。从图中可以看出，从顶层来看，CDF 函数看起来非常平滑和规则。但是，如果把单个记录放大，就会发现越来越多的不正常现象。这是一个众所周知的统计效应。因此，像神经网络、多项式回归等模型可能会更有效地利用 CPU 和空间，将整个数据集中的 item 位置缩小到数千个区域，但单个神经网络通常需要更多的空间和 CPU 时间来“最后一英里”，以进一步将误差从数千个减少到数百个。
• (3) B 树具有极高的缓存和操作效率，因为它们始终将顶部节点保存在缓存中，并在需要时访问其他页面。相比之下，标准神经网络需要所有的权重来计算预测，这在乘法次数上代价很高。

THE RM-INDEX

• 为了克服这些挑战并探索模型作为索引替代或优化的潜力，我们开发了学习索引框架 (LIF)、递归模型索引 (RMI) 和基于标准错误的搜索策略。我们主要关注简单的、全连接的神经网络，因为它们的简单性和灵活性，但我们相信其他类型的模型可能会提供额外的好处。

The Learning Index Framework (LIF)

• LIF 可以看作是一个索引综合体系；给定一个索引规范，LIF 会生成不同的索引配置，对它们进行优化，并自动对它们进行测试。虽然 LIF 可以实时学习简单的模型(例如线性回归模型)，但它依赖于 Tensorflow 来学习更复杂的模型(例如神经网络)。然而，它从不在推理中使用 Tensorflow。相反，给定一个训练好的 Tensorflow 模型，LIF 会自动从模型中提取所有权重，并根据模型规范在 C 语言中生成有效的索引结构。我们的代码生成是专门为小型模型设计的，它消除了 Tensorflow 管理大型模型时所有不必要的开销和工具。这里我们利用了[25]中的想法，它已经展示了如何避免 Spark 运行时的不必要开销。因此，我们能够在 30 纳秒的量级上执行简单的模型。然而，应该指出的是，LIF 仍然是一个实验性框架，并且被工具化以快速评估不同的索引配置(例如，ML 模型、页面大小、搜索策略等)，这会以额外的计数器、虚拟函数调用等形式引入额外的开销。此外，除了由编译器完成的向量化之外，我们没有使用特殊的 SIMD 特性。虽然这些低效率在我们的评估中并不重要，因为我们通过始终使用我们的框架来确保公平的比较，对于生产设置或将报告的性能数字与其他实现进行比较时，应该考虑/避免这些低效率。

The Recursive Model Index

• 如 2.3 节所述，构建替代 B 树的学习模型的关键挑战之一是最后一英里 last mile 搜索的准确性（即用户接近找到他们所需信息的阶段，搜索结果的准确性和相关性）。例如，使用单个模型将 100 万条记录的预测误差减少到数百条通常是困难的。但是，将误差从 100M 减小到 10K，例如，通过一个模型将 B-Tree 的前 2 层替换为 100*100 = 10000 的精度增益，即使是简单的模型也容易实现。类似地，将误差从 10K 减少到 100 是一个更简单的问题，因为模型可以只关注数据的一个子集。

• 基于这一观察，并受到专家混合工作[62]的启发，我们提出了递归回归模型(见图3)。也就是说，我们建立了一个模型层次结构，在每个阶段模型都将 Key 作为输入，并在此基础上选择另一个模型，直到最后阶段预测位置。更正式地说，对于我们的模型 ，其中 x 是键，y [0, N) 是位置，我们假设在阶段 有 个模型。我们在第 0 阶段训练模型，，因此，在阶段 的模型 ，用 表示，其训练损失为:

• 注意，我们在这里使用 递归执行如下公式。总的来说，我们用损失 迭代地训练每个阶段以构建完整的模型。

• 考虑不同模型的一种方法是，每个模型对键的位置进行预测时存在一定的误差，然后使用该预测来选择下一个模型，该模型负责键空间的特定区域，以便以更低的误差进行更好的预测。然而，递归模型索引不一定是树。如图 3 所示，一个阶段的不同模型可能在下一阶段选择相同的模型。此外，每个模型不一定像 B 树那样覆盖相同数量的记录(例如，页大小为 100 的 B 树覆盖 100 条或更少的记录) 最后，根据所使用的模型，不同阶段之间的预测不一定可以解释为位置估计，而应该被认为是选择一个对某些关键有更好知识的专家(参见[62])。

• 这种模型体系结构有几个好处:
• (1) 它将模型大小和复杂性与执行成本分离开来
• (2) 它利用了易于学习数据分布的整体形状的事实
• (3) 它有效地将空间划分为更小的子区域，如 B 树，使其更容易以更少的操作实现所需的“最后一英里”精度。
• (4) 在两个阶段之间不需要搜索过程。例如，直接使用模型 1.1 的输出来选择下一阶段的模型。这不仅减少了管理结构的指令数量，而且还允许将整个索引表示为 TPU/GPU 的稀疏矩阵乘法。

Hybrid Index

• 递归模型索引的另一个优点是，我们能够构建混合模型。例如，在顶层，一个小型的 ReLU 神经网络可能是最好的选择，因为它们通常能够学习大范围的复杂数据分布，而在模型层次的底层，模型可能是数千个简单的线性回归模型，因为它们在空间和执行时间上都不昂贵。此外，如果数据特别难以学习，我们甚至可以在底部阶段使用传统的 B 树。

• 在本文中，我们重点研究了 2 种模型，即具有 0 到 2 个完全连接隐藏层和 ReLU 激活函数的简单神经网络，层宽度高达 32 个神经元和 B 树(又名决策树)。注意，零隐藏层神经网络等价于线性回归。给定一个索引配置，其中指定了阶段的数量和每个阶段的模型数量作为一个大小数组，混合索引的端到端训练如算法 1 所示

• 从整个数据集(第3行)开始，它首先训练 top-node 模型。根据这个顶级节点模型的预测，它从下一阶段(第 9 行和第 10 行)选择模型，并添加属于该模型的所有键(第 10 行)。最后，在混合索引的情况下，如果绝对最小/最大误差高于预定义的阈值，则通过用 B 树替换 NN 模型来优化索引(第 11-14 行)。

• 注意，我们在最后阶段存储了每个模型的标准误差、最小误差和最大误差。这样做的好处是，我们可以根据每个键使用的模型单独限制搜索空间。目前，我们通过简单的网格搜索来调整模型的各种参数(即，阶段的数量，每个模型的隐藏层等)。然而，存在许多潜在的优化来加速从 ML 自动调整到采样的训练过程。

• 注意，混合索引允许我们将学习索引的最坏情况性能与 B 树的性能绑定在一起。也就是说，在极其难以学习数据分布的情况下，所有模型都将自动被 B 树取代，使其实际上成为一个完整的 B 树。

Search Strategies and Monotonicity

• 范围索引通常实现一个 upper_bound(key)[lower_ bound(key)] 接口，用于查找在排序数组中等于或高于查找键的第一个键的位置，以有效地支持范围请求。因此，对于学习范围索引，我们必须根据预测从查找键中找到更高[更低]的第一个键。尽管付出了许多努力，但反复报道[8]，对于具有小有效负载的记录，二分搜索或扫描通常是在排序数组中找到键的最快策略，因为替代技术的额外复杂性很少得到回报。然而，学习索引在这里可能有一个优势：模型实际上预测键的位置，而不仅仅是键的区域(即页面)。下面我们将讨论两种利用这些信息的简单搜索策略:
• Model Biased Search （模型偏差搜索）：我们的默认搜索策略，它与传统的二分搜索的唯一不同之处在于第一个中间点被设置为模型预测的值。
• Biased Quaternary Search：第四元搜索不是一个分割点，而是三个点，希望硬件一次预取所有三个数据点，以便在数据不在缓存中时获得更好的性能。在我们的实现中，我们将四元搜索的初始三个中点定义为 pos−σ， pos, pos + σ。也就是说，我们猜测我们的大多数预测是准确的，并将我们的注意力首先集中在位置估计上，然后我们继续进行传统的第四纪搜索。

• 对于我们所有的实验，我们使用最小误差和最大误差作为所有技术的搜索区域。也就是说，我们对每个键执行 RMI 模型，并存储每个最后阶段模型中最糟糕的过度和不足预测。虽然这种技术保证找到所有现有的键，但是对于不存在的键，如果 RMI 模型不是单调的，它可能返回错误的上界或下界。为了克服这个问题，一种选择是迫使我们的 RMI 模型是单调的，就像机器学习中研究的那样。

• 或者，对于非单调模型，我们可以自动调整搜索区域。也就是说，如果找到的上(下)界键位于由最小误差和最大误差定义的搜索区域的边界上，我们就增量地调整搜索区域。然而，另一种可能性是，使用指数搜索技术。假设存在正态分布误差，这些技术的平均效果应该与其他搜索策略一样好，同时不需要存储任何最小和最大误差。

Indexing Strings

• 我们主要关注索引实值键，但许多数据库依赖于索引字符串，幸运的是，重要的机器学习研究已经集中在字符串建模上。和前面一样，我们需要设计一个高效且富有表现力的字符串模型。为字符串做好这一点带来了许多独特的挑战。

• 第一个设计考虑是如何将字符串转换为模型的特征，通常称为标记化。为了简单和高效，我们考虑一个 n 长度的字符串是一个特征向量 x∈Rn，其中 xi 是 ASCII 十进制值(或Unicode十进制值，取决于字符串)。此外，如果所有输入的大小相等，大多数 ML 模型的运行效率会更高。因此，我们将设置最大输入长度 N。因为数据是按字典顺序排序的，所以我们将在标记化之前将键截断为长度 N。对于长度 n < N 的字符串，当 i > n 时，设置 xi = 0。

• 为了提高效率，我们通常采用与实值输入类似的建模方法。我们学习了一个相对较小的前馈神经网络的层次结构。唯一不同的是，输入不是单个实值 x，而是一个向量 x。线性模型 w·x + b 将乘法和加法的数量与输入长度 N 线性缩放。前馈神经网络即使只有一个宽度为 h 的隐藏层，也将进行 O(hN) 次乘法和加法运算

• 最终，我们相信未来会有大量的研究可以优化字符串键的学习索引。例如，我们可以很容易地想象其他标记化算法。在自然语言处理中，有大量关于字符串标记化的研究，将字符串分解为ML模型更有用的片段，例如翻译中的词块。此外，将后缀树的思想与学习索引结合起来以及探索更复杂的模型架构 (例如，循环和卷积神经网络) 可能会很有趣。

Training

• 虽然训练(即加载)时间不是本文的重点，但应该指出的是，我们所有的模型，浅神经网络甚至简单的线性/多元回归模型，训练速度都相对较快。尽管简单的神经网络可以使用随机梯度下降有效地训练，并且可以在不到一到几次的随机数据中收敛，但线性多变量模型(例如，也是0层神经网络)存在封闭形式的解决方案，并且它们可以在排序数据的单次传递中进行训练。因此，对于200M 记录，训练一个简单的 RMI 索引只需要几秒钟的时间(当然，这取决于执行了多少自动调优)；根据复杂度的不同，神经网络可以在每个模型的几分钟内进行训练。还要注意，通常没有必要在整个数据上训练顶级模型，因为这些模型甚至在对整个随机数据进行一次扫描之前就经常收敛。这在一定程度上是因为我们使用简单的模型，并且不太关心精度的最后几位数，因为它对索引性能的影响很小。最后，来自 ML 社区的关于提高学习时间的研究[27,72]适用于我们的背景，我们期望在这个方向上有很多未来的研究。

Results

• 我们在几个真实数据集和合成数据集上对学习范围索引的空间和速度进行了评估，并对比了其他读优化索引结构。

整数数据集

• 作为第一个实验，我们使用 2 阶段 RMI 模型和不同的第二阶段大小(10k、50k、100k和200k)与具有不同页面大小的读优化 B-Tree 在三个不同的整数数据集上比较了学习索引。对于数据，我们使用了 2 个真实世界的数据集，(1)Weblogs 和 (2)Maps[56]，以及 (3)一个合成数据集Lognormal。Weblogs 数据集包含 200 万个日志条目，记录了几年来对一个主要大学网站的每次请求。我们使用唯一的请求时间戳作为索引键。这个数据集几乎是学习索引的最坏情况，因为它包含非常复杂的时间模式，包括课表、周末、假期、午休、部门活动、学期休息等，这些都是出了名的难以学习。对于地图数据集，我们索引了全世界约 200M 用户维护的特征(例如，道路，博物馆，咖啡店)的经度。毫不奇怪，位置的经度是相对线性的，并且比 Weblogs 数据集具有更少的不规则性。最后，为了测试索引在重尾分布上的工作情况，我们生成了一个合成数据集，其中包含从 μ =0 和 σ = 2 的对数正态分布中采样的 190M 个唯一值。这些值被按比例放大为整数，最大可达 1B。这些数据当然是高度非线性的，这使得使用神经网络学习 CDF 更加困难。对于所有 B-Tree 实验，我们使用 64 位键和 64 位 payload/value。

• 作为我们的基准，我们使用了一个类似于 stx::btree 的产品质量 B-Tree 实现，但进行了进一步的 cacheline 优化、密集页面(即填充系数为100%)和非常有竞争力的性能。为了优化两阶段的学习索引，我们使用了简单的网格搜索，神经网络具有 0 到 2 个隐藏层，层宽范围为 4 到 32 个节点。一般来说，我们发现第一阶段的简单(0个隐藏层)到半复杂(2个隐藏层和8或16个宽)模型效果最好。在第二阶段，简单的线性模型表现最好。这并不奇怪，因为在最后一英里，执行复杂的模型通常是不值得的，线性模型可以最优地学习。

• Learned Index vs B-Tree performance:
• 主要结果如图4所示。注意，B-tree 的页大小表示每页的键数，而不是字节大小，字节大小实际上更大。作为主要指标，我们以 MB 为单位显示大小，以纳秒为单位显示总查找时间，以纳秒为单位显示执行模型的时间 (B-Tree遍历或ML模型)，并以与总时间相比的百分比表示。此外，作为大小和查找列的一部分，我们在括号中显示了与页面大小为 128 的 B-Tree 相比的加速和空间节省。我们选择页面大小为 128 作为固定参考点，因为它为 B-树提供了最佳的查找性能(注意，通过根本没有索引来节省空间总是很容易牺牲查找性能)。加速和大小列中的颜色编码表示索引相对于参考点的快或慢(大或小)。
• 如你所见，学习索引在几乎所有的配置中都优于 B-Tree 索引，速度高达 1.5 - 3 倍，而空间却要小两个数量级。当然，B 树可以进一步压缩，但要以 CPU 时间为代价进行解压缩。然而，大多数这些优化是正交的，并且同样适用于(如果不是更多的话)神经网络。例如，神经网络可以通过使用 4 位或 8 位整数而不是 32 位或 64 位浮点值来表示模型参数来进行压缩(这个过程称为量化)。这种级别的压缩可以为学习索引带来额外的收益。
• 不出所料，第二阶段的大小对索引大小和查找性能有重大影响。与§2.1中的分析相比，在第二阶段使用 10,000 或更多的模型尤其令人印象深刻，因为它表明我们的第一阶段模型可以比 B 树中的单个节点在精度上有更大的跳跃。最后，我们没有报告混合模型或其他搜索技术，相比于二分，没有提供显著的好处

• Learned Index vs Alternative Baselines
• 除了根据我们的 read-optimized B-tree 对学习索引进行详细评估外，我们还将学习索引与其他可选基线(包括第三方实现)进行比较。下面，我们将讨论一些可供选择的基线，并在适当的情况下将它们与学习索引进行比较:
• Histogram：B 树近似底层数据分布的CDF。一个明显的问题是直方图是否可以用作 CDF 模型。原则上，答案是肯定的，但是为了实现快速数据访问，直方图必须是 CDF 的低误差近似值。这通常需要大量的桶，这使得搜索直方图本身的成本很高。如果桶具有不同的桶边界以有效地处理数据倾斜，那么只有少数桶是空的或太满的，则尤其如此。这个问题的明显解决方案是生成 B 树，因此不再进一步讨论直方图。
• Lookup-Table：B 树的一个简单替代方案是(分层)查找表。通常，查找表具有固定的大小和结构(例如，64个槽，每个槽指向另外64个槽，等等)。查找表的优势在于，由于其固定大小，可以使用AVX指令对其进行高度优化。我们包含了一个与3阶段查找表的比较，该表是通过获取每64个键并将其放入包含填充的数组中来构造的，使其成为64的倍数。然后，我们在没有填充的情况下对数组再次重复该过程，总共创建两个数组。为了查询一个键，我们在上表上使用二分搜索，然后对第二个表和数据本身进行AVX优化的无分支扫描。与其他选择(例如，在顶层使用扫描，或在第二个数组或数据上使用二分搜索)相比，这种配置导致最快的查找时间。
• FAST：是一个高度 SIMD 优化的数据结构。我们使用[47]中的代码进行比较。但是，应该注意的是，FAST 总是需要以 2 的幂分配内存来使用无分支的 SIMD 指令，这可能会导致更大的索引。
• Fixed-size B-Tree & interpolation search：最后，正如最近的一篇博客文章[1]中提出的那样，我们创建了一个具有插值搜索的固定高度 B 树。设置 B-Tree 的高度，使树的总大小为 1.5MB，与我们学习的模型相似。
• Learned indexes without overhead：对于我们的学习索引，我们使用了一个两阶段的RMI 索引，顶部是多元线性回归模型，底部是简单线性模型。我们对顶层模型使用了简单的自动特征工程，通过自动创建和选择 key、log(key)、key^2 等形式的特征。多元线性回归是神经网络的一个有趣的替代方案，因为它特别适合于只需要少量操作就能拟合非线性模式。此外，我们在基准测试框架之外实现了学习索引，以确保公平比较。
• 为了进行比较，我们使用了带有 8 字节指针负载的 Lognormal 数据。结果如图 5 所示。可以看到，对于公平条件下的数据集，学习索引提供了最佳的整体性能，同时节省了大量内存。应该注意的是，由于对齐要求，FAST 索引很大。
• 虽然结果非常有希望，但我们绝不声称学习索引在大小或速度方面总是最好的选择。相反，学习索引提供了一种思考索引的新方法，需要进行更多的研究才能完全理解其含义

• String Datasets:
• 我们还创建了一个包含1000万个非连续文档 id 的二级索引，该索引是 Google 实际产品的一部分，用于测试学习索引在字符串上的表现。基于字符串的文档 id 数据集的结果如图 6 所示，其中现在还包括混合模型。此外，我们在表中包含了我们的最佳模型，这是一个非混合的 RMI 模型索引，具有四元搜索，命名为 Learned QS (表底部)。所有 RMI 索引在第二阶段使用了 10,000 个模型，对于混合索引，我们使用了两个阈值，128 和 64，作为模型在被 B 树取代之前的最大容忍绝对误差。
• 可以看到，字符串上学习索引的加速并不明显。部分原因是模型执行的成本相对较高，这是 GPU/ TPU 可以解决的问题。此外，搜索字符串的代价要高得多，因此更高的精度往往是值得的；这就是为什么混合索引通过 B 树取代性能差的模型有助于提高性能的原因。
• 由于搜索的成本，不同的搜索策略会产生更大的差异。例如，图 6 所示，具有 1 隐藏层和有偏二叉搜索的 NN 的搜索时间为 1102ns。相比之下，我们在相同模型下的偏置第四纪搜索 biased quaternary search 只需要 658ns，这是一个显著的改进。偏置搜索和四元搜索性能较好的原因是它们考虑了模型误差。

Point Index

• 除了范围索引之外，用于点查找的哈希映射在 DBMS 中也起着类似的重要作用。从概念上讲，哈希映射使用哈希函数来确定地将键映射到数组中的位置(参见图7(a))。任何有效的哈希映射实现的关键挑战是防止太多不同的键被映射到哈希映射中的相同位置，因此称为冲突。例如，假设有 100 万条记录，Hash-map 大小为 100 万条。对于统一随机化键的哈希函数，期望冲突的数量可以类似于生日悖论，并且期望在 33% 或 33M 插槽左右。对于每一种冲突，Hash-map 架构都需要处理这种冲突。例如，单独的链哈希映射将创建一个链表来处理冲突(参见图7(a))。然而，存在许多替代方案，包括二次探测，使用具有多个槽的桶，最多同时使用多个哈希函数(例如，Cuckoo hash[57]所做的)。

• 然而，无论采用何种 Hash-map 架构，冲突都可能对性能和/或存储需求产生重大影响，机器学习模型可能提供减少冲突数量的替代方案。虽然将模型作为哈希函数来学习的想法并不新鲜，但现有的技术并没有利用底层数据分布。例如，各种完美的哈希技术[26]也试图避免冲突，但作为哈希函数的一部分使用的数据结构随着数据大小而增长；学习模型可能没有的属性(回想一下，索引 1 到 100M 之间的所有键的例子)。据我们所知，是否有可能学习产生更有效的点索引的模型还没有被探索过。

The Hash-Model Index

• 令人惊讶的是，学习 Key 分布的 CDF 是学习更好的哈希函数的一种潜在方法。然而，与范围索引相比，我们的目标不是紧凑地存储记录或严格排序。相反，我们可以根据哈希映射的目标大小 M 来缩放 CDF，并使用 h(K)=F(K)*M 作为我们的哈希函数，K 为键。如果模型 F 完全学习了键的经验 CDF，则不存在冲突。此外，哈希函数与实际的哈希映射体系结构是正交的，可以与单独的链或任何其他哈希映射类型结合使用。

• 对于模型，我们可以再次利用前一节中的递归模型体系结构。显然，像以前一样，索引的大小和性能之间存在权衡，这受到模型和数据集的影响。

• 注意，如何处理插入、查找和冲突取决于 Hash-map 体系结构。因此，与传统哈希函数(将键映射到均匀分布的空间)相比，学习哈希函数提供的优势取决于两个关键因素:(1) 模型表示观察到的 CDF 的准确性。例如，如果数据是由均匀分布生成的，那么简单的线性模型将能够学习一般的数据分布，但生成的哈希函数不会比任何充分随机化的哈希函数更好。(2) 哈希映射架构：根据架构、实现细节、有效负载(即值)、冲突解决策略，以及将分配或可以分配多少内存(即插槽)，显著影响性能。例如，对于小键和小值或没有值，使用 Cuckoo 散列的传统散列函数可能会工作得很好，而更大的有效负载或分布式散列映射可能会从避免冲突中获益更多，从而从学习散列函数中获益更多。

Results

• 我们在前一节的三个整数数据集上评估了学习到的哈希函数的冲突率。作为我们的模型哈希函数，我们使用了前一节中的 2 阶段 RMI 模型，第 2 阶段有 100k 模型，没有任何隐藏层。作为基线，我们使用了一个简单的类似 murmurhash3 的散列函数，并比较了与记录槽数相同的表的冲突数量。

• 如图 8 所示，通过以合理的成本学习经验 CDF，学习到的模型可以在我们的数据集上减少多达77% 的冲突数量；执行时间与图 4 中的模型执行时间相同，约为 25-40ns。

• 在给定模型执行时间的情况下，减少冲突的好处取决于Hash-map架构、有效负载和许多其他因素。
• 例如，我们的实验(见附录B)表明，对于具有20字节记录的单独链散列映射架构，学习散列函数可以减少多达80%的存储浪费，而延迟仅比随机散列增加 13ns。它只增加了13ns而不是40ns的延迟的原因是，通常更少的冲突也会产生更少的缓存丢失，从而获得更好的性能。
• 另一方面，对于非常小的有效负载，使用标准哈希映射的cuckoo哈希可能仍然是最好的选择。然而，正如我们在附录C中所示，对于更大的有效负载，带有学习哈希函数的链哈希映射可以比杜鹃哈希和/或传统的随机哈希更快。
• 最后，我们看到了分布式设置的最大潜力。例如，NAM-DB[74]使用哈希函数在使用RDMA的远程机器上查找数据。由于每个冲突的成本非常高(即，每个冲突都需要一个额外的RDMA请求，其数量级为微秒)，因此模型执行时间可以忽略不计，即使冲突率的微小降低也可以显着提高整体性能。

• 综上所述，学习到的哈希函数独立于使用的哈希映射体系结构，并且取决于哈希映射体系结构，它们的复杂性可能值得也可能不值得。

EXISTENCE INDEX

• 最后一种常见的索引类型是存在索引，最重要的是Bloom过滤器，一种空间有效的概率数据结构，用于测试元素是否是集合的成员。它们通常用于确定密钥是否存在于冷存储中。例如，Bigtable使用它们来确定一个键是否包含在一个SSTable中

• 在内部，Bloom 过滤器使用大小为 m 的位数组和 k 个散列函数，每个散列函数将一个键映射到 m 个数组位置中的一个(参见图9(a))。要向集合中添加一个元素，需要向 k 个哈希函数提供一个键，并将返回位置的位设置为 1。为了测试一个键是否为集合的成员，再次将该键输入 k 个哈希函数以接收 k 个数组位置。如果这 k 个位置上有任何位是 0，那么这个键就不是集合的成员。换句话说，布隆过滤器确实保证不存在假阴性，但有潜在的假阳性。

• 虽然 Bloom 过滤器具有很高的空间效率，但它们仍然会占用大量内存。例如，对于 10 亿条记录，大约需要 1.76 GB。对于 0.01% 的FPR，我们需要 2.23 GB。已经有几次尝试提高布隆过滤器的效率[52]，但一般的观察结果仍然存在

• 然而，如果有某种结构可以确定集合的内部和外部是什么，这是可以学习的，那么就有可能构建更有效的表示。有趣的是，对于数据库系统的存在索引，延迟和空间需求通常与我们之前看到的大不相同。考虑到访问冷存储(例如磁盘甚至频带)的高延迟，我们可以负担得起更复杂的模型，而主要目标是最小化索引的空间和误报的数量。我们概述了使用学习模型构建存在性索引的两种潜在方法。

Learned Bloom filters

• 虽然范围索引和点索引都学习键的分布，但存在索引需要学习一个将键与其他所有内容分开的函数。换句话说，对于点索引来说，一个好的哈希函数应该是键之间很少有冲突的哈希函数，而对于布隆过滤器来说，一个好的哈希函数应该是键之间有很多冲突，非键之间也有很多冲突，但键和非键之间很少有冲突。下面我们将考虑如何学习这样的函数 f，以及如何将其合并到一个存在性索引中。

• 虽然传统的 Bloom 过滤器保证任何先验选择的查询集的假阴性率(FNR)为零和特定的假阳性率(FPR)[22]，但我们遵循的概念是，我们希望为现实查询提供特定的 FPR，特别是在保持 FNR 为零的同时。也就是说，我们在一个空白查询数据集上测量 FPR，这在评估 ML 系统中很常见[30]。虽然这些定义有所不同，但我们相信可以通过历史日志观察查询分布的假设在许多应用程序中都是成立的，尤其是在数据库中。

• 传统上，存在索引不使用键的分布，也不使用键与非键的区别，但学习过的 Bloom 过滤器可以。例如，如果我们的数据库包含 x 个整数时，只要计算如下公式，就可以在常数时间内计算存在性索引，并且几乎不占用内存。

• 在考虑 ML 目的的数据分布时，我们必须考虑非键数据集。在这项工作中，我们考虑了非键来自可观察历史查询的情况，并假设未来的查询来自与历史查询相同的分布。当这个假设不成立时，可以使用随机生成的键、由机器学习模型生成的非键[34]、重要性加权来直接解决协变量移位[18]，或者对抗性训练来增强鲁棒性[65]；我们把这个作为未来的工作。我们用 K 表示键的集合，用 U 表示非键的集合。

Bloom filters as a Classification Problem

• 构建存在性索引的一种方法是将其作为二元概率分类任务。也就是说，我们想学习一个可以预测查询 x 是键还是非键的模型 f。例如，对于字符串，我们可以训练一个循环神经网络(RNN)或卷积神经网络(CNN) [37,64]， D = {(xi, yi =1) | xi ∈ K} ∪ {(xi, yi =0) | xi ∈ U}。因为这是一个二元分类任务，我们的神经网络有一个 sigmoid 型激活来产生一个概率，并被训练成最小化对数损失:

• f(x) 的输出可以解释为 x 是我们数据库中的一个键的概率。因此，我们可以通过选择阈值 τ 将模型转换为存在性索引，我们将假设该键存在于我们的数据库中。与布隆过滤器不同，我们的模型可能具有非零的 FPR 和 FNR；事实上，随着 FPR 下降，FNR 会上升。为了保持存在索引的无假阴性约束，我们创建了一个溢出 Bloom 过滤器。即，我们考虑 K− τ= {x ∈K|f (x) < τ } 为 f 的假阴性集合，并为这个键子集创建一个 Bloom 过滤器。然后，我们可以像图9(c) 那样运行我们的存在索引：如果 f(x) ≥ τ，则认为键存在；否则，请检查溢出布隆过滤器。

• 一个问题是如何设置 τ，使我们学习的布隆滤波器具有期望的 FPR p。我们将模型的 FPR 表示为

• 这种设置是有效的，因为学习的模型相对于数据的大小可以相当小。此外，由于布隆过滤器随着键集的大小而缩放，溢出布隆过滤器将随着 FNR 而缩放。我们将通过实验看到，这种组合在减少存在索引的内存占用方面是有效的。

Bloom filters with Model-Hashes

• 构建存在索引的另一种方法是学习散列函数，其目标是最大化键和非键之间的冲突，同时最小化键和非键之间的冲突。有趣的是，我们可以使用与之前相同的概率分类模型来实现这一点。也就是说，我们可以创建一个哈希函数 d ，通过将其输出缩放为 d = f (x)∗m，将 f 映射到大小为 m 的位数组。因此，我们可以将 d 用作哈希函数，就像布鲁姆过滤器中的任何其他哈希函数一样。这样做的好处是，f 被训练成将大多数键映射到较高的位位置范围，而非键映射到较低的位位置范围(见图9(b))。对这种方法的更详细的解释见附录E。

Results

• 为了实验验证这一想法，我们探索了存在索引的应用，以跟踪黑名单钓鱼url。我们把谷歌透明度报告中的数据作为我们的一套键。”这个数据集由170万个唯一的url组成。我们使用一个负集，它是随机(有效)url和可能被误认为是网络钓鱼页面的白名单url的混合物。我们将负集随机分成训练集、验证集和测试集。我们训练字符级RNN(特别是GRU[24])来预测URL属于哪个集合;我们基于验证集设置 τ，并报告测试集上的FPR。

• 一个正常的布隆滤镜，需要 1% 的FPR，需要 2.04MB。我们考虑一个 16 维 GRU，每个字符有32维嵌入;此型号为0.0259MB。当建立一个可比的学习指数时，我们在验证集上设置τ为0.5% FPR;这就得到了55%的FNR。(测试集上的FPR为0.4976%，验证了所选阈值。)如上所述，我们的布隆过滤器的大小随FNR的变化而变化。因此，我们发现我们的模型加上溢出布隆过滤器使用1.31MB，大小减少了36%。如果我们想要强制执行0.1%的总体FPR，我们的FNR为76%，这将使Bloom过滤器的总大小从3.06MB降至2.59MB，内存减少15%。我们在图10中观察到这种一般关系。有趣的是，我们看到不同的大小模型如何以不同的方式平衡准确性与内存之间的权衡。

• 我们简要地考虑了在我们的查询分布中存在协变量移位的情况，我们在模型中没有解决这个问题。当只使用随机 url 的验证和测试集时，我们发现我们可以比 FPR 为 1% 的Bloom过滤器节省60%。当只使用白名单 url 的验证和测试集时，我们发现与 FPR 为1%的布隆过滤器相比，我们可以节省 21%。最终，负集的选择是特定于应用程序的，协变量移位可以更直接地解决，但这些实验旨在直观地说明该方法如何适应不同的情况。

• 显然，我们的模型越精确，节省的布隆过滤器尺寸就越好。其中一个有趣的特性是，我们的模型没有理由需要使用与 Bloom 过滤器相同的特征。例如，已经有大量研究使用 ML 来预测网页是否是钓鱼页面[10,15]。其他功能，如WHOIS数据或IP信息可以纳入模型，提高准确性，减少布隆过滤器的大小，并保持无假阴性的属性

• 此外，我们根据附录 E 第5.1.2节中的方法给出了其他结果。

Related Work

Conclusion and Future Work

• 我们已经证明，通过利用被索引的数据分布，学习索引可以提供显著的好处。这为许多有趣的研究问题打开了大门

Other ML Models

• 虽然我们的重点是线性模型和神经网络组合，但还有许多其他ML模型类型以及将它们与传统数据结构结合起来的方法，值得探索。

Multi-Dimensional Indexes

• 可以说，学习索引思想最令人兴奋的研究方向是将其扩展到多维索引。模型，尤其是神经网络，非常擅长捕捉复杂的高维关系。理想情况下，该模型将能够估计由任何属性组合过滤的所有记录的位置。

Beyond Indexing: Learned Algorithms

• 也许令人惊讶的是，CDF 模型也有可能加速排序和连接 Join，而不仅仅是索引。例如，加速排序的基本思想是使用现有的 CDF 模型 F 将记录大致按排序顺序排列，然后纠正接近完全排序的数据，例如，使用插入排序

GPU/TPUs

• 最后，正如本文多次提到的那样，GPU/TPU 将使学习索引的思想更加有价值。同时，GPU/TPU 也有自己的挑战，最重要的是高调用延迟。虽然假设所有学习索引都适合 GPU/TPU 是合理的，因为前面显示了异常的压缩比，但是调用任何操作仍然需要 2-3 微秒。

Summary

• 总之，我们已经证明了机器学习模型有潜力提供比最先进的索引更大的好处，我们相信这是未来研究的一个富有成效的方向。

附录

D. FUTURE DIRECTIONS FOR LEARNED B-TREES

• 在本文的主要部分，我们关注只读内存数据库系统的索引结构。在这里，我们概述了如何在未来扩展学习索引结构的思想。

Inserts and Updates

• 乍一看，插入似乎是学习索引的致命弱点，因为学习模型的成本可能很高，但是学习索引对于某些工作负载可能具有显著的优势。一般来说，我们可以区分两种类型的插入: (1) 追加插入和 (2)中间插入，例如在订单表上更新客户 id 上的二级索引。

• 让我们暂时关注第一种情况：追加。例如，我们可以合理地假设，对于web日志时间戳上的索引，就像我们之前的实验一样，大多数(如果不是全部)插入都将随着时间戳的增加而追加。现在，让我们进一步假设我们的模型泛化并且能够学习模式，这些模式也适用于未来的数据。因此，更新索引结构变成了一个 O(1) 操作;这是一个简单的追加，没有改变模型。而 B 树需要O(log n) 次操作来保持 B 树的平衡。对于中间的插入也可以提出类似的论点，但是，这些插入可能需要移动数据或在数据中保留空间，以便将新项放入正确的位置。

• 显然，这一观察也提出了几个问题。首先，在模型的通用性和“最后一英里”性能之间似乎存在一个有趣的权衡；可以说，“最后一英里”的预测越好，模型就越容易过度拟合，越不容易泛化到新的数据项。

• 其次，如果分布发生变化会发生什么?它可以被检测到吗?是否有可能提供与 B 树类似的强保证，B 树总是保证 0 (logn) 查找和插入成本? 虽然回答这个问题超出了本文的范围，但我们相信某些模型有可能实现它。更重要的是，机器学习提供了新的方法来调整模型以适应数据分布的变化，例如在线学习，这可能比传统的 B-Tree 平衡技术更有效。探索它们也是未来的工作。

• 最后，应该指出的是，总是存在通过构建增量索引来处理插入的更简单的替代方法[60]。所有的插入都保存在缓冲区中，并不时地与模型的潜在再训练合并。这种方法已经被广泛使用，例如在Bigtable[23]和许多其他系统中，并且最近在[32]中对学习索引进行了探索。

PAGING

• 在本节中，我们假设数据(实际记录或键)是指针。对存储在一个连续的块中。但是，特别是对于存储在磁盘上的数据的索引，将数据划分为存储在磁盘上单独区域的较大页面是很常见的。为此，我们观察到模型学习 CDF 不再成立，因为 pos = Pr(X < Key) ∗ N 被违反了。下面我们概述了几个解决这个问题的方法

• 利用 RMI 结构：RMI结构已经将空间划分为多个区域。通过对学习过程的小修改，我们可以最小化模型在它们覆盖的区域中重叠的数量。此外，还可能复制可能由多个模型访问的任何记录。

• 另一种选择是使用 <first_key, disk-position> 形式的附加转换表。对于翻译表，索引结构的其余部分保持不变。但是，如果磁盘页面非常大，这个想法将最有效。同时，可以使用带有最小和最大误差的预测位置来减少必须从大页面读取的字节数，因此页面大小的影响可以忽略不计。

• 对于更复杂的模型，实际上可以学习页面的实际指针。特别是如果使用文件系统来确定磁盘上的页面，并对磁盘上的块进行系统编号(例如，block1，…，block100)，则学习过程可以保持不变。

• 显然，为了更好地理解学习索引对基于磁盘的系统的影响，需要进行更多的研究。同时，显著的空间节省和速度优势使其成为未来工作的一个非常有趣的途径。