数据库中的机器学习：哈希表、B 树与学习索引
参考资料：
1. 主要内容
1.1 数据库索引
索引存在的意义：
- 我们有很多数据需要存储
- 我们需要快速查询一些特定条目
- 我们使用 索引 (Index) 完成这一任务
假设我们存储了许多数据，并且希望 快速 查找其中某条或者某个特定范围的数据时，索引 可以帮助我们实现这一点。这很重要，不论是对于分析软件还是机器学习使用者，只要我们构建了一些数据 Pipeline，当我们需要快速抓取所需数据时，我们就是索引结构的 “消费者”。而 学习索引 这个新研究方向的出现使得机器学习人员也可以成为索引结构的 “生产者”。
1.2 传统索引策略
几种常见的传统数据库索引结构及其应用场景：
- B 树：范围索引
- 哈希表：点索引
- Bloom 过滤器：存在索引
1.3 新的研究方向：学习索引
新型 学习索引 (Learned Index) 方向：
- Google 和 MIT 合作研究
- https://arxiv.org/abs/1712.01208
我们将介绍 Kraska 等人的这篇论文《The Case for Learned Index Structures》，他们提出了使用 RMI 等神经网络结构代替 B 树等传统索引结构的思路，开启了数据库领域的一个新的研究方向。
1.4 学习索引的优势在哪里
我们将探讨他们已经完成的初步研究工作：利用机器学习方法去解决之前传统索引结构解决过的一些问题，以及他们的对标实验和权衡比较：
- 什么情况下，传统算法具有优势？
- 什么情况下，学习索引具有优势？
- 实践中如何在两者之间进行权衡？
从长远看，学习索引可以更加充分利用硬件优势。随着指导预测 CPU 性能增长的摩尔定律日渐走向衰亡，目前来看，未来高性能计算将主要集中在 GPU 和并行数据指令集，机器学习方法可以很好地发挥这些优势，而传统索引结构很难做到这点。未来，随着 AI 工作负载在硬件方面的进一步深度优化，学习索引这类算法在未来将具有很大的发展潜力。
2. 什么是索引
我们先回顾一下索引：
- 索引可以帮助我们在海量数据中快速定位到某些特定条目。
- 尤其是当数据并没有按照我们要查询的字段排序时会非常有用。
假设我们存储了大量数据，当我们需要查询其中某些特定数据时，我们并不希望从头到尾扫描整个磁盘记录来寻找该数据，例如，当我们查询 “名字叫 Tim 的人有哪些” 或者 “某个特定日期范围内出生的人” 等，我们可以使用索引。
在数据库中，我们有很多行记录，每一行都存储在硬盘上，即下图中底部的块状条，其中每个格子代表一行记录：
假设现在我们想要查询名字为 Tim 的人对应的行记录所在的位置：
如果没有索引，整个查询过程将非常缓慢，因为我们需要依次扫描磁盘上的每一条记录。对于大公司而言，通常需要在数百万甚至数十亿条记录中搜索我们想要的结果，因此，这是一个计算成本和时间开销都非常高的过程：
为了解决这一问题，我们构建了一种辅助数据存储结构，称为索引。例如哈希表、B 树等等，我们将在后面对这些传统索引以及新型的学习索引进行讨论。假设我们构建了一个以用户名字为 Key 的索引结构，相比之前通过扫描整个表来查看数据库中的每条记录，现在我们可以直接询问索引 “嘿，名字为 Tim 的记录在哪里？”，然后索引将告诉我们名字为 Tim 的记录的内存地址的偏移量为 7。我们可以基于任何我们想要的 Key 来构建各种索引，例如用户 ID、名字、年龄等等，相比基础数据，这些索引都属于额外的辅助数据结构。
这里涉及到计算机科学研究中的一个典型的权衡问题：
- 索引是一种在内存用量和计算速度两者之间的权衡。
- 索引会占用一些内存，但是可以让查询更快。
我们使用一些内存来创建这样一种辅助数据存储，然后通过利用一些合适的算法和数据结构来加速进程，但是代价就是会占用部分内存。而这也是学习索引中最令人感兴趣的地方：传统的索引结构通常都非常大，并且其大小还会随着输入数据量的增加而增加；然而，对于机器学习模型，尤其是神经网络模型，我们能够以一种更小的格式来获得对数据更强的表征能力，因此，对于训练好的学习索引，通常会比传统索引更小，并且同样具备快速查找记录的能力，甚至更快。
3. 索引的性能
对于索引结构，我们一般会从以下几个方面考察其性能优劣：
- 查询类型 (单值查询 VS. 范围查询)
- 查找速度
- 插入一条新记录的开销
- 删除一条记录的开销
- 更新一条记录的开销
- 索引大小和利用率
我们将逐个介绍这几个方面，但是请注意，在我们要讨论的 Kraska 等人的这篇论文中，并没有显式地考虑插入、删除、更新记录的开销，该论文主要集中在只读数据集，因此并没有涉及到这些操作。所以实际上，这是目前学习索引存在局限性的一个方面，未来还需要对此进行更多研究。
当然，有些应用程序是专门针对只读索引的。例如 BigTable 使用只读索引并且在需要更新时会选择重构索引，以及像数据仓库这种，当涉及大量数据转储时，我们会选择在晚上访问流量较低时重构其索引。所以，目前学习索引的局限并非一种致命缺陷，但它仍然是一个有待进一步研究的问题。
3.1 查询类型
查询类型主要可以分为两种：点到点查询 和 范围查询。
我们可能希望利用索引查询某条或者某个范围内的特定数据，其中，对于单点查询，最常用的索引结构是哈希表；而对于范围查询，最常用的是 B 树索引。
此外，Karask 等人的论文中还提到了另一种常见的用于存在索引的 Bloom 过滤器以及相应的 AI 替代结构，但是这里我们不会对此进行展开，具体细节可以参考论文。
3.2 查找速度
查找速度也是一个非常重要的指标：当我们询问索引时，需要等待多久才能得到结果。通常，我们用大 $O$ 记号来表示其时间复杂度。此外，有时我们也会采用一些经验测量，因为目前已经有很多相关研究，例如缓存优化以及其他一些针对计算机硬件的优化等，并且实践表明它们在改进索引性能方面都取得了一定的效果。
3.3 插入和更新开销
如果我们要将一条新的记录插入数据库中，我们需要更新索引，这个过程中会引入一些无法忽视的开销。同理，对某条已存在的记录进行更新时，我们同样需要更新索引结构。
3.4 删除开销
从原数据库中删除某条记录同样需要更新索引结构。例如，当我们询问索引 “名字叫 Tim 的人记录在哪里” 时，索引会告诉我们在红色方格所在的内存地址；而当我们将该记录删除后，索引应当告诉我们不存在相关记录。
3.5 索引大小和利用率
索引会占用一些内存空间，具体大小取决于数据量，因为我们需要一种数据结构来支持我们查询索引中的每条记录或者每个 Key。利用率则是指索引中的信息密度，某些索引结构会占用远远超出其需求的大量空间，这意味着这些索引中存在许多待使用的空槽，我们将这些空槽占比称为利用率。例如，如果有一个索引结构，它实际占用的空间是其本身包含记录的两倍，那么该索引的利用率为 50%。通常，对于索引结构，尤其是哈希表，随着其利用率越来越高，其性能会逐渐下降。因此，在索引的利用率和性能之间也存在权衡问题。
3.6 注意事项
然而，在我们考虑时间开销等问题时，还有一些注意事项：
- 索引是一种工具，主要用于 数据量很大 的情况
- 优化访问硬盘次数比优化总操作数更为普遍
索引对于数据量很大的场景非常重要，尤其是数据多到需要使用硬盘存储时。很多索引结构实际上是在对新数据所需的硬盘访问次数进行优化，而不是在对总操作数进行优化。而这对机器学习而言是个好消息，因为我们可以将机器学习模型加载进内存，并且以一种高度并行的方式进行推断，然后告知用户应当去硬盘上的哪个地方查看指定记录，所以我们仍然可以在实现很多操作的同时最小化硬盘访问次数，甚至可能要比使用传统索引结构实现的操作数更多。并且，由于推断过程采用的是高度并行化的计算方式，学习索引还可以获得来自硬件方面的提升，例如使用 GPU 和 TPU 等，而传统索引结构则无法利用这些优势。
上面提到的访问 (Access) 和操作 (Operation) 的区别是什么？
当我们询问索引 “Tim 在哪里” 时，我们实际是在询问这个辅助数据存储，我们可能会在已经加载进 RAM 内存的索引中通过 10 个 CPU 周期来回答这个问题，这其中包含了一系列操作，例如计算哈希编码、内存查找指定记录的偏移量等。而在这里，关于 Tim 的记录所在的辅助数据存储区实际上是位于硬盘中的，对于 RAM 芯片和硬盘这两个单独的物理设备而言，从硬盘中访问某些内容要比从 RAM 中访问某些内容的时间开销更大，因此 RAM 的全部目的就是充当一种数据缓存区的功能 (或许在这里使用 “缓存” 这个词并不恰当，因为 CPU 上也有专门被称为内存高速缓存的区域)。与硬盘相比，RAM 距离 CPU 更近，访问速度也更快。因此，当谈到 访问 时，我们指的是硬盘访问；而当我们谈到 操作 时，我们指的是可以在 CPU 中完成的事情，例如单精度浮点算术运算之类的东西。
4. 哈希表
我们已经介绍了关于索引的一些基本概念，现在我们来看一下哈希表，它也是我们前面提到的两种主要的索引结构中的第一种。
4.1 哈希函数
哈希表中的基本组件之一就是 哈希函数。我们接受任意数据，将其输入哈希函数，然后得到某个整数值。存在许多不同种类的哈希函数，包括密码安全哈希函数、非密码哈希函数、完美哈希函数等等。哈希表最重要的一点在于哈希函数产生了一个来自 均匀分布 的整数，因此，哈希表中的任何整数与其他数字出现的可能性一样。这一点至关重要，我们既可以将其与 Kraska 等人的论文中讨论的机器学习哈希进行比较，也可以用于一般性地考虑哈希函数。
哈希函数将任意数据确定性地映射为一个整数：
4.2 哈希表
哈希表索引将这些整数映射到相应的数据库记录的内存地址：
这些由哈希函数生成的整数被称为 哈希编码，它被作为哈希表中的查找 Key，所以哈希表本质上就是 Key-Value 对，其中，Key 就是这些整数，而 Value 就是实际存储在硬盘上的数据库中对应记录的内存地址。
4.3 数据查找过程
当我们询问哈希表 “Tim” 所在记录的位置时，我们将字符串数据 “Tim” 输入哈希函数，然后得到了一个整数 15，该整数将受我们已经为哈希表分配的空间大小的限制，因此，哈希表的空间是预先分配好的。然后，我们查看哈希表中 Key 为 15 的位置 (即图中最右侧的绿色格子)，而该位置的 Value (这里为 2) 即为数据库中 “Tim” 所在记录的偏移量。
因此，相比直接对整个数据库进行表扫描并检查每条记录直到找到匹配 “Tim” 的记录的做法，哈希表的查找过程实际上分为两步：我们只进行了一次常数时间复杂度 $O(1)$ 的函数计算来得到 15 这个 Key，然后我们在 RAM 中直接对该位置进行单次查找，而 RAM 中该位置的 Value 则直接告诉我们去硬盘中相应的地址获取所需数据，这就是哈希表索引。
4.4 哈希表的性能
哈希表作为索引，在性能方面具有以下特点：
- 非常适用于单值查找，但对于范围查找表现很差。
- 查询时间复杂度为 $O(1)$，首先访问一次索引，然后访问一次内存。
- 插入和删除的时间复杂度为 $O(1)$，访问一次索引。
- 索引大小和利用率取决于所选择的哈希函数以及冲突处理策略，通常，哈希表的利用率大约在 50% 左右。
首先，哈希表非常适合单值查找的场景，但不适用于范围查找，这是由于哈希函数本身特性造成的。我们知道，哈希函数只是生成一些服从均匀分布的随机整数，如果我们的输入不变，那么输出总是确定的 (例如对于输入 “Tim”，输出总是 15)，所以这里的随机并不是说它们像随机数生成器那样，而是说这些整数来自某个均匀分布，我们并不能预先知道 “Tim” 对应的哈希编码，我们需要通过计算哈希函数才能得到结果。所以，对于单值查询，这个过程非常快，我们只需要计算一次哈希函数即可。但是，这种方法并不适用于范围查询，因为对于哈希函数而言，两个不同输入 (例如 “2020-01-01” 和 “2020-01-31”) 之间并不存在任何关联，它只会返回两个完全不同的不相关的数字。因此，哈希表不适用于范围查询，例如日期范围或者名字以某个字母开头的所有用户的记录块等。
然后，哈希表的查询时间复杂度为 $O(1)$，所以这是一个常数时间操作：计算一次哈希编码、单次索引查找、单次记录查找。
另外，插入和删除记录的时间复杂度也是 $O(1)$，但是这里有一些注意事项，如果我们插入/删除/更改某条记录，我们只需要在计算哈希编码时将其加入哈希表，然后查找该位置，将其加入索引，我们就完成了对该索引的更新。
最后，索引大小和利用率会根据我们所选择的哈希函数和冲突处理策略的不同具有较大差异。例如，我们有线性探测、分离链接法、布谷鸟哈希等等各种冲突处理策略，但是这里我们不会对其进行展开，因为机器学习版的哈希表只是简单地将哈希函数本身用机器学习模型代替，所以，和常规哈希函数一样，我们仍然可以将这些经典的冲突处理策略与学习型哈希函数一起使用。通常，哈希表的利用率为 50% 左右，但是也有一些高性能的哈希函数或者哈希表可以达到 90% 甚至 95% 的利用率。
4.5 注意事项
对于哈希表索引，有些可能存在的陷阱需要注意：
- 冲突处理策略的不同可能会带来相当大的性能差异。(线性探测 VS. 分离链接法 VS. 布谷鸟哈希)
- 对于插入操作，如果存在冲突过多或者表空间用尽的情况，可能会要求重建整个索引结构，而这同样也会对利用率造成影响。
- 哈希函数的选择可能会影响到冲突发生率和计算速度，而这会对查询速度和利用率造成影响。
冲突处理策略的不同会导致很大差异，但是对于机器学习模型而言问题不大，因为它们可以使用和传统哈希表相同的冲突处理策略。
在某些情况下，插入操作可能需要我们重建整个索引。因此，大多数情况下插入记录是常数时间操作，但某些情况下可能会变为线性时间操作。
为什么我们不能使哈希表的利用率尽可能高？
这是一个非常复杂的问题，这里仅提供一些大致的考虑。当索引利用率越高时，哈希表会越趋近饱和，此时，每个新插入的项与表中其他已存在项发生冲突的概率会越大。例如，在之前的例子中，我们的哈希表的大小为固定的 16 个单元，每次我们加入新的项时，我们需要将对应的哈希编码加入 0-15 之间的某个单元中。如果我们向该哈希表中一共插入了 17 个项，那么将产生冲突，因为我们无法同时将两个对象存储在同一块内存地址中。所以，随着利用率上升，冲突发生的可能性就越大，而当两个项需要放置在哈希表的同一个槽中时，我们要么重建整个哈希表，要么必须采用某种冲突处理策略，例如前面提到的线性探测、分离链接法、布谷鸟哈希等，但是这些操作的开销都非常高，因为我们不能简单地把这些项加入表中，我们需要管理这些冲突，而这将降低索引的性能。
5. B 树
5.1 B 树的结构
哈希表通常用于单点查询，而对于范围查询，最常见的索引结构是 B 树，其结构和二叉树非常相似，区别在于 B 树具有分支因子。
分支因子的一个常见取值是 100，即每个结点有 100 个子结点，因此，如果我们有 100 个项，我们可以使用单层的 B 树来表示数据；如果有 10,000 个项，我们可以使用两层的 B 树来表示数据；如果有 1,000,000 项，可以使用三层的 B 树来表示数据，以此类推。另外，我们也可以采取类似于二叉搜索树的表示方式对数据进行排序，即最左边的叶子结点总是排序项中的第一项，而最右的叶子结点总是排序项中的最后一项。
5.2 B 树的查找过程
B 树的划分策略：每个结点都是一个由划分点组成的列表。假如我们有一些小写文本数据，这里每个结点只有 9 个项。我们从根结点开始查找相对粗粒度的分区 (所有以 “a” 开头的成员，所有以 “b-d” 开头的成员等等)，结点中的每个成员的值都是一个指向下一个粒度更细的结点的指针，例如：根结点中第一项 “a” 的值是一个指向下一个包含以 “a” 开头前两个字母 (例如 “aa-ab”、“ac-ad” 等) 的内部结点的指针；第二项 “b-d” 的值是指向另一个内部结点的指针等等。
根节点和每个内部节点都是指向整体数据的已排序部分的指针列表：
如果现在我们需要查找以 “ae-ag” 开头的数据，我们将从根结点开始，沿着对应项 “a” 中的指针到达另一个粒度更细的内部结点，然后再根据对应项 “ae-ag” 中的指针到达相应的叶子结点，其中包含 4 个项：“aeon”、“afar”、“afraid”、“agriculture”。
而最终叶子结点中的每一项的值都是一个指向硬盘上的数据库表中对应数据条目的地址偏移量，我们可以通过这种方式取回所有以 “ae-ag” 开头的数据。
由于索引是针对硬盘访问进行优化的，每个结点的大小通常取决于硬盘上的存储块的大小，通常为 512K。
对于数据的读取过程，由于它最初是针对硬盘访问进行优化的，因此，与使用 B 树进行硬盘访问相比，我们将在内存中执行更多的操作，并且与哈希表相比，操作数要更多。因此，此过程是我们将数据块读入RAM，就像根节点一样。然后，我们对该数据块进行迭代搜索直到找到匹配项，并且实际上，通常此迭代过程是对排序后的数据进行二分查找。因此我们将找到下一个要访问的数据块或结点，只是通过简单的快速扫描，然后我们将读取下一个数据块并将其作为 B 树中的下一个结点。重复此过程，直到到达叶子结点并找到我们正在寻找的数据。
如果数据库中不存在 “j-p” 的记录，那么 B 树中会存在相应的结点吗？
这取决于具体的实现细节。由于叶子结点的存储方式是完全排序的，有时，这些存储页会被提前分配，即会存在一个用于存储 “j-p” 之间的数据的空间，只不过该空间内是空的 (即 Root 结点中 “j-p” 的单元格是空的)，因此，当我们搜索 “j-p” 时，我们会知道不存在相应记录，所以会立即停止搜索过程。但是考虑到利用率，这些数据也有可能已经分配好了，所以存储页可能已经存在，只不过包含的都是空记录，当我们搜索到这些空记录时会发现所要查找的记录并不存在。
在大部分 B 树实现中，不同内部结点中区间大小或者不同叶子结点中项的数量是否通常是相等的？
是的，我们对于每个结点大小的分配是基于一次从硬盘中获取的数据量的大小。所以，它是针对硬盘访问高度优化的，硬盘中有一些相对标准的数据块大小，而 B 树是以此为基础构建的。虽然，这并非构建 B 树数据结构时的强制要求，但是大部分 B 树都是这样构建的。
在上面的例子中，如果我们希望查找以 “ae-af” 开头的记录，应该如何实现过滤？
首先，我们先进入 “ae-ag” 所指向的内部结点。然后，我们对其指向的所有叶子结点进行扫描直到碰到第一个不符合查询条件的叶子结点。所以，我们会发现 “aeon”、“afar” 和 “afraid” 都符合查询条件，而 “agriculture” 不符合条件，然后我们停止搜索，并返回之前的三个符合条件的记录即可。
表扫描的范围不能太大，否则时间成本将很高，对吗？
是的，这些结点的大小都相对较小。另外，虽然不是必须的，但是通常对于叶子结点，我们会采用二分查找，所以并不只是简单的表扫描。
如果我们的数据库是可扩展的，那么 B 树可以设置为在给定一个利用率后可动态扩展吗？
可以，B 树不一定具有固定的利用率，它可以扩展、增长和变化。
为什么一个叶子结点中的索引数量和一个硬盘中的存储块大小相关？
在上面的例子中，“aeon”、“afar”、“afraid” 和 “agriculture” 这 4 个项都在同一个叶子结点中，而该叶子结点的大小是固定的，具体取决于硬盘的存储块大小。例如，如果满足条件以 “ae-ag” 开头的记录不足一个块大小 (512K)，那么该叶子结点中可能会存在空闲空间。但是，单个叶子结点中允许的最大实体数量是固定的。也就是说，对于单个叶子结点，我们会分配给其一个块大小 (512K) 的内存空间 (虽然其中某些槽可能是空的)，除了该结点外，其他对象无法使用该内存空间。
所有这些结点都在磁盘上吗？
是的，对于主流数据库，所有这些结点通常都在磁盘上。所以，访问根结点就是一次磁盘访问的过程，然后通过扫描该结点中的实体， 我们找到接下来应该访问磁盘中的哪个位置 (例如 “a” 指向的下一个内部结点)，只有在这之后，我们才会将根结点中的 “a” 所指向的整个内部结点从磁盘上加载进 RAM 中。
5.3 B 树的性能
B 树作为索引，在性能方面具有以下特点：
- 非常适用于范围查询，同时也很适用于单值查询。
- 查询时间复杂度为 $O(\log n)$，叶子结点包含了我们实际需要的数据，并且树的深度为 $\log n$。
- 插入和删除的时间复杂度为 $O(\log n)$，和查询一样。
- 索引大小和利用率取决于每个结点的大小、树的整体平衡度以及每个结点的饱和程度。
首先，与哈希表相比，B 树非常适合范围查询。例如，假如我们要查找所有 “au-az” 开头的记录，我们只需要访问所有 “au-av”、“aw-ax”、“ay-az” 这三个内部结点所对应的最终叶子结点即可，并且 B 树的结构可以使得整个过程非常高效。
然后，B 树的查询时间复杂度为 $O(\log n)$ 次的磁盘访问，但需要注意的是，每当我们进行一次磁盘访问时 (即访问 B 树中的一个结点)，我们都会扫描一个磁盘存储块的大小。当我们到达最终的叶子结点时，我们应该已经找到了所需的记录，整个过程包含了 $\log n$ 次查询。
另外，B 树中插入和删除的的时间复杂度也是 $O(\log n)$，同样需要注意的是，和哈希表类似，某些情况下插入和删除记录可能会导致需要重建整个或者部分索引结构，或者重新平衡 B 树，这些可能会导致更高的计算时间开销。
最后，索引大小和利用率根据数据量的大小变化会非常大。例如，假设我们有 9K 条记录，我们可以用三层的 B 树表示这些数据。但是一旦我们有了 10K 加 1 条记录，并且每个结点包含 100 条记录，那么我们需要为最后多出来的一条记录在 B 树中构建整个下一层的结点并分配相应的空间。
5.4 注意事项
对于 B 树索引，有些可能存在的陷阱需要注意：
- B 树必须是相对平衡的，否则其性能无法达到 $O(\log n)$。
- 对一个已经饱和的结点进行插入操作将导致该结点 “分裂” 为两个新结点，这会导致额外的计算开销，并且两个新结点的利用率将都比较低 (大约 50%)。
- 删除一个结点可能会导致高计算开销的重新平衡操作。
如果我们没有很好地构建 B 树 (当然，如今由于已经有很多良好的开源实现，很少会发生这种情况)，我们可能会得到一个近似链表结构的 B 树，这种极端不平衡的情况下，我们将无法达到预期的 $O(\log n)$ 时间复杂度。
另外，插入、删除、更新等操作有可能导致重新平衡 B 树或者重新分裂结点，甚至重构整个索引结构，这些都会带来额外的计算开销。
6. 学习索引
2018 年，一项由 Google 和 MIT 合作的研究探索了将机器学习应用于索引结构的想法。
论文地址：https://arxiv.org/abs/1712.01208
6.1 哈希表和 B 树只是模型
这篇论文的关键见解是：哈希表和 B 树都只是模型。这些模型可以将我们所感兴趣的条目的 Key 映射到某个相应的内存地址，而这本质上只是一个数据的 CDF (累积分布函数) 上的回归问题。
6.2 范围索引只是 CDF
我们可以只是模拟一个函数，它接受 Key 作为输入，然后我们将该函数的输出 (0 到 1 之间的某个值，代表 CDF) 乘以索引中的元素总数，我们将得到估计的位置。
基于这种思路，作者首先构建了一种非常朴素的索引结构，但是效果较差，但是最终在经过一些实验后，作者提出了一些让这些机器学习模型更好地工作的方式。
6.3 机器学习模型存在的问题
作者的第一个发现的问题是：机器学习模型不能很好地提供精确的答案。虽然，目前机器学习模型的性能正在变得越来越好，并且能够为我们的问题提供一个近似答案。但是，对于索引系统而言，近似答案还不够好，我们需要确切地知道所查找的记录在内存中的位置，否则我们将无法检索出正确记录。如果我们只是接受一个大概的位置，那么每次当我们请求 Tim 的记录时，我们可能会得到 Ted 或者 Tin 的记录 (或者其他一些不相关的记录)，而这样的结果实际上并没有什么用。因此，对于要充分用作索引结构的机器学习模型，我们必须解决这个近似问题。
作者是通过这种方式解决这一问题的：同时存储所使用的每个机器学习模型在训练数据上的最小误差和最大误差。
请注意，这种情况并非常见的机器学习研究场景：在这种特定情况下，训练数据同时也是测试数据。因为对于索引结构而言，它只需要处理我们已经加入索引中的数据，因此，当我们构建预测模型时，我们就已经拥有了它必须处理的所有数据。
对于机器学习人员而言，从某些方面来看这是一个好消息，因为现在我们不必担心过拟合问题，并且 实际上我们的目标正是过拟合：我们要使模型完全拟合所拥有的数据，而并非去考虑一些可能会出现的假设数据。
虽然，对于这类 只读内存数据库 (Read-only In-memory Databases) 而言，以上观点是正确的。但实际上，对于具有大量写工作负载或者只要涉及到写操作的数据库而言，这是一个巨大的问题。因为每当有新数据输入时，我们都有可能需要重新训练整个模型，而这显然是有问题的。因此，这是一个有待进一步研究的方向，作者在论文中并未尝试解决这方面的问题。
重点是，我们必须为每条记录，或者说训练机器学习模型所用到的整个数据集，存储最小误差和最大误差。然后，我们将得到一个 有界问题 (Bounded Problem)。因此，我们首先得到所要查找的记录在内存中的大概位置，然后只需要在基础数据库中使用二分查找或者其他搜索算法来查找我们感兴趣的记录即可，作者在论文中还提到了一些其他的搜索策略，但是通常而言，二分查找是最强大的。
过拟合和仅建立一个完整索引有什么区别，这对于不在完整索引中的新数据有帮助吗？
论文中对于第二个问题的答案尚不清楚，因为作者并没有尝试过考虑哪些数据可能会加入索引。因此，如果我们有一个完全过拟合的机器学习模型，即模型已经完全记住了训练数据，那么它将是一个完美且完整的索引。作者在论文中进行了一些相关尝试，目前来看，与经典索引结构相比，学习索引至少在时间框架上具有一定的竞争力。
作者有时甚至针对学习问题的某些部分使用非常简单的线性回归模型，但这并不是内存中位置不够精确导致的唯一问题。 因此，内存中位置不够精确导致的第二个问题是：机器学习模型并非超级精确，我们可能需要一个非常复杂的模型来训练一亿条记录并获得精确的答案，以便从这一亿条记录中找到该数据对应的 CDF 的位置。
6.4 递归模型索引 (Recursive Model Index, RMI)
作者并没有选择构建一个大型的复杂模型，而是构建了一个层次框架，并采用了一种类似于网格搜索的方法来为框架中的每个模型构建单独的参数。图中每一个方框都代表一个不同的单独训练的机器学习模型，该模型通常很小。作者在框架顶层使用了一个包含 2 个隐藏层的神经网络，当需要查询一条记录时，位于根结点的机器学习模型将预测在下一层中应该使用哪个机器学习模型来回答 “该记录在内存中的什么位置” 这一问题。作者尝试了不同层数的框架和模型，发现仅仅采用 2 层系统就能够获得最佳效果 (至少该设置在论文中是最成功的)。因此，在该框架下，一个机器学习模型会选择下一个单独的机器学习模型来完成 “最后一英里” 的工作，并预测记录在内存中的实际位置。
该层次模型的重点在于，我们可以训练一个简单的非常快速的推理模型，从而使我们逐步到达目标记录的位置。 因此，顶层模型将空间一分为二，作者在第二层中使用了大于 10,000 个简单模型，并且实验效果相当不错。因此，作者提出的是一个框架，其中包含了网格搜索和混合模型方法，其中所有这些模型可以是不同类型的模型，其中某些可能是神经网络，某些可能是线性回归，在某些情况下，甚至可以使某些机器学习模型实际上只是标准的 B 树实现。因此，当某种数据分布对于简单机器学习模型而言具有挑战性时，我们可以使用 B 树来解决此问题。
是否可以使用随机森林模型代替神经网络？
在论文中，作者并没有使用随机森林模型，而是采用了小型的简单神经网络进行了实验，该网络具有两个隐藏层，总共多达 32 个节点，并且作者尝试了一些不同的组合，例如：1 个隐藏层 8 个节点、1 个隐藏层 16 个节点、1 个隐藏层 32 个节点、2 个隐藏层每个 8 个节点等等，并且使用网格搜索策略确定合适的参数尺寸。但是，作者并没有尝试使用随机森林，当然，这将是一个有趣的研究领域，我们可以进行这种尝试以找出还有哪些其他类型的机器学习模型可能适用，尤其是在此层次模型结构的每一层。
这种多层简单模型是如何构建的？不同层上的模型应该如何排列？
基本上，作者采用的是网格搜索策略。作者提出的训练过程几乎像是对各种可能性进行网格搜索一样，因此他们构建了许多不同样式的模型，并且尝试了许多组合，直到找到一个在数据集上表现良好的组合，然后再将最优组合和基准进行对比测试。
6.5 学习哈希函数 (Learned Hash Function)
对于非范围查询，作者尝试替换点对点查询中的哈希函数，而不是尝试替换哈希表的全部相关内容 (例如冲突处理策略等等)。如上图所示，使用下方的机器学习模型 (由多个机器学习模型组成的层次系统) 替换哈希函数本身，然后我们得到的这个 学习哈希函数 (Learned Hash Function) 将能够考虑数据分布，并且 (但愿) 最终减少基础哈希表中的冲突，而标准的经典哈希函数就其本质而言不可能做到这点。
6.6 实验结果
论文作者主要关注简单模型，这篇论文是一个概念上的证明：
- 作者主要关注小型全连接神经网络
- 主要关注一次创建、只读、内存数据结构
- 对于具有大量写工作负载的场景，这些模型存在很大问题，而论文作者并没有尝试解决这些问题。
这里，我们将总结论文中的一些结果，如果希望知道更多相关细节 (例如：RMI 模型的损失函数如何选择、训练过程如何实现等)，请参阅论文原文。
作者首先比较了 B 树和学习索引在三个不同类型的数据集上的性能差异。对于这两种索引结构，作者对具有不同页面大小的 B 树和具有不同阶段二模型大小的学习索引 (两层模型，根结点用于预测第二层的 10K 到 200K 个简单模型) 进行了对比。
第一个数据集是地图数据，其中的 Key 是经度值，该数据可能来自 Google 地图 (因为该论文是与 Google 合作的，所以作者应该能够得到相关的地图数据)。论文中给出了更多相关细节，但总的来说，它们只是以经度作为 Key 的来自真实世界的数据。
第二个数据集是 Web 数据，它是由时间戳作为 Key 的 Web 日志记录 (来自 MIT 网站)。因此，对于经典索引结构而言，这确实是非常棘手的数据，因为这类数据的分布通常非常复杂：像班级时间表、假期等等所有这些奇怪的难以预测的东西都会被添加到这些时间戳中，非节假日或者期末考试期间，网站访问记录会比平时更多，所以它们对应的时间戳会包含更多的记录。
最后，作者还创建了一个人工数据集，通过对数正态分布生成了一个包含数百万条记录的数据集。
如上图结果所示，值得注意的是，和 B 树相比，学习索引的大小 (以 MB 为单位）减小了多少。可以看到，最小的 B 树与最大的学习索引模型一样大。因此，这是一个非常有趣的发现：我们可以用更少的内存来换取相对可观的性能。注意到 Jeff Dean 也是这篇论文的署名作者之一，上述结果项的比较应该是比较合理的，未来可以在此基础上进行进一步研究。可以看到，和 B 树相比，学习索引的内存占用量明显减少，并且在查询速度方面，在地图数据集上的速度提高了 2 到 3 倍左右；Web 数据集上的提升略小 (因为该数据分布很复杂)，只有 1.1 到 2 倍；类似地，在对数正态分布的人工数据上提升了大约 1.5 倍。该层次模型的所有不同参数组合上的性能改进都相对一致，值得进一步研究，并且我们对于这些模型能够达到多小很感兴趣。
对于论文中哈希表的相关工作，作者并没有对哈希表进行实质上的比较。因为，正如我们之前提到过的，我们可以使用相同的哈希表基础结构，因此作者在这里仅比较了冲突发生率。而且我们注意到，对于第一个地图数据集，冲突发生率仅为 7.9%，这意味着机器学习模型能够很好地学习到该基础经度数据的分布，从而显着减少了发生冲突的次数。对此，作者在论文中并没有提供相关图表，但的确指出了这点。
需要注意的是，与标准哈希函数相比，学习模型需要更长的时间用于计算，因此在此基础上还有更多工作要做。与非常高效的标准哈希函数相比 (类似 2 次乘法和 1 次移位运算)，学习模型在推理上的计算开销较高。因此，如果没有采用专门的加速硬件 (例如 GPU)，冲突减小了 77.5％ 这个数据看上去还是不错的。因此，在某些情况下，尤其是对于冲突非常昂贵的场景，这种学习哈希索引策略可能会很有用。
6.7 总结
最后，我们再总结几点：
- 事实证明，将数据分布考虑进去可以使模型变得更好：
- B 树和哈希表没有考虑数据的分布，这会对索引利用率产生负面影响。
- 机器学习模型从本质上考虑了数据的分布，这可以帮助提高索引利用率。
- 从某种程度上看，在学习索引中，过拟合是我们的目标：
- 索引结构永远不需要预测那些尚未建立索引的数据的位置。
- 对索引中的数据进行准确的预测要比泛化到保留数据集上更重要。
-
误差边界要比平均误差更重要：
表扫描将在最小误差边界和最大误差边界之间进行，因此，从对查询性能方面的影响考虑，相比如何使得猜测的位置更加准确，实际上我们更加关心的是如何缩小这个误差范围。所以这是另一种有趣的权衡，在一般的机器学习研究中我们通常不必考虑这点，至少并不总是需要将其作为目标，有时我们的目标只是为了使猜测尽可能准确，尤其是对于一般的分类问题而言。
- 关于扩展的有趣特性：
- 标准索引结构的大小会随着输入数据的增长而增长。
- 机器学习模型的大小不必随数据增长而增长，它只需要足够的复杂度即可生成 N 个值作为输出。
- 利用新硬件的优势：
- 摩尔定律正在日渐衰亡，传统索引结构并不能很好地适应并行化。
- 机器学习工作负载是当前硬件发展的主要驱动力，这意味着学习索引可以更好地利用新硬件的优势。
- 多维索引：
- 传统索引结构仅考虑某些数据的单个特征。
- 学习型索引结构可以跨多个维度建立索引，允许立即应用各种查询和过滤器。
- 这得益于机器学习在识别高维关系方面的能力。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！