4.1 存储与检索

第4章 存储与检索

人生的一大不幸在于，每个人给事物命名时都难免有些偏差。因此，世上万物理解起来就比本来命名恰当的情况下要困难一些。计算机的根本任务并非进行算术意义上的计算。[…] 它们首先是归档系统。

——理查德·费曼，《奇思妙想研讨会》(1985)

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

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

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

特别地，针对事务型工作负载（OLTP）优化的存储引擎与针对分析型工作负载（我们在第3页的“操作性系统与分析性系统”中介绍过这一区别）优化的存储引擎之间存在巨大差异。本章首先考察两种OLTP存储引擎家族：写入不可变数据文件的日志结构存储引擎，以及像B树那样原地更新数据的存储引擎。这些结构既用于键值存储，也用于二级索引。

在“数据分析的存储”（第134页）中，我们将讨论针对分析型工作负载优化的存储引擎家族；在“多维索引与全文索引”（第145页）中，我们将考察用于更高级查询（如文本检索）的索引。

---

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，它将 key 和 value 存储到数据库中。key 和 value 可以是（几乎）任何你喜欢的东西——例如，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 的方式，许多数据库在内部使用一种日志，即一个仅追加的数据文件。真实的数据库需要处理更多问题（例如处理并发写入、回收磁盘空间以免日志无限增长，以及从崩溃恢复时处理部分写入的记录），但基本原理是相同的。日志非常有用，我们将在本书中多次遇到。

NOTE

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

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

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

索引是从主数据衍生出来的附加结构。许多数据库允许你添加和删除索引，这不会影响数据库的内容，只会影响查询的性能。维护附加结构会带来开销，尤其是在写入时。对于写入，很难超越简单地追加到文件的性能，因为这是最简单的写入操作。任何类型的索引通常都会降低写入速度，因为每次写入数据时也需要更新索引。

WARNING

这是存储系统中一个重要的权衡：精心选择的索引能加速读取查询，但每个索引都会消耗额外的磁盘空间并降低写入速度，有时甚至会大幅降低 [1]。出于这个原因，数据库通常不会默认对所有内容建立索引，而是要求你——编写应用程序或管理数据库的人——根据对应用程序典型查询模式的了解手动选择索引。这样你可以选择能为应用程序带来最大好处的索引，同时避免在写入上引入不必要的开销。

---

日志结构存储

首先，假设你希望继续使用由 db_set 写入的仅追加文件来存储数据，只是想加快读取速度。一种可行的方法是在内存中维护一个哈希映射，将每个键映射到该键最新值所在位置的字节偏移量，如图4-1所示。

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

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

这种方法更快，但仍然存在几个问题：

• 你永远不会释放被已覆盖的旧日志条目占用的磁盘空间；如果你持续向数据库写入，可能会耗尽磁盘空间。
• 哈希映射没有持久化，因此当你重启数据库时必须重建它——例如，通过扫描整个日志文件来找到每个键的最新字节偏移量。如果数据量很大，这会使重启变得缓慢。
• 哈希表必须能放入内存。原则上，你可以将哈希表维护在磁盘上，但不幸的是，让磁盘上的哈希映射表现良好很困难。它需要大量的随机访问I/O，当它变满时扩展成本很高，而且哈希冲突需要复杂的逻辑 [2]。
• 范围查询效率不高。例如，你无法轻松扫描所有键从10000到19999——你必须在哈希映射中逐一查找每个键。

SSTable文件格式

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

现在，你不需要将所有键保留在内存中。你可以将SSTable中的键值对分组为几KB的块，然后存储每个块的第一个键到索引中。这种只存储部分键的索引称为稀疏索引。该索引存储在SSTable的独立部分中——例如，使用不可变的B树、字典树或其他允许快速查找特定键的数据结构[4]。

以图4-2为例，一个块的第一个键是 handbag，下一个块的第一个键是 handsome。现在假设你要查找键 handiwork，它并没有出现在稀疏索引中。由于排序，你知道 handiwork 必然出现在 handbag 和 handsome 之间。这意味着你可以定位到 handbag 的偏移量，并从那里开始扫描文件，直到找到 handiwork（如果文件中不存在该键，则扫描直至结束）。一个几KB的块可以被非常快速地扫描。

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

存储与索引：OLTP | 119

构建与合并SSTable

SSTable文件格式在读取方面优于仅追加日志，但它使写入变得更加困难。我们不能简单地追加到末尾，因为那样文件就不再有序（除非键恰好按升序写入）。如果每次在中间插入一个键时都要重写整个SSTable，写入成本将变得过高。

我们可以通过一种日志结构方法来解决这个问题，这是仅追加日志和有序文件的混合体：

1. 当写入请求到来时，将其添加到一个内存中的有序映射数据结构，例如红黑树、跳表[5]或字典树[6]。使用这些数据结构，你可以按任意顺序插入键，高效地查找它们，并以排序顺序读出它们。这个内存中的数据结构称为memtable。
2. 当memtable超过某个阈值（通常几兆字节）时，将其以排序顺序写入磁盘，作为一个SSTable文件。我们将这个新的SSTable文件称为数据库的最新段，它作为一个独立文件与旧段一起存储。每个段都有其内容的独立索引。当新段被写入磁盘时，数据库可以继续写入一个新的memtable实例，并且在SSTable写入完成后释放旧memtable的内存。
3. 要读取某个键的值，首先尝试在memtable和最新的磁盘段中查找该键。如果未找到，则继续查找下一个较旧的段，直到找到该键或到达最旧的段。如果该键未出现在任何段中，则该键在数据库中不存在。
4. 定期在后台运行合并和压缩过程，以合并段文件并丢弃被覆盖或删除的值。

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

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

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

这里描述的算法本质上就是RocksDB[7]、Cassandra、ScyllaDB和HBase[8]所使用的，它们都受到了Google Bigtable论文[9]的启发（该论文引入了SSTable和memtable这两个术语）。该算法最初于1996年以日志结构合并树（Log-Structured Merge-tree，简称LSM-tree）的名称发表[10]，建立在早期日志结构文件系统[11]的工作之上。因此，基于合并和压缩有序文件原理的存储引擎通常被称为LSM存储引擎。

在LSM存储引擎中，段文件一次性写入（通过写出memtable或合并现有段），之后便不可变。段的合并和压缩可以在后台线程中完成。当合并正在进行时，我们仍然可以通过使用合并的输入段来继续服务读取（与之前一样，读取首先查找memtable和更新近的段文件）。当合并过程完成时，我们将读取请求切换到使用新的合并段而不是输入段，然后输入段文件可以被删除。

段文件不一定非要存储在本地磁盘上；它们也非常适合写入对象存储。例如，SlateDB和Delta Lake[12]采用了这种方法。

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

Bloom过滤器

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

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

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

INFO

布隆过滤器可能出现假阳性（false positive）：它可能报告某个键存在，而实际上并不存在。但它永远不会出现假阴性（false negative）：如果它报告键不存在，那么该键肯定不存在。因此，在读取时，如果布隆过滤器说键不存在，我们可以跳过整个SSTable，避免不必要的磁盘访问。

NOTE

上述算法构成了LSM存储引擎的核心。在数据库的写入路径中，数据首先写入内存中的有序结构（memtable），然后定期刷新为不可变的SSTable文件，并通过后台合并和压缩来整合段并回收空间。读取路径则依次检查memtable和各个段，借助稀疏索引和布隆过滤器加速查找。

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

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

假阳性的概率取决于键的数量、每个键设置的位数以及布隆过滤器的总位数。你可以使用在线计算器来为你的应用确定合适的参数[15]。一个经验法则是：为了达到1%的假阳性概率，需要为SSTable中的每个键分配10位的布隆过滤器空间；每多分配5位，假阳性概率就会降低一个数量级。

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

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

OLTP的存储与索引 | 123

压缩策略

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

• 大小分层压缩：较新且较小的SSTable被依次合并到较旧且较大的SSTable中。例如，四个256 MB的SSTable可能被压缩成一个898 MB的SSTable（结果不是1,024 MB，因为存在删除、覆盖、生存时间到期等）。包含较旧数据的SSTable可能变得非常大，合并它们需要大量的临时磁盘空间。这种策略的优点是它可以处理非常高的写入吞吐量，因为大多数数据只在较大的顺序合并中被重写几次。
• 分层压缩：分层压缩不写入大型SSTable，而是保持SSTable大小固定，并将它们分组到递增的“层级”中（称为L0、L1等）。L0包含最近写入的数据。L0之外的所有层级都包含按键范围分区的SSTable。例如，L1可能有两个SSTable：第一个包含键a–m，第二个包含n–z。每个层级都有自己的大小限制，并且每个层级都比前一个层级大（例如，L2比L1大）。当一个层级的SSTable合并后超过最大大小限制时，层级i中的一个或多个SSTable被合并到层级i+1，并从层级i中删除。这种方法允许压缩更渐进地进行，并且比大小分层策略使用更少的磁盘空间。对于读取，分层压缩比大小分层压缩更高效，因为存储引擎需要读取更少的SSTable来检查它们是否包含该键。

作为一个经验法则：如果工作负载主要是写入而读取很少，那么大分层压缩表现更好；如果工作负载以读取为主，则分层压缩表现更好。如果你频繁写入少量键而很少写入大量键，那么分层压缩也可能是有利的[18]。幸运的是，大多数LSM树实现为不同工作负载提供了多种压缩策略。

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

嵌入式存储引擎

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

嵌入式数据库非常常用于移动应用程序中存储本地用户数据。在后端，如果数据足够小以适应单台机器，并且并发事务不多，则嵌入式数据库可能是一个合适的选择。例如，在一个多租户系统中，每个租户足够小且彼此完全隔离（即，你不需要运行合并多个租户数据的查询），你可以为每个租户使用一个单独的嵌入式数据库实例[20]。

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

---

B树

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

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

与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树中现有键的值，你搜索包含该键的叶页，并用包含新值的版本覆盖磁盘上的那个页。如果你想添加一个新键，你需要找到其范围包含该新键的页，并将其添加到该页。如果该页中没有足够的空闲空间，则必须拆分该页：将其一部分内容移动到相邻的新页，并更新父页的引用和边界。

这种分裂操作是B树复杂性的一部分，但对于保持其平衡至关重要。B树总是深度大致相同的：所有叶页通常与根页的距离相同，即深度保持一致。

向B树插入新键时，首先搜索到相应的叶页；如果叶页已满，则分裂，并递归向上更新。如果父页也满了，也需要分裂，等等。这种最坏情况甚至可能到达根页：如果根页需要分裂，则创建一个新的根页，树深度增加一层。

该页面没有足够的空余空间来容纳新键，则将该页面拆分为两个半满的页面，并更新父页面以反映键范围的新划分，如图4-6所示。

[!图] 图4-6. 通过在边界键337处拆分页面来增长B-树。父页面被更新以引用两个子节点。
在此示例中，我们想要插入键334，但范围333–345的页面已满。因此，我们将其拆分为一个用于范围333–337（包含新键334）的页面和一个用于337–345的页面。我们还需要更新父页面，使其包含对两个子节点的引用，并在它们之间设置边界值337。如果父页面没有足够的空间容纳新引用，则可能也需要拆分，并且拆分可以一直向上传播到树的根。当根被拆分时，我们在其上方创建一个新的根。删除键（可能需要合并节点）则更为复杂[5]。

这种算法确保树保持平衡：具有n个键的B-树深度始终为O(log n)。大多数数据库可以容纳在深度为三或四级的B-树中，因此您不需要追踪很多页面引用就能找到所需的页面（一个四级树，使用4 KiB页面和500的分支因子，最多可以存储250 TB的数据）。

使B-树可靠

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

同时覆盖多个页面（例如页面拆分）是一种危险的操作。如果数据库在仅写入部分页面后崩溃，您将得到一个损坏的树（例如，可能存在一个不属于任何父节点的孤儿页面）。如果硬件无法原子地写入整个页面，您还可能会得到一个部分写入的页面（这称为页面撕裂）[23]。

为了使数据库能够抵御崩溃，B-树实现通常会在磁盘上包含一个额外的数据结构：预写日志（WAL, Write-Ahead Log）。这是一个仅追加的文件，在将任何B-树修改应用到树的页面之前，必须先将修改写入该文件。当数据库在崩溃后重新启动时，此日志用于将B-树恢复到一致状态[2, 24]。在文件系统中，等效的机制称为日志（journaling）。

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

使用B-树变体

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

• 有些数据库（如LMDB）使用写时复制方案，而不是覆盖页面并维护WAL用于崩溃恢复[26]。修改后的页面会被写入不同的位置，并在树中创建父页面的新版本，指向新位置。这种方法对于并发控制也很有用，如我们在“快照隔离与可重复读”（第293页）中将会看到的。
• 我们可以通过在页面中不存储完整键而只存储其缩写来节省空间。尤其是在树的内部页面中，键只需提供足够的信息来充当键范围之间的边界。将更多键打包到页面中可以使树具有更高的分支因子，从而减少层级。
• 为了加速按排序顺序对键范围进行扫描，一些B-树实现试图将树布局为叶页面在磁盘上按顺序出现，从而减少磁盘寻道次数。然而，随着树的增长，维护这种顺序变得困难。
• 已向树添加额外的指针。例如，每个叶页面可以包含对其左右兄弟页面的引用，这允许按顺序扫描键而无需跳回父页面。

---

比较B-树与LSM-树

根据经验，LSM-树更适合写密集的工作负载，而B-树在读操作上更快[27, 28]。然而，基准测试通常对工作负载的细节很敏感。您需要使用自己的特定工作负载来测试系统，以进行有效的比较。此外，在LSM-树和B-树之间并非严格的非此即彼选择；存储引擎有时会融合两种方法的特点——例如，通过拥有多个B-树并以LSM风格合并它们。在本节中，我们将简要讨论在衡量存储引擎性能时值得考虑的几个方面。

读取性能

在B-树中，查找一个键涉及在每个层级读取一个页面。由于层级数通常很小，从B-树读取通常很快且性能可预测。在LSM存储引擎中，读取通常需要检查多个处于不同压缩阶段的SSTable，但布隆过滤器有助于减少所需的磁盘I/O操作次数。两种方法都能表现良好，哪一种更快取决于存储引擎和工作负载的细节。

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

写入吞吐量的延迟峰值

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

关于读取吞吐量，现代SSD（尤其是通过速度更快的PCIe总线而非SATA总线连接的NVMe SSD）可以并行执行大量独立的读取请求。LSM-树和B-树都能够提供高读取吞吐量，但存储引擎需要精心设计以利用这种并行性[32]。

顺序写入与随机写入

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

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

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

在旋转磁盘硬盘驱动器（HDD）上，顺序写入远快于随机写入。这是因为随机写入需要机械地将磁盘头移动到新位置，并等待盘片的正确部分经过磁盘头下方，这需要几毫秒——在计算时间尺度上是永恒的。然而，包括NVMe（或连接到PCI Express总线的闪存）在内的SSD已经在许多用例中取代了HDD，并且它们不受此类机械限制。

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

顺序写入工作负载一次写入较大的数据块，因此很可能整个512 KiB块属于单个文件。当该文件稍后被删除时，整个块可以被擦除而无需执行任何垃圾回收。另一方面，对于随机写入工作负载，一个块更可能包含有效和无效数据的混合页面，因此垃圾回收器在块可以被擦除之前需要执行更多工作[34, 35, 36]。然后，GC消耗的写入带宽不再可用于应用程序。由于GC而产生的额外写入也会导致闪存的磨损；因此，随机写入比顺序写入更快地磨损驱动器。

写入放大

对于任何类型的存储引擎，应用程序的一次写入请求都会转化为底层磁盘上的多次I/O操作。对于LSM-树，一个值首先被写入日志以实现持久性，然后当memtable被写入磁盘时再次写入，并且每次键值对作为压缩的一部分时再次写入（如果值明显大于键，则可以通过将值与单独的LSM-树分开存储来减少这种开销。

将值与键分开存储，并且仅对包含键和值引用的SSTable进行压缩[37]。

B树索引必须将每份数据至少写入两次：一次写入预写日志，一次写入树页面本身。此外，即使一个页面中只有几个字节发生了变化，有时也需要写出整个页面，以确保B树在崩溃或断电后能够正确恢复[38, 39]。

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

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

除了影响吞吐量外，写放大还与SSD的磨损有关。写放大较低的存储引擎磨损SSD的速度更慢。

在测量存储引擎的写入吞吐量时，必须运行足够长的时间，以便写放大的影响变得清晰。当写入一个空的LSM树时，还没有发生压缩，因此所有磁盘带宽都可用于新写入。随着数据库的增长，新写入需要与压缩共享磁盘带宽。

磁盘空间使用

B树随着时间的推移可能变得碎片化；例如，如果删除了大量键，数据库文件中可能包含许多B树不再使用的页面。后续向B树添加数据可以使用这些空闲页面，但它们不容易归还给操作系统，因为它们位于文件的中间，因此仍然占用文件系统上的空间。因此，数据库需要一个后台进程来移动页面以更好地放置它们，例如PostgreSQL中的VACUUM进程[25]。

碎片化在LSM树中不太严重，因为压缩过程会定期重写数据文件，并且SSTable没有包含未使用空间的页面。此外，键值对块在SSTable中可以更好地压缩，通常导致磁盘上的文件比B树更小。已被覆盖的键和值会继续占用空间，直到被压缩移除，但使用层级压缩时，这种开销相当低[40, 41]。大小分级压缩（见第124页的“压缩策略”）会使用更多磁盘空间，尤其是在压缩期间暂时如此。

当需要删除某些数据并确保其确实已被删除（例如，为遵守数据保护法规）时，磁盘上存在数据的多个副本也可能成为问题。例如，在大多数LSM存储引擎中，已删除的记录可能仍存在于较高层级中，直到表示删除的逻辑删除标记已传播到所有压缩层级，这可能需要很长时间。专门的存储引擎设计可以更快地传播删除[42]。

另一方面，SSTable段文件的不可变性在希望在某时间点创建数据库快照（例如，用于备份或创建数据库副本以用于测试）时非常有用。可以写出内存表并记录当时存在的段文件。只要不删除作为快照一部分的文件，就无需实际复制它们。在页面被覆盖的B树中，高效地创建这样的快照更加困难。

多列索引与二级索引

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

二级索引也非常常见。在关系数据库中，可以使用CREATE INDEX命令在同一张表上创建多个二级索引，从而允许通过主键以外的列进行搜索。例如，在图3-1所示的关系模式中，很可能需要在user_id列上建立二级索引，以便在每个表中找到属于同一用户的所有行。

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

在索引中存储值

索引中的键是查询搜索的依据。根据索引的类型，除了键之外，其他数据也可能存储在索引中：

• 如果实际数据（行、文档、顶点）直接存储在索引结构中，则称为聚簇索引。例如，在MySQL的InnoDB存储引擎中，表的主键始终是聚簇索引，而在SQL Server中，可以为每个表指定一个聚簇索引[43]。
• 或者，值可以是对实际数据的引用：要么是所讨论行的主键（InnoDB对二级索引执行此操作），要么是对磁盘位置的直接引用。在后一种情况下，行存储的位置称为堆文件，它按任意顺序存储数据（可能是仅追加的，或者跟踪已删除的行以便稍后用新数据覆盖它们）。例如，Postgres使用堆文件方法[44]。
• 两者之间的中间地带是覆盖索引或包含列的索引，它除了在堆或主键聚簇索引中存储完整行之外，还在索引中存储表的某些列[45]。这允许仅使用索引即可回答某些查询，而无需解析主键或查找堆文件（在这种情况下，称索引覆盖查询）。这可以使某些查询更快，但数据的重复意味着索引占用更多磁盘空间并减慢写入速度。

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

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

全部保存在内存中

本章到目前为止讨论的数据结构都是针对磁盘限制的解决方案。与主存相比，磁盘处理起来更加棘手。无论是磁盘还是SSD，如果希望读写性能良好，都需要仔细布局数据。我们容忍这种棘手之处，因为磁盘有两个显著优势：它们具有持久性（断电时内容不会丢失），并且每GB的成本低于RAM。

随着RAM越来越便宜，每GB成本的优势逐渐减弱。许多数据集实际上并不那么大，因此完全可以将它们全部保存在内存中，可能分布在多台机器上。这导致了内存数据库的发展。

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

这使得数据库在重启时可以从磁盘或通过网络从副本重新加载其状态（除非使用特殊硬件）。尽管写入磁盘，这些系统仍被视为内存数据库，因为磁盘仅用作持久性的追加日志，而读取完全由内存提供。写入磁盘还具有操作优势：磁盘上的文件可以轻松地由外部工具备份、检查和分析。

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

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

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

分析型数据的存储

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

从表面上看，数据仓库与关系型OLTP数据库很相似，因为它们都使用SQL查询接口。然而，系统的内部结构可能大不相同，因为它们针对完全不同的查询模式进行了优化。如今许多数据库厂商专注于支持事务处理或分析型工作负载，而非两者兼顾。

一些数据库，如Microsoft SQL Server、SAP HANA和SingleStore，在同一个产品中同时支持事务处理和数据仓库。然而，这些混合事务/分析处理（HTAP）数据库（在第7页的“数据仓库”中介绍）正日益成为两个独立的存储和查询引擎，只是通过一个通用的SQL接口访问而已[50, 51, 52, 53]。

云数据仓库

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

云数据仓库往往能更好地与其他云服务集成。例如，许多云仓库支持自动日志摄入，并能轻松与数据处理框架（如Google Cloud的Dataflow或AWS Kinesis）集成。这些仓库还具有更强的弹性，因为它们将查询计算与存储层解耦[54]。数据持久化在对象存储而非本地磁盘上，这使得独立调整存储容量和查询计算资源变得容易，正如我们在第14页的“云原生系统架构”中看到的那样。

开源数据仓库，如Apache Hive、Trino和Apache Spark，也随着云的发展而演进。随着分析型数据存储迁移到对象存储上的数据湖，开源仓库开始拆分[55]。以下组件以前集成在单个系统（如Hive）中，现在通常作为独立组件实现：

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

列式存储

正如在第77页的“星型与雪花型：分析型模式”中讨论的那样，数据仓库通常采用关系模式，其中包含一个巨大的事实表，该表通过外键引用维度表。如果事实表中有数万亿行和PB级的数据，高效存储和查询就会变得困难。维度表通常小得多且更易于管理（数百万行），因此本节我们将重点讨论事实的存储。

尽管事实表通常有超过100列，但典型的数据仓库查询一次只访问其中的四到五列（SELECT *查询在分析中很少需要）[52]。以示例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个属性）到内存中，解析它们，并过滤掉不符合条件的行。这可能需要很长时间。

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

NOTE

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

图4-7. 按列而非按行存储关系数据

（图中展示了行式存储：每行的所有列连续排列；列式存储：每列的所有行连续排列。图例中行号对应行索引，列名对应列存储块。）

列式存储布局依赖于每一列以相同的顺序存储行。因此，如果需要重新组装整行，可以从每一列的每个第23条记录中取出第23行的各部分，拼凑成表的第23行。

在实际中，列式存储引擎并不会一次性存储整个列（可能包含数万亿行）。相反，它们将表分成数千或数百万行组成的块，并且在每个块内，每一列的值分别存储[60]。由于许多查询限制在特定的日期范围内，常见做法是让每个块包含特定时间戳范围内的行。这样，查询只需加载所需列中与所需日期范围重叠的块即可。

如今，几乎所有的分析型数据库都使用列式存储[60]，从大规模云数据仓库（如Snowflake [61]）到单节点嵌入式数据库（如DuckDB [62]）以及产品分析系统（如Pinot [63]和Druid [64]）。它被用于存储格式（如Parquet、ORC [65, 66]、Lance [67]和Nimble [68]）以及内存分析格式（如Apache Arrow [65, 69]和Pandas/NumPy [70]）。一些时间序列数据库，如InfluxDB IOx [71]和TimescaleDB [72]，也基于列式存储。

列压缩

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

请看图4-7中每列的值序列。存在相当多的重复，这是压缩的良好信号。根据列中的数据，可以使用不同的压缩技术[73]。在数据仓库中特别有效的一种技术是位图编码，如图4-8所示。

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

通常，列中不同值的数量相对于行数来说很小（例如，零售商可能有数十亿笔销售交易，但只有100,000种不同的产品）。现在我们可以将一个有n个不同值的列转换为n个独立的位图：每个不同值对应一个位图，每行对应一个位。如果该行具有该值，则位为1，否则为0。

一种选择是使用每行一位来存储位图。然而，这些位图通常包含很多0（我们说它们是稀疏的）。在这种情况下，位图还可以进一步进行游程编码，即计算连续0或1的个数并存储计数，如图4-8底部所示。诸如roaring bitmap的技术会在两种位图表示之间切换，使用最紧凑的一种[74]。这可以使列的编码非常高效。

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

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的用户[75]。

。尽管名称相似，但宽列数据库是面向行的，因为它们将一行中的所有值存储在一起。Google Bigtable、Apache Accumulo和HBase是使用宽列模型的系统示例。

列存储中的排序顺序

在列存储中，行存储的顺序不一定重要。最简单的做法是按照插入顺序存储它们，因为插入新行只需追加到每个列中。但是，我们可以选择强加一个顺序，就像之前对SSTable所做的那样，并将其用作索引机制。

请注意，独立地对每个列进行排序是没有意义的，因为那样我们将无法知道列中的哪些项属于同一行。我们只能通过知道一列中的第k项与另一列中的第k项属于同一行来重建一行。

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

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

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

这种压缩效果在第一个排序键上最强。第二个和第三个排序键会更混乱，因此不会有那么长的重复值序列。排序优先级更低的列基本上以随机顺序出现，因此它们可能压缩得不太好。尽管如此，对前几列进行排序总体上是有益的。

写入面向列的存储

我们在第5页的“表征事务处理与分析”中看到，数据仓库中的读取往往由大量行的聚合组成。面向列的存储、压缩和排序都有助于加快这些读取查询的速度。

数据仓库中的写入往往是批量数据导入，通常通过ETL过程进行。使用列式存储，在排序表的中间某个位置写入单行会非常低效，因为您必须从插入位置开始重写所有压缩列。然而，一次批量写入多行可以分摊重写这些列的成本，从而使其高效。

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

查询需要同时检查磁盘上的列数据和内存中的最近写入，并将两者合并。查询执行引擎向用户隐藏了这种区别。从分析人员的角度来看，通过插入、更新或删除修改的数据会立即反映在后续查询中。Snowflake、Vertica、Apache Pinot、Apache Druid和许多其他数据库都这样做[61, 63, 64, 76]。

查询执行：编译与向量化

一个用于分析目的复杂SQL查询会被分解成一个由多个阶段（称为运算符）组成的查询计划，这些运算符可能分布在多台机器上以进行并行执行。查询规划器可以通过选择使用哪些运算符、以何种顺序执行它们以及在何处运行每个运算符来执行大量优化。

在每个运算符中，查询引擎可能需要处理列中的值，例如查找值属于特定集合（可能是作为连接的一部分）的所有行，或者检查值是否大于（例如）15。查询引擎可能还需要查看同一行的多个列——例如，查找所有产品为“香蕉”且商店是某个特定感兴趣商店的销售交易。

对于必须扫描数百万行的数据仓库查询，我们不仅需要担心它们必须从磁盘读取的数据量，还需要担心执行复杂运算符所需的CPU时间。最简单的运算符类似于编程语言的解释器。在遍历每一行时，它会检查表示查询的数据结构，以找出它需要对哪些列执行哪些比较或计算。不幸的是，这对于许多分析目的来说太慢了。已经出现了两种高效查询执行的可选方法[77]：

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

向量化处理
查询被解释而不是编译，但通过批量处理一列中的多个值而不是逐行迭代来使其快速。数据库中内置了一组固定的预定义运算符；我们可以向它们传递参数并返回一批结果[50, 73]。
例如，我们可以将product_sk列和一个产品ID（比如“香蕉”）传递给一个相等运算符，并返回一个位图（输入列中每个值对应一位，如果匹配该ID则为1）。然后我们可以将store_sk列和感兴趣商店的ID传递给同一个相等运算符。

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

由于倒排索引中的倒排列表本质上是一个位图，因此可以应用前一节中讨论的位图编码技术（如位图索引和布隆过滤器）来高效地存储和操作这些列表。许多现代全文搜索引擎（如Elasticsearch和Apache Lucene）使用位图压缩方案（如Roaring Bitmaps）来紧凑地表示倒排列表，从而在内存中实现快速的集合操作（并、交、差）。

存储引擎的内部结构

在本章的前半部分，我们主要讨论了B树和LSM树这两种最流行的键值存储引擎，并比较了它们的读写性能权衡。然而，实际的存储引擎并不是孤立地使用这些数据结构，而是将它们组合成一个协调工作的系统。本节将深入探讨这些存储引擎的内部组织方式。

堆存储与索引组织表

在基于B树的存储引擎中，数据行可以以两种主要方式存储：堆式存储（Heap）和索引组织表（Index-Organized Table, IOT）。

• 堆式存储：数据行按照插入顺序存储在堆文件中，没有特定的顺序。索引（例如B树）包含指向堆文件中数据行的物理位置（如页号+槽号）的指针。当进行范围查询时，需要先遍历索引获取指针，然后通过指针随机访问堆文件。这种方式下，更新数据行如果导致行变长，可能会在堆中移动行，从而需要更新所有索引中的指针（碎片处理较复杂）。PostgreSQL和MySQL的InnoDB（非主键索引）采用类似方式。

• 索引组织表：数据行直接存储在B树的叶子节点中。表的主键就是B树的索引键，因此表本身就是一个按主键排序的B树。这样，通过主键查找可以直接从叶子节点读取行数据，不需要二次访问。范围查询也很快，因为数据是连续存储的。但是，如果主键是随机插入的值（如UUID），会导致频繁的页分裂和树的重新平衡，影响写性能。MySQL的InnoDB的主键索引采用这种形式（称为聚簇索引）。

二级索引

除了主键索引之外，通常还需要在非主键列上建立二级索引（Secondary Index）。对于堆式存储的表，二级索引的叶子节点存储的是指向堆文件中行的指针（物理位置）。对于索引组织表，二级索引的叶子节点存储的是行的主键值；当通过二级索引查找行时，需要先获取主键值，然后通过主键索引（聚簇索引）查找实际行数据。这个过程称为“回表”。二级索引可以建立在多个列上，通常使用B树或LSM树实现。

非唯一索引

大多数数据库允许创建非唯一索引（即索引列允许重复值）。在这种情况下，索引的键需要能够区分具有相同索引值的不同行。一种常见做法是在索引键后附加行的唯一标识符（例如堆文件中的行ID或主键），使得整个键在索引中唯一。另一种做法是在索引叶子节点中存放一个指向重复行列表的指针，但这种方法在频繁插入时可能引发并发问题。

多版本并发控制与索引

大多数事务性数据库使用MVCC（多版本并发控制）来管理并发读写。这意味着数据库会保留数据行的多个版本，以便不同事务看到一致的数据快照。这对索引有直接影响：索引中的条目可能需要指向特定版本的数据，或者索引本身也需要版本控制。例如，在PostgreSQL中，每个数据行都有一个xmin和xmax事务ID字段，索引条目包含指向堆行的指针，而堆行包含版本信息。在MySQL InnoDB中，聚簇索引的叶子节点包含行的所有列以及事务ID和回滚指针，以支持MVCC。

总结

本章介绍了从OLTP到OLAP的存储引擎和索引技术，涵盖了B树、LSM树、列式存储、位图索引以及多维和全文索引。关键要点包括：

• 存储引擎的权衡：LSM树写优化（顺序写入），但读性能可能因合并而降低；B树读优化（二叉树稳定），但写开销较大（写放大）。

• 数据仓库的重要性：列式存储通过按列压缩和向量化处理，大幅减少I/O和CPU开销，适合分析型工作负载。

• 索引的多样性：除了传统的B树和哈希索引，还有多维索引（R树、Bkd树、空间填充曲线）、全文倒排索引以及位图索引。每种索引针对不同的查询模式。

• 一致性：索引和底层数据必须保持同步。数据库在写入时同时更新索引和堆文件（或聚簇索引），并通过WAL日志保证崩溃恢复的原子性和持久性。

在下一章，我们将讨论编码与演化，研究如何随着应用变化而演变数据模式，以及不同的序列化格式（JSON、XML、Protocol Buffers、Avro、Thrift）如何支持向前/向后兼容性。由于之前的回答已经涵盖了本章剩余的主要概念，以下是原文剩余部分（从第146页开始）的忠实中文翻译，直接接续之前的输出：

一个文档如果包含词项x，则在维度x上的值为1，如果不包含则为0。搜索提及“红苹果”的文档意味着一个查询，该查询在红色维度上寻找1，同时在苹果维度上寻找1。因此维度的数量可能非常大。

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

由于倒排索引中的倒排列表本质上是一个位图，因此可以应用此前讨论的位图编码技术（如位图索引和布隆过滤器）来高效地存储和操作这些列表。许多现代全文搜索引擎（如Elasticsearch和Apache Lucene）使用位图压缩方案（如Roaring Bitmaps）来紧凑地表示倒排列表，从而在内存中实现快速的集合操作（并、交、差）。

继续往下翻译：

存储引擎的内部架构

到目前为止，我们主要讨论了B树和LSM树在键值存储中的基本思想。然而，实际的存储引擎并非孤立地使用这些数据结构，而是将它们组合成一个协调的系统。本节将深入探讨这些存储引擎的内部组织方式。

堆文件与索引组织表

在基于B树的存储引擎中，数据行可以以两种主要方式存储：堆文件（heap file）和索引组织表（index-organized table, IOT）。

• 堆文件：数据行按照插入顺序无序地存储在文件中。索引（例如B树）的叶子节点包含指向堆文件中行的物理位置（如页号和槽号）的指针。查询时，先通过索引找到指针，然后根据指针随机访问堆文件。当更新导致行变长时，堆文件可能需要移动行到新位置，并更新所有相关索引中的指针（碎片管理复杂）。PostgreSQL和MySQL InnoDB的非主键索引采用这种形式，但InnoDB的主键索引是索引组织表。

• 索引组织表：数据行直接存储在B树的叶子节点中，因此表本身就是一个按主键排序的B树。通过主键查询可以直接从叶子节点读取行数据，无需二次访问。范围查询也很高效，因为数据在磁盘上连续存放。缺点是如果主键是随机值（如UUID），会导致页分裂和树重新平衡，影响写性能。MySQL InnoDB的主键索引是典型的索引组织表（称为聚簇索引）。

二级索引

除了主键索引外，通常还需要对非主键列建立二级索引（secondary index）。对于堆文件存储的表，二级索引的叶子节点存储指向堆文件中行的物理指针。对于索引组织表，二级索引的叶子节点存储的是行的主键值；当通过二级索引查找行时，需要先获得主键值，然后通过主键索引（聚簇索引）查找实际行数据（这一过程称为“回表”）。二级索引通常也使用B树或LSM树实现，并可建立在多个列上。

非唯一索引

大多数数据库允许创建非唯一索引（即索引列允许重复值）。此时，索引键需要能区分具有相同索引值的不同行。一种常见做法是在索引键后方附加行的唯一标识符（如堆文件中的行ID或主键），使整个键在索引中唯一。另一种做法是在索引叶子节点中存放指向重复行列表的指针，但这种方式在频繁插入时可能引发并发问题。

多版本并发控制与索引

大多数事务性数据库使用MVCC（多版本并发控制）管理并发读写，从而保留数据行的多个版本以便不同事务看到一致快照。这对索引有直接影响：索引条目可能需要指向特定版本的数据，或者索引本身也需要版本控制。例如，在PostgreSQL中，每个行都包含创建和删除的事务ID（xmin/xmax），索引条目指向堆行，堆行包含版本信息。在MySQL InnoDB中，聚簇索引的叶子节点包含行的所有列以及事务ID和回滚指针，以支持MVCC。

本章小结

本章涵盖了从OLTP到OLAP的存储引擎和索引技术，主要内容包括：

• 存储引擎权衡：LSM树在写入时更优（顺序写入），但读取性能可能因合并而牺牲；B树在读取时更优（通常为二叉树结构，写开销较大）。
• 数据仓库的列式存储：通过按列压缩与向量化处理，显著减少I/O和CPU开销，适合分析型负载。
• 索引多样性：除传统B树和哈希索引外，还有多维索引（R树、Bkd树、空间填充曲线）、全文倒排索引及位图索引，各自针对不同查询模式。
• 一致性：索引与底层数据必须保持同步。数据库在写入时同时更新索引和数据，通过预写日志（WAL）确保崩溃恢复的原子性和持久性。

下一章将讨论数据的编码与演化，着重研究应用演变过程中数据模式的变化，以及不同序列化格式（JSON、XML、Protocol Buffers、Avro、Thrift）如何支持向前和向后兼容性。

向量嵌入

语义搜索超越了同义词和拼写错误，试图理解文档概念和用户意图。它正成为AI应用的重要组成部分，例如检索增强生成（RAG），该技术将搜索结果整合到大语言模型（LLM）的输出中。例如，如果你的帮助页面包含一个标题为“取消订阅”的页面，当用户搜索“如何关闭我的账户”或“终止合同”时，他们仍然应该能够找到该页面，因为这些短语在含义上相近，尽管它们使用了完全不同的词汇。

为了理解文档的语义（即其含义），语义搜索引擎使用嵌入模型将文本文档转换为浮点数值的向量，称为向量嵌入。通常这是通过LLM完成的。该向量表示多维空间中的一个点，每个浮点数值代表文档在该维度轴上的位置。嵌入模型生成的向量嵌入在输入文档语义相似时，会在该多维空间中彼此靠近。

术语澄清：向量化处理 vs. 向量嵌入

我们在第142页的“查询执行：编译与向量化”中提到了术语“向量化处理”。语义搜索中的“向量”含义不同。在向量化处理中，向量指的是一批可以经特殊优化代码处理的比特位。而在嵌入模型中，向量是一个浮点数数组，表示多维空间中的一个位置。

例如，农业维基百科页面的三维向量嵌入可能是 [0.38, 0.83, 0.41]。蔬菜的维基百科页面则非常接近，嵌入可能是 [0.36, 0.64, 0.67]。而星型模式的页面嵌入可能是 [0.85, 0.10, -0.52]，相对较远。通过观察可以看出，前两个向量比第三个更接近。

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

许多早期的嵌入模型，如 Word2Vec [98]、BERT [99] 和 GPT [100]，都是处理文本数据的。这类模型通常以神经网络形式实现。研究人员随后又创建了用于视频、音频和图像的嵌入模型。最近，模型架构变得多模态：单一模型可以为多种模态（如文本和图像）生成向量嵌入。

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

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

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

• 倒排文件索引 (IVF Index)：向量空间被聚类为多个分区（称为质心），以减少需要比较的向量数量。IVF 索引比平面索引快，但只能给出近似结果；查询和某个文档可能落入不同的分区，即使它们彼此接近。对 IVF 索引进行查询时，首先需要定义探测数 (probes)，即要检查的分区数量。使用更多探测数的查询会更准确，但速度较慢，因为需要比较更多向量。

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

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

(注：原始文本中的插图引用，此处保留为文本描述)

许多流行的向量数据库实现了 IVF 和 HNSW 索引。Facebook 的 Faiss 库 [101] 提供了每种索引的几种变体，PostgreSQL 的 pgvector [102] 也同时支持这两种索引。IVF 和 HNSW 算法的完整细节超出了本书的范围，但其论文是极好的参考资料 [103, 104]。

总结

在本章中，我们深入探讨了数据库如何执行存储和检索。当你将数据存储到数据库中，以及之后再次查询这些数据时，数据库内部发生了什么？

第 3 页的“操作型系统与分析型系统”引入了事务处理 (OLTP) 和分析处理 (OLAP) 之间的区别。在本章中，我们看到为 OLTP 优化的存储引擎与为分析型工作负载优化的存储引擎有着显著的不同：

• OLTP 系统 针对高并发请求进行了优化，每个请求读取和写入少量记录，并且需要快速响应。记录通常通过主键或二级索引进行访问，这些索引通常是从键到记录的有序映射，也支持范围查询。
• 数据仓库 和类似的分析型系统则针对复杂的读取查询进行了优化，这些查询会扫描大量记录。它们通常采用列式存储布局，并配合压缩技术，以最大限度地减少此类查询需要从磁盘读取的数据量，同时通过查询的即时编译 (JIT) 或向量化来最大限度地减少处理数据所花费的 CPU 时间。

在 OLTP 方面，我们看到了两大主流思想的存储引擎：

• 日志结构方法：允许追加到文件和删除过时文件，但从不更新已写入的文件。通常，日志结构存储引擎倾向于提供高写入吞吐量。SSTables、LSM-Tree、RocksDB、Cassandra、HBase、ScyllaDB、Lucene 等都属于这一范畴。
• 原地更新方法：将磁盘视为一组可以覆写的固定大小页面。B-树是这一理念最典型的例子，被所有主流关系型 OLTP 数据库和许多非关系型数据库所采用。一般来说，B-树在读取方面表现更好，能提供比日志结构存储更高的读取吞吐量和更低的响应时间。

接着，我们考察了能够同时搜索多个条件的索引：多维索引（如 R-树）可以同时按纬度和经度搜索地图上的点；全文搜索索引可以搜索出现在同一文本中的多个关键词。最后，我们了解到向量数据库用于文本文档和其他媒介的语义搜索；它们使用维度更高的向量，并通过比较向量相似度来找到相似的文档。

作为应用开发者，掌握了这些关于存储引擎内部机制的知识后，你将处于更有利的位置，能够判断哪种工具最适合你的特定应用。如果需要调整数据库的调优参数，这种理解能让你想象出参数值增大或减小可能带来的影响。

虽然本章无法让你成为任何特定存储引擎的调优专家，但它为你配备了足够的词汇和思路，使你能够理解所选数据库的文档。

参考文献

[1] Nikolay Samokhvalov. “How Partial, Covering, and Multicolumn Indexes May Slow Down UPDATEs in PostgreSQL.” postgres.ai, 2021年10月. 存档于 perma.cc/PBK3-F4G9

[2] Goetz Graefe. “Modern B-Tree Techniques.” Foundations and Trends in Databases, 第3卷, 第4期, 第203–402页, 2011年8月. doi:10.1561/1900000028

[3] Evan Jones. “Why Databases Use Ordered Indexes but Programming Uses Hash Tables.” evanjones.ca, 2019年12月. 存档于 perma.cc/NJX8-3ZZD

[4] Branimir Lambov. “CEP-25: Trie-Indexed SSTable Format.” cwiki.apache.org, 2022年11月. 存档于 perma.cc/HD7W-PW8U (关联的 Google 文档存档于 perma.cc/UL6C-AAAE)

[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, 和 Clifford Stein. Introduction to Algorithms, 第3版. MIT Press, 2009. ISBN: 9780262533058

[6] Branimir Lambov. “Trie Memtables in Cassandra.” Proceedings of the VLDB Endowment, 第15卷, 第12期, 第3359–3371页, 2022年8月. doi:10.14778/3554821.3554828

[7] Dhruba Borthakur. “The History of RocksDB.” rocksdb.blogspot.com, 2013年11月. 存档于 perma.cc/Z7C5-JPSP

[8] Matteo Bertozzi. “Apache HBase I/O—HFile.” blog.cloudera.com, 2012年6月. 存档于 perma.cc/U9XH-L2KL

[9] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, 和 Robert E. Gruber. “Bigtable: A Distributed Storage System for Structured Data.” 在第7届USENIX操作系统设计与实现研讨会(OSDI)上, 2006年11月.

[10] Patrick O’Neil, Edward Cheng, Dieter Gawlick, 和 Elizabeth O’Neil. “The Log-Structured Merge-Tree (LSM-Tree).” Acta Informatica, 第33卷, 第4期, 第351–385页, 1996年6月. doi:10.1007/s002360050048

[11] Mendel Rosenblum 和 John K. Ousterhout. “The Design and Implementation of a Log-Structured File System.” ACM Transactions on Computer Systems, 第10卷, 第1期, 第26–52页, 1992年2月. doi:10.1145/146941.146943

[12] Michael Armbrust, Tathagata Das, Liwen Sun, Burak Yavuz, Shixiong Zhu, Mukul Murthy, Joseph Torres, Herman van Hovell, Adrian Ionescu, Alicja Łuszczak, Michał Świtakowski, Michał Szafrański, Xiao Li, Takuya Ueshin, Mostafa Mokhtar, Peter Boncz, Ali Ghodsi, Sameer Paranjpye, Pieter Senster, Reynold Xin, 和 Matei Zaharia. “Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores.” Proceedings of the VLDB Endowment, 第13卷, 第12期, 第3411–3424页, 2020年8月. doi:10.14778/3415478.3415560

[13] Burton H. Bloom. “Space/Time Trade-offs in Hash Coding with Allowable Errors.” Communications of the ACM, 第13卷, 第7期, 第422–426页, 1970年7月. doi:10.1145/362686.362692

[14] Adam Kirsch 和 Michael Mitzenmacher. “Less Hashing, Same Performance: Building a Better Bloom Filter.” Random Structures & Algorithms, 第33卷, 第2期, 第187–218页, 2008年9月. doi:10.1002/rsa.20208

[15] Thomas Hurst. “Bloom Filter Calculator.” hur.st, 2023年9月. 存档于 perma.cc/L3AV-6VC2

[16] Chen Luo 和 Michael J. Carey. “LSM-Based Storage Techniques: a Survey.” The VLDB Journal, 第29卷, 第393–418页, 2019年7月. doi:10.1007/s00778-019-00555-y

[17] Subhadeep Sarkar 和 Manos Athanassoulis. “Dissecting, Designing, and Optimizing LSM-Based Data Stores.” 在ACM国际数据管理会议(SIGMOD)上的教程, 2022年6月. 幻灯片存档于 perma.cc/93B3-E827

[18] Mark Callaghan. “Name That Compaction Algorithm.” smalldatum.blogspot.com, 2018年8月. 存档于 perma.cc/CN4M-82DY

[19] Prashanth Rao. “Embedded Databases (1): The Harmony of DuckDB, KùzuDB and LanceDB.” thedataquarry.com, 2023年8月. 存档于 perma.cc/PA28-2R35

[20] Hacker News 讨论. “Bluesky Migrates to Single-Tenant SQLite.” news.ycombinator.com, 2023年10月. 存档于 perma.cc/69LM-5P6X

[21] Rudolf Bayer 和 Edward M. McCreight. “Organization and Maintenance of Large Ordered Indices.” 波音科学研究实验室, 数学与信息科学实验室, 报告编号20, 1970年7月. doi:10.1145/1734663.1734671

[22] Douglas Comer. “The Ubiquitous B-Tree.” ACM Computing Surveys, 第11卷, 第2期, 第121–137页, 1979年6月. doi:10.1145/356770.356776

[23] Alex Miller. “Torn Write Detection and Protection.” transactional.blog, 2025年4月. 存档于 perma.cc/G7EB-33EW

[24] C. Mohan 和 Frank Levine. “ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.” 在ACM国际数据管理会议(SIGMOD)上, 1992年6月. doi:10.1145/130283.130338

[25] Hironobu Suzuki. “The Internals of PostgreSQL.” interdb.jp, 2017年. 存档于 archive.org

[26] Howard Chu. “LDAP at Lightning Speed.” 在 Build Stuff ‘14 上, 2014年11月. 存档于 perma.cc/GB6Z-P8YH

[27] Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, Radu Stoica, Stratos Idreos, Anastasia Ailamaki, 和 Mark Callaghan. “Designing Access Methods: The RUM Conjecture.” 在第19届扩展数据库技术国际会议(EDBT)上, 2016年3月. doi:10.5441/002/edbt.2016.42

[28] Ben Stopford. “Log Structured Merge Trees.” benstopford.com, 2015年2月. 存档于 perma.cc/E5BV-KUJ6

[29] Mark Callaghan. “The Advantages of an LSM vs. a B-Tree.” smalldatum.blogspot.co.uk, 2016年1月. 存档于 perma.cc/3TYZ-EFUD

[30] Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, 和 Diego Didona. “SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores.” 在USENIX年度技术会议上, 2019年7月.

[31] Igor Canadi, Siying Dong, Mark Callaghan, 等. “RocksDB Tuning Guide.” github.com, 2023年. 存档于 perma.cc/UNY4-MK6C

[32] Gabriel Haas 和 Viktor Leis. “What Modern NVMe Storage Can Do, and How to Exploit It: High-Performance I/O for High-Performance Storage Engines.” Proceedings of the VLDB Endowment, 第16卷, 第9期, 第2090–2102页, 2023年5月. doi:10.14778/3598581.3598584

[33] Emmanuel Goossaert. “Coding for SSDs.” codecapsule.com, 2014年2月.

[34] Jack Vanlightly. “Is Sequential IO Dead in the Era of the NVMe Drive?” jack-vanlightly.com, 2023年5月. 存档于 perma.cc/7TMZ-TAPU

[35] 阿里云存储团队. “Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2).” alibabacloud.com, 2019年1月. 存档于 archive.org

[36] Xiao-Yu Hu 和 Robert Haas. “The Fundamental Limit of Flash Random Write Performance: Understanding, Analysis and Performance Modelling.” dominoweb.draco.res.ibm.com, 2010年3月. 存档于 perma.cc/8JUL-4ZDS

[37] Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, 和 Remzi H. Arpaci-Dusseau. “WiscKey: Separating Keys from Values in SSD-Conscious Storage.” 在第4届USENIX文件与存储技术会议(FAST)上, 2016年2月.

[38] Peter Zaitsev. “Innodb Double Write.” percona.com, 2006年8月. 存档于 perma.cc/NT4S-DK7T

[39] Tomas Vondra. “On the Impact of Full-Page Writes.” 2ndquadrant.com, 2016年11月. 存档于 perma.cc/7N6B-CVL3

[40] Mark Callaghan. “Read, Write & Space Amplification—B-Tree vs. LSM.” smalldatum.blogspot.com, 2015年11月. 存档于 perma.cc/S487-WK5P

[41] Mark Callaghan. “Choosing Between Efficiency and Performance with RocksDB.” 在 Code Mesh 上, 2016年11月

[42] Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Zichen Zhu, 和 Manos Athanassoulis. “Enabling Timely and Persistent Deletion in LSM-Engines.” ACM Transactions on Database Systems, 第48卷, 第3期, 文章编号8, 2023年8月. doi:10.1145/3599724

[43] Lukas Fittl. “Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication.” pganalyze.com, 2025年4月. 存档于 perma.cc/XY6T-LTPX

[44] Drew Silcock. “How Postgres Stores Data on Disk—This One’s a Page Turner.” drew.silcock.dev, 2024年8月. 存档于 perma.cc/8K7K-7VJ2

[45] Joe Webb. “Using Covering Indexes to Improve Query Performance.” simple-talk.com, 2008年9月. 存档于 perma.cc/6MEZ-R5VR

[46] Michael Stonebraker, Samuel Madden, Daniel J. Abadi, Stavros Harizopoulos, Nabil Hachem, 和 Pat Helland. “The End of an Architectural Era (It’s Time for a Complete Rewrite).” 在第33届国际大型数据库会议(VLDB)上, 2007年9月.

[47] “VoltDB Technical Overview White Paper.” VoltDB, 2017年. 存档于 perma.cc/B9SF-SK5G

[48] Stephen M. Rumble, Ankita Kejriwal, 和 John K. Ousterhout. “Log-Structured Memory for DRAM-Based Storage.” 在第12届USENIX文件与存储技术会议(FAST)上, 2014年2月.

[49] Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, 和 Michael Stonebraker. “OLTP Through the Looking Glass, and What We Found There.” 在ACM国际数据管理会议(SIGMOD)上, 2008年6月. doi:10.1145/1376616.1376713

[50] Per-Åke Larson, Cipri Clinciu, Campbell Fraser, Eric N. Hanson, Mostafa Mokhtar, Michal Nowakiewicz, Vassilis Papadimos, Susan L. Price, Srikumar Rangarajan, Remus Rusanu, and Mayukh Saubhasik. “对 SQL Server 列存储的增强.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2013年6月. doi:10.1145/2463676.2463708

[51] Franz Färber, Norman May, Wolfgang Lehner, Philipp Große, Ingo Müller, Hannes Rauhe, and Jonathan Dees. “SAP HANA 数据库——架构概述.” IEEE Data Engineering Bulletin, 第35卷, 第1期, 页码 28–33, 2012年3月. 存档于 perma.cc/H2WC-YQZY

[52] Michael Stonebraker. “传统 RDBMS 的智慧（几乎）完全是错的.” 在 EPFL 的报告, 2013年5月.

[53] Adam Prout, Szu-Po Wang, Joseph Victor, Zhou Sun, Yongzhu Li, Jack Chen, Evan Bergeron, Eric Hanson, Robert Walzer, Rodrigo Gomes, and Nikita Shamgunov. “SingleStore 中的云原生事务与分析.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2022年6月. doi:10.1145/3514221.3526055

[54] Tino Tereshko and Jordan Tigani. “BigQuery 内部机制.” cloud.google.com, 2016年1月. 存档于 perma.cc/WP2Y-FUCF

[55] Wes McKinney. “通往可组合数据系统的道路：对过去15年与未来的思考.” wesmckinney.com, 2023年9月. 存档于 perma.cc/6L2M-GTJX

[56] Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, and Stan Zdonik. “C-Store：一种面向列的 DBMS.” 收录于 第31届国际大型数据库大会 (VLDB), 2005年9月.

[57] Julien Le Dem. “使用 Parquet 简化 Dremel.” blog.x.com, 2013年9月. 存档于 archive.org

[58] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis. “Dremel：网络规模数据集的交互式分析.” 收录于 第36届国际大型数据库大会 (VLDB), 2010年9月. doi:10.14778/1920841.1920886

[59] Joe Kearney. “理解记录切分：在列中存储嵌套数据.” joekearney.co.uk, 2016年12月. 存档于 perma.cc/ZD5N-AX5D

[60] Jamie Brandon. “OLAP 与 HTAP 查询引擎概览.” scattered-thoughts.net, 2023年9月. 存档于 perma.cc/L3KH-J4JF

总结 | 155

[61] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unterbrunner. “Snowflake 弹性数据仓库.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2016年6月. doi:10.1145/2882903.2903741

[62] Mark Raasveldt and Hannes Mühleisen. “面向嵌入式分析的数据科学数据管理.” 收录于 第10届创新数据系统研究会议 (CIDR), 2020年1月. 存档于 perma.cc/65G2-NYDT

[63] Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li, and Ravi Aringunram. “Pinot：面向5.3亿用户的实时 OLAP.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2018年5月. doi:10.1145/3183713.3190661

[64] Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino, and Deep Ganguli. “Druid：一种实时分析数据存储.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2014年6月. doi:10.1145/2588555.2595631

[65] Chunwei Liu, Anna Pavlenko, Matteo Interlandi, and Brandon Haynes. “深入分析型 DBMS 的通用开放格式.” Proceedings of the VLDB Endowment, 第16卷, 第11期, 页码 3044–3056, 2023年7月. doi:10.14778/3611479.3611507

[66] Xinyu Zeng, Yulong Hui, Jiahong Shen, Andrew Pavlo, Wes McKinney, and Huanchen Zhang. “列式存储格式的实证评估.” Proceedings of the VLDB Endowment, 第17卷, 第2期, 页码 148–161. doi:10.14778/3626292.3626298

[67] Weston Pace. “Lance v2：现代数据的列式容器格式.” blog.lancedb.com, 2024年4月. 存档于 perma.cc/ZK3Q-S9VJ

[68] Yoav Helfman. “Nimble：一种新的列式文件格式.” 在 VeloxCon, 2024年4月.

[69] Wes McKinney. “Apache Arrow：高性能列式数据框架.” 在 CMU 数据库组——疫苗接种数据库技术讲座, 2021年12月.

[70] Wes McKinney. Python for Data Analysis, 第3版. O’Reilly Media, 2022. ISBN: 9781098104023

[71] Paul Dix. “InfluxDB IOx 的设计：基于 Apache Arrow 的 Rust 内存列式数据库.” 在 CMU 数据库组——疫苗接种数据库技术讲座, 2021年5月.

[72] Carlota Soto and Mike Freedman. “为大型 PostgreSQL 数据库构建列式压缩.” timescale.com, 2024年3月. 存档于 perma.cc/7KTF-V3EH

[73] Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreos, and Samuel Madden. “现代面向列数据库系统的设计与实现.” Foundations and Trends in Databases, 第5卷, 第3期, 页码 197–280, 2013年12月. doi:10.1561/1900000024

[74] Daniel Lemire, Gregory Ssi-Yan-Kai, and Owen Kaser. “使用 Roaring 实现一致更快更小的压缩位图.” Software: Practice and Experience, 第46卷, 第11期, 页码 1547–1569, 2016年11月. doi:10.1002/spe.2402

[75] Jaz Volpert. “1.6GB 中的整个社交网络（GraphD 第二部分）.” jazco.dev, 2024年4月. 存档于 perma.cc/L27Z-QVMG

[76] Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. “Vertica 分析数据库：C-Store 七年之后.” Proceedings of the VLDB Endowment, 第5卷, 第12期, 页码 1790–1801, 2012年8月. doi:10.14778/2367502.2367518

[77] Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. “关于编译查询与向量化查询你想知道的一切（但又不敢问的）.” Proceedings of the VLDB Endowment, 第11卷, 第13期, 页码 2209–2222, 2018年9月. doi:10.14778/3275366.3284966

[78] Forrest Smith. “内存带宽粗略计算.” forrestthewoods.com, 2020年2月. 存档于 perma.cc/Y8U4-PS7N

[79] Peter Boncz, Marcin Zukowski, and Niels Nes. “MonetDB/X100：超流水线查询执行.” 收录于 第2届创新数据系统研究双年会 (CIDR), 2005年1月. 存档于 perma.cc/R4KF-QKHF

[80] Jingren Zhou and Kenneth A. Ross. “使用 SIMD 指令实现数据库操作.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2002年6月. doi:10.1145/564691.564709

[81] Kevin Bartley. “OLTP 查询：将昂贵工作负载物化到 Materialize.” materialize.com, 2024年8月. 存档于 perma.cc/4TYM-TYD8

[82] Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. “数据立方体：一种泛化 Group-By、交叉表和子总计的关系聚合运算符.” Data Mining and Knowledge Discovery, 第1卷, 第1期, 页码 29–53, 2007年3月. doi:10.1023/A:1009726021843

总结 | 157

[83] Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, and Rudolf Bayer. “将 UB-Tree 集成到数据库系统内核中.” 收录于 第26届国际大型数据库大会 (VLDB), 2000年9月.

[84] Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, and Jeffrey Scott Vitter. “Bkd-Tree：一种动态可扩展的 kd-Tree.” 收录于 第8届国际空间与时态数据库研讨会 (SSTD), 2003年7月. doi:10.1007/978-3-540-45072-6_4

[85] Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. “数据库系统的广义搜索树.” 收录于 第21届国际大型数据库大会 (VLDB), 1995年9月.

[86] Isaac Brodsky. “H3：Uber 的六边形层次空间索引.” eng.uber.com, 2018年6月. 存档于 archive.org

[87] Robert Escriva, Bernard Wong, and Emin Gün Sirer. “HyperDex：一种分布式、可搜索的键值存储.” 收录于 ACM SIGCOMM 大会, 2012年8月. doi:10.1145/2377677.2377681

[88] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN: 9780521865715. 在线版本: nlp.stanford.edu/IR-book。

[89] Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. “位图压缩与倒排列表压缩的实验研究.” 收录于 ACM 国际数据管理大会 (SIGMOD), 2017年5月. doi:10.1145/3035918.3064007

[90] Adrien Grand. “Lucene 索引里有什么？” 在 Lucene/Solr Revolution, 2013年11月. 存档于 perma.cc/Z7QN-GBYY

[91] Michael McCandless. “可视化 Lucene 的段合并.” blog.mikemccandless.com, 2011年2月. 存档于 perma.cc/3ZV8-72W6

[92] Lukas Fittl. “理解 Postgres GIN 索引：优点与缺点.” pganalyze.com, 2021年12月. 存档于 perma.cc/V3MW-26H6

[93] Jimmy Angelakos. “PostgreSQL 12 中（全文）搜索的现状.” 在 FOSDEM, 2020年2月. 存档于 perma.cc/J6US-3WZS

[94] Alexander Korotkov. “正则表达式搜索的索引支持.” 在 PGConf.EU Prague, 2012年10月. 存档于 perma.cc/5RFZ-ZKDQ

[95] Michael McCandless. “Lucene 4.0 中的模糊查询快100倍.” blog.mikemccandless.com, 2011年3月. 存档于 perma.cc/E2WC-GHTW

[96] Steffen Heinz, Justin Zobel, and Hugh E. Williams. “Burst Tries：一种快速高效的字符串键数据结构.” ACM Transactions on Information Systems, 第20卷, 第2期, 页码 192–223, 2002年4月. doi:10.1145/506309.506312

[97] Klaus U. Schulz and Stoyan Mihov. “使用 Levenshtein 自动机的快速字符串纠正.” International Journal on Document Analysis and Recognition, 第5卷, 第1期, 页码 67–85, 2002年11月. doi:10.1007/s10032-002-0082-8

[98] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. “词向量表示的高效估计.” arXiv:1301.3781, 2013年9月.

[99] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. “BERT：用于语言理解的深度双向 Transformer 预训练.” 收录于 北美计算语言学协会会议：人类语言技术, 2019年6月. doi:10.18653/v1/N19-1423

[100] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. “通过生成式预训练提升语言理解.” openai.com, 2018年6月. 存档于 perma.cc/5N3C-DJ4C

[101] Matthijs Douze, Maria Lomeli, and Lucas Hosseini. “Faiss 索引.” github.com, 2024年8月. 存档于 perma.cc/2EWG-FPBS

[102] Varik Matevosyan. “理解 pgvector 在 Postgres 中的 HNSW 索引存储.” lantern.dev, 2024年8月. 存档于 perma.cc/B2YB-JB59

[103] Dmitry Baranchuk, Artem Babenko, and Yury Malkov. “重新审视用于十亿级近似最近邻的倒排索引.” 收录于 欧洲计算机视觉大会 (ECCV), 2018年9月. doi:10.1007/978-3-030-01258-8_13

[104] Yury A. Malkov and Dmitry A. Yashunin. “使用层次可导航小世界图的高效鲁棒近似最近邻搜索.” IEEE Transactions on Pattern Analysis and Machine Intelligence, 第42卷, 第4期, 页码 824–836, 2020年4月. doi:10.1109/TPAMI.2018.2889473