4. 存储与检索

生活的苦恼之一是，每个人对事物的命名都有些偏差。这让我们理解世界变得比本该有的样子困难一些，要是命名方式不同就好了。计算机的主要功能并不是传统意义上的计算，比如算术运算。[……] 它们主要是归档系统。

理查德·费曼， 特立独行的思考 研讨会（1985）

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

在 第 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，它将在数据库中存储 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 所做的类似，许多数据库内部使用 日志，这是一个仅追加的数据文件。真正的数据库有更多问题要处理（如处理并发写入、回收磁盘空间以防日志无限增长，以及从崩溃中恢复时处理部分写入的记录），但基本原理是相同的。日志非常有用，我们将在本书中多次遇到它们。

Note

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

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

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

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

这是存储系统中的一个重要权衡：精心选择的索引加快了读查询速度，但每个索引都会消耗额外的磁盘空间并减慢写入速度，有时会大幅减慢 1。因此，数据库通常不会默认为所有内容建立索引，而是要求你 —— 编写应用程序或管理数据库的人 —— 使用你对应用程序典型查询模式的了解来手动选择索引。然后你可以选择为你的应用程序带来最大收益的索引，而不会引入超过必要的写入开销。

日志结构存储

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

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

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

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

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

SSTable 文件格式

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

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

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

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

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

构建和合并 SSTable

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

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

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

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

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

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

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

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

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

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

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

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

布隆过滤器

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

图 4-4 显示了一个包含两个键和 16 位的布隆过滤器示例（实际上，它会包含更多的键和更多的位）。对于 SSTable 中的每个键，我们计算一个哈希函数，产生一组数字，然后将其解释为位数组的索引 14。我们将对应于这些索引的位设置为 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。这种看起来键存在但实际上不存在的情况称为 假阳性（false positive）。

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

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

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

压实策略

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

分层压实（Size-tiered compaction）
较新和较小的 SSTable 依次合并到较旧和较大的 SSTable 中。包含较旧数据的 SSTable 可能变得非常大，合并它们需要大量的临时磁盘空间。这种策略的优点是它可以处理非常高的写入吞吐量。
分级压实（Leveled compaction）
键范围被分成较小的 SSTable，较旧的数据被移动到单独的"级别"中，这允许压实更增量地进行，并且比分层策略使用更少的磁盘空间。这种策略对于读取比分层压实更有效，因为存储引擎需要读取更少的 SSTable 来检查它们是否包含该键。

作为经验法则，如果你主要有写入而读取很少，分层压实表现更好，而如果你的工作负载以读取为主，分级压实表现更好。如果你频繁写入少量键，而很少写入大量键，那么分级压实也可能有优势 18。

尽管有许多细微之处，但 LSM 树的基本思想 —— 保持在后台合并的 SSTable 级联 —— 简单而有效。我们将在 “比较 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 中，分支因子为六。实际上，分支因子取决于存储页引用和范围边界所需的空间量，但通常为几百。

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

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

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

这个算法确保树保持 平衡：具有 n 个键的 B 树始终具有 O(log n) 的深度。大多数数据库可以适合三或四层深的 B 树，所以你不需要跟随许多页引用来找到你要查找的页。（具有 500 分支因子的 4 KiB 页的四层树可以存储多达 250 TB。）

使 B 树可靠

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

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

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

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

B 树变体

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

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

比较 B 树与 LSM 树

作为经验法则，LSM 树更适合写入密集型应用，而 B 树对读取更快 27 28。然而，基准测试通常对工作负载的细节很敏感。你需要使用特定的工作负载测试系统，以便进行有效的比较。此外，这不是 LSM 和 B 树之间的严格二选一选择：存储引擎有时会混合两种方法的特征，例如具有多个 B 树并以 LSM 风格合并它们。在本节中，我们将简要讨论在衡量存储引擎性能时值得考虑的几件事。

读取性能

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

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

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

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

顺序与随机写入

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

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

SSD 上的顺序与随机写入

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

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

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

GC 消耗的写入带宽就不能用于应用程序。此外，GC 执行的额外写入会导致闪存磨损；因此，随机写入比顺序写入更快地磨损驱动器。

写放大

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

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

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

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

除了影响吞吐量，写放大也与 SSD 的磨损有关：写放大较低的存储引擎将更慢地磨损 SSD。

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

磁盘空间使用

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

碎片化在 LSM 树中不太成问题，因为压实过程无论如何都会定期重写数据文件，而且 SSTable 没有未使用空间的页。此外，SSTable 中的键值对块可以更好地压缩，因此通常比 B 树在磁盘上产生更小的文件。被覆盖的键和值继续消耗空间，直到它们被压实删除，但使用分级压实时，这种开销相当低 40 41。分层压实（参见 “压实策略”）使用更多的磁盘空间，特别是在压实期间临时使用。

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

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

多列索引与二级索引

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

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

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

在索引中存储值

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

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

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

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

全内存存储

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

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

一些内存键值存储，例如 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）数据库（在 “数据仓库” 中介绍）越来越多地成为两个独立的存储和查询引擎，它们恰好可以通过通用的 SQL 接口访问 50 51 52 53。

云数据仓库

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

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

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

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

列式存储

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

尽管事实表通常有超过 100 列，但典型的数据仓库查询一次只访问其中的 4 或 5 列（分析很少需要 "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 57 是一种列式存储格式，它支持基于 Google 的 Dremel 58 的文档数据模型，使用一种称为 分解（shredding）或 条带化（striping）的技术 59。

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

面向列的存储布局依赖于每列以相同顺序存储行。因此，如果你需要重新组装整行，你可以从每个单独的列中取出第 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 中每列的值序列：它们看起来经常重复，这是压缩的良好迹象。根据列中的数据，可以使用不同的压缩技术。在数据仓库中特别有效的一种技术是 位图编码，如 图 4-8 所示。

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

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

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

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

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 的所有用户 74。列式数据库还有各种其他压缩方案，你可以在参考文献中找到 75。

Note

不要将面向列的数据库与 宽列（也称为 列族）数据模型混淆，在该模型中，一行可以有数千列，并且不需要所有行都有相同的列 9。尽管名称相似，宽列数据库是面向行的，因为它们将一行中的所有值存储在一起。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 和许多其他系统都这样做 61 63 64 76。

查询执行：编译与向量化

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

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

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

查询编译
查询引擎获取 SQL 查询并生成用于执行它的代码。代码逐行迭代，查看感兴趣列中的值，执行所需的任何比较或计算，如果满足所需条件，则将必要的值复制到输出缓冲区。查询引擎将生成的代码编译为机器代码（通常使用现有编译器，如 LLVM），然后在已加载到内存中的列编码数据上运行它。这种代码生成方法类似于 Java 虚拟机（JVM）和类似运行时中使用的即时（JIT）编译方法。
向量化处理
查询被解释，而不是编译，但通过批量处理列中的许多值而不是逐行迭代来提高速度。一组固定的预定义算子内置在数据库中；我们可以向它们传递参数并获得一批结果 50 75。

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

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

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

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

物化视图与多维数据集

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

当基础数据更改时，物化视图需要相应更新。一些数据库可以自动执行此操作，还有像 Materialize 这样专门从事物化视图维护的系统 81。执行此类更新意味着写入时需要更多工作，但物化视图可以改善在重复需要执行相同查询的工作负载中的读取性能。

物化聚合 是一种可以在数据仓库中有用的物化视图类型。如前所述，数据仓库查询通常涉及聚合函数，例如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果许多不同的查询使用相同的聚合，每次都处理原始数据可能会很浪费。为什么不缓存查询最常使用的一些计数或总和？多维数据集 或 OLAP 立方体 通过创建按不同维度分组的聚合网格来做到这一点 82。图 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 树索引 83。更常见的是，使用专门的空间索引，如 R 树或 Bkd 树 84；它们划分空间，使附近的数据点倾向于分组在同一子树中。例如，PostGIS 使用 PostgreSQL 的通用搜索树索引设施将地理空间索引实现为 R 树 85。也可以使用规则间隔的三角形、正方形或六边形网格 86。

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

全文检索

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

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

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

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

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

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

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

向量嵌入

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

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

Note

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

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

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

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

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

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

平面索引（Flat indexes）
向量按原样存储在索引中。查询必须读取每个向量并测量其与查询向量的距离。平面索引是准确的，但测量查询与每个向量之间的距离很慢。
倒排文件（IVF）索引
向量空间被聚类为向量的分区（称为 质心），以减少必须比较的向量数量。IVF 索引比平面索引更快，但只能给出近似结果：即使查询和文档彼此接近，它们也可能落入不同的分区。对 IVF 索引的查询首先定义 探针，这只是要检查的分区数。使用更多探针的查询将更准确，但会更慢，因为必须比较更多向量。
分层可导航小世界（HNSW）
HNSW 索引维护向量空间的多个层，如 图 4-11 所示。每一层都表示为一个图，其中节点表示向量，边表示与附近向量的接近度。查询首先在最顶层定位最近的向量，该层具有少量节点。然后查询移动到下面一层的同一节点，并跟随该层中的边，该层连接更密集，寻找更接近查询向量的向量。该过程继续直到到达最后一层。与 IVF 索引一样，HNSW 索引是近似的。
图 4-11. 在 HNSW 索引中搜索最接近给定查询向量的数据库条目。

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

总结

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

“分析型与事务型系统” 介绍了事务处理（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. Archived at perma.cc/PBK3-F4G9 ↩︎

  2. Goetz Graefe. Modern B-Tree Techniques. Foundations and Trends in Databases, volume 3, issue 4, pages 203–402, August 2011. doi:10.1561/1900000028 ↩︎ ↩︎ ↩︎

  3. Evan Jones. Why databases use ordered indexes but programming uses hash tables. evanjones.ca, December 2019. Archived at perma.cc/NJX8-3ZZD ↩︎

  4. Branimir Lambov. CEP-25: Trie-indexed SSTable format. cwiki.apache.org, November 2022. Archived at perma.cc/HD7W-PW8U. Linked Google Doc archived at perma.cc/UL6C-AAAE ↩︎

  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009. ISBN: 978-0-262-53305-8 ↩︎ ↩︎ ↩︎

  6. Branimir Lambov. Trie Memtables in Cassandra. Proceedings of the VLDB Endowment, volume 15, issue 12, pages 3359–3371, August 2022. doi:10.14778/3554821.3554828 ↩︎

  7. Dhruba Borthakur. The History of RocksDB. rocksdb.blogspot.com, November 2013. Archived at perma.cc/Z7C5-JPSP ↩︎

  8. Matteo Bertozzi. Apache HBase I/O – HFile. blog.cloudera.com, June 2012. Archived at perma.cc/U9XH-L2KL ↩︎

  9. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A Distributed Storage System for Structured Data. At 7th USENIX Symposium on Operating System Design and Implementation (OSDI), November 2006. ↩︎ ↩︎

  10. Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, volume 33, issue 4, pages 351–385, June 1996. doi:10.1007/s002360050048 ↩︎

  11. Mendel Rosenblum and John K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, volume 10, issue 1, pages 26–52, February 1992. 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, and Matei Zaharia. Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores. Proceedings of the VLDB Endowment, volume 13, issue 12, pages 3411–3424, August 2020. doi:10.14778/3415478.3415560 ↩︎ ↩︎

  13. Burton H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, volume 13, issue 7, pages 422–426, July 1970. doi:10.1145/362686.362692 ↩︎

  14. Adam Kirsch and Michael Mitzenmacher. Less Hashing, Same Performance: Building a Better Bloom Filter. Random Structures & Algorithms, volume 33, issue 2, pages 187–218, September 2008. doi:10.1002/rsa.20208 ↩︎

  15. Thomas Hurst. Bloom Filter Calculator. hur.st, September 2023. Archived at perma.cc/L3AV-6VC2 ↩︎

  16. Chen Luo and Michael J. Carey. LSM-based storage techniques: a survey. The VLDB Journal, volume 29, pages 393–418, July 2019. doi:10.1007/s00778-019-00555-y ↩︎

  17. Subhadeep Sarkar and Manos Athanassoulis. Dissecting, Designing, and Optimizing LSM-based Data Stores. Tutorial at ACM International Conference on Management of Data (SIGMOD), June 2022. Slides archived at perma.cc/93B3-E827 ↩︎

  18. Mark Callaghan. Name that compaction algorithm. smalldatum.blogspot.com, August 2018. Archived at perma.cc/CN4M-82DY ↩︎

  19. Prashanth Rao. Embedded databases (1): The harmony of DuckDB, KùzuDB and LanceDB. thedataquarry.com, August 2023. Archived at perma.cc/PA28-2R35 ↩︎

  20. Hacker News discussion. Bluesky migrates to single-tenant SQLite. news.ycombinator.com, October 2023. Archived at perma.cc/69LM-5P6X ↩︎

  21. Rudolf Bayer and Edward M. McCreight. Organization and Maintenance of Large Ordered Indices. Boeing Scientific Research Laboratories, Mathematical and Information Sciences Laboratory, report no. 20, July 1970. doi:10.1145/1734663.1734671 ↩︎

  22. Douglas Comer. The Ubiquitous B-Tree. ACM Computing Surveys, volume 11, issue 2, pages 121–137, June 1979. doi:10.1145/356770.356776 ↩︎

  23. Alex Miller. Torn Write Detection and Protection. transactional.blog, April 2025. Archived at perma.cc/G7EB-33EW ↩︎

  24. C. Mohan and Frank Levine. ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. At ACM International Conference on Management of Data (SIGMOD), June 1992. doi:10.1145/130283.130338 ↩︎

  25. Hironobu Suzuki. The Internals of PostgreSQL. interdb.jp, 2017. ↩︎ ↩︎

  26. Howard Chu. LDAP at Lightning Speed. At Build Stuff ’14, November 2014. Archived at perma.cc/GB6Z-P8YH ↩︎

  27. Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, Radu Stoica, Stratos Idreos, Anastasia Ailamaki, and Mark Callaghan. Designing Access Methods: The RUM Conjecture. At 19th International Conference on Extending Database Technology (EDBT), March 2016. doi:10.5441/002/edbt.2016.42 ↩︎

  28. Ben Stopford. Log Structured Merge Trees. benstopford.com, February 2015. Archived at perma.cc/E5BV-KUJ6 ↩︎

  29. Mark Callaghan. The Advantages of an LSM vs a B-Tree. smalldatum.blogspot.co.uk, January 2016. Archived at perma.cc/3TYZ-EFUD ↩︎

  30. Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. At USENIX Annual Technical Conference, July 2019. ↩︎

  31. Igor Canadi, Siying Dong, Mark Callaghan, et al. RocksDB Tuning Guide. github.com, 2023. Archived at perma.cc/UNY4-MK6C ↩︎

  32. Gabriel Haas and 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, volume 16, issue 9, pages 2090-2102. doi:10.14778/3598581.3598584 ↩︎

  33. Emmanuel Goossaert. Coding for SSDs. codecapsule.com, February 2014. ↩︎

  34. Jack Vanlightly. Is sequential IO dead in the era of the NVMe drive? jack-vanlightly.com, May 2023. Archived at perma.cc/7TMZ-TAPU ↩︎

  35. Alibaba Cloud Storage Team. Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2). alibabacloud.com, January 2019. Archived at archive.org ↩︎

  36. Xiao-Yu Hu and Robert Haas. The Fundamental Limit of Flash Random Write Performance: Understanding, Analysis and Performance Modelling. dominoweb.draco.res.ibm.com, March 2010. Archived at perma.cc/8JUL-4ZDS ↩︎

  37. Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. WiscKey: Separating Keys from Values in SSD-conscious Storage. At 4th USENIX Conference on File and Storage Technologies (FAST), February 2016. ↩︎

  38. Peter Zaitsev. Innodb Double Write. percona.com, August 2006. Archived at perma.cc/NT4S-DK7T ↩︎

  39. Tomas Vondra. On the Impact of Full-Page Writes. 2ndquadrant.com, November 2016. Archived at perma.cc/7N6B-CVL3 ↩︎

  40. Mark Callaghan. Read, write & space amplification - B-Tree vs LSM. smalldatum.blogspot.com, November 2015. Archived at perma.cc/S487-WK5P ↩︎ ↩︎

  41. Mark Callaghan. Choosing Between Efficiency and Performance with RocksDB. At Code Mesh, November 2016. Video at youtube.com/watch?v=tgzkgZVXKB4 ↩︎

  42. Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. Enabling Timely and Persistent Deletion in LSM-Engines. ACM Transactions on Database Systems, volume 48, issue 3, article no. 8, August 2023. doi:10.1145/3599724 ↩︎

  43. Lukas Fittl. Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication. pganalyze.com, April 2025. Archived at perma.cc/XY6T-LTPX ↩︎

  44. Drew Silcock. How Postgres stores data on disk – this one’s a page turner. drew.silcock.dev, August 2024. Archived at perma.cc/8K7K-7VJ2 ↩︎

  45. Joe Webb. Using Covering Indexes to Improve Query Performance. simple-talk.com, September 2008. Archived at perma.cc/6MEZ-R5VR ↩︎

  46. Michael Stonebraker, Samuel Madden, Daniel J. Abadi, Stavros Harizopoulos, Nabil Hachem, and Pat Helland. The End of an Architectural Era (It’s Time for a Complete Rewrite). At 33rd International Conference on Very Large Data Bases (VLDB), September 2007. ↩︎

  47. VoltDB Technical Overview White Paper. VoltDB, 2017. Archived at perma.cc/B9SF-SK5G ↩︎

  48. Stephen M. Rumble, Ankita Kejriwal, and John K. Ousterhout. Log-Structured Memory for DRAM-Based Storage. At 12th USENIX Conference on File and Storage Technologies (FAST), February 2014. ↩︎

  49. Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. OLTP Through the Looking Glass, and What We Found There. At ACM International Conference on Management of Data (SIGMOD), June 2008. 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. Enhancements to SQL Server Column Stores. At ACM International Conference on Management of Data (SIGMOD), June 2013. doi:10.1145/2463676.2463708 ↩︎ ↩︎

  51. Franz Färber, Norman May, Wolfgang Lehner, Philipp Große, Ingo Müller, Hannes Rauhe, and Jonathan Dees. The SAP HANA Database – An Architecture Overview. IEEE Data Engineering Bulletin, volume 35, issue 1, pages 28–33, March 2012. ↩︎

  52. Michael Stonebraker. The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong. Presentation at EPFL, May 2013. ↩︎ ↩︎

  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. Cloud-Native Transactions and Analytics in SingleStore. At ACM International Conference on Management of Data (SIGMOD), June 2022. doi:10.1145/3514221.3526055 ↩︎

  54. Tino Tereshko and Jordan Tigani. BigQuery under the hood. cloud.google.com, January 2016. Archived at perma.cc/WP2Y-FUCF ↩︎

  55. Wes McKinney. The Road to Composable Data Systems: Thoughts on the Last 15 Years and the Future. wesmckinney.com, September 2023. Archived at 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: A Column-oriented DBMS. At 31st International Conference on Very Large Data Bases (VLDB), pages 553–564, September 2005. ↩︎

  57. Julien Le Dem. Dremel Made Simple with Parquet. blog.twitter.com, September 2013. ↩︎

  58. Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis. Dremel: Interactive Analysis of Web-Scale Datasets. At 36th International Conference on Very Large Data Bases (VLDB), pages 330–339, September 2010. doi:10.14778/1920841.1920886 ↩︎

  59. Joe Kearney. Understanding Record Shredding: storing nested data in columns. joekearney.co.uk, December 2016. Archived at perma.cc/ZD5N-AX5D ↩︎

  60. Jamie Brandon. A shallow survey of OLAP and HTAP query engines. scattered-thoughts.net, September 2023. Archived at perma.cc/L3KH-J4JF ↩︎ ↩︎

  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. The Snowflake Elastic Data Warehouse. At ACM International Conference on Management of Data (SIGMOD), pages 215–226, June 2016. doi:10.1145/2882903.2903741 ↩︎ ↩︎

  62. Mark Raasveldt and Hannes Mühleisen. Data Management for Data Science Towards Embedded Analytics. At 10th Conference on Innovative Data Systems Research (CIDR), January 2020. ↩︎

  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: Realtime OLAP for 530 Million Users. At ACM International Conference on Management of Data (SIGMOD), pages 583–594, May 2018. doi:10.1145/3183713.3190661 ↩︎ ↩︎

  64. Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino, and Deep Ganguli. Druid: A Real-time Analytical Data Store. At ACM International Conference on Management of Data (SIGMOD), June 2014. doi:10.1145/2588555.2595631 ↩︎ ↩︎

  65. Chunwei Liu, Anna Pavlenko, Matteo Interlandi, and Brandon Haynes. Deep Dive into Common Open Formats for Analytical DBMSs. Proceedings of the VLDB Endowment, volume 16, issue 11, pages 3044–3056, July 2023. doi:10.14778/3611479.3611507 ↩︎ ↩︎

  66. Xinyu Zeng, Yulong Hui, Jiahong Shen, Andrew Pavlo, Wes McKinney, and Huanchen Zhang. An Empirical Evaluation of Columnar Storage Formats. Proceedings of the VLDB Endowment, volume 17, issue 2, pages 148–161. doi:10.14778/3626292.3626298 ↩︎

  67. Weston Pace. Lance v2: A columnar container format for modern data. blog.lancedb.com, April 2024. Archived at perma.cc/ZK3Q-S9VJ ↩︎

  68. Yoav Helfman. Nimble, A New Columnar File Format. At VeloxCon, April 2024. ↩︎

  69. Wes McKinney. Apache Arrow: High-Performance Columnar Data Framework. At CMU Database Group – Vaccination Database Tech Talks, December 2021. ↩︎

  70. Wes McKinney. Python for Data Analysis, 3rd Edition. O’Reilly Media, August 2022. ISBN: 9781098104023 ↩︎

  71. Paul Dix. The Design of InfluxDB IOx: An In-Memory Columnar Database Written in Rust with Apache Arrow. At CMU Database Group – Vaccination Database Tech Talks, May 2021. ↩︎

  72. Carlota Soto and Mike Freedman. Building Columnar Compression for Large PostgreSQL Databases. timescale.com, March 2024. Archived at perma.cc/7KTF-V3EH ↩︎

  73. Daniel Lemire, Gregory Ssi‐Yan‐Kai, and Owen Kaser. Consistently faster and smaller compressed bitmaps with Roaring. Software: Practice and Experience, volume 46, issue 11, pages 1547–1569, November 2016. doi:10.1002/spe.2402 ↩︎

  74. Jaz Volpert. An entire Social Network in 1.6GB (GraphD Part 2). jazco.dev, April 2024. Archived at perma.cc/L27Z-QVMG ↩︎

  75. Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreos, and Samuel Madden. The Design and Implementation of Modern Column-Oriented Database Systems. Foundations and Trends in Databases, volume 5, issue 3, pages 197–280, December 2013. doi:10.1561/1900000024 ↩︎ ↩︎

  76. Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. The Vertica Analytic Database: C-Store 7 Years Later. Proceedings of the VLDB Endowment, volume 5, issue 12, pages 1790–1801, August 2012. doi:10.14778/2367502.2367518 ↩︎

  77. Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask. Proceedings of the VLDB Endowment, volume 11, issue 13, pages 2209–2222, September 2018. doi:10.14778/3275366.3284966 ↩︎ ↩︎

  78. Forrest Smith. Memory Bandwidth Napkin Math. forrestthewoods.com, February 2020. Archived at perma.cc/Y8U4-PS7N ↩︎

  79. Peter Boncz, Marcin Zukowski, and Niels Nes. MonetDB/X100: Hyper-Pipelining Query Execution. At 2nd Biennial Conference on Innovative Data Systems Research (CIDR), January 2005. ↩︎

  80. Jingren Zhou and Kenneth A. Ross. Implementing Database Operations Using SIMD Instructions. At ACM International Conference on Management of Data (SIGMOD), pages 145–156, June 2002. doi:10.1145/564691.564709 ↩︎

  81. Kevin Bartley. OLTP Queries: Transfer Expensive Workloads to Materialize. materialize.com, August 2024. Archived at perma.cc/4TYM-TYD8 ↩︎

  82. Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. Data Mining and Knowledge Discovery, volume 1, issue 1, pages 29–53, March 2007. doi:10.1023/A:1009726021843 ↩︎

  83. Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, and Rudolf Bayer. Integrating the UB-Tree into a Database System Kernel. At 26th International Conference on Very Large Data Bases (VLDB), September 2000. ↩︎

  84. Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, and Jeffrey Scott Vitter. Bkd-Tree: A Dynamic Scalable kd-Tree. At 8th International Symposium on Spatial and Temporal Databases (SSTD), pages 46–65, July 2003. doi:10.1007/978-3-540-45072-6_4 ↩︎

  85. Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. Generalized Search Trees for Database Systems. At 21st International Conference on Very Large Data Bases (VLDB), September 1995. ↩︎

  86. Isaac Brodsky. H3: Uber’s Hexagonal Hierarchical Spatial Index. eng.uber.com, June 2018. Archived at archive.org ↩︎

  87. Robert Escriva, Bernard Wong, and Emin Gün Sirer. HyperDex: A Distributed, Searchable Key-Value Store. At ACM SIGCOMM Conference, August 2012. doi:10.1145/2377677.2377681 ↩︎

  88. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN: 978-0-521-86571-5, available online at nlp.stanford.edu/IR-book ↩︎

  89. Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. An Experimental Study of Bitmap Compression vs. Inverted List Compression. At ACM International Conference on Management of Data (SIGMOD), pages 993–1008, May 2017. doi:10.1145/3035918.3064007 ↩︎

  90. Adrien Grand. What is in a Lucene Index? At Lucene/Solr Revolution, November 2013. Archived at perma.cc/Z7QN-GBYY ↩︎

  91. Michael McCandless. Visualizing Lucene’s Segment Merges. blog.mikemccandless.com, February 2011. Archived at perma.cc/3ZV8-72W6 ↩︎

  92. Lukas Fittl. Understanding Postgres GIN Indexes: The Good and the Bad. pganalyze.com, December 2021. Archived at perma.cc/V3MW-26H6 ↩︎

  93. Jimmy Angelakos. The State of (Full) Text Search in PostgreSQL 12. At FOSDEM, February 2020. Archived at perma.cc/J6US-3WZS ↩︎

  94. Alexander Korotkov. Index support for regular expression search. At PGConf.EU Prague, October 2012. Archived at perma.cc/5RFZ-ZKDQ ↩︎

  95. Michael McCandless. Lucene’s FuzzyQuery Is 100 Times Faster in 4.0. blog.mikemccandless.com, March 2011. Archived at perma.cc/E2WC-GHTW ↩︎

  96. Steffen Heinz, Justin Zobel, and Hugh E. Williams. Burst Tries: A Fast, Efficient Data Structure for String Keys. ACM Transactions on Information Systems, volume 20, issue 2, pages 192–223, April 2002. doi:10.1145/506309.506312 ↩︎

  97. Klaus U. Schulz and Stoyan Mihov. Fast String Correction with Levenshtein Automata. International Journal on Document Analysis and Recognition, volume 5, issue 1, pages 67–85, November 2002. doi:10.1007/s10032-002-0082-8 ↩︎

  98. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient Estimation of Word Representations in Vector Space. At International Conference on Learning Representations (ICLR), May 2013. doi:10.48550/arXiv.1301.3781 ↩︎

  99. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. At Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 1, pages 4171–4186, June 2019. doi:10.18653/v1/N19-1423 ↩︎

  100. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving Language Understanding by Generative Pre-Training. openai.com, June 2018. Archived at perma.cc/5N3C-DJ4C ↩︎

  101. Matthijs Douze, Maria Lomeli, and Lucas Hosseini. Faiss indexes. github.com, August 2024. Archived at perma.cc/2EWG-FPBS ↩︎

  102. Varik Matevosyan. Understanding pgvector’s HNSW Index Storage in Postgres. lantern.dev, August 2024. Archived at perma.cc/B2YB-JB59 ↩︎

  103. Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. At European Conference on Computer Vision (ECCV), pages 202–216, September 2018. doi:10.1007/978-3-030-01258-8_13 ↩︎

  104. Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 42, issue 4, pages 824–836, April 2020. doi:10.1109/TPAMI.2018.2889473 ↩︎

最后更新于
3. 数据模型与查询语言5. 编码与演化