4 存储与检索

人生的苦恼之一，就是每个人给事物起的名字总有那么一点不对。于是，世上的一切都变得比换个名字时更难理解。计算机最主要的用途，并不是通常所谓做算术的“计算”。[……] 它们主要是档案系统。
理查德・费曼， 特立独行的思考 研讨会（1985 年）

一个数据库在最基础的层次上需要完成两件事情：当你把数据交给数据库时，它应当把数据存储起来；而后当你向数据库要数据时，它应当把数据返回给你。

在第 3 章中，我们讨论了数据模型和查询语言，即你将数据交给数据库时采用的格式，以及日后向数据库取回数据时使用的接口。在本章中，我们会从数据库的视角来讨论同样的问题：数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。

作为应用开发者，为什么要关心数据库内部存储与检索的机理？你可能不会从头开始实现自己的 存储引擎（storage engine），但是你确实需要从许多可用的存储引擎中选择一个适合应用的。为了让存储引擎能在你的工作负载上运行良好，你也需要大致了解它在底层究竟做了什么。

尤其需要注意，针对事务型工作负载（OLTP）优化的存储引擎，与针对分析型工作负载优化的存储引擎之间存在巨大差异（这种区别已在 “分析型与事务型系统” 中介绍）。本章首先考察 OLTP 存储引擎的两大类：写出不可变数据文件的 日志结构（log-structured）存储引擎，以及像 B 树 这样就地更新数据的存储引擎。键值存储（key-value store）和 二级索引（secondary index）都可以采用这两类结构。

稍后在 “分析型数据存储” 中，我们会讨论一类针对分析优化的存储引擎；在 “多维索引与全文索引” 中，还会简要介绍用于文本检索等复杂查询的索引。

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 所做的事情类似，许多数据库在内部使用日志（log），也就是仅追加的数据文件。真正的数据库还要处理更多问题（例如并发写入、回收磁盘空间以免日志无限增长，以及崩溃恢复时处理只写了一部分的记录），但基本原理是一样的。日志极其有用，我们还会在本书中多次遇到它。

说明

日志这个词通常指应用日志，即应用程序输出的、描述正在发生之事的文本。本书在更普遍的意义上使用日志一词：磁盘上仅追加的记录序列。它不一定供人阅读，也可能采用二进制格式，只供数据库系统内部使用。

另一方面，如果数据库中有大量记录，db_get 函数的性能就会非常糟糕。每次查找一个键，db_get 都必须从头到尾扫描整个数据库文件，寻找这个键。用算法的语言来说，查找开销是 O(n)：如果数据库中的记录数 n 翻了一倍，查找时间也要翻一倍。这就不好了。

为了高效查找数据库中特定键的值，我们需要一种数据结构：索引（index）。本章将介绍一系列索引结构，并比较它们之间的差异。索引背后的大致思想，是以某种特定方式组织数据（例如按某个键排序），从而更快地定位想要的数据。如果想以几种不同的方式搜索同一份数据，那么也许需要在数据的不同部分建立多个索引。

索引是从主数据衍生出的额外结构。许多数据库允许添加和删除索引，这不会影响数据库的内容，只会影响查询性能。维护额外结构会产生开销，特别是在写入时。写入性能很难超过简单地向文件末尾追加，因为追加是最简单的写入操作。任何类型的索引通常都会拖慢写入速度，因为每次写入数据时还必须更新索引。

这是存储系统中一项重要的权衡：精心选择的索引能加快读查询，但每个索引都会占用额外的磁盘空间，并拖慢写入速度，有时影响还相当显著 ¹。因此，数据库通常不会默认索引所有内容，而是要求编写应用程序或管理数据库的人，根据自己对典型查询模式的了解手动选择索引。这样便可以选出给应用带来最大收益的索引，同时避免不必要的写入开销。

日志结构存储

首先假设你仍想把数据保存在 db_set 写入的仅追加文件中，只是希望加快读取速度。最简单的索引策略是保留一个内存中的哈希映射，其中每个键都映射到数据文件里的一个字节偏移量，指明该键最新的值位于何处，如图 4-1 所示。

每当向文件追加新的键值对时，还要更新哈希映射，使它指向刚刚写入的数据。查找一个值时，先用哈希映射找到日志文件中的偏移量，再寻道至该位置读取即可。如果数据文件的这一部分已经在文件系统缓存中，读取甚至完全不需要磁盘 I/O。

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

被新值覆盖的旧日志条目仍占着磁盘空间，始终得不到释放；只要继续写入数据库，磁盘空间迟早会耗尽。
哈希映射没有持久化，数据库重启时必须重建。例如，可以扫描整个日志文件，找出每个键最新的字节偏移量。如果数据量很大，重启就会十分缓慢。
哈希表必须能放进内存。原则上可以在磁盘上维护哈希表，可惜磁盘哈希表很难有良好的性能：它需要大量随机访问 I/O，装满后的扩容代价很高，而且解决哈希冲突需要烦琐的逻辑 ²。
范围查询效率不高。例如，无法轻松扫描 10000 到 19999 之间的所有键，只能在哈希映射中逐个查找。

SSTable 文件格式

实践中，数据库索引很少采用哈希表，更常见的做法是把数据保存在 按键排序 的结构中 ³。排序字符串表（Sorted String Table，简称 SSTable）便是一例，如图 4-2 所示。这种文件格式同样存储键值对，但保证键值对按键排序，而且每个键在文件中只出现一次。

这样便不必在内存中保留所有键。可以把 SSTable 中的键值对分成若干个几千字节大小的块（block），索引只存储每个块的第一个键。这种只收录部分键的索引称为 稀疏索引（sparse index）。索引保存在 SSTable 的一个独立区域中，可以采用不可变 B 树、字典树或其他能快速查找特定键的数据结构 ⁴。

以图 4-2 为例，一个块的第一个键是 handbag，下一个块的第一个键是 handsome。假设要查找没有出现在稀疏索引中的 handiwork。根据排序关系可知，handiwork 必定在 handbag 与 handsome 之间。因此，可以寻道至 handbag 的偏移量，再从那里开始扫描文件，直到找到 handiwork；如果一直扫到下一个块仍未找到，就说明文件中没有这个键。几千字节的数据块很快就能扫描完。

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

构建和合并 SSTable

SSTable 文件格式比仅追加日志更利于读取，却让写入变得困难。不能直接向文件末尾追加，否则文件就不再有序（除非键碰巧按升序写入）。如果每次在文件中间插入一个键都要重写整个 SSTable，写入成本又会高得无法接受。

解决办法是采用 日志结构 方法，将仅追加日志与排序文件结合起来：

收到写入时，将其加入内存中的有序映射数据结构，例如红黑树、跳表 ⁵ 或字典树 ⁶。这类数据结构可以按任意顺序插入键、高效查找键，并按排序顺序读出键。这个内存数据结构称为 内存表（memtable）。
当内存表超过某个阈值（通常为几兆字节）时，按排序顺序将它写成磁盘上的 SSTable 文件。这个新的 SSTable 文件称为数据库最新的段（segment），它与较旧的段分别存放在独立文件中，每个段都有自己的索引。向磁盘写出新段期间，数据库可以继续向新的内存表实例写入；SSTable 写完后，旧内存表占用的内存即可释放。
读取某个键的值时，先在内存表和磁盘上最新的段中查找。如果没有找到，就依次查看更旧的段，直到找到这个键或查完最旧的段。如果任何段中都没有这个键，它就不存在于数据库中。
后台不时运行合并与压实过程，将段文件合并起来，并丢弃已经覆盖或删除的值。

段的合并类似于 归并排序 算法 ⁵，如图 4-3 所示。并行读取各个输入文件，比较每个文件当前的第一个键，把排序最靠前的键复制到输出文件，然后不断重复。如果同一个键出现在多个输入文件中，只保留较新的值。这样生成的新段仍按键排序，每个键只保留一个值；由于可以逐键遍历 SSTable，整个过程只需要很少的内存。

为了避免数据库崩溃时丢失内存表中的数据，存储引擎还会在磁盘上保存一个单独的日志，每次写入都会立即追加到这个日志。日志不按键排序，但这并不重要，因为它的唯一用途是在崩溃后恢复内存表。每当内存表写成 SSTable 后，日志中相应的部分便可丢弃。

如果要删除一个键及其关联的值，必须向数据文件追加一种称为墓碑（tombstone）的特殊删除记录。日志段合并时，墓碑会指示合并过程丢弃这个键此前的所有值。墓碑一旦合并进最旧的段，自身也就可以删除。

这里描述的算法，本质上就是 RocksDB ⁷、Cassandra、ScyllaDB 和 HBase ⁸ 所采用的算法。这些系统都受 Google Bigtable 论文 ⁹ 的启发；SSTable 和 memtable 两个术语正是由该论文提出的。

这一算法最初发表于 1996 年，名为 日志结构合并树（Log-Structured Merge-Tree，简称 LSM 树）¹⁰，它建立在更早的日志结构文件系统研究之上 ¹¹。因此，凡是以合并、压实有序文件为基本原理的存储引擎，通常都称为 LSM 存储引擎。

在 LSM 存储引擎中，段文件会一次写完（或者由内存表写出，或者由若干现有段合并而成），此后便不可变。段的合并与压实可以由后台线程完成；在此期间，旧段文件仍可继续处理读取请求。合并完成后，读取请求切换到新的合并段，旧段文件即可删除。

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

段文件不可变，也让崩溃恢复变得更简单：如果写出内存表或合并段时发生崩溃，数据库只需删除未完成的 SSTable，再重新开始即可。用于持久化内存表写入的日志，可能因写到一半时崩溃或磁盘已满而留下不完整记录；通常可以借助日志中的校验和检测这些记录，并丢弃损坏或不完整的条目。我们将在第 8 章进一步讨论持久性与崩溃恢复。

布隆过滤器

在 LSM 存储中，读取很久以前才更新过的键，或读取根本不存在的键，可能十分缓慢，因为存储引擎必须检查多个段文件。为了加快这类读取，LSM 存储引擎通常会为每个段配备一个 布隆过滤器（Bloom filter）¹³，用来快速、近似地判断某个键是否出现在某个 SSTable 中。

图 4-4 展示了一个包含两个键、长度为 16 位的布隆过滤器（实际的键和位都会多得多）。对 SSTable 中的每个键计算哈希函数，会得到一组数字，再将这些数字解释为位数组中的下标 ¹⁴。把这些位置上的位设为 1，其余位保持为 0。例如，键 handbag 的哈希结果是 (2, 9, 4)，于是将第 2、9、4 位设为 1。得到的位图会与稀疏键索引一起存入 SSTable。它会占用一点额外空间，不过布隆过滤器通常远小于 SSTable 的其余部分。

图 4-4 布隆过滤器以概率方式快速判断某个键是否存在于某个 SSTable 中。

要判断某个键是否出现在 SSTable 中，只需对它计算同样的哈希，再检查对应下标处的位。例如，图 4-4 查询的是键 handheld，其哈希结果为 (6, 11, 2)。其中第 2 位为 1，另外两位为 0。所有 CPU 都支持的位运算可以极快地完成这些检查。

只要其中至少一位为 0，就能确定 SSTable 中绝对没有这个键。如果查询对应的位全为 1，这个键很可能在 SSTable 中，但也可能只是其他键碰巧把这些位全都设成了 1。这种看似存在、实际却不存在的情况称为 假阳性（false positive）。

假阳性的概率取决于键的数量、每个键设置多少位，以及布隆过滤器的总位数。可以借助在线计算器为应用选择合适的参数 ¹⁵。粗略地说，SSTable 中每个键分配 10 位布隆过滤器空间，假阳性概率约为 1%；此后每个键再多分配 5 位，概率就会降低一个数量级。

对 LSM 存储引擎来说，假阳性不会造成正确性问题：

如果布隆过滤器判断键 不存在，就可以放心跳过这个 SSTable，因为其中一定没有该键。
如果布隆过滤器判断键存在，还要查询稀疏索引、解码键值对块，确认键是否真的在其中。如果遇到假阳性，不过是多做了一点无用功，并无其他危害；继续搜索下一个更旧的段即可。

压实策略

LSM 存储的一项重要设计细节，是何时执行压实，以及每次压实应包含哪些 SSTable。许多基于 LSM 的存储系统都允许配置压实策略，常见选择包括 ¹⁶ ¹⁷：

按大小分层压实（size-tiered compaction）: 将较新、较小的 SSTable 逐步合并到较旧、较大的 SSTable 中。保存旧数据的 SSTable 可能变得非常大，合并时需要大量临时磁盘空间。这种策略的优点是能应对很高的写入吞吐量。
分级压实（leveled compaction）: 将键范围拆分到较小的 SSTable 中，并把较旧的数据移入不同的“层级”。这样可以更增量地进行压实，所需磁盘空间也少于按大小分层策略。分级压实的读取效率更高，因为存储引擎只需检查较少的 SSTable，就能判断其中是否含有所需的键。

根据经验，如果工作负载以写入为主、读取很少，按大小分层压实通常表现更好；如果读取占主导，分级压实通常更好。若少量键经常写入，而大量键很少写入，分级压实也可能更有优势 ¹⁸。

尽管其中有许多微妙之处，LSM 树的基本思想——保存一系列在后台合并的 SSTable——简单而有效。我们将在 “比较 B 树与 LSM 树” 中更详细地讨论其性能特征。

嵌入式存储引擎

许多数据库以服务形式运行，通过网络接收查询；但也有一些 嵌入式（embedded）数据库并不提供网络 API。它们是与应用代码运行在同一进程中的库，通常读写本地磁盘上的文件，应用则通过普通函数调用与之交互。RocksDB、SQLite、LMDB、DuckDB 和 KùzuDB 都是嵌入式存储引擎 ¹⁹。

嵌入式数据库在移动应用中十分常见，可用于保存本地用户的数据。在后端，如果数据小到单机足以容纳，并发事务又不多，嵌入式数据库也可能是合适的选择。例如在多租户系统中，如果每个租户的数据量都很小，且彼此完全隔离（即不需要查询多个租户的合并数据），就可以考虑为每个租户分别运行一个嵌入式数据库实例 ²⁰。

本章讨论的存储与检索方法，既适用于嵌入式数据库，也适用于客户端—服务器数据库。在第 6 章和第 7 章中，我们将讨论如何把数据库扩展到多台机器。

B 树

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

B 树自 1970 年问世 ²¹，不到 10 年就被称为“无处不在”²²，很好地经受住了时间的考验。时至今日，它仍然是几乎所有关系数据库中的标准索引实现，许多非关系数据库也使用 B 树。

与 SSTable 一样，B 树按键保存有序的键值对，因而能够高效地查找键值和执行范围查询。但相似之处也到此为止：B 树有着截然不同的设计理念。

前面看到的日志结构索引把数据库分成大小可变的段（segment），通常每段为几兆字节或更大；段只写入一次，此后便不可变。相比之下，B 树把数据库分成大小固定的块或页，并允许就地覆盖页。传统的页大小是 4 KiB，不过 PostgreSQL 目前默认使用 8 KiB，MySQL 默认使用 16 KiB。

每一页都有页号作为标识，因此一页可以引用另一页——类似于指针，只不过位于磁盘而非内存。如果所有页都保存在同一个文件中，页号乘以页大小，就是该页在文件中的字节偏移量。利用这些页引用可以构造一棵页组成的树，如图 4-5 所示。

图 4-5 使用 B 树索引查找键 251。先从根页沿引用进入键 200–300 所在的页，再进入键 250–270 所在的页。

其中一页被指定为 B 树的根（root）；在索引中查找键时，总是从这里开始。根页包含若干个键和对子页的引用。每个子页负责一段连续的键范围，引用之间的键标示出相邻范围的边界。（这种结构有时称为 B+ 树，不过这里不必把它与其他 B 树变体区分开来。）

在图 4-5 的例子中，我们要寻找键 251，因此沿着边界 200 与 300 之间的页引用向下走。接下来的一页结构相似，只是把 200–300 进一步划分成更小的子范围。最终会到达包含各个键的叶页（leaf page）；叶页或者直接保存每个键的值，或者保存指向值所在页的引用。

B 树一页中对子页的引用数称为 分支因子（branching factor）。例如，图 4-5 中的分支因子为 6。实践中的分支因子取决于页引用和范围边界所需的空间，不过通常可达几百。

如果要更新 B 树中已有键的值，就先找到包含该键的叶页，再用含有新值的版本覆盖磁盘上的这一页。如果要添加新键，则找到范围涵盖该键的页，并把键加入其中。如果页内没有足够的空闲空间容纳新键，就把它拆成两个半满的页，并更新父页，以反映键范围的新划分。

图 4-6 在边界键 337 处拆分页，使 B 树增长；父页也随之更新，以引用两个子页。

在图 4-6 中，我们想插入键 334，但负责 333–345 范围的页已经装满。于是把它拆成两页：一页负责 333–337（并包含新键），另一页负责 337–344。父页也必须更新，增加对两个子页的引用，并以 337 作为二者的边界。如果父页容不下新的引用，它也要拆分；这种拆分可能一路向上传播到树根。根页拆分时，则在其上方创建一个新根。删除键还可能需要合并节点，处理起来更加复杂 ⁵。

这个算法可以确保树始终平衡（balanced）：包含 n 个键的 B 树深度总是 O(log n)。大多数数据库只需要三四层深的 B 树，因此不必沿着很多页引用就能找到目标页。（一棵四层深、页大小为 4 KiB、分支因子为 500 的树，最多可以存储 250 TB 数据。）

使 B 树可靠

B 树最基本的底层写操作，是用新数据覆写磁盘上的页，并假定覆写不会改变页的位置：也就是说，页被覆写后，所有指向它的引用仍然有效。这与 LSM 树一类日志结构索引形成鲜明对比；后者只向文件追加写入（并最终删除过时文件），从不就地修改文件。

一次覆写多个页——例如拆分页时——是很危险的操作。如果数据库只写完其中一部分就崩溃，最终会留下损坏的树（例如出现不属于任何父页的 孤儿页，orphan page）。如果硬件不能原子地写入整页，还可能留下只写了一部分的页，这称为 页撕裂（torn page）²³。

为了让数据库能够从崩溃中恢复，B 树实现通常会在磁盘上维护一个额外的数据结构：预写日志（write-ahead log，WAL）。这是一个仅追加文件；对 B 树的每项修改，都必须先写入 WAL，才能应用到树本身的页上。数据库在崩溃后重新启动时，会用这个日志把 B 树恢复到一致状态 ² ²⁴。文件系统中的对应机制称为 日志机制（journaling）。

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

B 树变体

由于 B 树已经存在很久，多年来发展出了许多变体。这里只举几例：

一些数据库（如 LMDB）不覆写页，也不靠 WAL 进行崩溃恢复，而是采用写时复制方案 ²⁶。修改过的页写入新的位置，并为树中的父页创建新版本，使其指向新位置。这种方法对并发控制也很有用，我们将在 “快照隔离与可重复读” 中看到。
可以不存储完整的键，而只存储其缩写，以节省页内空间。尤其在树的内部页中，键只需包含足够的信息，能够充当键范围之间的边界即可。一页容纳的键越多，树的分支因子就越大，层数也越少。
为了加快按排序顺序扫描键范围，有些 B 树实现会尽量安排树的布局，使叶页在磁盘上也按顺序出现，从而减少磁盘寻道。不过随着树不断增长，这种顺序很难维持。
还可以向树中加入额外的指针。例如，让每个叶页引用左右相邻的兄弟页，便能按顺序扫描键，而不必反复跳回父页。

比较 B 树与 LSM 树

根据经验，LSM 树更适合写入密集型应用，而 B 树的读取通常更快 ²⁷ ²⁸。不过，基准测试结果往往对工作负载的细节非常敏感。只有使用自己的实际工作负载测试系统，比较才有意义。此外，LSM 树与 B 树并非严格的二选一：存储引擎有时会融合两种方法的特点，例如维护多棵 B 树，再用 LSM 风格将它们合并。本节将简要讨论衡量存储引擎性能时值得考虑的几个方面。

读取性能

在 B 树中查找键，需要在树的每一层读取一页。由于层数通常很少，B 树读取一般很快，性能也比较容易预测。LSM 存储引擎往往需要检查处于不同压实阶段的多个 SSTable，不过布隆过滤器能减少实际需要执行的磁盘 I/O 次数。两种方法都可能有良好表现；究竟哪种更快，取决于存储引擎的具体实现和工作负载。

B 树本身有序，因此范围查询简单而快速。LSM 存储也能利用 SSTable 的排序，但必须并行扫描所有段，再把结果合并起来。布隆过滤器对范围查询无能为力，因为不可能计算范围内每个潜在键的哈希；所以在 LSM 存储中，范围查询的成本高于点查询 ²⁹。

在日志结构存储引擎中，高写入吞吐量可能在内存表填满时引发延迟尖峰。如果数据来不及写入磁盘——或许因为压实速度赶不上新增写入——就会出现这种情况。包括 RocksDB 在内的许多存储引擎会在此时施加背压（backpressure）：暂停所有读写，直到内存表写入磁盘 ³⁰ ³¹。

至于读取吞吐量，现代 SSD（尤其是 NVMe）可以并行处理许多相互独立的读取请求。LSM 树和 B 树都能提供很高的读取吞吐量，但存储引擎必须经过精心设计，才能利用这种并行能力 ³²。

顺序与随机写入

使用 B 树时，如果应用写入的键散布在整个键空间，产生的磁盘操作也会四处分散，因为存储引擎要覆写的页可能位于磁盘任何位置。日志结构存储引擎则一次写出整个段文件——无论是把内存表写出，还是压实现有段——其大小远远超过 B 树中的一页。

这种数量多、规模小而位置分散的写入模式（如 B 树）称为 随机写入（random write）；数量少、规模较大的写入模式（如 LSM 树）则称为 顺序写入（sequential write）。磁盘的顺序写入吞吐量通常高于随机写入，因此在相同硬件上，日志结构存储引擎一般能承受比 B 树更高的写入吞吐量。这种差异在机械硬盘（HDD）上尤其显著；如今多数数据库使用固态硬盘（SSD），差距有所缩小，但依然不可忽略（参见 “SSD 上的顺序与随机写入”）。

SSD 上的顺序与随机写入

在机械硬盘（HDD）上，顺序写入远快于随机写入：随机写入必须把磁头机械地移到新位置，还要等待盘片上的目标区域转到磁头下方，耗时可达数毫秒——以计算机的时间尺度看，简直是一生。如今，SSD（固态硬盘）已经在许多场景中取代 HDD，其中也包括 NVMe（Non-Volatile Memory Express，即通过 PCI Express 总线连接的闪存）；它们没有这种机械限制。

尽管如此，SSD 的顺序写入吞吐量仍然高于随机写入。闪存每次可以读写一页（通常为 4 KiB），却只能按块擦除（通常为 512 KiB）。同一个块中，有些页可能仍保存有效数据，另一些页中的数据则已经无用。擦除整个块之前，控制器必须先把含有有效数据的页搬到其他块；这个过程称为 垃圾回收（GC）³³。

顺序写入每次写入更大块的数据，所以一个完整的 512 KiB 块很可能都属于同一个文件；日后删除这个文件时，可以直接擦除整个块，不必执行 GC。随机写入则更容易让一个块混杂有效页和无效页，因此在擦除块之前，GC 必须完成更多搬运工作 ³⁴ ³⁵ ³⁶。

GC 占用的写入带宽无法再供应用使用；而且 GC 带来的额外写入会加剧闪存磨损。因此，随机写入比顺序写入更快地损耗 SSD。

写放大

无论采用哪种存储引擎，应用发出的一次写请求都会转化为底层磁盘上的多次 I/O。对 LSM 树而言，一个值首先写入日志以确保持久性；内存表写入磁盘时又写一次；此后每次所在的键值对参与压实，还要再次写入。（如果值远大于键，可以把键和值分开存放，只压实包含键和值引用的 SSTable，以降低这项开销 ³⁷。）

B 树索引也必须把每份数据至少写两次：一次写入预写日志，一次写入树页本身。为了确保 B 树能在崩溃或断电后正确恢复，有时即使页内只有几个字节发生变化，也必须写出整页 ³⁸ ³⁹。

把某个工作负载实际写入磁盘的总字节数，除以不带索引、只写仅追加日志时所需的字节数，得到的比值就是 写放大（write amplification）。（写放大有时也按 I/O 操作次数而非字节数定义。）在写入密集型应用中，瓶颈可能是数据库向磁盘写入的速度。此时写放大越高，在有限磁盘带宽内每秒能处理的写入就越少。

LSM 树和 B 树都有写放大问题。孰优孰劣取决于许多因素，例如键和值的长度，以及覆盖现有键与插入新键各有多频繁。对典型工作负载而言，LSM 树往往具有更低的写放大，因为它不必写出整页，还可以压缩 SSTable 中的数据块 ⁴⁰。这也是 LSM 存储引擎适合写入密集型工作负载的原因之一。

写放大除了影响吞吐量，也关系到 SSD 的磨损：存储引擎的写放大越低，SSD 损耗得就越慢。

测量存储引擎的写入吞吐量时，实验必须运行足够长的时间，才能显现写放大的影响。刚开始向空 LSM 树写入时，压实尚未发生，全部磁盘带宽都可供新写入使用。随着数据库增长，新写入便不得不与压实共享磁盘带宽。

磁盘空间使用

B 树可能随着时间推移逐渐 碎片化。例如，删除大量键之后，数据库文件里可能留下许多 B 树不再使用的页。以后向 B 树添加数据时可以复用这些空闲页，但它们位于文件中间，很难归还给操作系统，所以仍会占用文件系统空间。因此，数据库需要后台进程搬移并重新整理这些页，例如 PostgreSQL 的清理（vacuum）进程 ²⁵。

碎片化对 LSM 树来说问题较小，因为压实过程本来就会定期重写数据文件，而且 SSTable 中不存在留有空闲空间的页。此外，SSTable 中的键值对块更便于压缩，所以生成的磁盘文件通常小于 B 树。已经覆盖的键和值会继续占用空间，直到在压实中移除；不过采用分级压实时，这项开销相当低 ⁴⁰ ⁴¹。按大小分层压实（参见 “压实策略”）会占用更多磁盘空间，尤其是在压实过程中临时占用的空间。

如果需要删除某些数据并确信它们确实已经消失——例如为了遵守数据保护法规——磁盘上并存的多份副本也会带来麻烦。在大多数 LSM 存储引擎中，已删除的记录仍可能留在较高层级，直到代表删除操作的墓碑传遍所有压实层级；这一过程可能持续很久。有些专门的存储引擎设计可以更快地传播删除操作 ⁴²。

另一方面，SSTable 段文件的不可变性很适合为数据库创建时间点快照（例如用于备份，或复制一份数据库进行测试）：只需写出内存表，再记下当时存在哪些段文件。只要不删除属于快照的文件，就完全不必实际复制它们。B 树会覆写页，因此很难如此高效地创建快照。

多列索引与二级索引

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

二级索引 也很常见。在关系数据库中，可以用 CREATE INDEX 命令在同一张表上创建多个二级索引，从而按主键以外的列进行搜索。例如，图 3-1（见第 3 章）中的各张表很可能都要在 user_id 列上建立二级索引，以便找出属于同一用户的所有行。

二级索引很容易用键值索引构建。主要区别在于，二级索引中的被索引值不一定唯一，也就是说，同一个索引条目下可能对应许多行（或文档、顶点）。有两种解决办法：把索引中的值做成匹配行标识符的列表（类似全文索引的倒排列表）；或者在每个索引项后附加行标识符，使它成为唯一项。B 树一类就地更新的存储引擎和日志结构存储都可以实现二级索引。

在索引中存储值

索引中的键是查询要搜索的内容，而值可以采用以下几种形式：

如果实际数据（行、文档或顶点）直接存储在索引结构中，这就是 聚簇索引。例如，MySQL 的 InnoDB 存储引擎总是把表的主键作为聚簇索引；SQL Server 则允许每张表指定一个聚簇索引 ⁴³。
另一种选择是让值引用实际数据：它可以是相应行的主键（InnoDB 的二级索引便是如此），也可以直接引用磁盘上的位置。后一种情况下，存放行的地方称为 堆文件（heap file）；堆文件中的数据没有特定顺序，可以是仅追加的，也可以记录已删除的行，以便日后用新数据覆写。例如，Postgres 就使用堆文件 ⁴⁴。
两者之间的折中称为 覆盖索引（covering index）或 包含列的索引（index with included columns）：完整的行仍保存在堆文件或主键聚簇索引中，但索引也会保存表的部分列 ⁴⁵。这样，一些查询只用索引就能得到答案，不必再解析主键或访问堆文件；此时称该索引覆盖了查询。覆盖索引可以加快某些查询，但重复数据会占用更多磁盘空间，也会拖慢写入。

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

更新值但不改变键时，只要新值不大于旧值，堆文件就能就地覆写记录。如果新值更大，情况会复杂一些：记录可能必须移到堆内空间足够的新位置。此时，要么更新所有索引，使其指向记录在堆中的新位置；要么在旧位置留下一个转发指针 ²。

全内存存储

本章到目前为止讨论的数据结构，都是对磁盘局限的应对。与主内存相比，磁盘处理起来很麻烦。无论是磁性硬盘还是 SSD，要想获得良好的读写性能，都必须仔细安排数据在磁盘上的布局。不过我们能容忍这种麻烦，是因为磁盘有两项显著优势：它是持久的（断电后内容不会丢失），而且每 GB 的成本低于 RAM。

随着 RAM 越来越便宜，磁盘的每 GB 成本优势正在减弱。许多数据集本来就没有那么大，因此完全可以把它们全部放进内存，必要时还可以分布到多台机器上。于是，内存数据库 发展了起来。

有些内存键值存储（如 Memcached）仅用于缓存，机器重启时丢失数据也无妨。但另一些内存数据库以持久性为目标，可以借助特殊硬件（如电池供电的 RAM）、把变更日志写入磁盘、定期把快照写入磁盘，或把内存状态复制到其他机器来实现。

内存数据库重启时，需要从磁盘或通过网络从副本重新加载状态（使用特殊硬件时除外）。它虽然写磁盘，却仍然属于内存数据库，因为磁盘只是用作确保持久性的仅追加日志，所有读取都由内存处理。写入磁盘还有运维上的好处：外部工具可以轻松备份、检查和分析磁盘上的文件。

VoltDB、SingleStore 和 Oracle TimesTen 等产品是采用关系模型的内存数据库。供应商宣称，省去管理磁盘数据结构的全部开销后，它们可以大幅提高性能 ⁴⁶ ⁴⁷。RAMCloud 则是一个具备持久性的开源内存键值存储，对内存和磁盘中的数据都采用日志结构方法 ⁴⁸。

Redis 和 Couchbase 通过异步写入磁盘提供弱持久性。

反直觉的是，内存数据库的性能优势并不来自省去了磁盘读取。如果内存足够，即便基于磁盘的存储引擎也可能从不真正读取磁盘，因为操作系统本来就会把最近使用的磁盘块缓存在内存中。内存数据库之所以更快，是因为它省去了把内存数据结构编码成可写入磁盘的形式这一开销 ⁴⁹。

除了性能之外，内存数据库还有一个有趣之处：它可以提供很难用磁盘索引实现的数据模型。例如，Redis 为优先队列、集合等各种数据结构提供了类似数据库的接口。由于所有数据都放在内存中，实现起来相对简单。

分析型数据存储

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

表面上，数据仓库与关系型 OLTP 数据库十分相似，因为二者都有 SQL 查询接口。然而，它们的内部实现可能大相径庭，因为两者针对的查询模式完全不同。如今，许多数据库供应商只专注于事务处理或分析工作负载中的一种，而非两者兼顾。

Microsoft SQL Server、SAP HANA 和 SingleStore 等数据库在同一产品中同时支持事务处理和数据仓库。不过，这些混合事务/分析处理（HTAP）数据库（已在 “数据仓库” 中介绍）正日益演变成两套彼此独立的存储与查询引擎，只是恰好通过同一个 SQL 接口访问 ⁵⁰ ⁵¹ ⁵² ⁵³。

云数据仓库

Teradata、Vertica 和 SAP HANA 等数据仓库供应商，既以商业许可证销售本地部署的数据仓库，也提供云端解决方案。随着越来越多的客户迁往云端，Google Cloud BigQuery、Amazon Redshift 和 Snowflake 等新一代云数据仓库也得到广泛采用。与传统数据仓库不同，云数据仓库会利用对象存储、无服务器计算平台等可伸缩的云基础设施。

云数据仓库通常能更好地集成其他云服务，也更具弹性。例如，许多云数据仓库支持自动摄取日志，并且可以轻松接入 Google Cloud Dataflow、Amazon Web Services Kinesis 等数据处理框架。它们把查询计算与存储层解耦，因此也更具弹性 ⁵⁴。数据持久保存在对象存储而非本地磁盘上，于是存储容量和查询计算资源可以分别调整，正如 “云原生系统架构” 所介绍的那样。

Apache Hive、Trino 和 Apache Spark 等开源数据仓库也随着云计算共同演进。分析数据存储迁入对象存储上的数据湖之后，开源数据仓库开始拆分、解耦 ⁵⁵。过去集成在 Apache Hive 这类单一系统中的功能，如今往往由以下独立组件实现：

查询引擎: Trino、Apache DataFusion 和 Presto 等查询引擎负责解析 SQL 查询，将其优化成执行计划，再针对数据执行。查询通常需要由分布式任务并行处理。有些查询引擎内置了任务执行能力，另一些则借助 Apache Spark 或 Apache Flink 等第三方执行框架。
存储格式: 存储格式规定如何把表中的行编码成文件里的字节；文件通常保存在对象存储或分布式文件系统中 ¹²。查询引擎可以访问这些数据，使用同一数据湖的其他应用也可以。Parquet、ORC、Lance 和 Nimble 都属于这类格式，下一节还会进一步介绍。
表格式: 以 Apache Parquet 等存储格式写出的文件通常不可变。为了支持插入和删除行，还要使用 Apache Iceberg 或 Databricks Delta 等表格式。表格式用一种文件格式来定义哪些文件构成一张表，以及这张表采用什么模式。它还可以提供时间旅行（查询表在过去某个时刻的状态）、垃圾回收乃至事务等高级功能。
数据目录: 正如表格式定义哪些文件组成一张表，数据目录定义哪些表组成一个数据库。目录用于创建、重命名和删除表。与存储格式和表格式不同，Snowflake Polaris、Databricks Unity Catalog 等数据目录通常作为独立服务运行，并通过 REST 接口接受查询。Apache Iceberg 也提供目录，既可以嵌入客户端运行，也可以作为独立进程运行。查询引擎读写表时会使用目录信息。传统上，目录与查询引擎集成在一起；将二者解耦之后，数据发现和数据治理系统（见 “数据系统、法律与社会”）也可以访问目录中的元数据。

列式存储

正如 “星型与雪花型：分析模式” 所述，数据仓库通常采用关系模式：一张巨大的事实表通过外键引用各张维度表。如果事实表有数万亿行、数 PB 数据，如何高效存储和查询就成了严峻挑战。维度表通常小得多（只有数百万行），所以本节将重点讨论事实表的存储。

尽管事实表通常有 100 多列，但典型的数据仓库查询一次只访问其中 4、5 列（分析查询很少需要 "SELECT *"）⁵²。以示例 4-1 为例：它会访问大量行（2024 年中每一笔水果或糖果销售记录），却只需要 fact_sales 表中的三列：date_key、product_sk 和 quantity。其他所有列都被查询忽略了。

示例 4-1 分析人们在一周中的哪一天更倾向于购买新鲜水果或糖果

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

怎样才能高效执行这个查询？

大多数 OLTP 数据库都以 面向行（row-oriented）的方式布置存储：表中同一行的所有值相邻存放。文档数据库也很相似，通常把整个文档存成一段连续的字节序列。图 4-1 的 CSV 示例就是如此。

为了处理示例 4-1 这样的查询，可以在 fact_sales.date_key 和（或）fact_sales.product_sk 上建立索引，告诉存储引擎去哪里寻找某一天或某种产品的所有销售记录。但面向行的存储引擎仍要把这些完整的行（每行有 100 多个属性）从磁盘载入内存，逐一解析，再过滤掉不满足条件的行。这个过程可能十分耗时。

面向列（column-oriented，或列式，columnar）存储背后的想法很简单：不要把同一行中的所有值放在一起，而要把同一列中的所有值放在一起 ⁵⁶。每列分别存储后，查询只需读取和解析自己用到的列，能省下大量工作。图 4-7 用图 3-5 中事实表的扩展版本展示了这一原理。

说明

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

面向列的存储布局要求每一列都按相同的行顺序保存数据。因此，要重新拼出完整的一行，可以分别取出每列中的第 23 项，把它们组合成表的第 23 行。

实际上，列式存储引擎并不会把完整的一列（可能有数万亿行）一次存放在一起。它会把表切成若干个包含数千乃至数百万行的数据块，再在每个块内分别保存各列的值 ⁶⁰。许多查询只关注特定日期范围，因此常让每个块包含某个时间戳范围内的行。查询只需在与目标日期范围重叠的块中，加载自己需要的列。

如今，几乎所有分析数据库都采用列式存储 ⁶⁰：从 Snowflake ⁶¹ 这样的大型云数据仓库，到 DuckDB ⁶² 这样的单节点嵌入式数据库，再到 Pinot ⁶³、Druid ⁶⁴ 等产品分析系统。Parquet、ORC ⁶⁵ ⁶⁶、Lance ⁶⁷ 和 Nimble ⁶⁸ 等存储格式，以及 Apache Arrow ⁶⁵ ⁶⁹、pandas/NumPy ⁷⁰ 等内存分析格式，也都采用列式布局。InfluxDB IOx ⁷¹、TimescaleDB ⁷² 等时间序列数据库同样以列式存储为基础。

列压缩

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

看看图 4-7 中各列的值序列：它们往往相当重复，这是很适合压缩的信号。根据列中数据的不同，可以选用不同的压缩技术。其中对数据仓库特别有效的一种是 位图编码，如图 4-8 所示。

通常，一列中不同值的数量远小于总行数（例如，零售商可能有数十亿笔销售交易，却只有 100,000 种产品）。可以把一个具有 n 个不同值的列转换成 n 张独立位图：每个不同值对应一张位图，每一行对应其中一位。如果该行取这个值，对应位就是 1，否则为 0。

一种选择是按每行一位直接存储这些位图。不过，位图中通常有大量的 0，也就是十分稀疏。这时还可以使用游程编码：统计连续出现的 0 或 1 的数量，并存下这个数字，如图 4-8 底部所示。Roaring 位图会在两种位图表示之间切换，总是选用更紧凑的一种 ⁷³。这样可以极其高效地编码一整列。

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

WHERE product_sk IN (31, 68, 69):: 加载 product_sk = 31、product_sk = 68 和 product_sk = 69 对应的三张位图，再计算三者的按位或，这个操作可以非常高效地完成。
WHERE product_sk = 30 AND store_sk = 3:: 加载 product_sk = 30 和 store_sk = 3 对应的位图，再计算按位与。之所以可行，是因为各列中的行顺序相同：一列位图中的第 k 位，与另一列位图中的第 k 位对应同一行。

位图也可以回答图查询，例如找出社交网络中所有“被用户 X 关注、同时又关注用户 Y”的用户 ⁷⁴。列式数据库还有许多其他压缩方案，参见参考文献 ⁷⁵。

说明

不要把列式数据库与宽列（wide-column，又称列族，column-family）数据模型混为一谈。宽列模型的一行可以有数千列，各行也不必拥有相同的列 ⁹。尽管名字相似，宽列数据库其实是面向行的，因为它会把同一行的所有值存放在一起。Google Bigtable、Apache Accumulo 和 HBase 都属于宽列模型。

列存储中的排序顺序

在列式存储中，行的存储顺序并不一定重要。最简单的方式是按插入顺序存放，因为插入新行时只需向每一列追加数据。不过，也可以像此前处理 SSTable 那样，为数据指定某种顺序，并把这种顺序用作索引机制。

注意，分别对每一列独立排序毫无意义，因为那样就再也不知道不同列中的哪些项属于同一行。我们之所以能够重建一行，正是因为一列中的第 k 项与另一列中的第 k 项属于同一行。

因此，即使数据按列存储，排序也必须以整行为单位。数据库管理员可以根据自己对常见查询的了解，选择表按哪些列排序。例如，如果查询经常针对“上个月”这样的日期范围，就可以把 date_key 作为第一个排序键。这样查询只需扫描上个月的行，比扫描所有行快得多。

对于第一排序列中取值相同的行，可以用第二列进一步决定顺序。例如，如果图 4-7 以 date_key 为第一排序键，那么把 product_sk 作为第二排序键或许很有用：同一天、同一种产品的所有销售记录就会在存储中相邻。这有利于在特定日期范围内按产品分组或筛选销售记录的查询。

排序的另一个好处是有助于列压缩。如果主排序列没有太多不同的值，排序后会形成很长的连续序列，同一个值反复出现。使用简单的游程编码——就像图 4-8 中的位图一样——即可把这一列压缩到几千字节，即使表中有数十亿行也不例外。

这种压缩效果在第一排序键上最强。第二、第三排序键会更加杂乱，不会出现那么长的重复值序列。排序优先级更低的列基本呈随机顺序，压缩效果可能不佳。不过，只要前几列经过排序，整体上依然受益。

写入列式存储

我们在 “事务处理与分析的特征” 中看到，数据仓库的读取通常要聚合大量行；列式存储、压缩和排序都能加快这类读查询。数据仓库的写入则往往是批量导入数据，通常通过 ETL 流程完成。

对列式存储而言，在有序表的中间插入单独一行非常低效，因为从插入位置开始，所有压缩列都必须重写。但一次批量写入很多行，可以分摊重写这些列的成本，因而效率很高。

批量写入通常采用日志结构方法。所有写入先进入一个面向行、有序的内存存储。积累足够多的写入后，再与磁盘上的列编码文件合并，并成批写入新文件。旧文件保持不可变，新文件一次写成，所以对象存储很适合保存这些文件。

查询必须同时检查磁盘上的列数据和内存中的近期写入，再把两部分结果合并起来。查询执行引擎会向用户隐藏这项区别。在分析师看来，插入、更新或删除的数据会立刻反映在后续查询中。Snowflake、Vertica、Apache Pinot、Apache Druid 等许多系统都是这样做的 ⁶¹ ⁶³ ⁶⁴ ⁷⁶。

查询执行：编译与向量化

复杂的分析型 SQL 查询会被分解成一个 查询计划（query plan），其中包含多个称为算子（operator）的执行阶段；这些算子可能分布到多台机器上并行执行。查询规划器可以决定选用哪些算子、以什么顺序执行，以及每个算子在哪里运行，从而完成大量优化。

在每个算子内部，查询引擎都要对列中的值执行各种操作，例如找出值属于某个集合的所有行（或许是连接的一部分），或者判断值是否大于 15。查询引擎还要同时查看同一行的多个列，例如找出产品是香蕉、门店又恰好是目标门店的所有销售记录。

数据仓库查询需要扫描数百万行，因此不仅要关注从磁盘读取的数据量，还要关注执行复杂算子所需的 CPU 时间。最简单的算子就像编程语言解释器：遍历每一行时，查看表示查询的数据结构，弄清要对哪些列做什么比较或计算。遗憾的是，这种方式对许多分析场景来说太慢。实践中出现了两种高效执行查询的方法 ⁷⁷：

查询编译（query compilation）: 查询引擎根据 SQL 查询生成执行代码。代码逐行迭代，读取相关列中的值，完成所需的比较或计算；如果条件满足，就把必要的值复制到输出缓冲区。随后，查询引擎把生成的代码编译成机器码（往往借助 LLVM 等现有编译器），再对已经载入内存的列编码数据运行。这种代码生成方式类似 Java 虚拟机（JVM）等运行时采用的即时（JIT）编译。
向量化处理（vectorized processing）: 查询仍然采用解释执行，而非编译执行；但它不再逐行迭代，而是成批处理一列中的许多值，从而提高速度。数据库内置一组固定的预定义算子，向算子传入参数，就会得到一批结果 ⁵⁰ ⁷⁵。

例如，把 product_sk 列和“香蕉”的 ID 传给相等比较算子，会得到一张位图：输入列的每个值对应一位，是香蕉则为 1。再把 store_sk 列和目标门店的 ID 传给同一个算子，得到另一张位图。最后把两张位图传给“按位与”算子，如图 4-9 所示。结果位图中，特定门店售出的每一笔香蕉都对应一个 1。

这两种方法的实现大不相同，但都已投入实际使用 ⁷⁷。它们都能利用现代 CPU 的特点，获得优异性能：

优先顺序访问内存而非随机访问，减少缓存未命中 ⁷⁸；
把大部分工作放在紧凑的内层循环中（指令少且没有函数调用），使 CPU 指令流水线保持忙碌，并避免分支预测错误；
利用多线程和单指令多数据（SIMD）指令等并行机制 ⁷⁹ ⁸⁰；
直接处理压缩数据，不先解码成另一种内存表示，从而省去内存分配和复制的成本。

物化视图与多维数据集

我们曾在 “时间线的物化与更新” 中遇到 物化视图（materialized view）。在关系数据模型中，它是一种类似表的对象，内容是某个查询的结果。物化视图是实际写入磁盘的查询结果副本，而虚拟视图只是编写查询的快捷方式。从虚拟视图读取时，SQL 引擎会即时把它展开成底层查询，再处理展开后的查询。

底层数据变化时，物化视图也必须随之更新。有些数据库可以自动完成这项工作，Materialize 等系统则专门负责维护物化视图 ⁸¹。更新视图会增加写入工作量，但如果工作负载反复执行相同查询，物化视图可以改善读取性能。

物化聚合（materialized aggregate）是一类对数据仓库很有用的物化视图。如前所述，数据仓库查询经常使用 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX 等聚合函数。如果许多查询都使用相同的聚合，每次重新处理原始数据就太浪费了，何不把最常用的计数或总和缓存起来？多维数据集（data cube，或 OLAP 多维数据集，OLAP cube）会创建一个按不同维度分组的聚合网格，正是为了实现这种缓存 ⁸²。图 4-10 展示了一个例子。

暂且假设每条事实记录只外键引用两张维度表——图 4-10 中是 date_key 和 product_sk。这样可以画出一张二维表，一条轴表示日期，另一条轴表示产品。每个单元格保存具有相应“日期—产品”组合的所有事实记录中，某项属性（如 net_price）的聚合值（如 SUM）。再沿每一行或每一列应用同样的聚合，就能得到减少一个维度的汇总结果：不考虑日期的产品销售额，或者不考虑产品的逐日销售额。

一般而言，事实往往不止两个维度。图 3-5 中就有日期、产品、门店、促销和客户五个维度。五维超立方体很难想象，但原理仍然一样：每个单元格保存特定“日期—产品—门店—促销—客户”组合的销售额，随后可以沿每个维度反复汇总这些值。

物化多维数据集的优点，是某些查询会变得非常快，因为结果实际上已经预先计算好了。例如，要知道昨天每家门店的总销售额，只需查看相应维度上的汇总值，不必扫描数百万行。

缺点是多维数据集不如直接查询原始数据灵活。例如，价格不是其中一个维度，就无法计算有多大比例的销售额来自售价超过 100 美元的商品。因此，大多数数据仓库会尽可能保留原始数据，只把多维数据集等聚合用作某些查询的性能优化手段。

多维索引与全文索引

本章前半部分介绍的 B 树和 LSM 树，可以对单个属性执行范围查询。例如，如果键是用户名，就能用它们建立索引，高效找出所有以 L 开头的名字。但有时，只按一个属性搜索并不够用。

最常见的多列索引称为 联合索引（concatenated index）。它把一列接在另一列之后，将多个字段组合成一个键；字段的连接顺序由索引定义指定。这就像老式纸质电话簿提供的索引：从（姓、名）映射到电话号码。由于索引按这个顺序排列，可以找出某个姓氏对应的所有人，也可以找出特定 姓—名 组合对应的所有人。但如果只想查找某个名字对应的所有人，这个索引就毫无用处。

多维索引（multidimensional index）则允许同时查询多个列，这对地理空间数据尤其重要。例如，餐厅搜索网站的数据库可能保存了每家餐厅的经纬度。用户查看地图时，网站需要找出当前矩形地图区域内的所有餐厅。这就需要下面这样的二维范围查询：

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

在纬度和经度列上建立联合索引，无法高效回答这个查询：它只能返回某一纬度范围内的所有餐厅（经度任意），或者某一经度范围内的所有餐厅（纬度可以是南北两极之间的任意位置），却无法同时约束两者。

一种办法是使用空间填充曲线把二维位置转换成单个数字，再建立普通的 B 树索引 ⁸³。更常见的做法是使用 R 树、Bkd 树 ⁸⁴ 等专门的空间索引；它们对空间进行划分，让邻近的数据点尽量落在同一棵子树中。例如，PostGIS 使用 PostgreSQL 的通用搜索树索引设施，以 R 树实现地理空间索引 ⁸⁵。另一种选择是使用规则排布的三角形、正方形或六边形网格 ⁸⁶。

多维索引并不只用于地理位置。例如，电子商务网站可以在（红、绿、蓝）三个维度上建立索引，以搜索特定颜色范围内的产品；天气观测数据库也可以在（日期、温度）上建立二维索引，高效找出 2013 年中温度介于 25～30℃ 的所有观测记录。使用一维索引，要么必须扫描 2013 年的所有记录（不考虑温度）再按温度筛选，要么反过来处理。二维索引则可以同时按时间戳和温度缩小结果范围 ⁸⁷。

全文检索

全文检索（full-text search）允许按关键词搜索一组文本文档（网页、产品描述等），关键词可以出现在文本中的任意位置 ⁸⁸。信息检索是一门庞大而专门的学科，往往还要针对具体语言进行处理。例如，一些亚洲语言书写时不会在词与词之间添加空格或标点，因此把文本切分成词需要借助模型，判断哪些字符序列构成一个词。全文检索还经常需要匹配相似但不完全相同的词（例如拼写错误或同一个词的不同语法形式），以及同义词。这些问题都超出了本书的范围。

不过从核心原理看，全文检索也可以视为一种多维查询：文本中可能出现的每个词（即一个词项，term）都是一个维度。包含词项 x 的文档在维度 x 上取值为 1，不包含 x 则取值为 0。搜索提到“红苹果”的文档，就是同时寻找红维度和苹果维度都为 1 的文档。这样一来，维度数可能非常庞大。

许多搜索引擎使用 倒排索引（inverted index）回答这类查询。它是一种键值结构：键是词项，值是所有包含该词项的文档 ID 列表，即 倒排列表（postings list）。如果文档 ID 是连续数字，倒排列表也可以表示成图 4-8 那样的稀疏位图：如果 ID 为 n 的文档包含词项 x，那么词项 x 的位图中第 n 位就是 1 ⁸⁹。

现在，查找同时包含词项 x 和 y 的所有文档，就类似于用向量化数据仓库查询寻找满足两个条件的行（图 4-9）：载入 x 和 y 对应的两张位图，再计算按位与。即使位图经过游程编码，这个操作也可以高效完成。

Elasticsearch 和 Solr 使用的全文索引引擎 Lucene 就采用这种方法 ⁹⁰。它把从词项到倒排列表的映射保存在类似 SSTable 的有序文件中，再使用本章前面介绍的日志结构方法，在后台合并这些文件 ⁹¹。PostgreSQL 的 GIN 索引也通过倒排列表支持全文检索，以及 JSON 文档内部的索引 ⁹² ⁹³。

除了把文本切分成词，还可以找出所有长度为 n 的子串，称为 n-gram。例如，字符串 "hello" 的 3-gram（n = 3）是 "hel"、"ell" 和 "llo"。如果为所有 3-gram 建立倒排索引，就能搜索任意长度至少为三个字符的子串。这样的索引甚至支持在搜索查询中使用正则表达式，缺点是体积相当大 ⁹⁴。

为了应对文档或查询中的拼写错误，Lucene 可以搜索与目标词相差一定编辑距离的词（编辑距离为 1，表示增加、删除或替换了一个字母）⁹⁵。它把词项集合存储成一个以键中字符为边的有限状态自动机，结构类似 字典树（trie）⁹⁶；再将其转换成 莱文斯坦自动机（Levenshtein automaton），从而高效搜索给定编辑距离以内的词 ⁹⁷。

向量嵌入

语义搜索不只处理同义词和拼写错误，还试图理解文档表达的概念和用户的意图。例如，帮助中心有一页标题是“取消订阅”，那么用户搜索“如何关闭账户”或“终止合同”时也应当找到它：这些说法用词完全不同，意思却十分接近。

为了理解文档的语义，也就是它表达的含义，语义搜索索引会使用嵌入模型，把文档转换成由浮点数组成的向量，称为 向量嵌入（vector embedding）。这个向量表示多维空间中的一个点，每个浮点数表示文档在某一维坐标轴上的位置。如果输入文档的语义相似，嵌入模型就会生成在多维空间中彼此接近的向量。

说明

我们在 “查询执行：编译与向量化” 中见过 向量化处理 一词。语义搜索中的“向量”含义不同：向量化处理所说的向量，是一批可以用专门优化的代码处理的比特；嵌入模型所说的向量，则是一列浮点数，用来表示多维空间中的位置。

例如，一篇介绍农业的维基百科页面，其三维向量嵌入可能是 [0.1, 0.22, 0.11]。介绍蔬菜的页面应该离它很近，向量或许是 [0.13, 0.19, 0.24]。介绍星型模式的页面则可能得到 [0.82, 0.39, -0.74]，距离相对很远。只看数字也能发现，前两个向量比第三个更接近。

实际的嵌入模型使用大得多的向量，往往包含 1,000 多个数字，但原理相同。我们不会试图理解每个数字各自代表什么；它们只是嵌入模型用来指向抽象多维空间中某个位置的方式。搜索引擎通过余弦相似度、欧几里得距离等距离函数衡量向量间的距离。余弦相似度计算两个向量夹角的余弦，判断它们有多接近；欧几里得距离则计算空间中两点间的直线距离。

Word2Vec ⁹⁸、BERT ⁹⁹ 和 GPT ¹⁰⁰ 等许多早期嵌入模型都处理文本数据，通常以神经网络实现。后来，研究者又为视频、音频和图像创建了嵌入模型。近来，模型架构进一步走向 多模态（multimodal）：同一个模型可以为文本、图像等多种模态生成向量嵌入。

用户输入查询时，语义搜索引擎会把查询及其相关上下文（例如用户位置）交给嵌入模型，生成查询的向量嵌入。随后，搜索引擎还必须通过向量索引，找出向量嵌入与查询相似的文档。

向量索引保存一组文档的向量嵌入。查询时传入查询本身的向量嵌入，索引会返回向量最接近查询向量的文档。前面介绍的 R 树不适合维度很高的向量，因此需要专门的向量索引，例如：

平面索引（Flat indexes）: 向量原样保存在索引中。查询必须读取每个向量，并测量它与查询向量的距离。平面索引结果精确，但逐一计算查询与每个向量的距离很慢。
倒排文件（IVF）索引: 把向量空间聚类成若干向量分区，以减少必须比较的向量数；这些分区称为质心（centroid）。IVF 索引比平面索引更快，却只能给出近似结果：查询向量和某个文档向量可能十分接近，却恰好落入不同分区。查询 IVF 索引时，首先要指定 探测数（probes），也就是需要检查多少个分区。探测数越大，查询越准确，但也越慢，因为必须比较更多向量。
分层可导航小世界（HNSW）: HNSW 索引维护向量空间的多个层级，如图 4-11 所示。每层都表示成一张图：节点代表向量，边表示向量彼此接近。查询先在节点很少的最顶层找到最近向量，再进入下一层的同一节点；下一层连接更密集，查询沿边寻找更接近查询向量的向量。这个过程不断重复，直至最底层。与 IVF 一样，HNSW 也是近似索引。

许多流行的向量数据库都实现了 IVF 和 HNSW 索引。Facebook 的 Faiss 库为两者提供了许多变体 ¹⁰¹，PostgreSQL 的 pgvector 也同时支持这两种索引 ¹⁰²。IVF 和 HNSW 算法的完整细节超出了本书范围，不过介绍它们的论文是很好的参考资料 ¹⁰³ ¹⁰⁴。

总结

在本章中，我们试图深入了解数据库是如何处理存储与检索的。把数据存入数据库时会发生什么？日后再次查询这些数据时，数据库又会做什么？

“分析型与事务型系统” 介绍了事务处理（OLTP）与分析（OLAP）的区别。本章进一步看到，针对 OLTP 优化的存储引擎，与针对分析优化的存储引擎大不相同：

OLTP 系统针对大量请求优化；每个请求只读写少量记录，并且需要迅速响应。记录通常通过主键或二级索引访问，这些索引一般是从键到记录的有序映射，也支持范围查询。
数据仓库等分析型系统，针对需要扫描大量记录的复杂读查询优化。它们通常采用经过压缩的列式存储布局，尽可能减少查询要从磁盘读取的数据量；并通过查询的即时编译或向量化，尽可能减少处理数据所耗费的 CPU 时间。

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

日志结构学派只允许向文件追加数据和删除过时文件，从不更新已经写出的文件。SSTable、LSM 树、RocksDB、Cassandra、HBase、ScyllaDB、Lucene 等都属于这一类。一般而言，日志结构存储引擎能提供很高的写入吞吐量。
就地更新学派把磁盘视为一组大小固定、可以覆写的页。B 树是这种理念最典型的代表，所有主流关系型 OLTP 数据库和许多非关系数据库都使用它。根据经验，B 树通常更适合读取，其读取吞吐量高于日志结构存储，响应时间也更短。

随后，我们考察了能够同时搜索多个条件的索引：R 树等多维索引可以同时按经度和纬度搜索地图上的点；全文检索索引则可以搜索同一段文本中出现的多个关键词。最后，向量数据库用于对文本文档及其他媒体进行语义搜索；它把数据表示成高维向量，再通过比较向量相似度找出相似文档。

作为应用开发者，如果掌握了这些有关存储引擎内部机制的知识，就能更好地判断哪种工具最适合自己的应用。需要调整数据库的调优参数时，这种理解也让你能够设想参数调高或调低会产生怎样的影响。

尽管本章无法让你成为某一种存储引擎的调优专家，但希望它已经提供了足够的概念和词汇，让你能够读懂自己所选数据库的文档。

参考文献

Nikolay Samokhvalov. How partial, covering, and multicolumn indexes may slow down UPDATEs in PostgreSQL. postgres.ai, October 2021. Archived at perma.cc/PBK3-F4G9 ↩︎
Goetz Graefe. Modern B-Tree Techniques. Foundations and Trends in Databases, volume 3, issue 4, pages 203–402, August 2011. doi:10.1561/1900000028 ↩︎ ↩︎ ↩︎
Evan Jones. Why databases use ordered indexes but programming uses hash tables. evanjones.ca, December 2019. Archived at perma.cc/NJX8-3ZZD ↩︎
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 ↩︎
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 ↩︎ ↩︎ ↩︎
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 ↩︎
Dhruba Borthakur. The History of RocksDB. rocksdb.blogspot.com, November 2013. Archived at perma.cc/Z7C5-JPSP ↩︎
Matteo Bertozzi. Apache HBase I/O – HFile. blog.cloudera.com, June 2012. Archived at perma.cc/U9XH-L2KL ↩︎
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. ↩︎ ↩︎
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 ↩︎
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 ↩︎
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 ↩︎ ↩︎
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 ↩︎
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 ↩︎
Thomas Hurst. Bloom Filter Calculator. hur.st, September 2023. Archived at perma.cc/L3AV-6VC2 ↩︎
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 ↩︎
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 ↩︎
Mark Callaghan. Name that compaction algorithm. smalldatum.blogspot.com, August 2018. Archived at perma.cc/CN4M-82DY ↩︎
Prashanth Rao. Embedded databases (1): The harmony of DuckDB, KùzuDB and LanceDB. thedataquarry.com, August 2023. Archived at perma.cc/PA28-2R35 ↩︎
Hacker News discussion. Bluesky migrates to single-tenant SQLite. news.ycombinator.com, October 2023. Archived at perma.cc/69LM-5P6X ↩︎
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 ↩︎
Douglas Comer. The Ubiquitous B-Tree. ACM Computing Surveys, volume 11, issue 2, pages 121–137, June 1979. doi:10.1145/356770.356776 ↩︎
Alex Miller. Torn Write Detection and Protection. transactional.blog, April 2025. Archived at perma.cc/G7EB-33EW ↩︎
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 ↩︎
Hironobu Suzuki. The Internals of PostgreSQL. interdb.jp, 2017. ↩︎ ↩︎
Howard Chu. LDAP at Lightning Speed. At Build Stuff ’14, November 2014. Archived at perma.cc/GB6Z-P8YH ↩︎
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 ↩︎
Ben Stopford. Log Structured Merge Trees. benstopford.com, February 2015. Archived at perma.cc/E5BV-KUJ6 ↩︎
Mark Callaghan. The Advantages of an LSM vs a B-Tree. smalldatum.blogspot.co.uk, January 2016. Archived at perma.cc/3TYZ-EFUD ↩︎
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. ↩︎
Igor Canadi, Siying Dong, Mark Callaghan, et al. RocksDB Tuning Guide. github.com, 2023. Archived at perma.cc/UNY4-MK6C ↩︎
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 ↩︎
Emmanuel Goossaert. Coding for SSDs. codecapsule.com, February 2014. ↩︎
Jack Vanlightly. Is sequential IO dead in the era of the NVMe drive? jack-vanlightly.com, May 2023. Archived at perma.cc/7TMZ-TAPU ↩︎
Alibaba Cloud Storage Team. Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2). alibabacloud.com, January 2019. Archived at archive.org ↩︎
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 ↩︎
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. ↩︎
Peter Zaitsev. Innodb Double Write. percona.com, August 2006. Archived at perma.cc/NT4S-DK7T ↩︎
Tomas Vondra. On the Impact of Full-Page Writes. 2ndquadrant.com, November 2016. Archived at perma.cc/7N6B-CVL3 ↩︎
Mark Callaghan. Read, write & space amplification - B-Tree vs LSM. smalldatum.blogspot.com, November 2015. Archived at perma.cc/S487-WK5P ↩︎ ↩︎
Mark Callaghan. Choosing Between Efficiency and Performance with RocksDB. At Code Mesh, November 2016. Video at youtube.com/watch?v=tgzkgZVXKB4 ↩︎
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 ↩︎
Lukas Fittl. Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication. pganalyze.com, April 2025. Archived at perma.cc/XY6T-LTPX ↩︎
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 ↩︎
Joe Webb. Using Covering Indexes to Improve Query Performance. simple-talk.com, September 2008. Archived at perma.cc/6MEZ-R5VR ↩︎
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. ↩︎
VoltDB Technical Overview White Paper. VoltDB, 2017. Archived at perma.cc/B9SF-SK5G ↩︎
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. ↩︎
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 ↩︎
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 ↩︎ ↩︎
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. ↩︎
Michael Stonebraker. The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong. Presentation at EPFL, May 2013. ↩︎ ↩︎
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 ↩︎
Tino Tereshko and Jordan Tigani. BigQuery under the hood. cloud.google.com, January 2016. Archived at perma.cc/WP2Y-FUCF ↩︎
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 ↩︎
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. ↩︎
Julien Le Dem. Dremel Made Simple with Parquet. blog.twitter.com, September 2013. ↩︎
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 ↩︎
Joe Kearney. Understanding Record Shredding: storing nested data in columns. joekearney.co.uk, December 2016. Archived at perma.cc/ZD5N-AX5D ↩︎
Jamie Brandon. A shallow survey of OLAP and HTAP query engines. scattered-thoughts.net, September 2023. Archived at perma.cc/L3KH-J4JF ↩︎ ↩︎
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 ↩︎ ↩︎
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. ↩︎
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 ↩︎ ↩︎
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 ↩︎ ↩︎
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 ↩︎ ↩︎
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 ↩︎
Weston Pace. Lance v2: A columnar container format for modern data. blog.lancedb.com, April 2024. Archived at perma.cc/ZK3Q-S9VJ ↩︎
Yoav Helfman. Nimble, A New Columnar File Format. At VeloxCon, April 2024. ↩︎
Wes McKinney. Apache Arrow: High-Performance Columnar Data Framework. At CMU Database Group – Vaccination Database Tech Talks, December 2021. ↩︎
Wes McKinney. Python for Data Analysis, 3rd Edition. O’Reilly Media, August 2022. ISBN: 9781098104023 ↩︎
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. ↩︎
Carlota Soto and Mike Freedman. Building Columnar Compression for Large PostgreSQL Databases. timescale.com, March 2024. Archived at perma.cc/7KTF-V3EH ↩︎
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 ↩︎
Jaz Volpert. An entire Social Network in 1.6GB (GraphD Part 2). jazco.dev, April 2024. Archived at perma.cc/L27Z-QVMG ↩︎
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 ↩︎ ↩︎
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 ↩︎
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 ↩︎ ↩︎
Forrest Smith. Memory Bandwidth Napkin Math. forrestthewoods.com, February 2020. Archived at perma.cc/Y8U4-PS7N ↩︎
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. ↩︎
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 ↩︎
Kevin Bartley. OLTP Queries: Transfer Expensive Workloads to Materialize. materialize.com, August 2024. Archived at perma.cc/4TYM-TYD8 ↩︎
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 ↩︎
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. ↩︎
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 ↩︎
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. ↩︎
Isaac Brodsky. H3: Uber’s Hexagonal Hierarchical Spatial Index. eng.uber.com, June 2018. Archived at archive.org ↩︎
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 ↩︎
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 ↩︎
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 ↩︎
Adrien Grand. What is in a Lucene Index? At Lucene/Solr Revolution, November 2013. Archived at perma.cc/Z7QN-GBYY ↩︎
Michael McCandless. Visualizing Lucene’s Segment Merges. blog.mikemccandless.com, February 2011. Archived at perma.cc/3ZV8-72W6 ↩︎
Lukas Fittl. Understanding Postgres GIN Indexes: The Good and the Bad. pganalyze.com, December 2021. Archived at perma.cc/V3MW-26H6 ↩︎
Jimmy Angelakos. The State of (Full) Text Search in PostgreSQL 12. At FOSDEM, February 2020. Archived at perma.cc/J6US-3WZS ↩︎
Alexander Korotkov. Index support for regular expression search. At PGConf.EU Prague, October 2012. Archived at perma.cc/5RFZ-ZKDQ ↩︎
Michael McCandless. Lucene’s FuzzyQuery Is 100 Times Faster in 4.0. blog.mikemccandless.com, March 2011. Archived at perma.cc/E2WC-GHTW ↩︎
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 ↩︎
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 ↩︎
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 ↩︎
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 ↩︎
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 ↩︎
Matthijs Douze, Maria Lomeli, and Lucas Hosseini. Faiss indexes. github.com, August 2024. Archived at perma.cc/2EWG-FPBS ↩︎
Varik Matevosyan. Understanding pgvector’s HNSW Index Storage in Postgres. lantern.dev, August 2024. Archived at perma.cc/B2YB-JB59 ↩︎
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 ↩︎
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 ↩︎