第 4 章存储与检索

生活中的一大不幸是，每个人给事物起的名字都有点不太对劲。这让世界上的一切都稍微难以理解了一些。计算机并不主要是在”计算”的意义上做算术。[…] 它们主要是文件系统。

——理查德·费曼，《独特的思维方式》研讨会（1985）

致早期发布读者的说明

通过早期发布的电子书，你可以在作者撰写过程中就获取到最新内容—— raw 且未经编辑的原始内容——这样你就能在这些书籍正式发布前很久就开始利用这些技术。

这将是最终书籍的第 4 章。本书的 GitHub 仓库地址是 https://github.com/ept/ddia2-feedback。

如果你想积极参与审阅和评论这份草稿，请在 GitHub 上联系我们。

在最基本的层面上，数据库需要做两件事：当你给它一些数据时，它应该存储这些数据；当你稍后询问时，它应该把数据还给你。

在第 3 章中，我们讨论了数据模型和查询语言——即你给数据库数据的格式，以及你随后可以请求数据的接口。在本章中，我们从数据库的角度讨论同样的问题：数据库如何存储你给它的数据，以及当你请求时如何再次找到这些数据。

作为应用开发者，你为什么要关心数据库内部如何处理存储和检索呢？你可能不会从头实现自己的存储引擎，但你需要从众多可用选项中选择一个适合你应用的存储引擎。为了将存储引擎配置为在你的工作负载上表现良好，你需要大致了解存储引擎在底层做了什么。

特别是，针对事务工作负载优化的存储引擎（OLTP）与针对分析优化的存储引擎之间存在很大区别（我们在”分析型与操作型系统”中介绍了这一区别）。本章首先考察 OLTP 的两类存储引擎：写出不可变数据文件的日志结构存储引擎，以及原地更新数据的 B 树等存储引擎。这些结构既用于键值存储，也用于二级索引。

稍后，在”分析型数据存储”中，我们将讨论针对分析优化的存储引擎家族，在”多维索引与全文索引”中，我们将简要介绍用于更高级查询（如文本检索）的索引。

OLTP 的存储与索引

让我们看看世界上最简单的数据库，用两个 Bash 函数实现：

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

这两个函数实现了一个键值存储。你可以调用 db_set key value，将键和值存储在数据库中。键和值可以是（几乎）任何你喜欢的东西——例如，值可以是 JSON 文档。然后你可以调用 db_get key，查找与该特定键关联的最新值并返回它。

它确实有效：

$ db_set 12 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

存储格式非常简单：一个文本文件，每行包含一个键值对，用逗号分隔（大致像 CSV 文件，忽略转义问题）。每次调用 db_set 都会追加到文件末尾。如果你多次更新一个键，旧版本的值不会被覆盖——你需要查看文件中某个键的最后一次出现来找到最新值（因此 db_get 中有 tail -n 1）：

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
12,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

db_set 函数对于如此简单的实现来说性能相当不错，因为追加到文件通常非常高效。与 db_set 所做的类似，许多数据库内部使用日志，即一种仅追加的数据文件。真实数据库有更多问题需要处理（如处理并发写入、回收磁盘空间以防止日志无限增长、在从崩溃恢复时处理部分写入的记录），但基本原理是相同的。日志非常有用，我们将在本书中多次遇到它们。

注意

“日志”一词通常用于指应用日志，即应用输出描述正在发生事情的文本。在本书中，“日志”用于更一般的意义：磁盘上的仅追加记录序列。它不必是人类可读的；它可能是二进制的，仅供数据库系统内部使用。

另一方面，如果你的数据库中有大量记录，db_get 函数的性能就很糟糕。每次你想查找一个键时，db_get 都必须从头到尾扫描整个数据库文件，寻找该键的出现。用算法术语来说，查找的成本是 O(n)：如果你将数据库中的记录数 n 翻倍，查找时间也会翻倍。这不太好。

为了高效地找到数据库中特定键的值，我们需要一种不同的数据结构：索引。在本章中，我们将考察一系列索引结构并比较它们；基本思想是以特定方式组织数据（例如，按某个键排序），以便更快地定位你想要的数据。如果你想以几种不同的方式搜索相同的数据，你可能需要在数据的不同部分建立几个不同的索引。

索引是从主数据派生出的附加结构。许多数据库允许你添加和删除索引，这不会影响数据库的内容；它只影响查询的性能。维护附加结构会产生开销，特别是在写入时。对于写入，很难击败简单追加到文件的性能，因为那是尽可能简单的写操作。任何类型的索引通常会降低写入速度，因为每次写入数据时也需要更新索引。

这是存储系统中的一个重要权衡：精心选择的索引可以加速读查询，但每个索引都会消耗额外的磁盘空间并降低写入速度，有时相当显著。因此，数据库通常不会默认索引所有内容，而是需要你——编写应用或管理数据库的人——根据你对应用典型查询模式的了解手动选择索引。然后你可以选择给你的应用带来最大收益的索引，而不会引入不必要的写入开销。

日志结构存储

首先，假设你想继续存储 db_set 写入的仅追加文件中的数据，你只是想让读取更快。一种方法是在内存中保留一个哈希映射，其中每个键都映射到文件中最新的该键值的字节偏移量，如图 4-1 所示。

图 4-1 以类似 CSV 的格式存储键值对日志，用内存哈希映射索引。

每当你向文件追加新的键值对时，你也更新哈希映射以反映你刚写入数据的偏移量。当你想查找一个值时，你使用哈希映射找到日志文件中的偏移量，定位到该位置，然后读取值。如果数据文件的该部分已经在文件系统缓存中，读取根本不需要任何磁盘 I/O。

这种方法快得多，但它仍然有几个问题：

你从不释放被覆盖的旧日志条目占用的磁盘空间；如果你持续写入数据库，可能会耗尽磁盘空间。
哈希映射不会被持久化，所以当你重启数据库时必须重建它——例如，通过扫描整个日志文件找到每个键的最新字节偏移量。如果你有大量数据，这会使重启变慢。
哈希表必须能放入内存。原则上，你可以在磁盘上维护哈希表，但不幸的是，很难让磁盘上的哈希表表现良好。它需要大量随机访问 I/O，满时扩展很昂贵，哈希冲突需要繁琐的逻辑。
范围查询效率不高。例如，你不能轻松扫描键 10000 到 19999 之间的所有键——你必须在哈希映射中单独查找每个键。

SSTable 文件格式

在实践中，哈希表并不常用于数据库索引，更常见的是将数据保存在按键排序的结构中。这种结构的一个例子是排序字符串表（Sorted String Table，简称 SSTable），如图 4-2 所示。这种文件格式也存储键值对，但确保它们按键排序，并且每个键在文件中只出现一次。

图 4-2 带有稀疏索引的 SSTable，允许查询跳转到正确的块。

现在你不需要把所有键都保存在内存中：你可以将 SSTable 中的键值对分组为几千字节大小的块，然后将每个块的第一个键存储在索引中。这种只存储部分键的索引称为稀疏索引。这个索引存储在 SSTable 的单独部分，例如使用不可变 B 树、字典树或另一种允许快速查找特定键的数据结构。

例如，在图 4-2 中，一个块的第一个键是 handbag，下一个块的第一个键是 handsome。假设你在查找键 handiwork，它不在稀疏索引中。由于排序，你知道 handiwork 必须出现在 handbag 和 handsome 之间。这意味着你可以定位到 handbag 的偏移量，从那里开始扫描文件直到找到 handiwork（或者没找到，如果键不存在于文件中）。几千字节大小的块可以非常快地扫描。

此外，每个记录块都可以压缩（图 4-2 中阴影区域所示）。除了节省磁盘空间，压缩还减少了 I/O 带宽使用，代价是使用稍多的 CPU 时间。

构建与合并 SSTable

SSTable 文件格式对读取比仅追加日志更好，但它使写入更困难。我们不能简单地在末尾追加，因为那样文件就不再排序了（除非键恰好是按升序写入的）。如果我们每次在键插入到中间某处时都必须重写整个 SSTable，写入就会变得太昂贵。

我们可以用日志结构方法解决这个问题，这是仅追加日志和排序文件的混合：

Memtable：当写入到来时，将其添加到内存中的有序映射数据结构，如红黑树、跳表或字典树。使用这些数据结构，你可以按任意顺序插入键，高效地查找它们，并按排序顺序读回。这种内存中的数据结构称为 memtable。
写入磁盘：当 memtable 大于某个阈值——通常是几兆字节时——将其按排序顺序写出到磁盘作为 SSTable 文件。我们称这个新的 SSTable 文件为数据库的最新段，它与旧段一起作为单独的文件存储。每个段都有其内容的单独索引。当新段正在写入磁盘时，数据库可以继续写入新的 memtable 实例，当 SSTable 写入完成时，旧 memtable 的内存被释放。
读取：为了读取某个键的值，首先尝试在 memtable 和最新的磁盘段中查找该键。如果不在那里，就在次新的段中查找，依此类推，直到找到该键或到达最旧的段。如果键没有出现在任何段中，它就不存在于数据库中。
合并与压缩：不时地在后台运行合并和压缩过程，合并段文件并丢弃被覆盖或删除的值。

合并段的工作方式类似于归并排序算法。过程如图 4-3 所示：并排开始读取输入文件，查看每个文件中的第一个键，将最小的键（根据排序顺序）复制到输出文件，然后重复。如果同一个键出现在多个输入文件中，只保留最新的值。这产生了一个新的合并段文件，也按键排序，每个键一个值，并且它使用最少的内存，因为我们可以一次迭代一个键地遍历 SSTable。

图 4-3 合并多个 SSTable 段，只保留每个键的最新值。

为了确保如果数据库崩溃，memtable 中的数据不会丢失，存储引擎在磁盘上保留一个单独的日志，每个写入都立即追加到这个日志。这个日志不按键排序，但这没关系，因为它的唯一目的是在崩溃后恢复 memtable。每次 memtable 被写出到 SSTable 时，日志的相应部分就可以被丢弃。

如果你想删除一个键及其关联的值，你必须向数据文件追加一个特殊的删除记录，称为墓碑（tombstone）。当日志段合并时，墓碑告诉合并过程丢弃被删除键的任何先前值。一旦墓碑被合并到最旧的段中，它就可以被删除。

这里描述的算法本质上就是 RocksDB、Cassandra、Scylla 和 HBase 所使用的，它们都受到了 Google 的 Bigtable 论文（引入了 SSTable 和 memtable 这两个术语）的启发。

该算法最初于 1996 年以 日志结构合并树（Log-Structured Merge-Tree，简称 LSM-Tree）的名字发表，建立在早期日志结构文件系统的工作基础上。因此，基于合并和压缩排序文件原理的存储引擎通常称为 LSM 存储引擎。

在 LSM 存储引擎中，段文件是一次性写入的（通过写出 memtable 或合并现有段），之后就是不可变的。段的合并和压缩可以在后台线程中进行，当它进行时，我们仍然可以使用旧段文件继续提供读取。当合并过程完成时，我们将读取请求切换到使用新的合并段而不是旧段，然后旧段文件可以被删除。

段文件不一定必须存储在本地磁盘上：它们也非常适合写入对象存储。例如 SlateDB 和 Delta Lake 就采用了这种方法。

拥有不可变的段文件也简化了崩溃恢复：如果在写出 memtable 或合并段时发生崩溃，数据库只需删除未完成的 SSTable 并重新开始。持久化写入 memtable 的日志如果在写入记录中途发生崩溃，或磁盘已满时，可能包含不完整的记录；这些通常通过在日志中包含校验和来检测，并丢弃损坏或不完整的日志条目。我们将在第 8 章中更多地讨论持久性和崩溃恢复。

布隆过滤器

使用 LSM 存储，读取最近很久未更新或根本不存在的键可能会很慢，因为存储引擎需要检查多个段文件。为了加速这种读取，LSM 存储引擎通常在每个段中包含一个布隆过滤器（Bloom filter），它提供了一种快速但近似的方式来检查特定键是否出现在特定 SSTable 中。

图 4-4 显示了一个包含两个键和 16 位的布隆过滤器示例（实际上，它会包含更多键和更多位）。对于 SSTable 中的每个键，我们计算一个哈希函数，产生一组数字，然后将其解释为位数组中的索引。我们将这些索引对应的位设置为 1，其余保持为 0。例如，键 handbag 哈希到数字 (2, 9, 4)，所以我们将第 2、9、4 位设置为 1。然后位图作为 SSTable 的一部分存储，与键的稀疏索引一起。这需要一些额外空间，但布隆过滤器通常比 SSTable 的其余部分小得多。

图 4-4 布隆过滤器提供了一种快速、概率性的检查，用于确定特定键是否存在于特定 SSTable 中。

当我们想知道一个键是否出现在 SSTable 中时，我们计算该键的相同哈希，并检查这些索引处的位。例如，在图 4-4 中，我们查询键 handheld，它哈希到 (6, 11, 2)。其中一个位是 1（即第 2 位），而另外两个是 0。这些检查可以使用所有 CPU 都支持的位运算极快地进行。

如果至少有一个位是 0，我们就知道该键肯定不存在于 SSTable 中。如果查询中的位都是 1，那么该键很可能在 SSTable 中，但也可能是巧合，所有这些位都被其他键设置为 1。这种看起来键存在但实际上不存在的情况称为假阳性。

假阳性的概率取决于键的数量、每个键设置的位数以及布隆过滤器中的总位数。你可以使用在线计算工具为你的应用计算正确的参数。根据经验，你需要为 SSTable 中的每个键分配 10 位布隆过滤器空间，以获得 1%的假阳性概率，每增加 5 位，概率就会降低十倍。

在 LSM 存储引擎的上下文中，假阳性不是问题：

如果布隆过滤器说键不存在，我们可以安全地跳过该 SSTable，因为我们可以确定它不包含该键。
如果布隆过滤器说键存在，我们必须查阅稀疏索引并解码键值对块以检查键是否真的在那里。如果是假阳性，我们只是做了一些不必要的工作，但除此之外没有害处——我们只是继续搜索次新的段。

压缩策略

一个重要的细节是 LSM 存储如何选择何时执行压缩，以及哪些 SSTable 包含在压缩中。许多基于 LSM 的存储系统允许你配置使用哪种压缩策略，一些常见的选择有：

大小分层压缩（Size-tiered compaction） 较新和较小的 SSTable 依次合并到较旧和较大的 SSTable 中。包含较旧数据的 SSTable 可以变得非常大，合并它们需要大量临时磁盘空间。这种策略的优点是它可以处理非常高的写入吞吐量。

分层压缩（Leveled compaction） 键范围被分割成较小的 SSTable，较旧的数据被移动到单独的”层”中，这允许压缩更增量地进行，比大小分层策略使用更少的磁盘空间。这种策略对读取比分层压缩更有效，因为存储引擎需要读取更少的 SSTable 来检查它们是否包含该键。

根据经验，如果你主要是写入而很少读取，大小分层压缩表现更好；如果你的工作负载以读取为主，分层压缩表现更好。如果你频繁写入少量键，而很少写入大量键，那么分层压缩也可能更有利。

尽管有许多细微差别，LSM 树的基本思想——保持级联的 SSTable 在后台合并——简单且有效。我们将在”比较 B 树与 LSM 树”中更详细地讨论它们的性能特征。

嵌入式存储引擎

许多数据库作为服务运行，通过网络接受查询，但也有嵌入式数据库，它们不暴露网络 API。相反，它们是库，与你的应用代码在同一进程中运行，通常在本地磁盘上读写文件，你通过普通函数调用与它们交互。嵌入式存储引擎的例子包括 RocksDB、SQLite、LMDB、DuckDB 和 KùzuDB。

嵌入式数据库在移动应用中非常常用于存储本地用户数据。在后端，如果数据足够小可以放在单台机器上，并且并发事务不多，它们也可能是合适的选择。例如，在一个多租户系统中，如果每个租户都足够小且完全与其他租户分离（即你不需要运行组合多个租户数据的查询），你可以潜在地为每个租户使用单独的嵌入式数据库实例。

我们在本章中讨论的存储和检索方法既用于嵌入式数据库，也用于客户端-服务器数据库。在第 6 章和第 7 章中，我们将讨论跨多台机器扩展数据库的技术。

B 树

日志结构方法很流行，但它不是键值存储的唯一形式。通过键读写数据库记录最广泛使用的结构是 B 树。

B 树于 1970 年引入，不到 10 年后就被称为”无处不在”，经受住了时间的考验。它们仍然是几乎所有关系数据库的标准索引实现，许多非关系数据库也使用它们。

与 SSTable 一样，B 树保持键值对按键排序，这允许高效的键值查找和范围查询。但这就是相似之处的结束：B 树有非常不同的设计理念。

我们之前看到的日志结构索引将数据库分解为可变大小的段，通常几兆字节或更大，一次性写入然后不可变。相比之下，B 树将数据库分解为固定大小的块或页，可以原地覆盖页。页传统上是 4 KiB 大小，但 PostgreSQL 现在使用 8 KiB，MySQL 默认使用 16 KiB。

每个页可以使用页号标识，这允许一页引用另一页——类似于指针，但在磁盘上而不是内存中。如果所有页都存储在同一个文件中，将页号乘以页大小就得到该页在文件中的字节偏移量。我们可以使用这些页引用来构建页树，如图 4-5 所示。

图 4-5 使用 B 树索引查找键 251。从根页开始，我们首先跟随引用到键 200-300 的页，然后到键 250-270 的页。

一页被指定为 B 树的根；每当你想在索引中查找键时，都从这里开始。该页包含几个键和对子页的引用。每个子页负责一个连续的键范围，键之间的引用指示这些范围之间的边界在哪里。（这种结构有时称为 B+ 树，但我们不需要将其与其他 B 树变体区分开来。）

在图 4-5 的示例中，我们正在寻找键 251，所以我们知道我们需要跟随 200 和 300 之间的边界引用。这把我们带到一个看起来相似的页，进一步将 200-300 范围细分为子范围。最终我们到达一个包含单个键的页（叶页），它要么内联包含每个键的值，要么包含可以找到值的页的引用。

B 树中一页对子页引用的数量称为分支因子。例如，在图 4-5 中分支因子是 6。在实践中，分支因子取决于存储页引用和范围边界所需的空间，但通常是几百。

如果你想更新 B 树中现有键的值，你搜索包含该键的叶页，并用包含新值的版本覆盖磁盘上的该页。如果你想添加新键，你需要找到其范围包含新键的页，并将其添加到该页。如果页中没有足够的空闲空间容纳新键，该页被分裂成两个半满的页，父页被更新以反映键范围的新细分。

图 4-6 通过在边界键 337 处分裂页来增长 B 树。父页被更新以引用两个子页。

在图 4-6 的示例中，我们想插入键 334，但 333-345 范围的页已经满了。因此我们将其分裂为 333-337 范围（包括新键）的页和 337-344 范围的页。我们还必须更新父页以引用两个子页，它们之间有边界值 337。如果父页没有足够的空间容纳新引用，它也可能需要分裂，分裂可以继续到树的根。当根分裂时，我们在它上面创建一个新根。删除键（可能需要合并节点）更复杂。

这个算法确保树保持平衡：有 n 个键的 B 树深度总是 O(log n)。大多数数据库可以放入三到四层深的 B 树中，所以你不需要跟随很多页引用就能找到你要找的页。（一个四层树，4 KiB 页，分支因子 500，可以存储高达 250 TB。）

使 B 树可靠

B 树的基本底层写操作是用新数据覆盖磁盘上的页。假设覆盖不会改变页的位置；即，当页被覆盖时，对该页的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件。

一次覆盖多个页，如页分裂，是一个危险的操作：如果数据库在只有部分页被写入后崩溃，你最终会得到一个损坏的树（例如，可能有一个孤儿页不是任何父页的子页）。如果硬件不能原子性地写入整个页，你也可能最终得到一个部分写入的页（这称为撕裂页）。

为了使数据库对崩溃具有弹性，B 树实现通常在磁盘上包含一个额外的数据结构：预写日志（Write-Ahead Log，简称 WAL）。这是一个仅追加的文件，每个 B 树修改在应用到树本身的页之前必须先写入其中。当数据库在崩溃后恢复时，使用这个日志将 B 树恢复到一致状态。在文件系统中，等效机制称为日志记录。

为了提高性能，B 树实现通常不会立即将每个修改的页写入磁盘，而是先将 B 树页缓冲在内存中一段时间。然后预写日志还确保在崩溃情况下数据不会丢失：只要数据已写入 WAL，并使用 fsync() 系统调用刷新到磁盘，数据就是持久的，因为数据库在崩溃后能够恢复它。

B 树变体

由于 B 树已经存在了很长时间，多年来开发了许多变体。仅举几例：

写时复制：一些数据库（如 LMDB）使用写时复制方案，而不是覆盖页和维护 WAL 进行崩溃恢复。修改后的页被写入不同位置，并创建树中父页的新版本，指向新位置。这种方法也对并发控制有用。
键前缀压缩：我们可以通过不存储整个键，而是缩写它来节省页中的空间。特别是在树的内部页中，键只需要提供足够的信息来充当键范围之间的边界。将更多键打包到一页中允许树有更高的分支因子，从而更少的层级。
顺序布局：为了加速按键范围顺序扫描，一些 B 树实现尝试布局树，使叶页在磁盘上按顺序出现，减少磁盘寻道次数。然而，随着树的增长，很难保持这种顺序。
兄弟指针：在树中添加了额外的指针。例如，每个叶页可能有对其左右兄弟页的引用，这允许按顺序扫描键而无需跳回父页。

比较 B 树与 LSM 树

根据经验，LSM 树更适合写入密集型应用，而 B 树对读取更快。然而，基准测试通常对工作负载的细节很敏感。你需要用特定工作负载测试系统才能进行有效比较。此外，LSM 和 B 树之间不是严格的二选一：存储引擎有时会混合两种方法的特性，例如通过拥有多个 B 树并以 LSM 风格合并它们。

读取性能

在 B 树中，查找键涉及读取 B 树每一级的一页。由于层级数通常相当小，这意味着从 B 树的读取通常很快，性能可预测。在 LSM 存储引擎中，读取通常必须检查不同压缩阶段的几個不同 SSTable，但布隆过滤器有助于减少所需的实际磁盘 I/O 操作数量。两种方法都可以表现良好，哪种更快取决于存储引擎和工作负载的细节。

范围查询在 B 树上简单且快速，因为它们可以利用树的排序结构。在 LSM 存储上，范围查询也可以利用 SSTable 排序，但它们需要并行扫描所有段并组合结果。布隆过滤器对范围查询没有帮助（因为你需要计算范围内每个可能键的哈希，这是不切实际的），使得范围查询在 LSM 方法中比点查询更昂贵。

高写入吞吐量如果 memtable 填满，可能会导致日志结构存储引擎中的延迟峰值。如果数据不能足够快地写入磁盘，这可能是因为压缩过程跟不上传入的写入，就会发生这种情况。许多存储引擎，包括 RocksDB，在这种情况下执行反压：它们暂停所有读取和写入，直到 memtable 被写出到磁盘。

关于读取吞吐量，现代 SSD（尤其是 NVMe）可以并行执行许多独立的读取请求。LSM 树和 B 树都能够提供高读取吞吐量，但存储引擎需要精心设计以利用这种并行性。

顺序写入与随机写入

使用 B 树，如果应用写入分散在整个键空间的键，产生的磁盘操作也是随机分散的，因为存储引擎需要覆盖的页可能位于磁盘上的任何位置。另一方面，日志结构存储引擎一次写入整个段文件（要么写出 memtable，要么在压缩现有段时），这比 B 树中的页大得多。

许多小的、分散的写入模式（如 B 树中的）称为随机写入，而较少的大写入模式（如 LSM 树中的）称为顺序写入。磁盘通常具有比随机写入更高的顺序写入吞吐量，这意味着日志结构存储引擎通常可以在相同硬件上处理比 B 树更高的写入吞吐量。这种差异在机械硬盘（HDD）上特别大；在今天大多数数据库使用的固态硬盘（SSD）上，差异较小，但仍然明显。

SSD 上的顺序写入与随机写入

在机械硬盘（HDD）上，顺序写入比随机写入快得多：随机写入必须机械地将磁头移动到新位置并等待正确的盘片部分从磁头下经过，这需要几毫秒——在计算时间尺度上是永恒。然而，SSD（固态硬盘）包括 NVMe（非易失性内存 Express，即连接到 PCI Express 总线的闪存）现在已经超越 HDD 用于许多用例，它们不受这种机械限制。

尽管如此，SSD 的顺序写入吞吐量也高于随机写入。原因是闪存可以一次读写一页（通常 4 KiB），但只能一次擦除一个块（通常 512 KiB）。块中的一些页可能包含有效数据，而其他页可能包含不再需要的数据。在擦除块之前，控制器必须首先将包含有效数据的页移动到其他块；这个过程称为垃圾回收（GC）。

顺序写入工作负载一次写入较大的数据块，所以很可能整个 512 KiB 块属于单个文件；当该文件稍后再次被删除时，整个块可以擦除而无需执行任何 GC。另一方面，对于随机写入工作负载，块更可能包含有效和无效数据页的混合，所以 GC 必须在块可以擦除之前执行更多工作。

GC 消耗的写入带宽然后对应用不可用。此外，GC 执行的额外写入会加剧闪存的磨损；因此，随机写入比顺序写入更快地磨损驱动器。

写入放大

对于任何类型的存储引擎，应用的一个写入请求会转化为底层磁盘上的多个 I/O 操作。使用 LSM 树，值首先写入日志以保证持久性，然后在 memtable 写入磁盘时再次写入，每次键值对成为压缩的一部分时再次写入。（如果值明显大于键，这种开销可以通过将值与键分开存储，并仅对包含键和值引用的 SSTable 执行压缩来减少。）

B 树索引必须至少写入每个数据片段两次：一次写入预写日志，一次写入树页本身。此外，它们有时需要写出整个页，即使该页中只有几个字节发生了变化，以确保 B 树可以在崩溃或断电后正确恢复。

如果你取某个工作负载中写入磁盘的总字节数，除以如果你简单地写入没有索引的仅追加日志需要写入的字节数，你就得到了写入放大。（有时写入放大是根据 I/O 操作而不是字节来定义的。）在写入密集型应用中，瓶颈可能是数据库写入磁盘的速率。在这种情况下，写入放大越高，在可用磁盘带宽内它能处理的每秒写入次数就越少。

写入放大在 LSM 树和 B 树中都是问题。哪个更好取决于各种因素，如键和值的长度，以及你覆盖现有键与插入新键的频率。对于典型工作负载，LSM 树往往具有较低的写入放大，因为它们不必写入整个页，并且可以压缩 SSTable 的块。这是使 LSM 存储引擎非常适合写入密集型工作负载的另一个因素。

除了影响吞吐量，写入放大也与 SSD 的磨损相关：写入放大较低的存储引擎会使 SSD 磨损得更慢。

在测量存储引擎的写入吞吐量时，重要的是运行实验足够长时间，使写入放大的影响变得明显。当写入空 LSM 树时，还没有进行压缩，所以所有磁盘带宽都可用于新写入。随着数据库增长，新写入需要与压缩共享磁盘带宽。

磁盘空间使用

B 树可能随时间变得碎片化：例如，如果大量键被删除，数据库文件可能包含许多不再被 B 树使用的页。随后添加到 B 树可以使用这些空闲页，但它们不能轻易返回给操作系统，因为它们在文件中间，所以它们仍然占用文件系统上的空间。因此，数据库需要一个后台进程来移动页以更好地放置它们，如 PostgreSQL 中的 vacuum 进程。

在 LSM 树中，碎片化问题较小，因为压缩过程定期重写数据文件，SSTable 没有未使用空间的页。此外，键值对块在 SSTable 中可以更好地压缩，因此通常比 B 树产生更小的磁盘文件。已被覆盖的键和值继续占用空间，直到被压缩移除，但使用分层压缩时这种开销相当低。大小分层压缩（见”压缩策略”）使用更多磁盘空间，特别是在压缩期间临时使用。

磁盘上有某些数据的多个副本也可能在你需要删除某些数据并确信它确实已被删除时成为问题（也许是为了遵守数据保护法规）。例如，在大多数 LSM 存储引擎中，删除的记录可能仍然存在于较高层，直到代表删除的墓碑通过所有压缩层传播，这可能需要很长时间。专门的存储引擎设计可以更快地传播删除。

另一方面，如果你想在某个时间点对数据库进行快照（例如用于备份或创建数据库副本进行测试），SSTable 段文件的不可变性是有用的：你可以写出 memtable 并记录当时存在的段文件。只要你不删除属于快照的文件，你就不需要实际复制它们。在页被覆盖的 B 树中，高效地进行这种快照更困难。

多列索引与二级索引

到目前为止，我们只讨论了键值索引，它们类似于关系模型中的主键索引。主键唯一标识关系表中的一行，或文档数据库中的一个文档，或图数据库中的一个顶点。数据库中的其他记录可以通过其主键（或 ID）引用该行/文档/顶点，索引用于解析这种引用。

拥有二级索引也很常见。在关系数据库中，你可以使用 CREATE INDEX 命令在同一表上创建多个二级索引，允许你按主键以外的列搜索。例如，在第 3 章的图 3-1 中，你很可能会在 user_id 列上有二级索引，以便你可以在每个表中找到属于同一用户的所有行。

二级索引可以很容易地从键值索引构建。主要区别在于，在二级索引中，索引值不一定是唯一的；即，同一个索引条目下可能有许多行（文档、顶点）。这可以通过两种方式解决：要么使索引中的每个值成为匹配行标识符的列表（如全文索引中的倒排列表），要么通过向其附加行标识符使每个条目唯一。具有原地更新的存储引擎（如 B 树）和日志结构存储都可以用于实现索引。

在索引中存储值

索引中的键是查询搜索的内容，但值可以是以下几种之一：

聚集索引（Clustered index）：如果实际数据（行、文档、顶点）直接存储在索引结构内，则称为聚集索引。例如，在 MySQL 的 InnoDB 存储引擎中，表的主键总是聚集索引，在 SQL Server 中，你可以为每个表指定一个聚集索引。
堆文件（Heap file）：或者，值可以是对实际数据的引用：要么是所讨论行的主键（InnoDB 对二级索引这样做），要么是对磁盘上位置的直接引用。在后一种情况下，存储行的位置称为堆文件，它以特定顺序存储数据（它可能是仅追加的，或者可能跟踪删除的行以便稍后覆盖新数据）。例如，Postgres 使用堆文件方法。
覆盖索引（Covering index）或包含列的索引：这是两者之间的中间地带，它在索引内存储表的一些列，此外还将完整行存储在堆或主键聚集索引中。这允许仅使用索引回答一些查询，而无需解析主键或查看堆文件（在这种情况下，索引被称为”覆盖”查询）。这可以使一些查询更快，但数据重复意味着索引使用更多磁盘空间并降低写入速度。

到目前为止讨论的索引只将单个键映射到一个值。如果你需要同时查询表的多个列（或文档中的多个字段），请参见”多维索引与全文索引”。

在不改变键的情况下更新值时，堆文件方法允许记录原地覆盖，前提是新值不大于旧值。如果新值更大，情况就更复杂了，因为它可能需要移动到堆中有足够空间的新位置。在这种情况下，要么需要更新所有索引以指向记录的新堆位置，要么在旧堆位置留下转发指针。

全内存存储

本章到目前为止讨论的数据结构都是对磁盘限制的回应。与主内存相比，磁盘处理起来很麻烦。对于机械磁盘和 SSD，如果你想在读写上有良好的性能，磁盘上的数据需要仔细布局。然而，我们容忍这种麻烦，因为磁盘有两个显著优势：它们是持久的（如果断电内容不会丢失），每千兆字节成本比 RAM 低。

随着 RAM 变得更便宜，每千兆字节成本的论点被削弱。许多数据集根本没有那么大，所以完全将它们保存在内存中是可行的，可能分布在几台机器上。这导致了内存数据库的发展。

一些内存键值存储，如 Memcached，仅用于缓存，如果机器重启数据丢失是可以接受的。但其他内存数据库旨在实现持久性，这可以通过特殊硬件（如电池供电的 RAM）、将更改日志写入磁盘、将定期快照写入磁盘，或将内存状态复制到其他机器来实现。

当内存数据库重启时，它需要重新加载其状态，要么从磁盘，要么通过网络从副本（除非使用特殊硬件）。尽管写入磁盘，它仍然是内存数据库，因为磁盘仅用作仅追加日志以保证持久性，读取完全由内存服务。写入磁盘也有操作优势：磁盘上的文件可以轻松备份、检查和分析。

VoltDB、SingleStore 和 Oracle TimesTen 等产品是具有关系模型的内存数据库，供应商声称通过消除与管理磁盘数据结构相关的所有开销，可以提供巨大的性能改进。RAMCloud 是一个开源的内存键值存储，具有持久性（对内存中的数据和磁盘上的数据都使用日志结构方法）。Redis 和 Couchbase 通过异步写入磁盘提供弱持久性。

反直觉的是，内存数据库的性能优势并不是因为它们不需要从磁盘读取。即使基于磁盘的存储引擎，如果你有足够内存，也可能永远不需要从磁盘读取，因为操作系统反正会将最近使用的磁盘块缓存在内存中。相反，它们可以更快，因为它们可以避免将内存数据结构编码为可以写入磁盘的形式的开销。

除了性能，内存数据库的另一个有趣领域是提供难以用磁盘索引实现的数据模型。例如，Redis 为各种数据结构（如优先队列和集合）提供类似数据库的接口。因为它将所有数据保存在内存中，其实现相对简单。

分析型数据存储

数据仓库的数据模型最常见的是关系型，因为 SQL 通常非常适合分析查询。有许多图形数据分析工具可以生成 SQL 查询，可视化结果，并允许分析师探索数据（通过下钻、切片和切块等操作）。

从表面上看，数据仓库和关系型 OLTP 数据库看起来很相似，因为它们都有 SQL 查询接口。然而，系统的内部可能看起来非常不同，因为它们针对非常不同的查询模式进行了优化。许多数据库供应商现在专注于支持事务处理或分析工作负载，而不是两者都支持。

一些数据库，如 Microsoft SQL Server、SAP HANA 和 SingleStore，在同一产品中支持事务处理和数据仓库。然而，这些混合事务和分析处理（HTAP）数据库（在”数据仓库”中介绍）正日益成为两个独立的存储和查询引擎，只是碰巧可以通过通用 SQL 接口访问。

云数据仓库

Teradata、Vertica 和 SAP HANA 等数据仓库供应商既销售商业许可的本地仓库，也销售基于云的解决方案。但随着许多客户迁移到云端，新的云数据仓库如 Google Cloud BigQuery、Amazon Redshift 和 Snowflake 也得到了广泛采用。与传统数据仓库不同，云数据仓库利用可扩展的云基础设施，如对象存储和无服务器计算平台。

云数据仓库往往与其他云服务更好地集成，并且更具弹性。例如，许多云仓库支持自动日志摄取，并提供与 Google Cloud 的 Dataflow 或 Amazon Web Services 的 Kinesis 等数据处理框架的轻松集成。这些仓库也更具弹性，因为它们将查询计算与存储层解耦。数据持久化在对象存储而不是本地磁盘上，这使得独立调整存储容量和查询计算资源变得容易，正如我们之前在”云原生系统架构”中看到的。

Apache Hive、Trino 和 Apache Spark 等开源数据仓库也随着云的发展而发展。随着分析数据存储转移到对象存储上的数据湖，开源仓库开始解耦。以下组件，以前集成在 Apache Hive 等单一系统中，现在通常作为独立组件实现：

查询引擎：Trino、Apache DataFusion 和 Presto 等查询引擎解析 SQL 查询，将其优化为执行计划，并对数据执行它们。执行通常需要并行、分布式数据处理任务。一些查询引擎提供内置任务执行，而其他选择使用第三方执行框架如 Apache Spark 或 Apache Flink。
存储格式：存储格式决定表的行如何编码为文件中的字节，然后通常存储在对象存储或分布式文件系统中。这些数据然后可以被查询引擎访问，也可以被使用数据湖的其他应用访问。此类存储格式的例子包括 Parquet、ORC、Lance 或 Nimble，我们将在下一节中看到更多关于它们的内容。
表格式：Apache Parquet 和类似存储格式写入的文件一旦写入通常是不可变的。为了支持行插入和删除，使用 Apache Iceberg 或 Databricks 的 Delta 格式等表格式。表格式指定定义哪些文件构成表以及表模式的文件格式。此类格式还提供高级功能，如时间旅行（查询表在之前时间点的状态的能力）、垃圾回收，甚至事务。
数据目录：就像表格式定义哪些文件构成表一样，数据目录定义哪些表构成数据库。目录用于创建、重命名和删除表。与存储和表格式不同，Snowflake 的 Polaris 和 Databricks 的 Unity Catalog 等数据目录通常作为独立服务运行，可以使用 REST 接口查询。Apache Iceberg 也提供目录，可以在客户端内部或作为单独进程运行。查询引擎在读写表时使用目录信息。传统上，目录和查询引擎是集成的，但解耦它们使数据发现和数据治理系统（在”数据系统、法律与社会”中讨论）也能够访问目录的元数据。

列式存储

正如在”星型与雪花型：分析模式”中讨论的，数据仓库按惯例通常使用关系模式，其中包含一个大的事实表，包含对外键维度表的引用。如果你的事实表中有数万亿行和 PB 级数据，高效地存储和查询它们成为一个具有挑战性的问题。维度表通常小得多（数百万行），因此在本节中我们将专注于事实的存储。

尽管事实表通常有 100 多列宽，但典型的数据仓库查询一次只访问其中的 4 或 5 列（分析很少需要 SELECT * 查询）。以示例 4-1 中的查询为例：它访问大量行（2024 日历年期间每次购买水果或糖果的出现），但它只需要访问 fact_sales 表的三个列：date_key、product_sk 和 quantity。该查询忽略所有其他列。

示例 4-1 分析人们在不同星期几更倾向于购买新鲜水果还是糖果

SELECT
  dim_date.weekday, dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date    ON fact_sales.date_key   = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2024 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;

我们如何高效地执行这个查询？

在大多数 OLTP 数据库中，存储以行式布局：表中一行的所有值都存储在一起。文档数据库类似：整个文档通常存储为一个连续的字节序列。你可以在图 4-1 的 CSV 示例中看到这一点。

为了处理像示例 4-1 这样的查询，你可能在 fact_sales.date_key 和/或 fact_sales.product_sk 上有索引，告诉存储引擎在哪里找到特定日期或特定产品的所有销售。但是，行式存储引擎仍然需要将所有这些行（每行包含 100 多个属性）从磁盘加载到内存中，解析它们，并过滤掉不符合所需条件的行。这可能需要很长时间。

列式（或列导向）存储背后的想法很简单：不要将一行的所有值存储在一起，而是将每列的所有值存储在一起。如果每列单独存储，查询只需要读取和解析该查询中使用的那些列，这可以节省大量工作。图 4-7 使用图 3-5 中事实表的扩展版本说明了这个原理。

注意

列存储最容易在关系数据模型中理解，但它同样适用于非关系数据。例如，Parquet 是一种列式存储格式，支持文档数据模型，基于 Google 的 Dremel，使用称为分解或条带化的技术。

图 4-7 按列而不是按行存储关系数据。

列式存储布局依赖于每列以相同顺序存储行。因此，如果你需要重新组装整行，你可以从每个单独列中取第 23 个条目，将它们组合在一起形成表的第 23 行。

事实上，列式存储引擎实际上并不将整个列（可能包含数万亿行）一次性存储。相反，它们将表分成数千或数百万行的块，在每个块内单独存储每列的值。由于许多查询限制在特定日期范围内，通常让每个块包含特定时间戳范围的行。然后查询只需要加载它在所需日期范围重叠的块中需要的列。

列式存储几乎用于当今所有分析数据库，从大规模云数据仓库如 Snowflake 到单节点嵌入式数据库如 DuckDB，以及产品分析系统如 Pinot 和 Druid。它用于 Parquet、ORC、Lance 和 Nimble 等存储格式，以及 Apache Arrow 和 Pandas/NumPy 等内存分析格式。一些时序数据库，如 InfluxDB IOx 和 TimescaleDB，也基于列式存储。

列压缩

除了只从磁盘加载查询所需的列，我们还可以通过压缩数据进一步减少对磁盘吞吐量和网络带宽的需求。幸运的是，列式存储通常非常适合压缩。

看看图 4-7 中每列的值序列：它们通常看起来相当重复，这是压缩的好兆头。根据列中的数据，可以使用不同的压缩技术。在数据仓库中特别有效的一种技术是位图编码，如图 4-8 所示。

图 4-8 单列的压缩、位图索引存储。

通常，列中不同值的数量与行数相比很小（例如，零售商可能有数十亿销售交易，但只有 10 万个不同的产品）。我们现在可以将有 n 个不同值的列转换为 n 个单独的位图：每个不同值一个位图，每行一位。如果该行有该值，位为 1，否则为 0。

一个选项是使用每行一位来存储这些位图。然而，这些位图通常包含大量零（我们说它们是稀疏的）。在这种情况下，位图还可以额外进行游程编码：计算连续零或一的数量并存储该数字，如图 4-8 底部所示。Roaring bitmaps 等技术在两种位图表示之间切换，使用最紧凑的那种。这可以使列的编码非常高效。

此类位图索引非常适合数据仓库中常见的查询类型。例如：

WHERE product_sk IN (31, 68, 69)：加载 product_sk = 31、product_sk = 68 和 product_sk = 69 的三个位图，并计算三个位图的按位 OR，这可以非常高效地完成。
WHERE product_sk = 30 AND store_sk = 3：加载 product_sk = 30 和 store_sk = 3 的位图，并计算按位 AND。这可行是因为列以相同顺序包含行，所以一列位图中的第 k 位对应于另一列位图中的第 k 位所对应的同一行。

位图也可用于回答图查询，例如查找社交网络中被用户 X 关注且也关注用户 Y 的所有用户。列式数据库还有各种其他压缩方案，你可以在参考文献中找到。

注意

不要将列式数据库与宽列（也称为列族）数据模型混淆，在宽列模型中，一行可以有数千列，并且不需要所有行都有相同的列。尽管名称相似，宽列数据库是行式的，因为它们将一行的所有值存储在一起。Google 的 Bigtable、Apache Accumulo 和 HBase 是宽列模型的例子。

列存储中的排序顺序

在列存储中，行存储的顺序不一定重要。最容易按插入顺序存储它们，因为那样插入新行就意味着追加到每列。然而，我们可以选择施加顺序，就像我们之前对 SSTable 所做的那样，并将其用作索引机制。

注意，独立地对每列排序是没有意义的，因为那样我们就不知道列中的哪些项属于同一行。我们只能重建一行，因为我们知道一列中的第 k 项与另一列中的第 k 项属于同一行。

相反，数据需要一次对整个行排序，即使它是按列存储的。数据库管理员可以选择表应该按哪些列排序，利用他们对常见查询的了解。例如，如果查询经常针对日期范围，如上个月，将 date_key 作为第一个排序键可能是有意义的。然后查询可以只扫描上个月的行，这比扫描所有行快得多。

第二列可以确定第一列中具有相同值的任何行的排序顺序。例如，如果 date_key 是图 4-7 中的第一个排序键，将 product_sk 作为第二个排序键可能是有意义的，这样同一天同一产品的所有销售在存储中就组合在一起。这将帮助需要在特定日期范围内按产品分组或过滤销售的查询。

排序顺序的另一个优势是它可以帮助列压缩。如果主排序列没有太多不同值，那么排序后，它会有很长的序列，其中相同的值重复多次。简单的游程编码，就像我们用于图 4-8 中的位图一样，可以将该列压缩到几千字节——即使表有数十亿行。

这种压缩效果在主排序键上最强。第二和第三排序键会更混乱，因此不会有如此长的重复值序列。排序优先级较低的列基本上以随机顺序出现，所以它们可能压缩得不好。但让前几列排序总体上仍然是胜利的。

写入列式存储

正如在”刻画事务处理与分析”中看到的，数据仓库中的读取往往由对大量行的聚合组成；列式存储、压缩和排序都有助于使这些读取查询更快。数据仓库中的写入往往是数据的批量导入，通常通过 ETL 过程。

使用列式存储，在排序表的中间某处写入单行将非常低效，因为你必须重写从插入位置开始的所有压缩列。然而，一次批量写入多行可以分摊重写这些列的成本，使其高效。

通常使用日志结构方法来执行批量写入。所有写入首先进入面向行的、排序的、内存中的存储。当积累了足够的写入时，它们与磁盘上的列编码文件合并，并一次性批量写入新文件。由于旧文件保持不可变，新文件一次性写入，对象存储非常适合存储这些文件。

查询需要检查磁盘上的列数据和内存中的近期写入，并将两者结合起来。查询执行引擎对用户隐藏这种区别。从分析师的角度来看，用插入、更新或删除修改的数据立即反映在后续查询中。Snowflake、Vertica、Apache Pinot、Apache Druid 和许多其他系统都这样做。

查询执行：编译与向量化

复杂的分析 SQL 查询被分解为由多个阶段组成的查询计划，称为算子，它们可以分布在多台机器上并行执行。查询规划器可以通过选择使用哪些算子、以什么顺序执行它们以及在哪里运行每个算子来执行大量优化。

在每个算子内，查询引擎需要对列中的值做各种事情，例如找到值在特定值集合中的所有行（可能是连接的一部分），或检查值是否大于 15。它还需要查看同一行的几列，例如找到产品是香蕉且商店是特定感兴趣商店的所有销售交易。

对于需要扫描数百万行的数据仓库查询，我们不仅需要担心它们需要从磁盘读取的数据量，还需要担心执行复杂算子所需的 CPU 时间。最简单的算子就像编程语言的解释器：在迭代每行时，它检查代表查询的数据结构，找出需要对哪些列执行哪些比较或计算。不幸的是，对于许多分析目的来说，这太慢了。出现了两种替代方法来实现高效查询执行：

查询编译 查询引擎获取 SQL 查询并生成执行它的代码。代码逐行迭代，查看感兴趣列中的值，执行所需的任何比较或计算，如果满足所需条件，则将必要的值复制到输出缓冲区。查询引擎将生成的代码编译为机器代码（通常使用现有编译器如 LLVM），然后在已加载到内存的列编码数据上运行它。这种代码生成方法类似于 Java 虚拟机（JVM）和类似运行时中使用的即时（JIT）编译方法。

向量化处理 查询被解释，而不是编译，但通过一次批量处理列中的许多值而不是逐行迭代来加速。一组固定的预定义算子内置于数据库中；我们可以向它们传递参数并取回一批结果。

例如，我们可以将 product_sk 列和”bananas”的 ID 传递给相等算子，取回一个位图（输入列中每个值一位，如果是香蕉则为 1）；然后我们可以将 store_sk 列和感兴趣商店的 ID 传递给相同的相等算子，取回另一个位图；然后我们可以将两个位图传递给”按位 AND”算子，如图 4-9 所示。结果将是一个位图，包含特定商店中所有香蕉销售的 1。

图 4-9 两个位图之间的按位 AND 适合向量化。

这两种方法在实现上非常不同，但都在实践中使用。两者都可以通过利用现代 CPU 的特性实现非常好的性能：

优先选择顺序内存访问而不是随机访问以减少缓存未命中
在紧密的内循环中完成大部分工作（即指令数量少且没有函数调用）以保持 CPU 指令处理流水线繁忙并避免分支预测错误
利用并行性，如多线程和单指令多数据（SIMD）指令
直接在压缩数据上操作而无需将其解码为单独的内存表示，这节省了内存分配和复制成本

物化视图与数据立方体

我们之前在”物化与更新时间线”中遇到过物化视图：在关系数据模型中，它们是内容来自某些查询结果的表状对象。区别在于，物化视图是实际写入磁盘的查询结果副本，而虚拟视图只是编写查询的快捷方式。当你从虚拟视图读取时，SQL 引擎会将其动态展开为视图的底层查询，然后处理展开的查询。

当底层数据变化时，物化视图需要相应更新。一些数据库可以自动完成，还有如 Materialize 等系统专门从事物化视图维护。执行此类更新意味着写入时更多工作，但物化视图可以在需要重复执行相同查询的工作负载中提高读取性能。

物化聚合是数据仓库中可能有用的物化视图类型。如前所述，数据仓库查询通常涉及聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果许多不同查询使用相同的聚合，每次遍历原始数据可能很浪费。为什么不缓存查询最常使用的一些计数或总和呢？数据立方体或 OLAP 立方体通过创建按不同维度分组的聚合网格来实现这一点。图 4-10 显示了一个例子。

图 4-10 数据立方体的两个维度，通过求和聚合数据。

暂时假设每个事实只引用两个维度表——在图 4-10 中，这些是 date_key 和 product_sk。你现在可以画一个二维表，一个轴是日期，另一个轴是产品。每个单元格包含具有该日期-产品组合的所有事实的属性（例如 net_price）的聚合（例如 SUM）。然后你可以沿每行或每列应用相同的聚合，得到一个减少了一个维度的摘要（按产品不论日期的销售，或按日期不论产品的销售）。

一般来说，事实通常有两个以上的维度。在图 3-5 中有五个维度：日期、产品、商店、促销和客户。很难想象五维超立方体是什么样子，但原理保持不变：每个单元格包含特定日期-产品-商店-促销-客户组合的销售。然后可以沿每个维度重复总结这些值。

物化数据立方体的优势是某些查询变得非常快，因为它们实际上已经被预计算了。例如，如果你想知道昨天每个商店的总销售额，你只需要查看适当维度的总计——无需扫描数百万行。

缺点是数据立方体不像查询原始数据那样灵活。例如，没有办法计算来自价格超过 100 美元项目的销售比例，因为价格不是维度之一。因此，大多数数据仓库试图保留尽可能多的原始数据，并仅将数据立方体等聚合用作某些查询的性能提升。

多维索引与全文索引

我们在本章前半部分看到的 B 树和 LSM 树允许对单个属性进行范围查询：例如，如果键是用户名，你可以使用它们作为索引来高效找到所有以 L 开头的名字。但有时，按单个属性搜索是不够的。

最常见的多列索引类型称为连接索引，它通过将一列追加到另一列来简单地将几个字段组合成一个键（索引定义指定字段连接的顺序）。这就像老式的纸质电话簿，提供从（姓，名）到电话号码的索引。由于排序顺序，索引可用于找到具有特定姓氏的所有人，或具有特定姓氏-名字组合的所有人。然而，如果你想找到具有特定名字的所有人的索引，它就无用了。

另一方面，多维索引允许你同时查询几列。一个特别重要的情况是地理空间数据。例如，餐厅搜索网站可能有一个数据库，包含每家餐厅的纬度和经度。当用户查看地图上的餐厅时，网站需要搜索用户当前查看的矩形地图区域内的所有餐厅。这需要如下所示的二维范围查询：

SELECT * FROM restaurants WHERE latitude  > 51.4946 AND latitude  < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

纬度经度列上的连接索引无法有效回答这种查询：它可以给你一定纬度范围内的所有餐厅（但任何经度），或一定经度范围内的所有餐厅（但南北极之间的任何地方），但不能同时给出两者。

一个选择是使用空间填充曲线将二维位置转换为单个数字，然后使用常规 B 树索引。更常见的是使用专门的空间索引，如 R 树或 Bkd 树；它们划分空间，使附近的数据点倾向于分组在同一子树中。例如，PostGIS 使用 PostgreSQL 的通用搜索树索引工具将地理空间索引实现为 R 树。也可以使用规则间隔的三角形、正方形或六边形网格。

多维索引不仅用于地理位置。例如，在电子商务网站上，你可以使用维度（红、绿、蓝）上的三维索引来搜索特定颜色范围内的产品，或在天气观测数据库中，你可以在（日期、温度）上建立二维索引，以高效搜索 2013 年期间温度在 25 到 30℃ 之间的所有观测。使用一维索引，你必须扫描 2013 年的所有记录（无论温度）然后按温度过滤，或反之亦然。二维索引可以同时按时间戳和温度缩小范围。

全文搜索

全文搜索允许你通过可能出现在文本任何位置的关键词搜索文本文档集合（网页、产品描述等）。信息检索是一个庞大、专业的主题，通常涉及特定语言的处理：例如，几种亚洲语言书写时没有单词之间的空格或标点符号，因此将文本拆分为单词需要一个模型来指示哪些字符序列构成单词。全文搜索还经常涉及匹配相似但不完全相同的单词（如拼写错误或单词的不同语法形式）和同义词。这些问题超出了本书的范围。

然而，在其核心，你可以将全文搜索视为另一种多维查询：在这种情况下，可能出现在文本中的每个单词（词项）都是一个维度。包含词项 x 的文档在维度 x 中的值为 1，不包含 x 的文档值为 0。搜索提及”red apples”的文档意味着查找在 red 维度中为 1，同时在 apples 维度中也为 1 的查询。因此维度数量可能非常大。

许多搜索引擎用于回答此类查询的数据结构称为倒排索引。这是一种键值结构，其中键是词项，值是包含该词项的所有文档的 ID 列表（倒排列表）。如果文档 ID 是顺序数字，倒排列表也可以表示为稀疏位图，如图 4-8 所示：词项 x 的位图中的第 n 位为 1，如果 ID 为 n 的文档包含词项 x。

找到包含词项 x 和 y 的所有文档现在类似于向量化数据仓库查询，搜索匹配两个条件的行（图 4-9）：加载词项 x 和 y 的两个位图并计算它们的按位 AND。即使位图是游程编码的，这也可以非常高效地完成。

例如，Lucene 是 Elasticsearch 和 Solr 使用的全文索引引擎，就是这样工作的。它将词项到倒排列表的映射存储在类似 SSTable 的排序文件中，使用我们在本章前面看到的相同日志结构方法在后台合并。PostgreSQL 的 GIN 索引类型也使用倒排列表来支持全文搜索和 JSON 文档内的索引。

除了将文本拆分为单词，另一种方法是找到所有长度为 n 的子字符串，称为 n-gram。例如，字符串 “hello” 的三元组（n=3）是 “hel”、“ell” 和 “llo”。如果我们构建所有三元组的倒排索引，我们可以搜索至少三个字符长的任意子字符串的文档。三元组索引甚至允许搜索查询中的正则表达式；缺点是它们相当大。

为了处理文档或查询中的拼写错误，Lucene 能够在文本中搜索一定编辑距离内的单词（编辑距离为 1 意味着添加、删除或替换了一个字母）。它通过将词项集存储为键中字符上的有限状态自动机（类似于字典树），并将其转换为 Levenshtein 自动机来实现，该自动机支持在给定编辑距离内高效搜索单词。

向量嵌入

语义搜索超越了同义词和拼写错误，试图理解文档概念和用户意图。例如，如果你的帮助页面包含标题为”取消订阅”的页面，当用户搜索”如何关闭我的账户”或”终止合同”时，他们仍然应该能够找到该页面，这些在意义上很接近，尽管使用了完全不同的词。

为了理解文档的语义——它的含义——语义搜索索引使用嵌入模型将文档转换为浮点值向量，称为向量嵌入。向量代表多维空间中的一个点，每个浮点值代表文档沿一个维度轴的位置。嵌入模型生成在多维空间中彼此接近（在这个多维空间中）的向量嵌入，当嵌入的输入文档在语义上相似时。

注意

我们在”查询执行：编译与向量化”中看到了”向量化处理”一词。语义搜索中的向量有不同的含义。在向量化处理中，向量指的是可以用专门优化代码处理的一批位。在嵌入模型中，向量是代表多维空间中位置的浮点数列表。

例如，关于农业的维基百科页面的三维向量嵌入可能是 [0.1, 0.22, 0.11]。关于蔬菜的维基百科页面会很近，嵌入可能是 [0.13, 0.19, 0.24]。关于星型模式的页面可能有 [0.82, 0.39, -0.74] 的嵌入，相对较远。我们可以通过观察看出前两个向量比第三个更接近。

嵌入模型使用更大的向量（通常超过 1,000 个数字），但原理相同。我们不试图理解单个数字的含义；它们只是嵌入模型指向抽象多维空间中位置的一种方式。搜索引擎使用余弦相似度或欧几里得距离等距离函数来测量向量之间的距离。余弦相似度测量两个向量角度的余弦来确定它们有多接近，而欧几里得距离测量空间中两点之间的直线距离。

许多早期嵌入模型如 Word2Vec、BERT 和 GPT 处理文本数据。此类模型通常实现为神经网络。研究人员继续为视频、音频和图像创建嵌入模型。最近，模型架构已经多模态化：单个模型可以为多种模态（如文本和图像）生成向量嵌入。

语义搜索引擎在用户输入查询时使用嵌入模型生成向量嵌入。用户的查询和相关上下文（如用户位置）被输入嵌入模型。嵌入模型生成查询的向量嵌入后，搜索引擎必须使用向量索引找到具有相似向量嵌入的文档。

向量索引存储文档集合的向量嵌入。要查询索引，你传入查询的向量嵌入，索引返回其向量最接近查询向量的文档。由于我们之前看到的 R 树对多维度向量效果不佳，因此使用专门的向量索引，如：

平面索引 向量按原样存储在索引中。查询必须读取每个向量并测量其与查询向量的距离。平面索引准确，但测量查询与每个向量之间的距离很慢。

倒排文件（IVF）索引 向量空间被聚类为向量的分区（称为质心），以减少必须比较的向量数量。IVF 索引比平面索引快，但只能给出近似结果：查询和文档可能落入不同的分区，即使它们彼此接近。对 IVF 索引的查询首先定义探测，即简单地为要检查的分区数量。使用更多探测的查询将更准确，但会更慢，因为必须比较更多向量。

分层可导航小世界（HNSW） HNSW 索引维护向量空间的多层，如图 4-11 所示。每层表示为一个图，其中节点代表向量，边代表与附近向量的邻近性。查询从定位最顶层中的最近向量开始，该层节点数量较少。然后查询移动到下一层中的相同节点并跟随该层中的边，该层连接更密集，寻找更接近查询向量的向量。该过程继续直到到达最后一层。与 IVF 索引一样，HNSW 索引是近似的。

图 4-11 在 HNSW 索引中搜索最接近给定查询向量的数据库条目。

许多流行的向量数据库实现了 IVF 和 HNSW 索引。Facebook 的 Faiss 库有每种索引的许多变体，PostgreSQL 的 pgvector 也支持两者。IVF 和 HNSW 算法的完整细节超出了本书的范围，但它们的论文是极好的资源。

总结

在本章中，我们试图深入了解数据库如何执行存储和检索。当你将数据存储在数据库中时会发生什么，以及当你稍后查询数据时数据库会做什么？

“分析型与操作型系统”介绍了事务处理（OLTP）与分析（OLAP）之间的区别。在本章中，我们看到针对 OLTP 优化的存储引擎与针对分析优化的存储引擎看起来非常不同：

OLTP 系统针对大量请求进行优化，每个请求读写少量记录，需要快速响应。记录通常通过主键或二级索引访问，这些索引通常是从键到记录的有序映射，也支持范围查询。
数据仓库和类似的分析系统针对扫描大量记录的复杂读取查询进行优化。它们通常使用列式存储布局和压缩，最小化此类查询需要从磁盘读取的数据量，以及查询的即时编译或向量化，以最小化处理数据所花费的 CPU 时间。

在 OLTP 方面，我们看到了来自两个主要思想流派的存储引擎：

日志结构方法，只允许追加到文件和删除过时文件，但从不更新已写入的文件。SSTable、LSM 树、RocksDB、Cassandra、HBase、Scylla、Lucene 等都属于这一组。一般来说，日志结构存储引擎倾向于提供高写入吞吐量。
原地更新方法，将磁盘视为可以覆盖的固定大小页集。B 树是这种哲学的最大例子，用于所有主要的关系 OLTP 数据库和许多非关系数据库。根据经验，B 树往往更适合读取，提供比日志结构存储更高的读取吞吐量和更低的响应时间。

然后，我们研究了可以同时搜索多个条件的索引：如 R 树等多维索引，可以同时按纬度和经度搜索地图上的点，以及可以搜索同一文本中出现的多个关键词的全文搜索索引。最后，向量数据库用于文本文档和其他媒体的语义搜索；它们使用维度数量较多的向量，并通过比较向量相似性来找到相似的文档。

作为应用开发者，如果你掌握了这些关于存储引擎内部的知识，你就能更好地了解哪种工具最适合你的特定应用。如果你需要调整数据库的调优参数，这种理解让你能够想象更高或更低的值可能有什么效果。

虽然本章不能让你成为调优任何特定存储引擎的专家，但它希望为你提供了足够的词汇和想法，使你能够理解你选择的数据库的文档。

参考文献

[1] Nikolay Samokhvalov. How partial, covering, and multicolumn indexes may slow down UPDATEs in PostgreSQL. postgres.ai, October 2021.

[2] Goetz Graefe. Modern B-Tree Techniques. Foundations and Trends in Databases, volume 3, issue 4, pages 203–402, August 2011.

[3] Evan Jones. Why databases use ordered indexes but programming uses hash tables. evanjones.ca, December 2019.

…（参考文献列表保持原样，略）…

第 4 章 存储与检索