第 4 章 存储与检索

人生的不幸之一，是每个人给事物起名字时都起得稍微有点不对。这让世界上一切事物都比"如果它们的名字起得不一样"要更难理解。[……] 计算机的本意并不在于做算术意义上的"计算"。[……] 它们本质上是档案系统。

——Richard Feynman，Idiosyncratic Thinking 研讨会（1985）

在最基本的层面上，数据库要做两件事：当你把数据交给它时，它应当把数据存起来；之后你向它要数据时，它应当再把数据交还给你。

第 3 章我们讨论了数据模型与查询语言——也就是你交给数据库的数据格式，以及你之后用来重新询问的接口。本章我们从数据库的视角讨论同样的问题：数据库如何存储你交给它的数据，又如何在你查询时找回这些数据。

作为应用开发者，为什么要关心数据库内部如何处理存储与检索？你大概不会从零实现自己的存储引擎，但你确实需要在众多可用方案中为你的应用挑选合适的存储引擎。要让存储引擎在你的工作负载上表现良好，你需要对它在底层做什么有大致的了解。

特别是，针对事务负载（OLTP）优化的存储引擎，与针对分析优化的存储引擎之间存在很大差别（我们在"运营系统与分析系统"——第 3 页——已经引入这一区分）。本章首先考察 OLTP 的两类存储引擎：写出不可变数据文件的日志结构（log-structured）存储引擎，以及就地更新数据的B 树这类存储引擎。这两类结构同时用于键值存储与二级索引。

在"用于分析的数据存储"（第 134 页）我们将讨论一组针对分析优化的存储引擎；在"多维与全文索引"（第 145 页）我们将看用于更高级查询（如文本检索）的索引。

用于 OLTP 的存储与索引

考虑这世上最简单的数据库——用两个 bash 函数实现：

#!/bin/bash

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

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

这两个函数实现了一个键值存储。你可以调用 db_set key value，它会在数据库中存下 key 与 value。键和值可以是（几乎）任何东西——例如，值可以是一份 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 的性能其实相当不错，因为往文件末尾追加通常很高效。与 db_set 类似，许多数据库内部使用日志（log）——一种仅追加的数据文件。真实数据库要处理更多问题（如并发写、回收磁盘空间以防日志无限增长、崩溃恢复时处理写到一半的记录），但基本原则相同。日志非常有用，本书会多次遇到它。

log 这个词常被用来指应用日志——应用输出的、描述其正在发生什么的文本。本书在更宽泛的意义上使用 log：磁盘上仅追加的记录序列。它不一定可读；可能是二进制的，且仅供数据库系统内部使用。

另一方面，如果数据库里记录数很多，db_get 的性能就糟糕了。每次查找一个键，db_get 都要从头到尾扫描整份数据库文件，找出这个键的所有出现。从算法角度看，查找的代价是 O(n)：数据库记录数翻倍，查找时间也翻倍。这显然不行。

要在数据库中高效找到某个键的值，我们需要另一种数据结构：索引（index）。本章将考察一系列索引结构并加以比较。基本思路是以特定方式组织数据（例如按键排序），让你想要的数据更易定位。如果你想以多种方式搜索同一份数据，可能需要在数据的不同部分上建多个索引。

索引是从主数据派生出来的额外结构。许多数据库允许你增删索引，这并不会影响数据库内容，只会影响查询性能。维护额外结构会带来开销——尤其在写入时。对写入而言，没有什么比简单地追加文件更快——这是最简单的写操作。任何索引通常都会让写入变慢，因为每次写入数据时索引也得更新。

这是存储系统中一个重要的取舍：选得好的索引可加速读查询，但每个索引都会消耗额外的磁盘空间，并让写变慢，有时显著变慢 [1]。因此数据库通常不会默认对所有内容建索引，而是要求你——也就是应用的开发者或数据库管理员——根据你对应用典型查询模式的了解，手动选择索引。这样你就能选出那些给应用带来最大收益的索引，同时不引入超出必要的写入开销。

日志结构存储

假设你想继续把数据存到 db_set 写出的仅追加文件里，只想加快读取。一种做法是在内存中维护一个哈希映射：把每个键映射到该键最新值在文件中的字节偏移，如图 4-1 所示。

图 4-1. 把键值对日志以类 CSV 格式存放，并用内存哈希映射建索引

图示文字描述： 图示左侧"In-memory hash map"含两行：(key=12, byte offset=0) 与 (key=42, byte offset=60)；右侧是磁盘上的日志文件，每个方框是一个字节，第 0 字节起为 12,{"name":"London",...}\n，第 60 字节起为 42,{"name":"San Francisco",...}\n。

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

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

• 你从不释放被旧的、被覆盖的日志条目占用的磁盘空间；如果不停往数据库里写，最终会用尽磁盘空间。
• 哈希映射没有持久化，因此重启数据库时必须重建——例如扫描整份文件、为每个键找到最新偏移。这会让数据多时重启变慢。
• 哈希表必须能装下内存。原则上你也可以在磁盘上维护哈希表，但要让磁盘上的哈希表表现良好很难：它需要大量随机 I/O，满了再扩展代价高，处理哈希冲突的逻辑也烦琐 [2]。
• 范围查询效率不高。例如你不能轻松扫描键 10000 到 19999 之间的所有键——你必须在哈希映射中逐一查找。

SSTable 文件格式

实践中数据库索引很少使用哈希表。更常见的做法是把数据按键排序存放 [3]。这种结构的一个例子是 Sorted Strings Table，简称 SSTable，如图 4-2 所示。这种文件格式仍然存储键值对，但要求它们按键排序，并且每个键在文件中只出现一次。

图 4-2. 带稀疏索引的 SSTable，使查询可直接跳到正确的块

图示文字描述： 图示左侧 Sparse index：(hammock 100491)、(handbag 102134)、(handsome 104667)、(hangout 106812)；右侧是按键排序的键值对文件（SSTable），每若干键值对组成一个块（标"Compressible block"）：第一块 handbag/handcuffs/handful/handicap/handiwork/handkerchief...；下一块 handlebars/handoff/handprinted...；下一块 handsome/handwaving/handwriting...

现在，你不需要把所有键都放进内存。你可以把 SSTable 内的键值对分成若干 KB 的块（blocks），并把每块的第一个键存在索引里。这种只存部分键的索引称为稀疏索引（sparse）。该索引会作为 SSTable 的一个独立部分存放——例如使用不可变 B 树、字典树（trie）或其他能让查询快速找到特定键的数据结构 [4]。

例如，在图 4-2 中，某块的第一个键是 handbag，下一块的第一个键是 handsome。假设你要找键 handiwork，它没出现在稀疏索引中。由于是按序排列的，你知道 handiwork 必在 handbag 与 handsome 之间。所以你可以跳到 handbag 的偏移，从那里开始扫描文件直到找到 handiwork（若不存在则跳过）。几 KB 的块可以被极快地扫描完。

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

构建与合并 SSTable

SSTable 文件格式比仅追加日志更利于读取，但写入会更难。我们不能简单地往末尾追加，因为那会破坏排序（除非键恰好按升序写入）。如果每次往中间插入一个键都要重写整个 SSTable，写入代价就高得多了。

我们可以用一种日志结构做法来解决这一问题——它是仅追加日志与排序文件的混合体：

1. 当一次写入到来时，把它加进一个内存中的有序映射数据结构，例如红黑树、跳表 [5] 或字典树 [6]。这些数据结构允许你以任意顺序插入键、高效查找、按序读回。这个内存中的数据结构称为 memtable。
2. 当 memtable 大于某个阈值（通常几 MB）时，把它按排序顺序作为一个 SSTable 文件写到磁盘。我们把这个新的 SSTable 文件称为数据库最近的段（segment），它作为独立文件与较旧的段并列存放。每个段都有自己内容的索引。当新段在写入磁盘时，数据库可以继续写入一个新的 memtable 实例；旧 memtable 的内存在 SSTable 写完后释放。
3. 要读取一个键的值，先在 memtable 中找；没找到就在最新的磁盘段里找；还没找到就到次新的段里找，依此类推，直到找到该键或到达最旧段。如果该键不出现在任何段中，则它不在数据库里。
4. 不时地在后台运行*合并与压实（merging and compaction）*流程，把段文件合并并丢弃被覆盖或删除的值。

合并段的过程类似*归并排序（mergesort）*算法 [5]。如图 4-3 所示：并排读输入文件，看每个文件中的第一个键，把（按排序顺序的）最小键复制到输出文件，再循环。如果同一个键出现在多个输入文件中，只保留较新的那一个。这会产生一个新的合并段文件，也按键排序、每个键只有一个值，且消耗的内存极少——因为我们一次处理一个键即可遍历各 SSTable。

为防止数据库崩溃时 memtable 中的数据丢失，存储引擎会在磁盘上保留一份独立日志，每次写入都立即追加到该日志。这份日志并非按键排序，但这无关紧要——它唯一的目的是在崩溃后恢复 memtable。每次 memtable 被写出为一个 SSTable 时，对应那部分日志就可以丢弃。

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

图示文字描述： 图示三段输入 Segment 1/2/3，每段含若干键值条目；下方的 + Compaction and merging process 合并它们为底部的 Merged 1, 2, 3，对每个键只保留最新值。

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

这里描述的算法本质上就是 RocksDB [7]、Cassandra、ScyllaDB、HBase [8] 所使用的算法，全部受 Google Bigtable 论文 [9] 启发（该论文引入了术语 SSTable 与 memtable）。该算法最初于 1996 年以 Log-Structured Merge-tree 的名字发表 [10]，建立在更早的日志结构文件系统工作之上 [11]。正因如此，基于"合并与压实有序文件"原则的存储引擎常被称为 LSM 存储引擎。

在 LSM 存储引擎中，段文件是一次性写出的（要么写出 memtable，要么合并若干已有段），写出后即不可变。段的合并与压实可由后台线程完成。合并进行时，我们仍可使用合并的输入段来服务读取（如前所述，先查 memtable，再查更新的段文件）；当合并过程完成后，把读请求切换到使用新的合并段，于是输入段文件可以删除。

段文件不一定要存放在本地磁盘；它们也很适合写到对象存储——SlateDB 和 Delta Lake [12] 就采用这种做法。

不可变段文件也简化了崩溃恢复。如果在写出 memtable 或合并段过程中崩溃，数据库可以删掉未完成的 SSTable 重新开始。承载对 memtable 写入的日志若在写到一半时遭遇崩溃或磁盘已满，可能含不完整记录；这些问题通常通过在日志中包含校验和、并丢弃损坏或不完整的日志条目来检测。我们将在第 8 章更多讨论持久性与崩溃恢复。

布隆过滤器

在 LSM 存储中，读取一个很久之前才更新过的键，或读一个不存在的键，可能很慢——因为存储引擎需要检查多个段文件。为加速这类读取，LSM 存储引擎常在每个段中加入一个布隆过滤器（Bloom filter） [13]，它提供一种快速但近似的方式来检查某个键是否存在于某个 SSTable 中。

图 4-4 给出一个示例：一个布隆过滤器含两个键、16 位（实际中会有更多键和更多位）。对 SSTable 中的每个键，我们计算一个哈希函数，得到一组数字，并把这些数字解释为位数组的索引 [14]。把这些索引对应的位置 1，其余位为 0。例如键 handbag 哈希到数字 (2, 9, 4)，于是把第 2、9、4 位置 1。位图作为 SSTable 的一部分与稀疏索引一起存放。它会占用一些额外空间，但布隆过滤器相对 SSTable 其余部分通常很小。

要查询某键是否在 SSTable 中，对它计算同样的哈希，再检查那些索引上的位。例如在图 4-4 中我们查询键 handheld，它哈希到 (6, 11, 2)。其中一位是 1（第 2 位），其余两位是 0。这种检查可以用所有 CPU 都支持的位运算极快地完成。

图 4-4. 布隆过滤器：对"某键是否存在于某 SSTable"做一次快速的概率性检查

图示文字描述： 图示上部"Keys that exist in the SSTable"列出 Hash("handbag")=0010 1001 0100 → 索引 2,9,4；Hash("handoff")=1001 1111 0101 → 9,15,5。中部 16 位 Bloom filter 数组（位 0-15），与上述索引对应位被设为 1。下部"Key being queried" Hash("handheld")=0110 1011 0010 → 6,11,2；查这三位的取值 0,0,1，因此 handheld 不存在。

如果至少有一位为 0，我们就知道该键肯定不在 SSTable 里。如果查询的所有位都为 1，该键很可能在 SSTable 中，但也可能因为别的键碰巧把那些位都置为 1，看起来似乎存在却其实并不存在——这种情况称为假阳性（false positive）。

假阳性概率取决于键的数量、每个键设置的位数，以及布隆过滤器的总位数。你可以用在线计算器来确定适合应用的参数 [15]。一个经验是：为每个 SSTable 中的键分配 10 位布隆过滤器空间可得到约 1% 的假阳性概率，每多分 5 位概率再降十倍。

在 LSM 存储引擎里，假阳性不是问题：

• 如果布隆过滤器说某键不在，我们可以放心跳过该 SSTable，因为可以确定它不含此键。
• 如果布隆过滤器说该键在，我们必须查稀疏索引并解码键值对块以检查是否真存在。如果是假阳性，我们只是做了一点白工，无害——继续到次旧段中查就是了。

压实策略

一个重要的细节是：LSM 存储何时执行压实，以及哪些 SSTable 参与一次压实。许多 LSM 存储系统让你配置压实策略。常见的选择如下 [16, 17]：

Size-tiered compaction（按大小分层压实） ：较新、较小的 SSTable 被相继合并为较旧、较大的 SSTable。例如 4 个 256 MB 的 SSTable 可能被压实成 1 个 898 MB 的 SSTable（结果不是 1024 MB，是因为有删除、覆盖、TTL 过期等）。含旧数据的 SSTable 会变得很大，合并它们需要大量临时磁盘空间。该策略的优点是能承载非常高的写吞吐——因为多数数据只在大型顺序合并里被重写少数几次。

Leveled compaction（分级压实） ：分级压实不是写出大 SSTable，而是让 SSTable 大小保持固定，并按递增的"级（levels）"分组（称为 L0、L1 等）。L0 含最近写入的数据。L0 之上的所有级都包含按键范围分片的 SSTable。例如 L1 可能有两个 SSTable：第一个键范围 a–m，第二个 n–z。每级都有自己的大小限制，并且每级都比上一级大（如 L2 比 L1 大）。当某级的 SSTable 合起来超过最大尺寸时，i 级的一个或多个 SSTable 会被合并到 i+1 级，并从 i 级删除。这种做法让压实可以更增量地推进，占用更少磁盘空间。分级压实在读取上比按大小分层更高效——存储引擎检查某键是否存在时只需读较少的 SSTable。

经验是：如果你的工作主要是写、读较少，按大小分层表现更好；若以读为主，分级压实更佳。如果你少量键经常被写、大量键很少被写，分级压实也可能更有利 [18]。所幸大多数 LSM 树实现提供多种压实策略，以适应不同负载。

虽然细节很多，但 LSM 树的基本思想——保留一系列在后台被合并的 SSTable——简单且有效。我们将在"比较 B 树与 LSM 树"（第 129 页）中更详细讨论它们的性能特性。

嵌入式存储引擎

许多数据库以服务方式接收网络请求，但也有嵌入式数据库不暴露网络 API。它们是与你应用代码同进程运行的库，通常通过常规函数调用与之交互，并在本地磁盘上读写文件。嵌入式存储引擎的例子包括 RocksDB、SQLite、LMDB、DuckDB 与 KùzuDB [19]。

嵌入式数据库常被移动 App 用以存放本地用户数据。在后端，如果数据小到能装下一台机器、且没有许多并发事务，嵌入式数据库可能是合适的选择。例如在多租户系统里，每个租户都很小、且与其他租户完全独立（即不需要跨租户合并数据的查询），你可以为每个租户使用一个独立的嵌入式数据库实例 [20]。

本章讨论的存储与检索方法在嵌入式数据库与客户端/服务器型数据库中都会用到。第 6 章与第 7 章我们将讨论让数据库跨多台机器扩展的技术。

B 树

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

B 树于 1970 年被提出 [21]，不到 10 年后就被称作"无处不在" [22]。B 树经受住了时间的考验，至今仍是几乎所有关系数据库的标准索引实现，许多非关系数据库也在使用它。

与 SSTable 一样，B 树也按键排序保存键值对，因此能高效做键值查找与范围查询。但相似性到此为止：B 树有截然不同的设计哲学。

我们之前看到的日志结构索引把数据库分成可变大小的段，通常几 MB 或更大，一次写完后就不可变。B 树则把数据库分成固定大小的块（blocks）或页（pages），可以就地覆盖某一页。一页传统上是 4 KiB，PostgreSQL 现在默认 8 KiB，MySQL 默认 16 KiB。

每页可由页码标识，从而让一页能引用另一页——类似于指针，但在磁盘上而非内存中。如果所有页都存放在同一个文件中，把页号乘以页大小就能算出该页在文件中的字节偏移。我们可以用这些页引用构成一棵页树，如图 4-5 所示。

图 4-5. 用 B 树索引查找键 251。从根页起，先沿到"键 200–300"的页引用，再到"键 250–270"的页

图示文字描述： 图示根页含 100/200/300/400/500 等区间分隔；箭头指向下一级页：第二级页含 111/135/152/169/190/210/230/250/270/290 等；最底层叶页含 250/251/252/253/254 各自的 val。

其中一页被指定为 B 树的根（root）；当你想在索引里查一个键时，就从这里开始。该页含若干键与到子页的引用。每个子页负责一段连续的键范围，引用之间的键就是这些范围的边界。（这种结构有时叫 B+ 树，但本书不区分它与 B 树的其他变体。）

在图 4-5 的例子中我们要找键 251，于是沿边界 200 与 300 之间的页引用走。这会把我们带到一张类似的页，进一步把 200–300 拆成子区间。最终我们到达含具体键的页（叶页（leaf page）），它要么内嵌每个键的值，要么含到值所在页的引用。

B 树一页中到子页的引用数称为分支因子（branching factor）。例如在图 4-5 中分支因子是 6。实际中，分支因子取决于存放页引用与边界所需的空间大小，但通常是几百。

如果你想更新 B 树中某个已存在键的值，先搜索到含该键的叶页，把页中那个值用含新值的版本覆盖即可。如果想新增一个键，需要找到键范围包含该键的页并把它加进去。如果该页空间不够容纳新键，就把这页拆成两个半满的页，并更新父页以反映键范围的新切分，如图 4-6 所示。

图 4-6. 通过在边界键 337 拆页使 B 树成长。父页被更新以引用两个子页

图示文字描述： 图示"Before"：父页含 ref/310/ref/333/ref/345/ref（含一段空闲），叶页 333–345 范围有 333/335/337/340/342。"After adding key 334"：父页变成 ref/310/ref/333/ref/337/ref/345/ref，叶页拆为左侧 333/334/335 与右侧 337/340/342。

例如我们要插入键 334，但范围 333–345 的页已满，于是我们把它拆成范围 333–337（含新键 334）的页与范围 337–345 的页。我们还要更新父页，让它包含两个子页的引用，且两者之间的边界值为 337。如果父页没有足够空间放新引用，它也可能要被拆分；拆分可能一路传到树根。当根被拆时，我们会在它之上新建一个根。删除键（可能要求节点合并）更复杂 [5]。

该算法保证树保持平衡：含 n 个键的 B 树深度为 O(log n)。多数数据库都能放进三或四级深的 B 树，不需要追多个页引用就能找到目标。（有 4 KiB 页、分支因子 500 的四级树可存到 250 TB。）

让 B 树可靠

B 树底层基本的写操作是"用新数据覆盖磁盘上的一页"。这里假设覆盖不会改变页的位置；覆盖之后所有指向这页的引用仍然有效。这与日志结构索引（如 LSM 树）截然相反——后者只追加（最终删除过时文件），从不就地修改文件。

一次操作中覆盖多页（如页拆分）是一个危险动作。如果数据库在写出一些页后崩溃，会得到一棵损坏的树（例如可能有一个孤儿页，不再是任何父页的子页）。如果硬件无法原子地写出整页，你也可能得到部分写出的页（这叫撕裂页（torn page） [23]）。

为让数据库对崩溃健壮，常见做法是在 B 树实现中包含一种额外的磁盘数据结构：预写日志（write-ahead log，WAL）。这是一个仅追加文件，每次 B 树修改在被应用到树自身页之前必须先写到这里。当数据库崩溃后重启，这份日志会被用来把 B 树恢复到一致状态 [2, 24]。在文件系统中，等价机制叫日志（journaling）。

为提升性能，B 树实现通常不会立即把每个被修改的页写到磁盘，而是先在内存中缓冲一会儿。WAL 也能确保崩溃时数据不丢——只要数据已被写到 WAL 并通过 fsync 系统调用刷到磁盘，数据就是持久的，因为数据库能在崩溃后恢复 [25]。

使用 B 树变种

B 树存在已久，多年来发展出了许多变种。仅举几例：

• 一些数据库（如 LMDB）不覆盖页、也不维护 WAL 来做崩溃恢复，而是采用*写时复制（copy-on-write）*方案 [26]。修改后的页写到不同位置，并创建包含新位置指针的父页新版本。这种做法对并发控制也有用，参见"快照隔离与可重复读"（第 293 页）。
• 通过不存整个键、对键做缩写，可以节约页中空间。尤其在树内部页中，键只需提供足够信息以充当键范围间的边界。把更多键塞进一页能让树有更高的分支因子，从而层级更少。
• 为加速按排序顺序的范围扫描，一些 B 树实现会尝试把树排布成叶页在磁盘上顺序紧邻——这能减少磁盘寻址。但随着树的成长，维持这种顺序很困难。
• 在树上加额外指针。例如每个叶页可能有指向左右兄弟页的引用，从而无需回到父页就能按序扫描键。

比较 B 树与 LSM 树

经验是：LSM 树更适合写多的应用，B 树读起来更快 [27, 28]。然而基准测试常常对工作负载细节敏感。你需要用自己的具体负载来测试系统，才能做出有效比较。而且，并不是非此即彼——存储引擎有时会混合两种思路，例如同时拥有多个 B 树并以 LSM 风格合并它们。本节我们简要讨论几个值得考虑的方面。

读性能

在 B 树里，查一个键需要在每级读一页。由于级数通常相当少，B 树读取一般快且性能可预测。在 LSM 存储引擎中，读取通常需要检查处于不同压实阶段的多个 SSTable，但布隆过滤器有助于减少所需的磁盘 I/O 次数。两种方法都能表现良好；哪种更快取决于存储引擎的具体细节与负载。

范围查询在 B 树上简单且快——它能利用树的有序结构。在 LSM 存储中，范围查询也可利用 SSTable 的有序，但需并行扫描所有段并合并结果。布隆过滤器对范围查询没什么帮助（因为得对范围内每一个可能的键都计算哈希，不现实），所以在 LSM 中范围查询比点查询更贵 [29]。

如果 memtable 装满了，高写入吞吐可能在日志结构存储中引发延迟尖峰。这种情况发生在数据写入磁盘的速度跟不上输入写入时——例如压实跟不上。许多存储引擎（包括 RocksDB）在这种情形下会施加背压：暂停所有读写，直到 memtable 写到磁盘 [30, 31]。

就读吞吐而言，现代 SSD（尤其是通过比 SATA 快得多的 PCIe 总线连接的 NVMe SSD）能并行执行许多独立的读请求。LSM 树与 B 树都能提供高读吞吐，但需要存储引擎精心设计以利用这种并行性 [32]。

顺序 vs 随机写

在 B 树中，如果应用写入分散在键空间各处的键，磁盘上对应的写也会分散——存储引擎需要覆盖的页可能位于磁盘上任何位置。而日志结构存储引擎一次写出整个段文件（写出 memtable 或合并已有段），这些段文件比 B 树里的页大得多。

许多小而分散的写（如 B 树）这种模式称为随机写；少数大写（如 LSM 树）这种模式称为顺序写。磁盘的顺序写吞吐通常比随机写高，意味着日志结构存储引擎在同一硬件上一般能承担比 B 树更高的写入吞吐。这种差异在机械硬盘上尤其大；在如今多数数据库使用的 SSD 上，差异较小但仍可见。

SSD 上的顺序 vs 随机写

在机械硬盘（HDD）上，顺序写比随机写快得多。这是因为随机写要把磁头机械移动到新位置，等盘面正确部分旋转到磁头下方，要花若干毫秒——在计算机时间尺度上简直是一辈子。然而 NVMe 等 SSD（或通过 PCIe 总线连接的闪存）在许多用例上已经超越了 HDD，且不受这种机械限制。

但 SSD 的顺序写吞吐仍高于随机写。原因是闪存可以一次按一页（通常 4 KiB）读写，但只能一次按一块（通常 512 KiB）擦除。一个块中某些页可能含有效数据，其他可能已不再需要。擦块前控制器必须把含有效数据的页搬到其他块；这个过程称为垃圾回收（GC） [33]。

顺序写工作负载一次写较大块数据，因此可能整个 512 KiB 块都属于一个文件。当该文件之后被删除时，整个块可被擦除而无需 GC。相反在随机写中，块更可能混杂着有效与无效页，所以 GC 在能擦掉该块之前必须做更多工作 [34, 35, 36]。GC 所消耗的写带宽因此对应用不可用。GC 引起的额外写也会对闪存造成磨损；因此随机写比顺序写更快磨穿驱动器。

写放大

对任何存储引擎而言，应用的一次写请求都会变为底层磁盘上多次 I/O 操作。LSM 树先把值写到日志以保证持久，然后在 memtable 写到磁盘时再次写入，每次该键值对参与压实时又会写一次。（如果值显著大于键，可以把值与键分别存放、只对含键和到值引用的 SSTable 做压实，从而减少这种开销 [37]。）

B 树索引必须把每条数据至少写两次：一次写到 WAL，一次写到树页本身。此外，有时不得不写出整页——即便只有几字节变了——以保证 B 树能在崩溃或电源故障后被正确恢复 [38, 39]。

如果你把负载下写到磁盘的总字节数除以"假如简单写仅追加日志且无索引时本应写的字节数"，就得到写放大。（有时写放大用 I/O 操作次数定义，而非字节数。）在写多的应用中，瓶颈可能就是数据库写到磁盘的速率。这种情况下，写放大越高，可用磁盘带宽内每秒能处理的写就越少。

写放大在 LSM 树与 B 树中都是问题。哪种更好取决于多种因素，例如键值长度，以及覆盖已有键 vs 插入新键的频率。对典型工作负载，LSM 树的写放大较低，因为它们不必写整个页，且能压缩 SSTable 的块 [40]。这是又一个让 LSM 存储引擎适合写多负载的因素。

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

测量存储引擎写吞吐时，让实验跑得足够久很重要，要让写放大效应清晰显现。写到一个空的 LSM 树时还没有发生压实，所以全部磁盘带宽都用于新写。随着数据库增长，新写需与压实分享带宽。

磁盘空间使用

B 树会随时间碎片化；例如大量键被删时，数据库可能含许多 B 树不再使用的页。后续添加可以使用这些空闲页，但它们不能轻易归还操作系统——因为它们位于文件中部，仍占用文件系统中的空间。因此数据库需要后台流程把页搬来搬去以更好地排布，比如 PostgreSQL 的 vacuum 流程 [25]。

碎片化在 LSM 树中不太成问题，因为压实流程会定期重写数据文件，且 SSTable 中没有未用空间的页。此外 SSTable 中的键值对块可以被更好地压缩，常使磁盘文件比 B 树更小。被覆盖的键和值会持续占用空间，直到被一次压实清除，但使用分级压实时这一开销很低 [40, 41]。Size-tiered 压实（参见"压实策略"，第 124 页）则使用更多磁盘空间，尤其在压实过程中临时占用更多。

当你需要删除某些数据并希望确认它真的被删（例如为遵守数据保护法规）时，磁盘上保留同一份数据的多份副本也可能成为问题。例如在大多数 LSM 存储引擎中，被删记录可能仍存在于较高级，直到表示删除的墓碑被传播到所有压实级——这可能要花很长时间。专门的存储引擎设计可以让删除更快传播 [42]。

另一方面，SSTable 段文件的不可变特性在你要给数据库做某时刻的快照（如做备份或建测试副本）时很有用。你可以写出 memtable 并记录当时存在的段文件列表。只要不删除属于快照的文件，就不必真正复制它们。在覆盖页的 B 树中，要高效做这种快照就比较难。

多列与二级索引

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

二级索引也很常见。在关系数据库中，可以用 CREATE INDEX 命令在同一张表上建多个二级索引，让你按主键之外的列搜索。例如在图 3-1 的关系模式中，你最可能为各从表的 user_id 列建二级索引，以便找出属于同一用户的所有行。

二级索引可以由键值索引轻松构造。主要差别在于：二级索引中被索引的值不一定唯一——可能有多行（文档、顶点）出现在同一索引项下。可以用两种方式解决：要么让索引中每个值是匹配行标识符的列表（像全文索引中的倒排表），要么给每条索引项附加行标识符使其唯一。可就地更新的存储引擎（如 B 树）与日志结构存储都可用来实现索引。

把值存进索引内

索引中的键是查询要搜索的目标。除了键，索引里可能还存其他数据，具体取决于索引类型：

• 如果实际数据（行、文档、顶点）直接存在索引结构内，就叫聚集索引（clustered index）。例如 MySQL 的 InnoDB 中，表的主键总是聚集索引；在 SQL Server 中，每张表可指定一个聚集索引 [43]。
• 也可以让索引值是到实际数据的引用：要么是主键（InnoDB 的二级索引就是这样），要么是磁盘上某位置的直接引用。在后一种情形下，行所在的位置称为堆文件（heap file）——它以无特定顺序的方式存放数据（可能是仅追加的，也可能记录被删行以便日后用新数据覆盖）。例如 PostgreSQL 采用堆文件做法 [44]。
• 介于两者之间的是覆盖索引（covering index）或带列索引（index with included columns）——除把整行存在堆或主键聚集索引中之外，再把表的某些列存进索引 [45]。这让某些查询仅靠索引就能回答，无需回到主键或堆文件（这种情况下称索引覆盖该查询）。这能让某些查询更快，但数据复制意味着索引占用更多磁盘空间，写入也更慢。

到目前为止讨论的索引都只把单一键映射到值。如果你需要同时按表的多列（或文档的多字段）查询，见"多维与全文索引"（第 145 页）。

如果你要在不改键的情况下更新值，堆文件做法允许在原地覆盖记录——只要新值不大于旧值。新值更大时情况更复杂，记录大概要被搬到堆中有足够空间的新位置 [2]。这种情形下，所有索引都需要更新以指向记录的新堆位置，或在旧堆位置留一个转发指针。

全部存内存

到目前为止本章讨论的数据结构都是对磁盘局限性的应对。相比主存而言，磁盘很难处理。无论机械盘还是 SSD，要获得良好的读写性能，数据布局都需精心设计。我们之所以容忍这种笨拙，是因为磁盘有两个显著优势：持久（断电不丢内容），且每 GB 价格比 RAM 低。

随着 RAM 越来越便宜，"每 GB 价格"这一论点被削弱。许多数据集本就没那么大，把它们完全放进内存是可行的——也可以跨多台机器分布存放。这促成了*内存数据库（in-memory databases）*的发展。

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

这让数据库能在重启时从磁盘或网络上的副本重新加载状态（除非用了特殊硬件）。尽管会写到磁盘，这些系统仍被视为内存数据库——磁盘仅被用作仅追加的持久日志，读取全部由内存提供。写到磁盘也带来运维便利：磁盘上的文件易于备份、检查、被外部工具分析。

VoltDB、SingleStore、Oracle TimesTen 等产品是带关系模型的内存数据库；其供应商声称：由于消除了所有与"管理磁盘上数据结构"相关的开销，可以带来巨大的性能改善 [46, 47]。RAMCloud 是一个开源的内存键值存储，对内存数据与磁盘数据都使用日志结构方法 [48]。Redis 与 Couchbase 通过异步写盘提供较弱的持久性。

反直觉的是，内存数据库的性能优势并非源于"不用读磁盘"。即便是基于磁盘的存储引擎，只要内存够大，也可能从不需要读磁盘——因为操作系统本来就会把最近用过的磁盘块缓存到内存。它们快，是因为避开了"把内存中的数据结构编码成可写到磁盘的形式"这一开销 [49]。

除性能之外，内存数据库的另一项有趣用途，是提供基于磁盘索引难以实现的数据模型。例如 Redis 为各种数据结构（如优先队列与集合）提供类数据库的接口。由于全部数据在内存里，其实现相当简单。

用于分析的数据存储

数据仓库的数据模型最常是关系型的，因为 SQL 通常很适合分析查询。还有许多图形化的数据分析工具，它们生成 SQL 查询、把结果可视化，让分析师以*下钻（drill-down）与切片切块（slicing and dicing）*等操作探索数据。

表面上看，数据仓库与关系型 OLTP 数据库类似——两者都有 SQL 查询接口。然而它们内部可能差异很大，因为它们针对截然不同的查询模式做了优化。如今许多数据库厂商专注于支持事务处理或分析负载之一，而不两者通吃。

一些数据库——如 Microsoft SQL Server、SAP HANA 与 SingleStore——对事务处理与数据仓库都支持。然而，"混合事务/分析处理（HTAP）"数据库（在"数据仓库"，第 7 页中介绍）正越来越多地演变为两套独立的存储与查询引擎，只是恰好可以通过同一 SQL 接口访问 [50, 51, 52, 53]。

云数据仓库

老牌数据仓库厂商（如 Teradata、Vertica、SAP HANA）既提供按商业许可的本地部署，也提供云端方案。但随着越来越多客户上云，仅在云上提供的数据仓库——如 Google Cloud BigQuery、Amazon Redshift 与 Snowflake——也已被广泛采用。与传统数据仓库不同，云数据仓库可以利用对象存储、无服务器计算等可扩展的云基础设施。

云数据仓库通常更易于与其他云服务集成。例如许多云仓库支持自动日志摄取，并能轻松对接 Google Cloud Dataflow、AWS Kinesis 等数据处理框架。这类仓库也更具弹性——因为它们把查询计算与存储层解耦 [54]。数据持久于对象存储而非本地磁盘，便于独立调整存储容量与查询计算资源（参见"云原生系统架构"，第 14 页）。

开源数据仓库——如 Apache Hive、Trino 与 Apache Spark——也随云演化。当用于分析的数据存储迁向对象存储上的数据湖之后，开源仓库开始走向"分而治之" [55]。下列组件——以前在 Hive 这样的单一系统中集成在一起——如今常被实现为独立组件：

查询引擎（Query engine） ：Trino、Apache DataFusion、Presto 这类查询引擎解析 SQL 查询，把它们优化为执行计划，并对数据执行。执行通常需要并行的、分布式的数据处理任务。某些查询引擎内置任务执行，另一些选择借助 Spark 或 Flink 等第三方执行框架。

存储格式（Storage format） ：存储格式决定一行如何被编码为文件中的字节，文件随后通常存到对象存储或分布式文件系统中 [12]。这些数据既可被查询引擎访问，也可被使用同一数据湖的其他应用访问。这类存储格式包括 Parquet、ORC、Lance 与 Nimble；下一节会讨论。

表格式（Table format） ：以 Parquet 等存储格式写出的文件通常一旦写完就不可变。要支持行的插入与删除，可使用 Apache Iceberg、Databricks 的 Delta 这类表格式。表格式指明哪些文件构成一张表以及表的模式。这类格式还提供高级特性，如时间旅行（在过去某时刻查询表）、GC，乃至事务。

数据目录（Data catalog） ：正如表格式定义"哪些文件组成一张表"，数据目录则定义"数据库里有哪些表"。目录用于在数据库中创建、重命名与删除表。与存储格式和表格式不同，数据目录（如 Snowflake 的 Polaris、Databricks 的 Unity Catalog）通常作为独立服务运行，可通过 REST 接口查询。Apache Iceberg 也提供一个目录，可在客户端内运行或作为独立进程运行。查询引擎在读写表时使用目录信息。传统上目录与查询引擎是集成在一起的，但把它们解耦让数据发现与数据治理系统（参见"数据系统、法律与社会"，第 24 页）也能访问目录的元数据。

列式存储

如"用于分析的星型与雪花型模式"（第 77 页）所讨论，数据仓库按惯例使用关系模式：一张大事实表加上引用维度表的外键。如果你的事实表里有数万亿行、数 PB 数据，要高效存储与查询就不容易。维度表通常小得多、好管理（数百万行），因此本节聚焦事实表的存储。

虽然事实表常宽达 100+ 列，但典型的数据仓库查询通常一次只访问其中四五列（SELECT * 这种查询在分析中很少需要）[52]。看示例 4-1 中的查询：它访问大量行（2024 日历年里每一次有人买水果或糖果的事件），但只需要 fact_sales 表的三列：date_key、product_sk、quantity。该查询忽略其他所有列。

示例 4-1. 分析"工作日不同，人们更倾向买新鲜水果还是糖果"

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

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

在大多数 OLTP 数据库中，存储是按*行式（row-oriented）*布局的：一行中的所有值彼此相邻存放。文档数据库类似：一份文档通常作为连续字节序列存放。在图 4-1 的 CSV 例子里就能看到这种布局。

要处理类似示例 4-1 的查询，你可能在 fact_sales.date_key 与/或 fact_sales.product_sk 上有索引——它们告诉存储引擎到哪里能找到某日期或某商品的所有销售。但即便如此，行式存储引擎仍需把所有相关行（每行 100+ 属性）从磁盘加载到内存、解析，再把不满足条件的过滤掉，这可能要花很长时间。

列式（column-oriented，或 columnar）存储的思想很简单：与其把一行里的所有值存在一起，不如把每列的所有值存在一起 [56]。如果每列分开存，查询只需读取并解析查询中用到的那些列，能省下大量工作。图 4-7 用图 3-5 事实表的扩展版演示了这一原则。

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

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

图示文字描述： 图示上部是 fact_sales 表，列为 date_key, product_sk, store_sk, promotion_sk, customer_sk, quantity, net_price, discount_price，含若干行；下部是 columnar storage layout，列出每个列的值序列：date_key: 260102,260102,260102,260102,260103,260103,260103,260103；product_sk: 69,69,69,74,30,30,30,30；store_sk: 4,5,5,3,2,3,3,8；promotion_sk: NULL,19,NULL,23,NULL,NULL,21,NULL；customer_sk: NULL,NULL,191,202,NULL,NULL,123,233；quantity: 1,3,1,5,1,3,1,1；net_price: 13.99,14.99,14.99,0.99,2.49,14.99,49.99,0.99；discount_price: 13.99,9.99,14.99,0.89,2.49,9.99,39.99,0.99。

列式存储布局依赖每一列以同样的顺序存放各行。因此要重组成一整行，可以从各个列分别取出第 23 项再拼成第 23 行。

实践中，列式存储引擎并不真的把整列（可能有数万亿行）一次性存起来。它会把表分成数千或数百万行的块，块内每列分开存 [60]。由于许多查询限定在某个时间戳范围内，常见做法是让每块包含某时间戳范围内的行。查询只需加载所需列在与所需时间范围重叠的块里的部分。

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

列压缩

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

看图 4-7 中各列的值序列。它们重复相当多，这是适合压缩的好兆头。视列中数据不同，可以使用不同的压缩技术 [73]。一种在数据仓库中特别有效的技术是位图编码（bitmap encoding），如图 4-8 所示。

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

图示文字描述： 图示一列 product_sk 值序列：69,69,69,69,74,30,30,30,30,29,31,30,30,30,30,68,69,69。下方为每个可能值的位图：product_sk=29: 0,0,0,...,1,...,0,0,0,0,0,0,0；30: 0,0,0,0,0,1,1,1,1,0,0,1,1,1,1,0,0,0；31: 0,0,...,1,...,0；68: 0,...,1,0,0；69: 1,1,1,1,0,...,1,1；74: 0,0,0,0,1,0,...。下方游程编码：29: 9,1；30: 5,4,3,3；31: 10,2；68: 15,1；69: 0,4,12,2；74: 4,1。

通常一列里不同值的数量比行数少得多（例如零售商可能有数十亿销售事务，但只有 100,000 种不同商品）。我们可以把含 n 个不同值的列变成 n 个独立位图：每个不同值一个位图，每行一位。该位为 1 表示该行有此值，否则为 0。

一种选择是用每行一位来存这些位图。然而这些位图通常含很多 0（我们说它们是稀疏的）。这种情况下位图还可以被游程长度编码（run-length encoded），即按图 4-8 底部所示数出连续 0 或 1 的个数并存下计数。诸如 roaring bitmaps 等技术能在两种位图表示之间切换，使用最紧凑的那一种 [74]。这能让一列被编码得极为高效。

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

WHERE product_sk IN (31, 68, 69) ：加载 product_sk = 31、product_sk = 68 与 product_sk = 69 的三个位图，对其按位 OR，可极快完成。

WHERE product_sk = 30 AND store_sk = 3 ：加载 product_sk = 30 与 store_sk = 3 的位图，做按位 AND。这之所以可行，是因为各列以同样顺序存放各行——所以一列位图的第 k 位对应另一列位图同一行的第 k 位。

位图也能用来回答图查询，例如找出社交网络上"被用户 X 关注，并且也关注用户 Y"的所有用户 [75]。

别把列式数据库与*宽列（wide-column，又称 column-family）*数据模型混淆——后者一行可以有数千列，且不需要所有行都有相同的列 [9]。尽管名字相似，宽列数据库是行式的——它把一行的所有值存在一起。Google Bigtable、Apache Accumulo、HBase 是这种宽列模型的例子。

列存储中的排序

列存储中行的存储顺序未必重要。最简单的做法是按写入顺序存（插入新行只需对每列做追加）。但我们也可以选择强加一个顺序——就像前面的 SSTable 那样——并以此作为索引机制。

注意：对每列单独排序没有意义，因为这样我们就不知道列里哪些项属于同一行。我们之所以能重建一行，仅因为我们知道一列的第 k 项与另一列的第 k 项属于同一行。

数据应整行排序，即便它按列存。数据库管理员可基于对常用查询的了解选择"按哪些列排"。例如，若查询常常针对日期范围（如最近一月），把 date_key 设为第一排序键就合理。这样查询只需扫上月的行，比扫所有行快得多。

第二列可以决定第一列值相同的行的顺序。例如若 date_key 是第一排序键，把 product_sk 作为第二排序键就合理——这样同一天对同一商品的所有销售在存储中相邻。这有助于那些需要在某日期范围内按商品分组或过滤销售的查询。

排序还有助于压缩列。如果首要排序列没有许多不同的值，排序后该列将出现长串重复值——简单的游程长度编码（就像图 4-8 中位图的那种）能把该列压缩到几 KB——即便表有数十亿行。

这种压缩效果对首要排序键最强；第二、第三排序键较为混杂，不会有那么长的重复串。位于排序优先级更靠后的列基本是随机出现的，所以可能压缩得没那么好。但前几列被排序总体上仍然是收益。

写入列式存储

我们在"事务处理与分析处理的特征"（第 5 页）看到，数据仓库的读取主要由"对大量行做聚合"组成。列式存储、压缩与排序都有助于让这些读查询更快。

数据仓库中的写入往往是数据的批量导入，常通过 ETL 完成。在列式存储下，把单行写到一张已排序表的中间会非常低效——因为你得从插入位置往后重写所有压缩列。然而一次批量写入许多行，能把重写这些列的成本摊销开来，使其变得高效。

常见做法是用日志结构方法批量写入。所有写入先到一个行式、有序、位于内存中的存储。当积累到足够多写入时，再与磁盘上列编码的文件合并，并以批量方式写到新的不可变文件。由于旧文件保持不可变、新文件一次写完，对象存储很适合存放它们。

查询要同时检查磁盘上的列数据与内存中的近期写入，并把两者结合。查询执行引擎对用户隐藏了这一区别。从分析师的视角看，被插入、更新或删除所修改的数据会立刻反映在后续查询中。Snowflake、Vertica、Apache Pinot、Apache Druid 等许多数据库都这么做 [61, 63, 64, 76]。

查询执行：编译与向量化

一条复杂的分析 SQL 查询会被分解为一份查询计划（query plan），由多个被称为*算子（operators）*的阶段组成，可能跨多台机器分布以并行执行。查询规划器可通过选择"用哪些算子、按何顺序执行、每个算子在哪里运行"做大量优化。

在每个算子内部，查询引擎可能要对一列中的值做各种处理，如找出值属于某集合的所有行（也许作为连接的一部分），或检查值是否大于 15。该查询引擎也可能要为同一行查看多列——例如找出产品是"香蕉"且门店是某具体感兴趣门店的所有销售事务。

对那些必须扫描数百万行的数据仓库查询，我们不仅要操心从磁盘读多少数据，还要操心执行复杂算子需要多少 CPU 时间。最简单的一种算子就像编程语言的解释器：在每行迭代时，查阅一份代表查询的数据结构，决定要在哪些列上做哪些比较或计算。可惜对许多分析目标这太慢。要高效执行查询，已出现两种替代做法 [77]：

查询编译 ：查询引擎接收 SQL 查询并生成执行它的代码。代码逐行迭代，查看感兴趣列里的值，做必要的比较或计算，若条件满足则把必要的值复制到输出缓冲。然后把生成的代码编译为机器码（常用现成的编译器如 LLVM），并对已加载到内存的列编码数据运行。这种代码生成做法类似于 Java 虚拟机（JVM）等运行时所用的即时（JIT）编译。

向量化处理 ：查询是被解释而非编译的，但通过对每列以批的方式处理多个值来加速——而非逐行迭代。一组预定义算子被内置进数据库；我们可以向其传入参数并取回一批结果 [50, 73]。

例如，可以把 product_sk 列与某商品 ID（如"香蕉"）传给一个相等算子，得到一个位图（输入列每个值占一位，匹配该 ID 时为 1）。再把 store_sk 列与感兴趣门店的 ID 传给同一相等算子，得到另一个位图。最后把两个位图传给按位 AND 算子（如图 4-9 所示）；结果是一份对所有"门店里香蕉的销售"行为 1 的位图。

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

图示文字描述： 图示 product_sk = 30: 5,4,3,3 → 0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0；store_sk = 3: 4,1,1,2,5,3 → 0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,1,1,0,0；与运算结果 → 0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0；游程压缩 6,2,5,2。

两种做法的实现方式差别很大，但都在实践中被广泛使用 [77]。两者都能通过利用现代 CPU 的特性获得很好的性能：

• 优先顺序内存访问而非随机访问，以减少缓存未命中 [78]
• 把大量工作放在紧凑的内层循环中（即少量指令、不带函数调用），让 CPU 指令流水线保持繁忙、避免分支预测错误
• 利用并行——多线程与单指令多数据（SIMD）指令 [79, 80]
• 直接操作压缩数据，无需先解码到独立内存中——省去内存分配与复制成本

物化视图与数据立方

我们之前在"物化与更新时间线"（第 35 页）见过物化视图：在关系数据模型中它是一种表状对象，其内容是某查询的结果。物化视图是查询结果的实际副本，写到磁盘上；虚拟视图只是书写查询的快捷方式。从虚拟视图读取时，SQL 引擎会把它展开为底层查询并即时处理。

底层数据变化时，物化视图也要相应更新。某些数据库可自动完成这件事，也有 Materialize 这样的专门系统在维护物化视图 [81]。"维护物化视图"（第 516 页）会回到此话题。这种更新意味着写入要做更多工作，但物化视图能在反复执行同样查询的负载下改进读性能。

*物化聚合（Materialized aggregates）*是对数据仓库有用的一类物化视图。如前所述，数据仓库查询常涉及聚合函数，如 SQL 的 COUNT、SUM、AVG、MIN、MAX。如果同样的聚合被许多查询使用，每次都对原始数据"嚼一遍"未免浪费。何不缓存查询最常用的某些计数或求和？数据立方（data cube）——也称 OLAP cube——通过创建按不同维度分组的聚合网格来做这件事 [82]。图 4-10 给出一例。

图 4-10. 数据立方的两个维度，按求和聚合数据

图示文字描述： 图示一张二维网格，纵向为 date_key (260101, 260102, 260103, 260104...)，横向为 product_sk (32, 33, 34, 35..., total)。每格含该日期-商品组合下 net_price 的 SUM 值（如 260101 列 32 的 149.60，列 33 的 31.01，行 total 40710.53；列 32 的 total 14967.09 等）。两侧示例 SQL: SELECT SUM(net_price) FROM fact_sales WHERE date_key=260101 AND product_sk=32；以及 WHERE date_key=260101；以及 WHERE product_sk=32。

设事实只有两个维度表的外键；图 4-10 中是 date_key 与 product_sk。可以画一张二维表，一边是日期，另一边是商品。每格含某属性（如 net_price）在该日期-商品组合下所有事实的聚合（如 SUM）。然后可以沿任一行或任一列继续应用同一聚合，得到沿一个维度被消去后的汇总（如不论日期、对该商品的销售，或不论商品、对该日期的销售）。

一般而言，事实通常有不止两个维度。在图 3-5 中有五个维度：date、product、store、promotion、customer。一个五维超立方体看起来什么样难以想象，但原理一样：每格含某具体 date–product–store–promotion–customer 组合的销售。这些值可沿每个维度反复汇总。

物化数据立方的优势是某些查询会变得非常快，因为它们已经被有效地预先计算。例如想知道每家店昨天的总销售，只需查看相应维度上的总数——不必扫描数百万行。

劣势是数据立方不像查原始数据那么灵活。例如没有办法计算"超过 100 美元的商品在销售中所占的比例"，因为价格不是维度之一。多数数据仓库因此尽量保留尽可能多的原始数据，把数据立方等聚合仅作为某些查询的性能加速器。

多维与全文索引

本章上半段看到的 B 树与 LSM 树允许对单个属性做范围查询；例如键是用户名时，可用作索引高效找出所有以 L 开头的名字。但有时按单一属性搜索还不够。

最常见的多列索引是串联索引（concatenated index）——通过把一列接到另一列的方式，把若干字段简单合并到一个键里（索引定义指明顺序）。这就像旧式纸质电话簿——它给出 (lastname, firstname) 到电话号码的索引。由于排序顺序，索引可以用来找姓某姓的所有人，或找特定 lastname-firstname 组合的所有人。但要找特定名（firstname）的所有人，索引就没用了。

另一方面，多维索引让你能同时按多列查询。这对地理空间数据尤为重要。例如餐厅搜索网站的数据库可能含每家餐厅的纬度与经度。当用户在地图上查看餐厅时，网站需在用户当前可视矩形地图区域内搜索所有餐厅。这要求一种二维范围查询，例如：

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

在 latitude 与 longitude 上的串联索引并不能高效回答这种查询。索引可以给出一段纬度范围内的所有餐厅（任意经度），或一段经度范围内的所有餐厅（介于南北极之间任意位置），但不能同时给出两者。

一个选择是用空间填充曲线把二维位置转换为单一数值，再用普通 B 树索引 [83]。更常见的是用专门的空间索引——如 *R 树（R-trees）*或 Bkd 树 [84]——它们划分空间，使得相邻数据点更可能位于同一子树中。例如 PostGIS 利用 PostgreSQL 的 Generalized Search Tree 设施把地理空间索引实现为 R 树 [85]。也可以使用等距的三角形、方形或六边形格子 [86]。

多维索引并不只用于地理位置。例如电商网站可在 (red, green, blue) 三维上用三维索引搜某色彩范围内的产品；天气观测库可在 (date, temperature) 上建二维索引以高效搜索某年中温度在 25 °C 到 30 °C 之间的所有观测。在一维索引下你要么扫该年所有记录（不论温度）再按温度过滤，要么反之。二维索引则能同时按时间戳与温度缩小结果 [87]。

全文搜索

全文搜索让你能用"可能出现在文本任何位置"的关键词来搜索一组文本文档（网页、产品描述等）[88]。信息检索是一个庞大的专门主题，常涉及语言相关处理；例如多种亚洲语言书写时词与词之间没有空格或标点，把文本切成词需要一个模型来指明哪些字符序列构成一个词。全文搜索还常涉及匹配相似但不完全相同的词（处理拼写错误或语法形式差异）以及同义词。这些问题超出本书范围。

但在本质上，可以把全文搜索视为另一种多维查询。这里，文本中可能出现的每个词（一个词项，term）都是一个维度。含词项 x 的文档在维度 x 上取值 1，不含 x 的取 0。搜索提到"red apples"的文档意味着同时在 red 维度找 1 且在 apples 维度也找 1 的文档。这样维度数可能非常多。

许多搜索引擎用以回答此类查询的数据结构叫倒排索引（inverted index）。这是一种键值结构：键是词项，值是含该词项的所有文档 ID 的列表（postings list）。如果文档 ID 是顺序数字，postings list 还能像图 4-8 那样以稀疏位图表示——位图中第 n 位若为 1，即表示 ID 为 n 的文档含词项 x [89]。

要找含词项 x 与 y 的所有文档，就像数据仓库中查"满足两条件的行"的向量化查询（图 4-9）：加载 x 与 y 的两个位图，计算它们的按位 AND。即便位图被游程长度编码，这也极为高效。

例如 Lucene——Elasticsearch 与 Solr 所用的全文索引引擎——就是这样做的 [90]。它把"词项→postings list"的映射保存到 SSTable 风格的有序文件中，并用本章前面讲过的同样的日志结构方法在后台合并 [91]。PostgreSQL 的 GIN 索引类型也用 postings list 支持全文检索以及对 JSON 文档内部建索引 [92, 93]。

除了把文本切成词，还有一种做法是找所有长度为 n 的子串，称为 n-grams。例如字符串 hello 的三元组（n=3）是 hel、ell、llo。如果建一个含所有三元组的倒排索引，就能用至少 3 个字符的任意子串搜索文档。三元组索引甚至允许在搜索查询里使用正则；不利之处是它们相当大 [94]。

要应付文档或查询中的拼写错误，Lucene 能在某编辑距离内搜词（编辑距离为 1 表示一个字符被增、删、替）[95]。它通过把词项集合作为键中字符上的有限状态自动机存储（类似字典树）[96]，再把它转换成支持给定编辑距离内词搜索的 Levenshtein 自动机来实现这件事 [97]。

向量嵌入

语义搜索超越同义词与拼写，试图理解文档的概念与用户的意图。它正成为 AI 应用的重要组成部分，例如检索增强生成（RAG）——把搜索结果纳入大语言模型（LLM）的输出。例如若你的帮助页里有一页叫"取消订阅"，用户搜"如何关闭账户"或"终止合同"时也应能找到此页——它们在语义上接近，尽管用词完全不同。

要理解文档的语义——其含义——语义搜索索引使用嵌入模型把文本文档翻译成由浮点数组成的向量，称为向量嵌入（vector embedding）。这一过程通常借助 LLM 完成。该向量代表多维空间中的一个点，每个浮点值代表文档沿一个维度的位置。当输入文档语义相似时，嵌入模型生成的向量在该多维空间中彼此接近。

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

例如关于农业的维基百科页面的三维向量嵌入可能是 [0.38, 0.83, 0.41]。关于蔬菜的页面会很接近，嵌入也许是 [0.36, 0.64, 0.67]。关于星型模式的页面嵌入可能是 [0.85, 0.10, -0.52]，相对远些。我们能看出前两个向量比第三个更接近。

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

许多早期嵌入模型——如 Word2Vec [98]、BERT [99] 与 GPT [100]——处理文本数据。这些模型通常实现为神经网络。研究者后来也为视频、音频与图像创建了嵌入模型。最近，模型架构变得多模态：单一模型能为多种模态（如文本与图像）生成向量嵌入。

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

向量索引存放一组文档的向量嵌入。要查询索引，传入查询的向量嵌入，索引返回向量与查询向量最接近的文档。因为我们之前看到的 R 树在维度很多时表现不佳，会用专门的向量索引，例如：

Flat 索引（扁平） ：向量原样存放在索引中。查询必须读每个向量并算出它到查询向量的距离。Flat 索引精确，但算距离慢。

Inverted file（IVF）索引 ：把向量空间聚到若干分区（称为centroids）以减少需要比较的向量数量。IVF 索引比 flat 快，但只能给出近似结果；查询和文档可能落到不同分区，即便它们距离接近。在 IVF 索引上查询时先定义探针（probes）——简单地说就是要检查的分区数量。使用更多探针的查询更准确但更慢，因为要比较更多向量。

Hierarchical Navigable Small World（HNSW）索引 ：HNSW 索引保留向量空间的多个层，如图 4-11 所示。每层用一个图表示，节点为向量，边表示与邻近向量的相邻关系。查询从最顶层（节点少）开始定位最近向量。然后下移到下一层的同一节点，沿边找更接近查询向量的向量；下层连接更密。过程持续到最底层。和 IVF 一样，HNSW 是近似的。

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

图示文字描述： 图示三层（layer 2 / layer 1 / layer 0）；每层都画成图，节点是向量，边连邻近向量；query vector 从最顶层节点处出发，沿层下移，每层定位最近节点；最底层 layer 0 节点最稠密。

许多流行的向量数据库都实现了 IVF 与 HNSW。Facebook 的 Faiss 库提供两者的若干变体 [101]，PostgreSQL 的 pgvector 也都支持 [102]。IVF 与 HNSW 算法的全部细节超出本书范围，但其论文是优秀的参考资料 [103, 104]。

小结

本章我们试图刨清数据库如何执行存储与检索的根。当你把数据存进数据库时发生了什么？之后你查询数据时它做了什么？

"运营系统与分析系统"（第 3 页）引入了事务处理（OLTP）与分析（OLAP）的区分。本章我们看到 OLTP 优化的存储引擎与分析优化的非常不同：

• OLTP 系统针对大量请求做优化，每个请求读写少量记录，需要快速响应。这些记录通常通过主键或二级索引访问，索引一般是从键到记录的有序映射，也支持范围查询。
• 数据仓库与类似分析系统则针对扫描大量记录的复杂读查询做优化。它们普遍使用列式存储布局并压缩，以尽可能减少此类查询从磁盘读出的数据量；并通过 JIT 编译查询或向量化来尽量减少处理数据的 CPU 时间。

在 OLTP 一侧，我们看到了来自两种主要思路的存储引擎：

• 日志结构方法，允许追加文件并删除过时文件，但不就地更新已写文件。SSTable、LSM 树、RocksDB、Cassandra、HBase、ScyllaDB、Lucene 等都属此组。一般而言，日志结构存储引擎的写入吞吐高。
• 就地更新方法，把磁盘视作可被覆盖的固定大小页集合。B 树是这种哲学最常见的例子，被用于所有主要关系型 OLTP 数据库与许多非关系型数据库。经验是 B 树在读取上更佳，能提供更高的读吞吐与更低的响应时间。

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

作为应用开发者，掌握这些存储引擎内部知识能让你更清楚哪种工具最适合你的应用。如果你需要调整数据库的调参参数，这些理解能让你设想"取较高或较低的值会有什么影响"。

虽然本章并不能让你成为某具体存储引擎调优的专家，但希望它给了你足够的词汇与思想，让你能读懂你所选数据库的文档。

参考文献

[1] Nikolay Samokhvalov. "How Partial, Covering, and Multicolumn Indexes May Slow Down UPDATEs in PostgreSQL." postgres.ai, October 2021. 归档于 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.

[3] Evan Jones. "Why Databases Use Ordered Indexes but Programming Uses Hash Tables." evanjones.ca, December 2019. 归档于 perma.cc/NJX8-3ZZD

[4] Branimir Lambov. "CEP-25: Trie-Indexed SSTable Format." cwiki.apache.org, November 2022. 归档于 perma.cc/HD7W-PW8U

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

[6] Branimir Lambov. "Trie Memtables in Cassandra." Proceedings of the VLDB Endowment, volume 15, issue 12, pages 3359–3371, August 2022.

[7] Dhruba Borthakur. "The History of RocksDB." rocksdb.blogspot.com, November 2013. 归档于 perma.cc/Z7C5-JPSP

[8] Matteo Bertozzi. "Apache HBase I/O—HFile." blog.cloudera.com, June 2012. 归档于 perma.cc/U9XH-L2KL

[9] Fay Chang 等。"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 等。"The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica, volume 33, issue 4, pages 351–385, June 1996.

[11] Mendel Rosenblum, 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.

[12] Michael Armbrust 等。"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.

[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.

[14] Adam Kirsch, Michael Mitzenmacher. "Less Hashing, Same Performance: Building a Better Bloom Filter." Random Structures & Algorithms, volume 33, issue 2, pages 187–218, September 2008.

[15] Thomas Hurst. "Bloom Filter Calculator." hur.st, September 2023. 归档于 perma.cc/L3AV-6VC2

[16] Chen Luo, Michael J. Carey. "LSM-Based Storage Techniques: a Survey." The VLDB Journal, volume 29, pages 393–418, July 2019.

[17] Subhadeep Sarkar, Manos Athanassoulis. "Dissecting, Designing, and Optimizing LSM-Based Data Stores." Tutorial at ACM International Conference on Management of Data (SIGMOD), June 2022. 幻灯片归档于 perma.cc/93B3-E827

[18] Mark Callaghan. "Name That Compaction Algorithm." smalldatum.blogspot.com, August 2018. 归档于 perma.cc/CN4M-82DY

[19] Prashanth Rao. "Embedded Databases (1): The Harmony of DuckDB, KùzuDB and LanceDB." thedataquarry.com, August 2023. 归档于 perma.cc/PA28-2R35

[20] Hacker News discussion. "Bluesky Migrates to Single-Tenant SQLite." news.ycombinator.com, October 2023. 归档于 perma.cc/69LM-5P6X

[21] Rudolf Bayer, Edward M. McCreight. "Organization and Maintenance of Large Ordered Indices." Boeing Scientific Research Laboratories, report no. 20, July 1970.

[22] Douglas Comer. "The Ubiquitous B-Tree." ACM Computing Surveys, volume 11, issue 2, pages 121–137, June 1979.

[23] Alex Miller. "Torn Write Detection and Protection." transactional.blog, April 2025. 归档于 perma.cc/G7EB-33EW

[24] C. Mohan, 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.

[25] Hironobu Suzuki. "The Internals of PostgreSQL." interdb.jp, 2017. 归档于 archive.org

[26] Howard Chu. "LDAP at Lightning Speed." At Build Stuff '14, November 2014. 归档于 perma.cc/GB6Z-P8YH

[27] Manos Athanassoulis 等。"Designing Access Methods: The RUM Conjecture." At 19th International Conference on Extending Database Technology (EDBT), March 2016.

[28] Ben Stopford. "Log Structured Merge Trees." benstopford.com, February 2015. 归档于 perma.cc/E5BV-KUJ6

[29] Mark Callaghan. "The Advantages of an LSM vs. a B-Tree." smalldatum.blogspot.co.uk, January 2016. 归档于 perma.cc/3TYZ-EFUD

[30] Oana Balmau 等。"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 等。"RocksDB Tuning Guide." github.com, 2023. 归档于 perma.cc/UNY4-MK6C

[32] Gabriel Haas, Viktor Leis. "What Modern NVMe Storage Can Do, and How to Exploit It." Proceedings of the VLDB Endowment, volume 16, issue 9, pages 2090–2102, May 2023.

[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. 归档于 perma.cc/7TMZ-TAPU

[35] Alibaba Cloud Storage Team. "Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2)." alibabacloud.com, January 2019. 归档于 archive.org

[36] Xiao-Yu Hu, Robert Haas. "The Fundamental Limit of Flash Random Write Performance." domino.research.ibm.com, March 2010. 归档于 perma.cc/8JUL-4ZDS

[37] Lanyue Lu 等。"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. 归档于 perma.cc/NT4S-DK7T

[39] Tomas Vondra. "On the Impact of Full-Page Writes." 2ndquadrant.com, November 2016. 归档于 perma.cc/7N6B-CVL3

[40] Mark Callaghan. "Read, Write & Space Amplification—B-Tree vs. LSM." smalldatum.blogspot.com, November 2015. 归档于 perma.cc/S487-WK5P

[41] Mark Callaghan. "Choosing Between Efficiency and Performance with RocksDB." At Code Mesh, November 2016

[42] Subhadeep Sarkar 等。"Enabling Timely and Persistent Deletion in LSM-Engines." ACM Transactions on Database Systems, volume 48, issue 3, article no. 8, August 2023.

[43] Lukas Fittl. "Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication." pganalyze.com, April 2025. 归档于 perma.cc/XY6T-LTPX

[44] Drew Silcock. "How Postgres Stores Data on Disk—This One's a Page Turner." drew.silcock.dev, August 2024. 归档于 perma.cc/8K7K-7VJ2

[45] Joe Webb. "Using Covering Indexes to Improve Query Performance." simple-talk.com, September 2008. 归档于 perma.cc/6MEZ-R5VR

[46] Michael Stonebraker 等。"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. 归档于 perma.cc/B9SF-SK5G

[48] Stephen M. Rumble, Ankita Kejriwal, 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 等。"OLTP Through the Looking Glass, and What We Found There." At ACM International Conference on Management of Data (SIGMOD), June 2008.

[50] Per-Åke Larson 等。"Enhancements to SQL Server Column Stores." At ACM International Conference on Management of Data (SIGMOD), June 2013.

[51] Franz Färber 等。"The SAP HANA Database—An Architecture Overview." IEEE Data Engineering Bulletin, volume 35, issue 1, pages 28–33, March 2012. 归档于 perma.cc/H2WC-YQZY

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

[53] Adam Prout 等。"Cloud-Native Transactions and Analytics in SingleStore." At ACM International Conference on Management of Data (SIGMOD), June 2022.

[54] Tino Tereshko, Jordan Tigani. "BigQuery Under the Hood." cloud.google.com, January 2016. 归档于 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. 归档于 perma.cc/6L2M-GTJX

[56] Michael Stonebraker 等。"C-Store: A Column-Oriented DBMS." At 31st International Conference on Very Large Data Bases (VLDB), September 2005.

[57] Julien Le Dem. "Dremel Made Simple with Parquet." blog.x.com, September 2013. 归档于 archive.org

[58] Sergey Melnik 等。"Dremel: Interactive Analysis of Web-Scale Datasets." At 36th International Conference on Very Large Data Bases (VLDB), September 2010.

[59] Joe Kearney. "Understanding Record Shredding: Storing Nested Data in Columns." joekearney.co.uk, December 2016. 归档于 perma.cc/ZD5N-AX5D

[60] Jamie Brandon. "A Shallow Survey of OLAP and HTAP Query Engines." scattered-thoughts.net, September 2023. 归档于 perma.cc/L3KH-J4JF

[61] Benoit Dageville 等。"The Snowflake Elastic Data Warehouse." At ACM International Conference on Management of Data (SIGMOD), June 2016.

[62] Mark Raasveldt, Hannes Mühleisen. "Data Management for Data Science Towards Embedded Analytics." At 10th Conference on Innovative Data Systems Research (CIDR), January 2020. 归档于 perma.cc/65G2-NYDT

[63] Jean-François Im 等。"Pinot: Realtime OLAP for 530 Million Users." At ACM International Conference on Management of Data (SIGMOD), May 2018.

[64] Fangjin Yang 等。"Druid: A Real-Time Analytical Data Store." At ACM International Conference on Management of Data (SIGMOD), June 2014.

[65] Chunwei Liu 等。"Deep Dive into Common Open Formats for Analytical DBMSs." Proceedings of the VLDB Endowment, volume 16, issue 11, pages 3044–3056, July 2023.

[66] Xinyu Zeng 等。"An Empirical Evaluation of Columnar Storage Formats." Proceedings of the VLDB Endowment, volume 17, issue 2, pages 148–161.

[67] Weston Pace. "Lance v2: A Columnar Container Format for Modern Data." blog.lancedb.com, April 2024. 归档于 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, 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, Mike Freedman. "Building Columnar Compression for Large PostgreSQL Databases." timescale.com, March 2024. 归档于 perma.cc/7KTF-V3EH

[73] Daniel J. Abadi 等。"The Design and Implementation of Modern Column-Oriented Database Systems." Foundations and Trends in Databases, volume 5, issue 3, pages 197–280, December 2013.

[74] Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser. "Consistently Faster and Smaller Compressed Bitmaps with Roaring." Software: Practice and Experience, volume 46, issue 11, pages 1547–1569, November 2016.

[75] Jaz Volpert. "An Entire Social Network in 1.6GB (GraphD Part 2)." jazco.dev, April 2024. 归档于 perma.cc/L27Z-QVMG

[76] Andrew Lamb 等。"The Vertica Analytic Database: C-Store 7 Years Later." Proceedings of the VLDB Endowment, volume 5, issue 12, pages 1790–1801, August 2012.

[77] Timo Kersten 等。"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.

[78] Forrest Smith. "Memory Bandwidth Napkin Math." forrestthewoods.com, February 2020. 归档于 perma.cc/Y8U4-PS7N

[79] Peter Boncz, Marcin Zukowski, Niels Nes. "MonetDB/X100: Hyper-Pipelining Query Execution." At 2nd Biennial Conference on Innovative Data Systems Research (CIDR), January 2005. 归档于 perma.cc/R4KF-QKHF

[80] Jingren Zhou, Kenneth A. Ross. "Implementing Database Operations Using SIMD Instructions." At ACM International Conference on Management of Data (SIGMOD), June 2002.

[81] Kevin Bartley. "OLTP Queries: Transfer Expensive Workloads to Materialize." materialize.com, August 2024. 归档于 perma.cc/4TYM-TYD8

[82] Jim Gray 等。"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.

[83] Frank Ramsak 等。"Integrating the UB-Tree into a Database System Kernel." At 26th International Conference on Very Large Data Bases (VLDB), September 2000.

[84] Octavian Procopiuc 等。"Bkd-Tree: A Dynamic Scalable kd-Tree." At 8th International Symposium on Spatial and Temporal Databases (SSTD), July 2003.

[85] Joseph M. Hellerstein, Jeffrey F. Naughton, 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. 归档于 archive.org

[87] Robert Escriva, Bernard Wong, Emin Gün Sirer. "HyperDex: A Distributed, Searchable Key-Value Store." At ACM SIGCOMM Conference, August 2012.

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

[89] Jianguo Wang 等。"An Experimental Study of Bitmap Compression vs. Inverted List Compression." At ACM International Conference on Management of Data (SIGMOD), May 2017.

[90] Adrien Grand. "What Is in a Lucene Index?" At Lucene/Solr Revolution, November 2013. 归档于 perma.cc/Z7QN-GBYY

[91] Michael McCandless. "Visualizing Lucene's Segment Merges." blog.mikemccandless.com, February 2011. 归档于 perma.cc/3ZV8-72W6

[92] Lukas Fittl. "Understanding Postgres GIN Indexes: The Good and the Bad." pganalyze.com, December 2021. 归档于 perma.cc/V3MW-26H6

[93] Jimmy Angelakos. "The State of (Full) Text Search in PostgreSQL 12." At FOSDEM, February 2020. 归档于 perma.cc/J6US-3WZS

[94] Alexander Korotkov. "Index Support for Regular Expression Search." At PGConf.EU Prague, October 2012. 归档于 perma.cc/5RFZ-ZKDQ

[95] Michael McCandless. "Lucene's FuzzyQuery Is 100 Times Faster in 4.0." blog.mikemccandless.com, March 2011. 归档于 perma.cc/E2WC-GHTW

[96] Steffen Heinz, Justin Zobel, 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.

[97] Klaus U. Schulz, Stoyan Mihov. "Fast String Correction with Levenshtein Automata." International Journal on Document Analysis and Recognition, volume 5, issue 1, pages 67–85, November 2002.

[98] Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean. "Efficient Estimation of Word Representations in Vector Space." arXiv:1301.3781, September 2013.

[99] Jacob Devlin, Ming-Wei Chang, Kenton Lee, 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, June 2019.

[100] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever. "Improving Language Understanding by Generative Pre-Training." openai.com, June 2018. 归档于 perma.cc/5N3C-DJ4C

[101] Matthijs Douze, Maria Lomeli, Lucas Hosseini. "Faiss Indexes." github.com, August 2024. 归档于 perma.cc/2EWG-FPBS

[102] Varik Matevosyan. "Understanding pgvector's HNSW Index Storage in Postgres." lantern.dev, August 2024. 归档于 perma.cc/B2YB-JB59

[103] Dmitry Baranchuk, Artem Babenko, Yury Malkov. "Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors." At European Conference on Computer Vision (ECCV), September 2018.

[104] Yury A. Malkov, 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.