数据库系统

把 20 万个用户存进 SQLite，按邮箱查一个人要 8 毫秒；加一行 CREATE INDEX，同一个查询变成 0.014 毫秒，快了五百多倍。再做一个实验：转账写到一半把进程直接杀掉，重新打开数据库，钱一分没少。这两件事分别对应数据库要回答的两个问题：数据大到放不进内存时怎么查得快，以及在崩溃和并发下怎么保证不丢不乱。

前置：文件系统与 IO、内存层次与缓存、数据结构（树）

页：数据库和磁盘打交道的单位

最朴素的存法是把每行写成一行 CSV 追加到文件里。查询时从头扫到尾，更新一行就得重写它之后的所有内容。数据库不这么做，原因在硬件：磁盘（包括 SSD）按块读写，随机读一次 4 KB 和读 4 字节代价几乎一样，而一次 SSD 随机读要几十微秒，是内存访问的上千倍（见 内存层次与缓存）。所以数据库把文件切成固定大小的页（page，SQLite 默认 4 KB，PostgreSQL 8 KB，MySQL InnoDB 16 KB），所有读写都以页为单位，目标是让每次 IO 都尽量带回有用的数据。

页内最常见的组织方式是槽式页（slotted page）：页头之后是一个从前往后长的槽数组，记录每条元组在页内的偏移；元组本身从页尾往前填。两者相向生长，中间是空闲空间。这样变长的行可以紧凑存放，删除和整理碎片时只需挪动元组、改槽里的偏移，外部引用的”（页号，槽号）“这个记录 ID 保持不变。

一张表的所有页合起来叫堆文件，行没有特定顺序。SQLite 稍有不同，表本身就组织成一棵以 rowid 为键的 B 树。看看 20 万行占了多少页：

import sqlite3, random
db = sqlite3.connect("t.db")
db.execute("CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT, age INT)")
random.seed(0)
db.executemany("INSERT INTO users(email, age) VALUES (?, ?)",
               ((f"u{i}@x.com", random.randint(18, 80)) for i in range(200_000)))
db.commit()
print("page_size", db.execute("PRAGMA page_size").fetchone()[0],
      "page_count", db.execute("PRAGMA page_count").fetchone()[0])

page_size 4096 page_count 1152

1152 页，约 4.5 MB，平均每页放 170 多行。

页内按行存（一行的所有列挨在一起）叫行存，适合”取出一个用户的全部信息”这类事务型（OLTP）负载。分析型（OLAP）查询常常只碰一两列却扫全表，行存会把无关列也读进来。列存把每列单独存成连续的页，只读需要的列，同类型数据还好压缩，ClickHouse、Parquet 都是列存。

停一下，检查理解单选

一张 100 列的宽表，分析查询 SELECT AVG(price) FROM orders 在列存上通常比行存快很多。主要原因是什么？

列存会为每一列自动建 B+ 树索引列存只需读取 price 这一列的页，而且同类型数据压缩率高，IO 量少得多列存把数据全部常驻内存行存不支持聚合函数，需要先转换格式

检查答案

Buffer pool：数据库自己管的缓存

每次访问都去读磁盘太慢，自然想到把常用的页缓存在内存里。数据库在启动时申请一大块内存，切成与页同样大小的帧（frame），这就是 buffer pool。一张页表记录”哪个页号在哪个帧”。上层要访问某页时调用 fetch(page_id)：命中就直接返回；没命中就挑一个帧换出，如果被换出的页被改过（dirty），先写回磁盘，再把目标页读进来。

正在被使用的页不能被换出，所以每帧有一个 pin 计数，用完要 unpin。换出谁由替换策略决定。LRU 是常见选择，但它怕顺序扫描：一次全表扫描会把所有页依次读一遍，把真正的热点页全挤出去，而这些扫描页以后再也不会被访问。所以实际系统会做改进，比如 LRU-K 看最近第 K 次访问的时间，只访问过一次的页优先淘汰；或者 Clock 用引用位近似 LRU。

为什么不直接 mmap 整个文件、交给操作系统（见 虚拟内存）？因为数据库更清楚自己的访问模式，而且必须控制脏页什么时候写回：崩溃恢复要求日志先于数据落盘，操作系统却可能随时刷回一个脏页。所以成熟数据库都自管 buffer pool。

停一下，检查理解单选

数据库的 buffer pool 为什么不简单地使用纯 LRU 替换策略？

LRU 需要记录每个页的访问时间，内存开销太大，无法实现一次大的顺序扫描会把热点页全部挤出，而扫描过的页之后不会再用LRU 会优先淘汰脏页，导致写回过于频繁LRU 不支持 pin，正在使用的页可能被换出

检查答案

B+ 树：把查找从扫描变成三次 IO

现在按邮箱找一个人。没有索引，只能把 1152 页全部读一遍：

q = "SELECT age FROM users WHERE email = 'u123456@x.com'"
print(db.execute("EXPLAIN QUERY PLAN " + q).fetchall()[0][3], f"{bench():.2f} ms")
db.execute("CREATE INDEX idx_email ON users(email)")
print(db.execute("EXPLAIN QUERY PLAN " + q).fetchall()[0][3], f"{bench():.3f} ms")
print("page_count", db.execute("PRAGMA page_count").fetchone()[0])
print(db.execute("EXPLAIN QUERY PLAN SELECT * FROM users WHERE email LIKE '%456@x.com'").fetchall()[0][3])

SCAN users 8.18 ms
SEARCH users USING INDEX idx_email (email=?) 0.014 ms
page_count 2200
SCAN users

（bench() 取 20 次平均。）SCAN 是全表扫描，SEARCH ... USING INDEX 是走索引。代价是文件从 1152 页涨到 2200 页，且每次写入都要维护索引。最后一行说明索引不是万能的：LIKE '%456@x.com' 的前缀不确定，有序结构帮不上忙，只能退回扫描。

这个索引是一棵 B+ 树。为什么不用二叉搜索树？二叉树每个节点只有 2 个孩子，20 万个键高度约 18，每下一层都可能是一次随机 IO。B+ 树让每个节点就是一页，一页里塞几百个键，于是扇出（fanout）有几百，树变得又矮又胖：

• 内部节点只存键和子页指针，用来导航；所有真实数据（或指向行的记录 ID）都在叶子里。
• 叶子之间用指针串成有序链表，所以范围查询 WHERE age BETWEEN 20 AND 30 找到起点后顺着链表扫就行。
• 插入时叶子满了就分裂成两半，把中间键推给父节点；父节点满了继续往上分裂。树只会从根部长高，所以所有叶子永远在同一深度，查找代价稳定。删除时节点过空则与兄弟合并或借键。

算一下：键 8 字节加指针 8 字节，4 KB 页的扇出约 250。三层能索引 250^3 ≈ 1500 万个键，四层接近 40 亿。根和第二层总是热的，常驻 buffer pool，所以一次点查实际只要一两次磁盘 IO。

索引的另一面是代价：多一个索引，写入就多维护一棵树，占更多空间；索引列选择性低（比如只有男女两个值的性别列）时，走索引后回表随机读，可能比直接扫描更慢。哈希索引等值查找 O(1)，但不支持范围和排序，所以默认索引是 B+ 树。

停一下，检查理解多选

关于 B+ 树索引，下列哪些说法正确？

每个节点占一页、扇出几百，所以千万级的数据通常只有 3–4 层叶子节点串成链表，因此适合范围查询和 ORDER BY建了索引的列，任何 WHERE 条件都能走索引加速B+ 树插入时从叶子向下生长，所以不同叶子的深度可能不同

检查答案

查询执行与优化：同一句 SQL，很多种算法

SQL 是声明式的，只说”要什么”，不说”怎么做”。数据库先把 SQL 解析成关系代数树（扫描、过滤、投影、连接、聚合），再由优化器挑一个执行计划，交给执行器跑。

执行器最经典的组织方式是火山模型（iterator model）：每个算子实现一个 next()，调用一次吐出一行。顶层算子不断调 next()，请求一层层往下拉，数据一行行往上流。它简单、易组合，缺点是每行都要穿过多层函数调用，所以分析型数据库改用一次返回一批列式数据的向量化执行。

连接（join）是最贵的操作，也是算法差别最大的地方。设外表 R 有 M 页、r 行，内表 S 有 N 页：

算法	思路	IO 代价（大致）	适用
嵌套循环	对 R 的每行扫一遍 S	逐行是 M + r·N，按块是 M + M·N	小表，或内表连接列有索引
索引嵌套循环	对 R 的每行在 S 的索引上查找	M + r·(索引查找代价)	内表有索引，外表结果少
排序归并	两表按连接键排序后双指针合并	排序代价 + M + N	输入已有序，或需要有序输出
哈希连接	用小表建哈希表，扫大表去探测	约 3(M + N)（需要分区时）	等值连接、无索引的大表

优化器估算每种计划的代价并选最小的：先做与数据无关的规则改写（把过滤条件尽量下推到扫描附近，越早丢弃无关行越好），再基于统计信息（每列的不同值个数、直方图）估计每一步的结果行数，枚举连接顺序和算法。

基数估计是优化器最薄弱的一环（它常假设各列独立），所以查询突然变慢时，先看执行计划：

EXPLAIN QUERY PLAN
SELECT u.name, SUM(o.amt) FROM u JOIN o ON o.uid = u.id WHERE o.amt > 100 GROUP BY u.name;
 
SCAN o
SEARCH u USING INTEGER PRIMARY KEY (rowid=?)
USE TEMP B-TREE FOR GROUP BY

SQLite 选择扫描订单表 o，对每行用主键去 u 里查，这就是索引嵌套循环；分组时临时建了一棵 B 树。

停一下，检查理解单选

两张大表做等值连接，连接列上都没有索引，内存放不下任何一张表。下列哪种算法通常最合适？

逐行嵌套循环连接，因为它不需要额外内存哈希连接，先按连接键把两表分区写到磁盘，再逐个分区建表、探测索引嵌套循环连接先对两表做笛卡尔积再过滤

检查答案

事务：要么全做，要么全不做

转账是两步：A 减 50，B 加 50。如果第一步做完进程崩溃了，钱就凭空消失；如果两个转账同时修改同一个账户，可能有一笔被覆盖。事务把一组操作包装成一个整体，并承诺 ACID：

• 原子性（Atomicity）：要么全部生效，要么全部回滚。
• 一致性（Consistency）：事务前后数据满足约束（比如总额不变）。这主要靠应用逻辑和约束，另外三条是数据库提供的手段。
• 隔离性（Isolation）：并发执行的事务互不干扰，效果如同某种串行顺序。
• 持久性（Durability）：一旦提交，即使马上断电也不会丢。

用 SQLite 实际做一个崩溃实验：子进程开事务给 alice 扣钱，不提交就用 os._exit 直接退出（不做任何清理，接近真实崩溃）：

import sqlite3, subprocess, sys
a = sqlite3.connect("b.db", isolation_level=None)   # 自己控制 BEGIN/COMMIT
a.execute("PRAGMA journal_mode=WAL")
a.execute("CREATE TABLE acct(name TEXT PRIMARY KEY, bal INT)")
a.execute("INSERT INTO acct VALUES ('alice', 100), ('bob', 0)")
crash = """
import sqlite3, os
c = sqlite3.connect('b.db', isolation_level=None)
c.execute('BEGIN'); c.execute("UPDATE acct SET bal = bal - 50 WHERE name='alice'")
os._exit(1)
"""
subprocess.run([sys.executable, "-c", crash])
print("after crash:", a.execute("SELECT * FROM acct").fetchall())

after crash: [('alice', 100), ('bob', 0)]

未提交的修改没有留下痕迹。数据库是怎么做到的，要等到最后一节的日志。先看隔离性。

停一下，检查理解单选

下列哪项不是数据库通过事务机制直接保证的？

提交成功的事务在断电后仍然存在崩溃时执行到一半的事务被完整回滚转账代码里把"减 50"错写成"减 5"时，总额依然正确两个并发事务的效果等价于某种串行执行（在可串行化级别下）

检查答案

并发控制：锁，还是多版本

如果事务一个接一个地执行，隔离性自然成立，但吞吐太低。允许交错执行，就会出现各种异常：读到别人未提交、后来又回滚的数据（脏读）；同一事务内两次读同一行结果不同（不可重复读）；两次按条件查询，第二次多出了别人新插入的行（幻读）；两个事务都基于旧值写，一个覆盖了另一个（丢失更新）。SQL 标准按允许哪些异常定义了四个隔离级别，从读未提交、读已提交、可重复读到可串行化。级别越高，异常越少，并发越受限。

实现可串行化的经典方法是两阶段锁（2PL）：读之前加共享锁，写之前加排他锁；事务分两个阶段，加锁阶段只加不放，一旦开始放锁就不能再加。可以证明这样产生的调度一定等价于某种串行顺序。实际系统用严格 2PL，所有锁到提交时才一起释放，避免别人读到将来会回滚的数据。锁的老问题是死锁（原理见 并发与同步）：T1 锁了 A 等 B，T2 锁了 B 等 A。数据库会维护一张”等待图”定期找环，找到就挑一个事务中止回滚；或者按事务的时间戳规定只许老的等新的（wait-die / wound-wait）来预防。

锁的另一个问题是读写互相阻塞：一个长时间的报表查询会卡住所有写入。现代数据库（PostgreSQL、MySQL InnoDB、Oracle、SQLite 的 WAL 模式）大多采用 MVCC：每次写不覆盖旧值，而是生成一个带时间戳的新版本；每个事务开始时拿一个快照，只看在它开始之前已经提交的版本。于是读不阻塞写，写也不阻塞读。在上面的数据库上实验：

b = sqlite3.connect("b.db", isolation_level=None)
b.execute("BEGIN"); print("b sees:", b.execute("SELECT bal FROM acct WHERE name='bob'").fetchone())
a.execute("BEGIN"); a.execute("UPDATE acct SET bal=bal-30 WHERE name='alice'")
a.execute("UPDATE acct SET bal=bal+30 WHERE name='bob'"); a.execute("COMMIT")
print("b still sees:", b.execute("SELECT bal FROM acct WHERE name='bob'").fetchone())
b.execute("COMMIT")
print("b new txn:", b.execute("SELECT bal FROM acct WHERE name='bob'").fetchone())

b sees: (0,)
b still sees: (0,)
b new txn: (30,)

b 的读事务开着的时候，a 照样完成了转账并提交，没有被阻塞；b 在自己的事务里始终看到开始时的快照，结束后开新事务才看到 30。

MVCC 默认提供的是快照隔离，它防住了脏读、不可重复读，但不是完全的可串行化。经典反例叫写偏斜：医院规定至少一名医生值班，两名医生同时查到”还有两人在班”，各自把自己改成下班，两个事务改的是不同的行，没有冲突，提交后没人值班了。PostgreSQL 的 SERIALIZABLE 级别额外追踪读写依赖来检测它。旧版本要靠后台垃圾回收（如 PostgreSQL 的 VACUUM）清理。

停一下，检查理解多选

关于 2PL 与 MVCC，下列哪些说法正确？

严格 2PL 能保证可串行化，但读写会相互阻塞，并可能死锁MVCC 下长时间运行的只读事务不会阻塞写事务快照隔离能防止所有并发异常，等价于可串行化MVCC 不需要任何垃圾回收，因为旧版本在事务提交时立即删除

检查答案

恢复：先写日志，再写数据

回到崩溃实验。修改先发生在 buffer pool 的页里，什么时候写回磁盘由替换策略决定。这带来两个矛盾的场景：一个未提交事务的脏页可能已经被换出写到了磁盘（崩溃后要撤销它）；一个已提交事务的脏页可能还没写回（崩溃后要重做它）。如果强制提交前把所有脏页刷盘、并且禁止未提交的页落盘，问题就没了，但这意味着每次提交都要做大量随机写，buffer pool 也几乎失去了自由。

解法是预写日志（WAL，Write-Ahead Logging）。每次修改先追加一条日志记录：哪个事务、改了哪页的哪里、旧值是什么、新值是什么。两条铁律：

1. 一个脏页写回磁盘之前，描述它的日志必须先落盘。这样任何落盘的修改都能被撤销。
2. 事务提交时，它的所有日志（包括 COMMIT 记录）必须落盘，提交才算成功。数据页可以以后慢慢写。

日志顺序追加，一次提交只需一次顺序写加 fsync，还能多个事务攒成一次（组提交）。这跟 文件系统与 IO 里的日志文件系统是同一个思想。

崩溃后，工业界的标准算法 ARIES 分三步：分析，从最近的检查点开始读日志，弄清崩溃时哪些事务还活着、哪些页可能是脏的；重做，把日志里的所有修改（不管提交与否）重放一遍，让数据库回到崩溃那一刻的精确状态；撤销，把崩溃时未提交的事务按日志倒序回滚。撤销本身也写日志（补偿日志记录），这样恢复过程中再次崩溃也能正确继续。系统还定期做检查点，免得恢复时从头读日志。

SQLite 的 WAL 模式更简单：修改的页整页追加到 -wal 文件（实验结束时它有 24752 字节），读者依据其中的提交标记决定看哪个版本，这也是上一节多版本读的实现方式；崩溃的子进程没写提交标记，它的修改等于不存在。

停一下，检查理解单选

WAL 规则要求"提交时日志必须落盘"，却允许数据页晚些再写。崩溃后，一个已提交、但数据页还没写回的事务会怎样？

它的修改丢失，因为数据页上没有新值恢复时根据已落盘的日志重做，修改得以保留恢复时把它当作未提交事务撤销数据库拒绝启动，需要人工从备份恢复

检查答案

记住这三件事

1. 数据库的一切设计都围绕”磁盘按页、随机 IO 很贵”：槽式页、自管的 buffer pool、高扇出的 B+ 树，让一次点查只需寥寥几次 IO。
2. 隔离性靠并发控制：2PL 用锁排队，MVCC 用多版本快照让读写互不阻塞，但快照隔离仍有写偏斜。
3. 原子性和持久性靠 WAL：日志先于数据落盘，崩溃后重做已提交的、撤销未提交的。

延伸阅读

• CMU 15-445/645 Intro to Database Systems 讲义与视频（15445.courses.cs.cmu.edu）
• Silberschatz et al., Database System Concepts，第 13–19 章
• Mohan et al., ARIES: A Transaction Recovery Method（TODS 1992）
• Hellerstein, Stonebraker, Hamilton, Architecture of a Database System（2007）
• SQLite 文档：Write-Ahead Logging、Query Planning（sqlite.org）
• Crotty, Leis, Pavlo, Are You Sure You Want to Use MMAP in Your DBMS?（CIDR 2022）