数据库系统笔记

总览

索引

章	主题
1	导论：模式、独立性、引擎
2	关系模型与关系代数
3	SQL 概要
4	ER 模型与模式转换
5	关系数据库设计与范式
6	物理存储与文件组织
7	索引
8	查询处理
9	查询优化
10	事务
11	并发控制
12	恢复（WAL / checkpoint / ARIES）
13	代价公式与 B+ 演算补充
14	综合演算与复习对照
15	408与讲义补强

SQL 语法、嵌套、JOIN、窗口、面试题等见独立文档：SQL详解。

参考：菜鸟教程 SQL、牛客 SQL。

导论

定义

数据库（Database） ：长期存储在计算机内、有组织、可共享的数据集合。

数据库管理系统（DBMS，Database Management System） ：管理数据库的软件系统，负责定义、操纵、保护、并发与恢复。

数据库系统（Database System） ：数据库 + DBMS + 应用程序 + 用户。

相对文件系统，DBMS 典型能力包括：数据持久性、访问便利、完整性约束、多用户并发、故障恢复、安全控制。

数据视图

数据在系统中通常分为三层：

层次	英文	典型内容	对应 DDL 直觉
外模式 / 视图层	View / External	面向用户的局部逻辑结构	CREATE VIEW
概念模式 / 逻辑层	Logical	全体逻辑结构：表、约束	CREATE TABLE
内模式 / 物理层	Physical	文件、索引、页、存储布局	CREATE INDEX 等

模式（Schema） 类似程序中的“类型”；实例（Instance） 类似某一时刻的“值”。模式相对稳定，实例随更新变化。

层间由映射连接：视图↔逻辑、逻辑↔物理。三级结构使系统既能适应物理介质变化，也能在一定程度上隔离业务视图变化。

数据独立性

• 物理数据独立性（Physical Data Independence） ：物理存储或索引策略改变时，逻辑模式与应用程序尽量不受影响。
• 逻辑数据独立性（Logical Data Independence） ：逻辑模式局部调整时，可通过修改视图映射使外模式保持不变。物理独立性通常比逻辑独立性更容易实现。

▸类比：图书馆

书目卡片（视图）不必知道书在几号书架第几层（物理）；把书从 A 区搬到 B 区（改物理）不必改读者检索习惯。若编目规则改了（改逻辑），则可能要改卡片映射，这就是逻辑独立性更难的原因。

数据模型

数据模型描述数据、数据联系、语义与约束，是数据库的基本特征。常见类型：

模型	说明
关系模型（Relational Model）	表 + 关系运算；主流 RDBMS
实体-联系（ER，Entity-Relationship）	概念设计阶段常用
对象 / 对象-关系	面向对象或混合特征
半结构化 XML/JSON	灵活模式
网状 / 层次	早期模型，理解历史即可

语言分类

DDL

（Data Definition Language，数据定义语言）

定义模式、表、约束、权限等。DDL 编译结果写入数据字典（Data Dictionary） ，其中保存元数据（Metadata） ：模式、完整性约束、授权信息等。

CREATE TABLE instructor (
    ID          CHAR(5),
    name        VARCHAR(20),
    dept_name   VARCHAR(20),
    salary      NUMERIC(8,2),
    PRIMARY KEY (ID)
);

DML

（Data Manipulation Language，数据操纵语言）

增删改查。按风格分为：

• 过程式（Procedural） ：说明“要什么”以及“怎么取”；
• 非过程式 / 声明式（Declarative） ：只说明“要什么”。SQL 属后者。

关系代数（Relational Algebra） 是过程式理论语言；元组关系演算（Tuple Relational Calculus） / 域关系演算（Domain Relational Calculus） 是声明式理论语言；三者表达能力等价（在安全表达式意义下）。

引擎结构

DBMS 引擎可粗分为三块：

1. 存储管理器（Storage Manager） ：文件管理、缓冲、完整性与授权、事务相关存储接口；实现数据文件、数据字典、索引、统计信息等结构。
2. 查询处理器（Query Processor） ：DDL 解释、DML 编译与查询优化、查询执行引擎。路径大致为：SQL → 关系代数表达式 → 候选计划 → 代价估计选优 → 执行。
3. 事务管理（Transaction Management） ：恢复管理器保证故障后一致；并发控制管理器保证多事务互不破坏一致性。

用户角色

角色	交互方式
初级用户（Naive User）	调用既有应用程序（如教务系统）
应用程序员	通过嵌入式 SQL / ODBC / JDBC 等访问
DBA	模式定义、存储与访问方法、权限、完整性、性能调优
分析师 / DBMS 开发者	需求与系统实现

关系模型

基本术语

一张关系（Relation） 对应一张表；元组（Tuple） 对应一行；属性（Attribute） 对应一列。属性取值来自域（Domain） 。关系模型要求属性值原子（Atomic） ——不可再分。

形式上，关系是各属性域笛卡尔积的一个子集。关系是集合（理论模型下去重、无序）；SQL 实际多为多重集（Multiset） ，默认保留重复。

关系模式（Relation Schema） $R(A_1,\ldots,A_n)$ 描述结构；$r(R)$ 表示该模式下的一个关系实例。模式与实例常共用同一名称，需依语境区分。

键

概念	定义要点
超键（Superkey）	能唯一标识元组的属性集；可含冗余属性。若 $A$ 是超键，则 $(A,B)$ 也是
候选键（Candidate Key）	不含多余属性的超键（极小超键）
主键（Primary Key）	从候选键中选定的一个；不允许 NULL
外键（Foreign Key）	$R_1$ 中引用 $R_2$ 主键（或候选键）的属性集；可为空（视约束而定）

▸函数依赖视角

$K$ 是 $R$ 的超键 $\Leftrightarrow$ $K \rightarrow R$。$K$ 是候选键 $\Leftrightarrow$ $K \rightarrow R$ 且 $K$ 的任何真子集都不能决定 $R$。键是函数依赖的特例。

完整性直觉

• 实体完整性（Entity Integrity） ：主键非空且唯一。
• 参照完整性（Referential Integrity） ：外键为空，或等于被参照关系中某主键值。
• 用户定义完整性（User-defined Integrity） ：CHECK、断言、触发器等。

关系代数

地位

关系代数是过程式查询语言，由若干运算组成：输入一或两个关系，输出一个关系。六种基本运算足以表达其余许多常用运算。关系代数不是图灵完备的，但对关系查询足够。

三种“纯”语言表达能力等价：

1. 关系代数
2. 元组关系演算
3. 域关系演算

六种基本运算

设关系为集合。

运算	符号	含义	SQL 粗对应
选择（Selection）	$\sigma_P(r)$	选满足谓词 $P$ 的元组	WHERE
投影（Projection）	$\Pi_{A}(r)$	保留属性集 $A$，集合语义下去重	SELECT（理论去重）
并（Union）	$r \cup s$	并集；模式相容	UNION
差（Difference）	$r - s$	差集；模式相容	EXCEPT
笛卡尔积（Cartesian Product）	$r \times s$	元组两两拼接	FROM r, s / CROSS JOIN
改名（Rename）	$\rho_x(r)$ / $\rho_{x(A_1,\ldots)}(r)$	关系或属性改名	AS

模式相容（Union Compatibility） （并、差、交）：属性个数相同，且对应属性域相容。

▸并是基本运算，交不是

交可由差导出：$r \cap s = r - (r - s)$。考研填空常考这一点。

▸选择与投影

关系 student(sid, name, dept, age)。

• 找 CS 系学生：$\sigma_{\mathrm{dept}=’CS’}(\mathrm{student})$
• 只要姓名：$\Pi_{\mathrm{name}}(\sigma_{\mathrm{dept}=’CS’}(\mathrm{student}))$

投影会去掉因舍弃列而产生的重复行（集合语义）。

多重集语义

理论关系代数按集合去重；SQL 默认多重集（bag） ：投影与并等默认保留重复，需 DISTINCT / UNION（非 UNION ALL）才去重。讲义 Multiset Algebra 即说明：同一运算在多重集下的计数规则与集合不同，代价估计也常按多重集中间结果行数。

扩展运算

交

交（Intersection）：$r \cap s = r - (r - s)$。SQL：INTERSECT。

自然连接

自然连接（Natural Join） $r \bowtie s$：在同名属性上等值匹配，结果中同名属性只保留一列。可写为先笛卡尔积再选择再投影。

慎用：同名但语义不同的列会被错误等值连接。

条件连接（Theta Join）

$r \bowtie_\theta s = \sigma_\theta(r \times s)$。$\theta$ 为一般谓词（不必仅等值）。

外连接

外连接（Outer Join） ：在连接结果上保留悬浮元组，缺失侧填 NULL。

类型	保留侧
左外连接（Left Outer Join）	左侧全部
右外连接（Right Outer Join）	右侧全部
全外连接（Full Outer Join）	两侧全部

除法

（Division）

设关系 $r(R)$、$s(S)$，且属性集 $S \subseteq R$。记「只属于 $r$、不属于 $s$」的属性为 $R-S$（结果里留下的那些列）。

语义（先记这个） ：$r \div s$ = 在 $R-S$ 上取值的那些「对象」，它们在 $r$ 里与 $s$ 的每一个元组都配过对。

口诀：除法 = 全称量化（Universal Quantification） =「选了 $s$ 里全部东西的那些人」。

小数据（先会判，再看公式）

$r$（选课，模式 $\mathrm{sid},\mathrm{cid}$）：

sid	cid
1	C1
1	C2
2	C1
3	C1
3	C2
3	C3

$s$（要求「全部」掌握的课，模式 $\mathrm{cid}$）：

cid
C1
C2

$S={\mathrm{cid}} \subseteq R={\mathrm{sid},\mathrm{cid}}$，故 $R-S={\mathrm{sid}}$：结果是一列学号。

逐人检查「是否与 $s$ 中每一门都配对」：

sid	在 $r$ 里选了哪些	是否含齐 ${C1,C2}$	进不进 $r\div s$
1	C1, C2	是	进
2	仅 C1	缺 C2	不进
3	C1, C2, C3	是（多选 C3 无妨）	进

故

$$
r \div s = {1,\ 3}
$$

（写成单列表）。$s$ 变大（例如再加 C3）时，只有 3 还能留下——被除的「除数」越大，商通常越小。

与连接的区别

	连接 / 普通选择	除法
问的是	「至少有一门 / 某一门」	「每一门都有」
典型题	选过 C1 的学生	选过 $s$ 中全部课的学生

用基本运算怎么写（公式拆开）

教材恒等式（不必死背，考试能还原思路即可）：

$$
r \div s = \Pi_{R-S}(r) - \Pi_{R-S}\Big(\big(\Pi_{R-S}(r)\times s\big) - \Pi_{(R-S)\cup S}(r)\Big)
$$

差集两侧模式须一致，故右侧本应投影到 $(R-S)\cup S$。本例 $r$ 的属性恰好是 ${\mathrm{sid},\mathrm{cid}}$，该投影等于 $r$ 本身，书写时可把 $\Pi_{(R-S)\cup S}(r)$ 直接写成 $r$。

对上例逐步：

1. $\Pi_{\mathrm{sid}}(r)={1,2,3}$：所有「可能」的学号。
2. $\Pi_{\mathrm{sid}}(r)\times s$：每人配上 $s$ 里每一门，得到「若要合格必须具备的全部 (sid,cid)」。
   此表不是 $r$：只与除数 $s={C1,C2}$ 做笛卡尔积，因此会出现 $r$ 里没有的 $(2,C2)$，也不会出现 $r$ 多选的 $(3,C3)$。

sid	cid	是否已在 $r$ 中
1	C1	是
1	C2	是
2	C1	是
2	C2	否（缺课）
3	C1	是
3	C2	是

3. 从上表减去真正的选课 $r$（集合差：左有右无）。缺课对只剩：

sid	cid
2	C2

4. 再投影到 $\mathrm{sid}$：有缺课的对象 = ${2}$。
5. 全部候选减去有缺课的：${1,2,3}-{2}={1,3}$。即为商。

▸公式在说什么

「先假设人人都选了 $s$ 的全部课（笛卡尔积），减去真实选课 → 得到缺课清单；有缺课的人淘汰；剩下的人就是除法结果。」

SQL 侧（无 DIVIDE 运算符）

与《SQL详解》中「全称 / NOT EXISTS」同构，两种常用写法：

1. 双重否定：不存在一门 $s$ 中的课，使得该生没选。
2. 分组计数：按 sid 分组，要求 COUNT(DISTINCT cid)（且 cid 落在 $s$ 中）等于 $|s|$。

-- 分组计数示意（s 为 CS 全部课程号的关系/子查询）
SELECT sid
FROM r
WHERE cid IN (SELECT cid FROM s)
GROUP BY sid
HAVING COUNT(DISTINCT cid) = (SELECT COUNT(*) FROM s);

▸认题

题干出现「全部课程」「所有 JL SUN 的社」「每种零件都供应」→ 关系代数用除法，SQL 用 NOT EXISTS 或分组计数，不要写成普通连接（普通连接只表达「至少一次」）。

广义投影与聚集

广义投影（Generalized Projection） 允许投影列表中出现算术表达式。聚集（Aggregation） ：

$$
{}_{G_1,\ldots,G_n}\mathcal{G}_{F_1(A_1),\ldots,F_m(A_m)}(E)
$$

按分组属性聚集，常用 $F \in {\mathrm{SUM},\mathrm{MAX},\mathrm{MIN},\mathrm{AVG},\mathrm{COUNT} }$。

赋值

赋值（Assignment）：$x \leftarrow E$，便于分步书写复杂表达式。

形式定义摘要

基本表达式：库中关系，或常量关系。若 $E_1,E_2$ 为表达式，则下列亦为表达式：

$E_1 \cup E_2$，$E_1 - E_2$，$E_1 \times E_2$，$\sigma_P(E_1)$，$\Pi_S(E_1)$，$\rho_x(E_1)$。

习题型例子

模式：

student(sid, name, age, gender, department, building, room)
dorm(building, room, capacity)

1. CS 系且住“白沙1幢”213 的学生姓名：

$$
\Pi_{\mathrm{name}}(\sigma_{\mathrm{department}=’CS’ \land \mathrm{building}=’白沙1幢’ \land \mathrm{room}=213}(\mathrm{student}))
$$

2. 名为“王小强”的室友（不含本人）：

$$
\Pi_{\mathrm{name}}\big(\sigma_{\mathrm{name}\neq ‘王小强’}(\mathrm{student} \bowtie \Pi_{\mathrm{building},\mathrm{room}}(\sigma_{\mathrm{name}=’王小强’}(\mathrm{student})))\big)
$$

3. 不同系但同宿舍的学生姓名对（笛卡尔积 + 选择 + 投影，注意改名消歧）。

▸笛卡尔积行数

$|r \times s| = |r|\cdot|s|$。随堂常见坑：5 行表自连接得 25 行；投影去重后再数不同值。

SQL 概要

定位

SQL（Structured Query Language） 是声明式、基于多重集的查询语言。执行逻辑顺序（理解用，非语法书写顺序）：

$$
\mathrm{FROM} \rightarrow \mathrm{WHERE} \rightarrow \mathrm{GROUP\ BY} \rightarrow \mathrm{HAVING} \rightarrow \mathrm{SELECT} \rightarrow \mathrm{ORDER\ BY}
$$

主笔记只保留与关系代数、事务、优化衔接的要点；语法细节、复杂嵌套、面试题与大量例子见独立文《SQL详解》。

与关系代数的对应

关系代数	SQL
$\sigma$	WHERE
$\Pi$	SELECT（默认保留重复，DISTINCT 去重）
$\times$	FROM 多表 / CROSS JOIN
$\bowtie$	JOIN ... ON / NATURAL JOIN
$\cup,-,\cap$	UNION / EXCEPT / INTERSECT
聚集	GROUP BY + 聚集函数 + HAVING
除法	NOT EXISTS 双重嵌套等

最小示例

SELECT instructor.ID, department.building
FROM instructor, department
WHERE instructor.dept_name = department.dept_name
  AND department.dept_name = 'Physics';

SELECT dept_name, AVG(salary) AS avg_salary
FROM instructor
GROUP BY dept_name
HAVING AVG(salary) > 50000;

“全部 / 仅含”类语义（全称量化）优先用 NOT EXISTS，见《SQL详解》与习题 Quiz2。

视图与权限（摘要）

• 视图（View） ：CREATE VIEW v AS <subquery>，提供逻辑独立性与安全裁剪；可更新视图条件严格（通常单表、无聚集/DISTINCT 等）。
• 权限（Authorization） ：GRANT / REVOKE；角色 CREATE ROLE。

ER 模型

实体与联系

ER（Entity-Relationship，实体-联系） 模型用于概念设计。实体（Entity） ：现实中可区分的对象；实体集（Entity Set） 为同类实体的集合。图中用矩形表示，主键属性加下划线。

联系（Relationship） ：实体间的关联；联系集（Relationship Set） 为同类联系的集合。图中用菱形表示。联系也可带属性（常用虚线连到菱形）。

联系集关联的实体集个数称为度（Degree） ，以二元为主。

属性类型

类型	含义	转关系模式时
简单 / 复合（Simple / Composite）	复合可拆为 street、city 等	通常拆成简单列，不必单独成表
单值 / 多值（Single-valued / Multivalued）	多值如电话列表	多值属性单独成表（含原实体主键 + 多值）
派生（Derived）	可由其他属性算出	通常不存，或存缓存值
键属性（Key Attribute）	唯一标识	主键

▸随堂易错

ER 转关系时，必须单独成关系的属性类型是多值属性，不是复合或派生。复合属性拆列即可；派生可不物化。

映射基数

二元联系的映射基数（Mapping Cardinality） ：一对一、一对多、多对一、多对多。ER 图中常见约定：箭头表示“一”，直线表示“多”（以课程讲义为准）。

三元联系中箭头至多出现一次，否则易产生二义性。

参与约束

• 完全参与（Total） ：实体集中每个实体至少参与一次联系；双线。
• 部分参与（Partial） ：允许不参与；单线。

弱实体集

弱实体集（Weak Entity Set） 自身属性不足以形成主键，必须依赖标识性强实体集（Identifying Owner / Strong Entity Set） 。联系用双线菱形；分辨符（Discriminator）用虚下划线。

弱实体主键 = 强实体主键 ∪ 分辨符。

▸职工与家属

家属不能脱离职工独立标识：家属为弱实体，分辨符可以是“家属姓名”，主键为 (职工号, 家属姓名)。

特化、泛化与聚集

• 特化（Specialization） ：自顶向下细分，子类继承超类属性；可重叠（overlapping）或不相交（disjoint）。
• 泛化（Generalization） ：自底向上按共性综合。
• 聚集（Aggregation） ：把一部分实体集+联系集框成更高层实体，以便再与其他实体建立联系。

转为关系模式

ER 构件	转换要点
强实体集（Strong Entity Set）	一表；主键同实体主键
弱实体集（Weak Entity Set）	一表；主键 = 主人主键 + 分辨符；外键指向主人
多值属性	单独一表
1:1	可把一侧主键并入另一侧作外键；或单独联系表
1:N	“一”端主键进入“多”端作外键
M:N	必须单独联系表，含两端主键（作联合主键或另加代理键（Surrogate Key） ）及联系属性

▸随堂易错

必须单独转换成关系模式的联系集类型是 Many-to-Many。1:1 与 1:N 通常可合并到实体表。

关系数据库设计

目标

好的关系设计应：减少不必要冗余；避免插入异常（Insertion Anomaly） 、删除异常（Deletion Anomaly） 、更新异常（Update Anomaly） ；保证无损连接；尽可能保持函数依赖；在冗余与查询性能间权衡（有时故意反规范化（Denormalization） ）。

▸坏模式 inst_dept

把教师与系合并：inst_dept(id, name, salary, dept_name, building, budget)。同一系的 building、budget 随每位教师重复 → 更新异常、插入异常（尚无教师时难登记系信息）。

第一范式

1NF（First Normal Form，第一范式） ：所有属性原子。仅满足 1NF 仍可能严重冗余。

第二范式

2NF（Second Normal Form，第二范式） ：在 1NF 基础上，每个非主属性（Nonprime Attribute） 都完全函数依赖（Full Functional Dependency） 于某个候选键（不存在非主属性对候选键的部分依赖（Partial Dependency） ）。

▸部分依赖

$R(\mathrm{学号},\mathrm{课程号},\mathrm{成绩},\mathrm{姓名})$，$F={ {\mathrm{学号},\mathrm{课程号} }\rightarrow\mathrm{成绩},\ \mathrm{学号}\rightarrow\mathrm{姓名} }$。
候选键为 $(\mathrm{学号},\mathrm{课程号})$。$\mathrm{姓名}$ 只依赖学号 → 部分依赖 → 非 2NF。
分解为 $(\mathrm{学号},\mathrm{姓名})$ 与 $(\mathrm{学号},\mathrm{课程号},\mathrm{成绩})$。

关系链：通常 $1\mathrm{NF}\Leftarrow 2\mathrm{NF}\Leftarrow 3\mathrm{NF}\Leftarrow \mathrm{BCNF}\Leftarrow 4\mathrm{NF}$（在相应依赖假设下）。

【考研常问：有部分依赖先想到 2NF；有传递依赖（Transitive Dependency） 想到 3NF；决定因素（Determinant） 非超键想到 BCNF。】

▸理解：1NF / 2NF 在防什么

1NF（格子里只能放一个值）

一行一列里不要塞清单。例如「选修课」列写成 C1,C2,C3 就不原子；应拆成多行，每行一门课。做到这一点只是「能当正经关系表用」，冗余照样可以很严重。

2NF（非键列不许只挂在「复合键的一半」上）

先看键是不是由多列拼成的。上例键是 (学号, 课程号)——要唯一锁定一行选课记录，两列都要。

• 成绩：必须「谁 + 哪门课」才定得下来 → 依赖整个键 → 合格。
• 姓名：只看学号就定得下来，跟选哪门课无关 → 只依赖键的一半 → 这叫部分依赖 → 不满足 2NF。

小表直观（同一人上两门课，姓名抄两遍）：

学号	课程号	成绩	姓名
1	C1	90	小明
1	C2	85	小明

小明改名时要改两行，漏改就不一致——正因为姓名本该单独放在「学生表」里，而不是跟选课绑在一起。

拆开之后：

学号	姓名
1	小明

学号	课程号	成绩
1	C1	90
1	C2	85

记法：键是「组合拳」时，问每个非键列——「是不是只用组合拳的一半就能打出来？」能 → 部分依赖 → 还没到 2NF。

（单列主键时通常没有「一半」，2NF 往往自动满足，矛盾多出现在后面的 3NF / BCNF。）

无损分解与有损分解

将 $R$ 分解为 $R_1,R_2$（$R=R_1\cup R_2$）。

• 无损连接（Lossless-join） ：对任意合法实例 $r$，$\Pi_{R_1}(r)\bowtie\Pi_{R_2}(r)=r$。
• 有损分解（Lossy Decomposition） ：自然连接可能产生多余元组，信息不确定性增加。

二元分解无损的充要条件（在 $F^+$ 下）：

$$
R_1\cap R_2 \rightarrow R_1 \quad\text{或}\quad R_1\cap R_2 \rightarrow R_2
$$

即交属性集至少是其中一侧的超键。

▸有损反例

employee(ID, name, street, city, salary) 拆成 (ID, name) 与 (name, street, city, salary)：同名不同人会在连接时张冠李戴。

函数依赖

函数依赖（Functional Dependency，FD） ：$R$ 上 $\alpha\rightarrow\beta$（$\alpha,\beta\subseteq R$）成立：对任意合法实例中任两元组，若在 $\alpha$ 上相等，则在 $\beta$ 上必相等。读作“$\alpha$ 决定 $\beta$”。

（符号：$R$ = 当前这张表的全部属性；$\alpha\rightarrow\beta$ = 一条函数依赖，左边 $\alpha$、右边 $\beta$ 都是属性集合，可读作「$\alpha$ 决定 $\beta$」。）

Armstrong 公理与常用规则

Armstrong 公理（Armstrong’s Axioms）：

• 自反：若 $\beta\subseteq\alpha$，则 $\alpha\rightarrow\beta$（平凡依赖（Trivial Dependency） ）
• 增广：$\alpha\rightarrow\beta \Rightarrow \gamma\alpha\rightarrow\gamma\beta$
• 传递：$\alpha\rightarrow\beta,\ \beta\rightarrow\gamma \Rightarrow \alpha\rightarrow\gamma$
• 合并：$\alpha\rightarrow\beta,\ \alpha\rightarrow\gamma \Rightarrow \alpha\rightarrow\beta\gamma$
• 分解：$\alpha\rightarrow\beta\gamma \Rightarrow \alpha\rightarrow\beta$ 且 $\alpha\rightarrow\gamma$
• 伪传递：$\alpha\rightarrow\beta,\ \beta\gamma\rightarrow\delta \Rightarrow \alpha\gamma\rightarrow\delta$

▸用公理推依赖

已知 $A\rightarrow B$，$BC\rightarrow D$。由增广得 $AC\rightarrow BC$，再与 $BC\rightarrow D$ 传递（或伪传递）得 $AC\rightarrow D$。闭包算法算 $AC^+$ 可机械验证同一结论。

闭包

• 闭包（Closure） $F^+$：由 $F$ 逻辑蕴含的全部 FD 之集。
• 属性集闭包（Attribute Closure） $\alpha^+$：所有满足 $\alpha\rightarrow\beta\in F^+$ 的 $\beta$ 中属性之并。

计算 $\alpha^+$（考试必会）：

result := α
while result 有变化:
    for each β → γ in F:
        if β ⊆ result then result := result ∪ γ

用途：测超键（$\alpha^+=R$）；测 $\alpha\rightarrow\beta$ 是否成立（$\beta\subseteq\alpha^+$）；帮助求候选键。

▸理解：闭包在算什么

考试几乎只考 属性集闭包 $\alpha^+$（给定一些已知依赖 $F$，从属性集合 $\alpha$ 出发「能推出哪些列」）。$F^+$ 是「全部能推出的依赖」那一大筐，一般不用手枚举。

人话：把 $\alpha$ 当成手里已有的证件；每条依赖 $\beta\rightarrow\gamma$ 像一条规则——「若证件已齐 $\beta$，就可再盖章得到 $\gamma$」。反复盖章，直到盖不出新的，手里那一摞就是 $\alpha^+$。

小例子（逐步对照伪代码）

设 $R={A,B,C,D}$，$F={A\rightarrow B,\ B\rightarrow C,\ CD\rightarrow A}$，求 $A^+$。

轮次	result 当前	扫到的规则	能否用	变化
初值	${A}$	—	—	—
1	${A}$	$A\rightarrow B$	$A$ 已有	并入 $B$ → ${A,B}$
1	${A,B}$	$B\rightarrow C$	$B$ 已有	并入 $C$ → ${A,B,C}$
1	${A,B,C}$	$CD\rightarrow A$	缺 $D$	不动
2	${A,B,C}$	再扫一遍	无新属性	停止

故 $A^+={A,B,C}$（没有 $D$）。

三个用途怎么用这个结果

1. 是不是超键：若 $\alpha^+=R$（推出了全部属性），则 $\alpha$ 能唯一锁定一行 → 超键。上例 $A^+\neq R$，所以单靠 $A$ 不是超键。
2. 某条依赖成不成立：问「$A\rightarrow C$ 成不成立？」→ 看 $C$ 是否落在 $A^+$ 里。上例 $C\in A^+$ → 成立（不必再手推公理）。
3. 找候选键：对可疑的小属性集算闭包，找「$\alpha^+=R$ 且再少一个属性就不行」的那些 $\alpha$。

和伪代码的对应：result := α 即初值；while 有变化 即上表多轮；β ⊆ result 即「左边证件是否已齐」；result ∪ γ 即盖新章。

BCNF

BCNF（Boyce-Codd Normal Form，Boyce-Codd 范式） 要求：对 $F^+$ 中每条 FD $\alpha\rightarrow\beta$，至少其一成立：

1. 平凡（$\beta\subseteq\alpha$）；或
2. $\alpha$ 是 $R$ 的超键。

检验：对 $F$ 中非平凡 FD 算 $\alpha^+$，看 $\alpha$ 是否超键。注意：检验分解后的各模式时，不能只用原 $F$ 的“局部投影”偷懒到出错，需在各 $R_i$ 上考虑成立的依赖。

BCNF 分解思想：找违背 BCNF 的 $\alpha\rightarrow\beta$，用 $(R-\beta)$ 与 $(\alpha\beta)$ 替换 $R$，递归至全部满足。保证无损，但不一定保持依赖。

▸BCNF 分解演算

$R=(C,S,Z)$（课程、学生、教师），$F={CS\rightarrow Z,\ Z\rightarrow C}$。
候选键：$CS$、$SZ$（验证闭包）。$Z\rightarrow C$ 中 $Z$ 非超键 → 非 BCNF。
用 $Z\rightarrow C$ 分解：$(Z,C)$ 与 $(S,Z)$。再检查各片直至都是 BCNF。
注意：$CS\rightarrow Z$ 跨片，依赖保持可能失败——这正是有时改用 3NF 分解的原因。

▸理解：BCNF 判定与分解（对着上例）

一句话：每条「真正有用」的依赖，左边都必须能当超键——谁决定别人，谁就得能锁定整行。

两条放行条件（对应定义）

情况	含义	要不要管
平凡：$\beta\subseteq\alpha$	右边已在左边里，如 $CS\rightarrow C$	永远不违背 BCNF
$\alpha$ 是超键	左边能推出 $R$ 全部属性	合格
其它	左边推得出右边，却推不出整行	违背 → 要分解

上例逐步：先找候选键

$R={C,S,Z}$，$F={CS\rightarrow Z,\ Z\rightarrow C}$。

起点 $\alpha$	算 $\alpha^+$	是否 $=R$
$C$	${C}$（$Z\rightarrow C$ 用不上，因缺 $Z$）	否
$S$	${S}$	否
$Z$	${Z,C}$（用 $Z\rightarrow C$）	缺 $S$，否
$CS$	${C,S}$再加 $Z$ → ${C,S,Z}$	是 → $CS$ 是超键；但是否候选键？去掉一个：$C^+$、$S^+$ 都不是 $R$，故 $CS$ 是候选键
$SZ$	${S,Z}$ → 加 $C$ → $R$	是；极小 → 候选键
$CZ$	${C,Z}$ → 仍无 $S$ 规则可用	否

故候选键是 $CS$ 与 $SZ$（与上表 EXAMPLE 一致）。

为何非 BCNF

• 看非平凡依赖 $Z\rightarrow C$：左边只有 $Z$。
• $Z^+={Z,C}\neq R$ → $Z$ 不是超键。
• 于是「教师决定课程」成立，但教师锁定不了「学生」→ 违反 BCNF。
• 另一条 $CS\rightarrow Z$：左边 $CS$ 是超键 → 这条合格。

怎么拆（公式 $(R-\beta)$ 与 $(\alpha\beta)$）

违背依赖是 $\alpha\rightarrow\beta = Z\rightarrow C$，故 $\alpha={Z}$，$\beta={C}$：

• $(\alpha\beta)=(Z,C)$：专放「教师↔课程」
• $(R-\beta)=(C,S,Z)-{C}=(S,Z)$：专放「学生↔教师」

直观：一张表里既有「谁教哪门课」又有「谁选哪门/跟哪位教师」，教师决定课程时，同一教师会随多个学生重复抄课程信息——拆开后各管一块。

拆完再检查

片	上成立的依赖（直观）	左边是否超键	BCNF？
$(Z,C)$	$Z\rightarrow C$	$Z$ 在本片是超键	是
$(S,Z)$	往往只有平凡依赖（或键为整片）	—	是

「依赖保持失败」是什么意思

原依赖 $CS\rightarrow Z$ 需要 $C$ 与 $S$ 同在一张表里才能直接检查；拆开后 $C$ 在 $(Z,C)$、$S$ 在 $(S,Z)$，单看任一片都写不出 $CS\rightarrow Z$。
连接两片后数据仍可无损还原，但「只改一片就可能暂时违反对 $CS\rightarrow Z$ 的约束」——所以说 BCNF 分解无损却未必保持依赖；若业务必须就地检查该约束，常改走 3NF 分解。

第三范式

3NF（Third Normal Form，第三范式） 要求：对 $F^+$ 中每条 $\alpha\rightarrow\beta$，至少其一：

1. 平凡；或
2. $\alpha$ 是超键；或
3. $\beta-\alpha$ 中每个属性都属于某个候选键（即均为主属性（Prime Attribute） ）。

关系：BCNF $\Rightarrow$ 3NF。3NF 允许“主属性传递依赖于非超键”，以换取更好的依赖保持。3NF 分解可做到无损且保持依赖；可能残留少量冗余。

▸理解：3NF / BCNF 在防什么

先分清两个词

• 决定因素（Determinant） ：箭头左边（由谁推出别人）。
• 超键（Superkey） ：能唯一锁定整行的属性集（候选键及其超集）。

3NF 在防：非主属性「隔山打牛」（传递依赖）

典型坏表：把学生和系主任塞一张表。

学号	姓名	系名	系主任
1	小明	CS	张老师
2	小红	CS	张老师
3	小刚	EE	李老师

依赖链：学号 → 系名，系名 → 系主任，于是学号 传递 决定系主任。
键是学号；系主任 是非主属性，却不是「直接由键决定」，而是经由 系名 绕一圈——传递依赖 → 未到 3NF。

坏处：同一系主任随每个学生抄一遍；改系主任要改多行；系里暂时没学生时，系主任信息甚至插不进去。

拆法直觉（与上表三行对应）：

学号	姓名	系名
1	小明	CS
2	小红	CS
3	小刚	EE

系名	系主任
CS	张老师
EE	李老师

记法（3NF） ：非主列是否「只通过另一个非键列」才连到主键？是 → 传递依赖 → 再拆一刀。

BCNF 更严：谁当决定因素，谁就必须是超键

不管左边推出的是主属性还是非主属性——只要左边不是超键，就违反 BCNF。

教材常例：$R(\mathrm{课程},\mathrm{学生},\mathrm{教师})$，$CS\rightarrow Z$，$Z\rightarrow C$（一位教师只教一门课）。
候选键可以是 $CS$、$SZ$。此时 $Z\rightarrow C$：左边教师不是超键，却能决定课程（课程是主属性）→ 满足 3NF 的宽松条款，但不满足 BCNF。

	3NF	BCNF
核心直觉	非主属性不要对候选键传递依赖	每个决定因素都得是超键
更严的是谁	较松	更严（BCNF $\Rightarrow$ 3NF）
分解代价	常可无损且保持依赖	保证无损，但可能丢依赖

考试认题：看到传递依赖 → 先想 3NF；看到「决定因素不是超键」（哪怕右边是主属性）→ 想 BCNF。

依赖保持

依赖保持（Dependency Preservation） ：分解 ${R_1,\ldots,R_n}$ 保持依赖：若令 $F_i$ 为只涉及 $R_i$ 属性的 FD，则 $(\bigcup F_i)^+=F^+$。

检验某 $\alpha\rightarrow\beta$ 是否被保持：从 $\alpha$ 出发，反复用各 $R_i$ 上的属性闭包“增长”，看能否覆盖 $\beta$。

最小覆盖（Canonical Cover）$F_c$

最小覆盖（Canonical Cover） $F_c$：与 $F$ 等价、无多余 FD、无多余属性，且左部唯一（同左部已合并）。

多余属性：

• 左部 $A\in\alpha$ 多余：若用 $(\alpha-A)\rightarrow\beta$ 替换后仍蕴含原 $F$。
• 右部 $A\in\beta$ 多余：削弱右部后仍能推出原 $F$。

步骤概要：合并同左部 → 去左右多余属性 → 重复至稳定。

多值依赖与 4NF

多值依赖（Multivalued Dependency，MVD） $\alpha\rightarrow\rightarrow\beta$：在固定 $\alpha$ 时，$\beta$ 与 $R-\alpha-\beta$ 的取值彼此独立（需形式定义时按教材“元组对交换”条件）。

4NF（Fourth Normal Form，第四范式） ：对 $D^+$ 中 $\alpha\rightarrow\rightarrow\beta$，或平凡，或 $\alpha$ 为超键。4NF $\Rightarrow$ BCNF。存在由独立多值事实造成的冗余时，仅 BCNF 不够。

▸考研策略

必会：候选键、闭包算法、无损判定、BCNF/3NF 判定与分解、最小覆盖。4NF/MVD 作拓展，按试卷要求深度掌握。

范式对照

范式	英文	在消除 / 约束什么	判定抓手（一句话）	分解常见保证
1NF	First Normal Form	非原子属性（一格多值）	每个属性值不可再分	—
2NF	Second Normal Form	非主属性对候选键的部分依赖	非主列是否只依赖复合键的一半	通常先拆部分依赖
3NF	Third Normal Form	非主属性对候选键的传递依赖	非主列是否经另一非主列才连到键	可无损 + 保持依赖
BCNF	Boyce-Codd Normal Form	决定因素不是超键（含主属性被非超键决定）	每条非平凡 FD 左边是否超键	无损；依赖保持不保证
4NF	Fourth Normal Form	非平凡多值依赖造成的独立事实交叉	MVD 的左边是否超键	针对 MVD 再拆
5NF	Fifth Normal Form	连接依赖（了解）	是否存在非候选键蕴含的连接依赖	考纲多作拓展

蕴含关系（满足更高 ⇒ 满足更低）：

$$
5\mathrm{NF}\ \Rightarrow\ 4\mathrm{NF}\ \Rightarrow\ \mathrm{BCNF}\ \Rightarrow\ 3\mathrm{NF}\ \Rightarrow\ 2\mathrm{NF}\ \Rightarrow\ 1\mathrm{NF}
$$

（在相应依赖类型假设下；箭头表示「更严 / 模式集合更小」。）

▸理解：各 NF 怎么一层层推上来

总逻辑：先让表「像关系」（1NF）→ 再按函数依赖削冗余（2NF → 3NF → BCNF）→ 若还有多值独立事实交叉，上到 4NF。

1NF  属性原子
 │
 │  复合键 + 非主列只靠键的一部分？
 ▼
2NF  去掉部分依赖          例：成绩跟(学号,课号)，姓名却只跟学号
 │
 │  非主列经另一非主列才到键？
 ▼
3NF  去掉传递依赖          例：学号→系名→系主任
 │
 │  还有「左边不是超键」的 FD？（哪怕右边是主属性）
 ▼
BCNF 每个决定因素都是超键   例：教师→课程，但键是(学生,教师)/(学生,课程)
 │
 │  FD 清干净后，仍有两套独立多值事实叉乘？
 ▼
4NF  多值依赖左边也须超键   例：课程既对应多教材又对应多参考书，彼此无关

推导时的问题链（由低到高问，哪个「否」就停在哪一层之下）：

1. 有没有一格多值 / 嵌套表？→ 否才谈 1NF 以上。
2. 有没有非主属性只依赖候选键的真子集？→ 有则非 2NF。
3. 有没有非主属性对候选键存在传递依赖？→ 有则非 3NF。
4. 有没有非平凡 FD 的决定因素不是超键？→ 有则非 BCNF（此时仍可能是 3NF）。
5. 有没有非平凡 MVD 且左边不是超键？→ 有则非 4NF。

3NF 与 BCNF 的分叉（考试最爱）

• 只盯非主属性的部分/传递 → 停在 2NF/3NF 口径。
• 连主属性被非超键决定也不许 → 才是 BCNF。
• 故存在：是 3NF、不是 BCNF；不存在「是 BCNF 却不是 3NF」。

设计选型（逻辑关系落到做法）

目标	倾向
要无损且尽量保持依赖（约束好局部检查）	常分解到 3NF
要更彻底消灭「坏决定因素」	上到 BCNF（接受可能丢依赖）
FD 已 OK，仍见独立多值交叉冗余	再考虑 4NF

和前面工具的衔接：判定任一层前，先用闭包找候选键、分清主/非主；分解后查无损；若走 3NF 路线再查依赖保持。

▸从 1NF 往下拆（同一套选课数据）

0. 尚未 1NF（对照用）

学号	姓名	选修
1	小明	C1/90, C2/85

「选修」一格多值 → 非 1NF。拆成多行后进入下面的宽表。

1. 已是 1NF，但很胖：$R$

学号	姓名	系名	系主任	课程号	成绩	学分
1	小明	CS	张老师	C1	90	3
1	小明	CS	张老师	C2	85	2
2	小红	CS	张老师	C1	88	3

给定 $F$：

• ${\mathrm{学号},\mathrm{课程号}} \rightarrow \mathrm{成绩}$
• $\mathrm{学号} \rightarrow \mathrm{姓名},\mathrm{系名}$
• $\mathrm{系名} \rightarrow \mathrm{系主任}$
• $\mathrm{课程号} \rightarrow \mathrm{学分}$

候选键：${\mathrm{学号},\mathrm{课程号}}$（闭包为全部属性；学号或课程号单独都不行）。
主属性：学号、课程号。非主属性：姓名、系名、系主任、成绩、学分。
属性已原子 → 满足 1NF；下面查更高范式。

2. 非 2NF → 拆掉部分依赖

非主属性	依赖谁	问题
成绩	整个候选键	完全依赖，OK
姓名、系名	仅学号	部分依赖
学分	仅课程号	部分依赖
系主任	学号（经系名）也能决定	对候选键真子集可决定 → 亦属对键的部分依赖；3NF 阶段再清传递

按部分依赖分解（保留键上的完全依赖）：

模式	属性	此片候选键
$R_1$ 学生	学号, 姓名, 系名, 系主任	学号
$R_2$ 课程	课程号, 学分	课程号
$R_3$ 选课	学号, 课程号, 成绩	(学号, 课程号)

各片已无「非主属性只靠复合键一半」→ 达到 2NF。
但 $R_1$ 仍有 $\mathrm{学号}\rightarrow\mathrm{系名}\rightarrow\mathrm{系主任}$。

3. 非 3NF → 拆掉传递依赖

$R_1$ 中：系主任是非主属性，且 $\mathrm{学号}\xrightarrow{T}\mathrm{系主任}$（经系名）→ 非 3NF。

再拆 $R_1$：

模式	属性	候选键	依赖
$R_{11}$ 学生	学号, 姓名, 系名	学号	学号 → 姓名, 系名
$R_{12}$ 系	系名, 系主任	系名	系名 → 系主任
$R_2$ 课程	课程号, 学分	课程号	课程号 → 学分
$R_3$ 选课	学号, 课程号, 成绩	(学号, 课程号)	(学号, 课程号) → 成绩

每片上，非平凡 FD 的左边都是该片超键 → 已是 3NF，且同时是 BCNF（本套 $F$ 下到此即可）。

小数据对照（拆完后不再抄冗余）：

学生

学号	姓名	系名
1	小明	CS
2	小红	CS

系

系名	系主任
CS	张老师

课程

课程号	学分
C1	3
C2	2

选课

学号	课程号	成绩
1	C1	90
1	C2	85
2	C1	88

4. 另例：已是 3NF、尚非 BCNF（须再拆）

$R=(C,S,Z)$（课程, 学生, 教师），$F={CS\rightarrow Z,\ Z\rightarrow C}$。候选键 $CS$、$SZ$。
$Z\rightarrow C$：左边非超键，右边 $C$ 是主属性 → 3NF 允许，BCNF 不允许。
用 $Z\rightarrow C$ 拆成 $(Z,C)$ 与 $(S,Z)$ → BCNF（可能不再保持 $CS\rightarrow Z$）。

5. 另例：BCNF 仍不够 → 4NF

课程既对应多本教材、又对应多本参考书，且两套名单彼此独立：
$R(\mathrm{课程},\mathrm{教材},\mathrm{参考书})$ 会出现叉乘行。
存在非平凡 MVD，决定因素不是超键 → 拆成 $(\mathrm{课程},\mathrm{教材})$ 与 $(\mathrm{课程},\mathrm{参考书})$ → 4NF。

小结（对照本题）

步骤	动作	达到
多值格拆行	原子化	1NF
拆姓名/系/学分等部分依赖	上表 $R\rightarrow R_1,R_2,R_3$	2NF
拆系主任传递	$R_1\rightarrow R_{11},R_{12}$	3NF（本例=BCNF）
教师→课程类	另例再拆	BCNF
独立多值交叉	另例再拆	4NF

物理存储

存储层次

层级	特点	例子
主存 / Cache	快、易失	DRAM、CPU cache
二级（在线）	非易失、较快	SSD/闪存、磁盘
三级（近线/离线）	大、便宜、慢	磁带、部分光存储

数据库性能关键瓶颈常在 I/O（磁盘访问） ，故代价模型多以块读写与寻道为主。

磁盘要点

• 磁道（Track） / 扇区（Sector） ：扇区是读写基本单位（传统 512B，常见高级格式 4KB）。
• 块（Block） ：连续扇区组成，是 DBMS 与缓冲管理的基本传输单位。
• 访问时间 ≈ 寻道（Seek） + 旋转延迟（Rotational Latency） + 传输时间。
• 优化手段：缓冲、预读、磁盘臂调度、按访问模式组织文件。

文件与记录

数据库由文件组成；文件含记录；记录含字段。块内可放多条记录（通常记录不跨块，定长设计更简单）。

变长记录 / 槽式页（Slotted Page） ：页头记录槽位数、自由空间末尾、每条记录的偏移与长度；记录可在页内移动而槽号稳定，利于更新。

文件组织方式：

组织	含义
Heap	新记录插入空闲处，无序
Sequential	按某搜索键排序
Hashing	按哈希分桶
多表聚簇（Multitable Clustering）	相关表记录聚簇存放

缓冲管理

缓冲管理器（Buffer Manager） 决定磁盘块在内存缓冲中的安置与置换。块已在缓冲则直接返回；否则分配帧（可能淘汰其他块）再读入。

• 常用置换：LRU 等。
• Pinned block：正在使用或恢复需要，禁止写回/淘汰。
• 脏页写回策略影响事务持久性实现。

▸计算题口径

阻塞因子（Blocking Factor） ：设记录长 $L$，块大小 $B$，则每块约 $\lfloor B/L\rfloor$ 条；$N$ 条记录约 $\lceil N / \lfloor B/L\rfloor\rceil$ 块。B+ 树扇出见索引章。

索引

基本概念

搜索键（Search Key） ：用于查找的属性（集）。索引项（Index Entry） ：(search-key, pointer)。索引文件通常远小于数据文件。

两大类：

1. 有序索引（Ordered Index）
2. 哈希索引（Hash Index）

评价维度：点查 / 范围查、查找时间、插入删除维护、空间。

主索引与辅助索引

类型	含义
主索引 / 聚集索引（Primary / Clustering Index）	搜索键顺序与文件物理顺序一致
辅助索引 / 非聚集索引（Secondary / Nonclustering Index）	搜索键顺序与文件顺序不同

主索引的搜索键不必等于主键，但常常是。

稠密与稀疏

• 稠密（Dense） ：每个搜索键值（或每条记录）都有索引项。
• 稀疏（Sparse） ：仅部分搜索键有索引项；要求数据按搜索键序存放。查 $K$：找 $\le K$ 的最大索引项，再顺序扫描。

稀疏更省空间、维护轻，点查通常慢于稠密。折中：每块一条稀疏项（块内最小搜索键）。

多级索引

一级索引过大无法常驻内存时，对其再建稀疏索引，形成 outer / inner 多层，思想通向 B+ 树（B+-Tree） 。

B+ 树

• 参考：
  • 知乎-B+树看这一篇就够了
  • 知乎-一文详解 B-树，B+树，B*树
• B+树模拟网站 & B树模拟网站

为何需要

磁盘一次读一整块（常见 4KB），寻道远贵于内存比较。普通二叉搜索树（BST）每个结点往往只存一个键、两个孩子：树高约 $\log_2 K$，百万键约 20 层，最坏退化成链则更糟——每下一层可能一次随机 I/O，点查代价不可接受。

B+ 树把「一个结点 = 一块磁盘页」：一块里塞几十到上百个键与指针（扇出 fanout 很大），树高压到常为 3–4。根与高层内部页易常驻缓冲；点查通常只需几次块读。叶层再用链表串起来，使 BETWEEN、排序扫描不必反复从根下行。

▸形象：图书馆多层目录

• 内部结点像多层目录卡：只写「分界书号 + 指向下一层目录/书架区的指针」，不放整本书。
• 叶结点像真正挂书的书架格：键有序，并指向数据行（或聚簇存放的记录本身）。
• 叶链像书架侧面的「下一格」箭头：范围查询定位到起点后，沿链扫过去即可。

目录再厚，也要求每一层目录卡大小接近一块磁盘页——这就是「高扇出、矮树」的工程含义。

结构性质

所有根到叶路径等长（平衡）。

对阶参数 $n$（节点最多 $n$ 个指针）：

• 非根内部节点：$\lceil n/2\rceil$ 到 $n$ 个孩子；
• 叶节点：$\lceil (n-1)/2\rceil$ 到 $n-1$ 个搜索键；
• 根若为内部节点至少 2 孩子；若为叶则可更少。

叶节点内搜索键有序，并通过指针串成有序链表，范围查询友好。内部节点形成对叶层的多层稀疏索引。

内部节点分隔键含义（标准教材）：指针 $P_i$ 指向的子树中，搜索键落在相邻分隔值界定的区间内。

▸阶 $n$ 与「键个数 / 指针个数」

教材写法不一，答题前与 PPT 对齐即可。常见约定：

• 内部结点最多 $n$ 个孩子指针，于是最多 $n-1$ 个分隔键（指针比键多 1）。
• 叶结点存搜索键 + 记录指针（或行标识），另可有指向右兄弟叶的指针；键的上下界常用 $\lceil(n-1)/2\rceil$～$n-1$。

「半满」约束保证：插入分裂、删除合并后，除根外结点不会过稀，高度仍为对数。

结点里到底存什么

部位	存什么	不存什么（相对 B 树）
内部结点	分隔键 + 指向孩子页的指针	一般不挂完整记录；键可作「路标副本」
叶结点	全部搜索键（有序）+ 指向元组/主键的指针	—
叶与叶之间	横向链表（常还有双向链）	—

因此：真实数据入口几乎都在叶层；内部键可能与叶键重复出现（副本），查到内部匹配仍须下到叶才能取记录。代价是多占一点索引空间；收益是内部更「瘦」、同页可放更多路标 → 扇出更大、更矮。

分隔键如何指路（小例子）

设某内部结点键为 $10,\ 20,\ 30$，指针为 $P_0,P_1,P_2,P_3$（从左到右）：

指针	子树搜索键应满足
$P_0$	$<10$
$P_1$	$\ge 10$ 且 $<20$
$P_2$	$\ge 20$ 且 $<30$
$P_3$	$\ge 30$

（边界「$\ge$ / $>$」教材略有差异，同一本书内保持一致。）查键 $25$：根上比较得走 $P_2$，再在下一层重复，直到叶。

高度

约 $O(\log_{\lceil n/2\rceil} K)$，$K$ 为搜索键个数。节点大小常取一个磁盘块（如 4KB），$n$ 可达百数量级，故实际高度很小（常 3–4）。

▸数量级直觉

若每页至少约 $100$ 个孩子（半满也按 $100$ 估），则：

• 高度 1（仅根为叶）：$\le 100$ 个键量级
• 高度 2：$100^2=10^4$
• 高度 3：$100^3=10^6$
• 高度 4：$100^4=10^8$

故「亿级行、高度仍个位数」在 B+ 下并不夸张；真正贵的是叶层范围扫的 I/O，以及非聚簇时回表随机读。

查询

从根下行：在节点内找分隔区间，跟随指针；叶上精确匹配或报告不存在。范围查：定位起点后沿叶链扫描。

▸点查 vs 范围查

等值点查 WHERE id = 42：根→…→叶，比较次数在结点内可用二分；I/O 约等于树高（根常缓存）。

范围查 WHERE id BETWEEN 100 AND 200：

1. 下行定位 $\ge 100$ 的第一个叶项；
2. 沿叶链向右扫，直到键 $>200$ 停止。

不必对范围内每个键都从根走一遍。这是 B+ 相对普通 B 树在范围场景上的关键优势（B 树也可中序扫，但记录散落在各层，跳跃更多）。

插入与删除

• 插入：找到叶插入；溢出则分裂，中位键上推；可能级联至根（长高）。
• 删除：叶删除；下溢则借调或合并，可能级联（变矮）。

插入（逐步）

1. 下行找到应插入的叶（与点查相同路径）。
2. 叶未满：按序写入键（及记录指针），结束。
3. 叶满（溢出）：将原键 + 新键共 $n$ 个（按约定）排序后分裂为左、右两叶；选一个分隔键上推到父结点（B+ 中上推的键通常仍保留在右叶或按教材规则复制一份到父——叶层仍保有全部键）。
4. 父结点若因插入新孩子指针而溢出：对内部结点同样分裂，中位分隔键上推；可能一路传到根。
5. 根分裂：分配新根，树高 $+1$。这是 B+ 长高的唯一方式（总是在顶上长，保持全叶同深）。

▸叶分裂素描

设叶最多 3 个键，当前叶为 [5, 10, 15]，再插入 $12$。

• 排序得 5,10,12,15，从中劈开，例如左 [5,10]、右 [12,15]；
• 向父上推分隔（常取右叶最小键 $12$ 或中间键，依讲义）；
• 父中原指向该叶的指针，改为指向左叶，并在旁插入「键 $12$ + 右叶指针」。

可用文首模拟网站逐步点按，对照父结点键的变化。

完整建树走查

下面用同一套小参数从头插到长高，再查、再删。数字故意选成整十，便于对照。

▸本例约定（先钉死，否则每本教材对不上）

项目	本例取值	★易错
叶最多键数	3	第 4 个键进来才分裂，不是「满了就不能插」
内部最多孩子	3（故最多 2 个分隔键）	「阶 / order」定义不统一，答题以题目为准
非根叶最少键	2（$\lceil 3/2\rceil$）	删到 1 个键 = 下溢
非根内部最少孩子	2	根可暂时只有 1 个键、2 个孩子
叶分裂后上推	复制右叶最小键到父；两叶都保留全部键	当成 B 树「搬走」会丢叶上的键
内部分裂上推	中间分隔键上移到父（内部可不留副本）	与叶的「复制」搞混

图例：[a|b] = 内部路标；{a,b,c} = 叶（真实键）；→ = 叶链表。

▸第 0～3 步：只有一层（根即叶）

依次插入：5, 15, 25。

插 5  →  根叶 {5}
插 15 →  根叶 {5, 15}
插 25 →  根叶 {5, 15, 25}   ← 已满（3 个），但还合法

★难点：满 ≠ 立刻分裂。分裂发生在「再插进第 4 个」时。

▸第 4 步：第一次叶分裂 → 树高变为 2

再插 35。临时序列 5,15,25,35（4 个）须分裂：

• 左叶 {5, 15}，右叶 {25, 35}
• 复制右叶最小键 25 到新根（路标）
• 叶链：{5,15} → {25,35}

      [25]          ← 新根：只有路标，不存整行数据
     /    </span>{5,15} → {25,35}    ← 全部真实键仍在叶；25 在叶里也有一份
{5,15} → {25,35}    ← 全部真实键仍在叶；25 在叶里也有一份

★易错 1：以为 25「搬上去」后右叶变成 {35} —— 错。B+ 叶必须留着 25。
★易错 2：在根 [25] 上看到 25 就宣布「找到记录」—— 错。B+ 点查必须落到叶。

▸第 5～6 步：右叶再满、再裂；根变成两个路标

插 45：走 $\ge 25$ 的右叶 → {25,35,45}（满，合法）。
插 55：右叶溢出 25,35,45,55 → 左 {25,35}、右 {45,55}，复制 45 给父。

父原为 [25]（2 孩子），现变为 [25|45]（3 孩子，仍未超）：

      [25 | 45]
     /    |    </span>{5,15}→{25,35}→{45,55}
{5,15}→{25,35}→{45,55}

路标怎么用（查 40）：$40\ge 25$ 且 $40<45$ → 走中间孩子 {25,35}；叶上无 40 → 不存在。
★形象：[25|45] 像两块隔板，把数轴切成 $(-\infty,25),\ [25,45),\ [45,+\infty)$ 三段（边界写法与讲义对齐即可）。

▸第 7～8 步：右叶再裂 → 父溢出 → 根分裂 → 树高变为 3

插 65：最右叶 → {45,55,65}。
插 75：溢出 45,55,65,75 → {45,55} 与 {65,75}，复制 65 给父。

父若硬塞会变成 [25|45|65] 且 4 个孩子——超过「最多 3 孩子」→ 内部分裂：

1. 临时父键：25, 45, 65（中间是 45）
2. 45 上移成新根（内部是搬走，不必在下层内部再留 45）
3. 左内部留下 [25]，管叶 {5,15}、{25,35}
4. 右内部留下 [65]，管叶 {45,55}、{65,75}

            [45]              ← 新根（树高 +1 的唯一方式）
          /      </span>      [25]        [65]        ← 内部：只指路     /    \      /    </span>{5,15}→{25,35}→{45,55}→{65,75}
      [25]        [65]        ← 内部：只指路
     /    \      /    </span>{5,15}→{25,35}→{45,55}→{65,75}
{5,15}→{25,35}→{45,55}→{65,75}

★易错 3：以为任意结点分裂都会长高 —— 只有根分裂才长高。
★易错 4：叶上推是「复制」，内上推是「上移」——两种不要混。
★对照：键 45 仍在叶 {45,55} 里；根上的 45 只是路标副本。

▸第 9～10 步：往左叶塞，再裂一次（父未满）

插 10：根 $10<45$ → 左；内部 $10<25$ → 叶 {5,15} → {5,10,15}。
插 20：同叶溢出 5,10,15,20 → {5,10} 与 {15,20}，复制 15 给左内部。

左内部由 [25] 变为 [15|25]（恰好 3 孩子，合法）：

              [45]
            /      </span>      [15|25]       [65]     /   |   \     /    </span>{5,10}→{15,20}→{25,35}→{45,55}→{65,75}
      [15|25]       [65]
     /   |   \     /    </span>{5,10}→{15,20}→{25,35}→{45,55}→{65,75}
{5,10}→{15,20}→{25,35}→{45,55}→{65,75}

最终叶链（从小到大）：5,10 | 15,20 | 25,35 | 45,55 | 65,75 —— 已覆盖全部插入键，无遗漏、无只存在于内部的「幽灵数据键」。

▸用这棵树做点查与范围查

点查 20

1. 根：$20 < 45$ → 左孩子 [15|25]
2. 内部：$20 \ge 15$ 且 $20 < 25$ → 中间叶 {15,20}
3. 叶上命中 20 → 再跟随记录指针（本例省略）取行

★若在根或内部「看见等于某键」就停 —— 那是 B 树习惯，B+ 仍须下叶。

范围查 $[20,50]$

1. 先点查定位 $\ge 20$ 的起点 → 叶 {15,20} 的 20
2. 沿 → 扫描：20, 25,35, 45, 下一叶 55$>50$ 停止
3. 结果键：20,25,35,45

★不必对 25、35、45 各走一遍根→叶；叶链就是为这件事准备的。

▸删除走查：下溢时「合并」（借不动就合）

在最终树上删 10（比删最右端更干净，便于手算）：

1. 点查路径：$10<45$ → 左内部；$10<15$ → 叶 {5,10}
2. 删 10 后叶变成 {5} —— 少于最少 2 个键 → 下溢
3. 右兄弟 {15,20} 也只有 2 个键（已到下限），无法再借（两叶合计仅 3 个键，匀不成「每叶 ≥2」）
4. 于是合并：{5} 与 {15,20} → 一叶 {5,15,20}；父 [15|25] 删掉路标 15 及多余指针

合并前左内部:     [15 | 25]
                 /    |    </span>             {5}  {15,20}  {25,35}     ← {5} 已下溢合并后左内部:        [25]                    /    </span>             {5,15,20} → {25,35}       ← 路标 15 随合并删掉
             {5}  {15,20}  {25,35}     ← {5} 已下溢

合并后左内部:        [25]
                    /    </span>             {5,15,20} → {25,35}       ← 路标 15 随合并删掉
             {5,15,20} → {25,35}       ← 路标 15 随合并删掉

整棵变为：

            [45]
          /      </span>        [25]      [65]       /    \    /    </span>{5,15,20}→{25,35}→{45,55}→{65,75}
        [25]      [65]
       /    \    /    </span>{5,15,20}→{25,35}→{45,55}→{65,75}
{5,15,20}→{25,35}→{45,55}→{65,75}

★易错：看见下溢就「向兄弟借一个」——若兄弟自身也在下限，借完对方会下溢，必须改走合并。
★借调何时可以：例如某叶 {5,10,15}（3 个）与下溢叶 {20}（1 个），合计 4，才能匀成两叶各 2，并改父路标。

若合并导致内部下溢，继续向上借/合；根只剩一个孩子时丢掉空根，树高 −1。

▸易错点清单（对着上树自检）

★标记	错误想法	正确理解
1	内部有键 = 找到数据	B+ 内部键是路标副本；数据入口在叶
2	上推 = 从叶删掉该键	叶分裂上推是复制；叶上键一个都不能少
3	内部分裂也是复制中间键	内部中间键通常上移；与叶不同
4	结点一满就分裂	溢出时（再进一个）才分裂
5	每次分裂树都变高	只有根分裂才高度 +1
6	范围查每个键都从根找	定位起点后走叶链
7	「B-树」是另一种减号树	中文 B-树多半就是 B 树（见下节）
8	阶 $n$ 全世界同一含义	先看题目：限制的是「最大孩子数」还是「最大键数」

插入序列小结（本例）：5,15,25,35,45,55,65,75,10,20 → 最终三层树；关键拐点是插 35（高变 2）、插 75（高变 3）、插 20（左内部出现双路标）。

删除（逐步）

1. 下行到叶，删掉目标键。
2. 若叶仍满足最少键数：可能还需把父中仅作路标的副本键改掉（实现相关）；结束。
3. 下溢（键数 $<$ 下限）：
   • 优先向兄弟借调（重新分布），并更新父中分隔键；
   • 兄弟也太瘦则合并两叶，并从父中删掉相应分隔与指针。
4. 父若下溢：同样借调/合并，可能传到根。
5. 根只剩一个孩子：丢掉空根，树高 $-1$。

相对插入，删除的边界与「父键是否为副本」更绕，考试常考思想：下溢 → 借或合；合则可能变矮。

与 B 树

B 树（B-Tree） 内部节点也可带记录指针；B+ 树数据（或主键指针）主要挂在叶层，内部更“胖”、扇出更大，范围扫更干净。实践中数据库多用 B+ 树家族。

树族对照

名称极易混淆，先定术语：

写法	通常指什么
B 树 / B-tree	Bayer & McCreight（1972）多路平衡查找树；英文一般写作 B-tree
B-树（中文教材）	多数情况就是 B 树，「B-」是中文连写习惯，不是「B 减树」
B+ 树 / B+-tree	叶存全量键并拉链；内部主要作索引
B* 树 / B*-tree	B 树（或 B+）的变体：结点更满、溢出先挤兄弟再分裂
B*+ 等	工程/论文中的进一步变体，考纲少单独考

▸「B-树」不是另一种树

口语里「B减树」若被理解成「比 B 树少点什么」是误传。中文「B-树」≈ 英文 B-tree ≈ 下文的 B 树。真正要和 B+ 对比的，是这种「内外层都可挂数据」的经典 B 树。

总表

维度	B 树	B+ 树	B* 树（常见变体）
数据/记录指针位置	内部 + 叶都可有	主要在叶；内部多为路标	多基于 B 或 B+ 改填充策略
内部结点空间	键旁常跟记录指针，占空间	几乎只放键+孩子指针，更胖	同所基于的树，但填充率更高
扇出 / 高度	同页大小下扇出往往小于 B+	扇出更大，通常更矮	平均填充高 → 空间利用率更好，高度也偏矮
叶链表	经典定义不要求	有（范围查核心）	视实现；B*+ 常保留
点查	可能在内部就命中结束	必须落到叶	同所基于的树
范围 / 顺序扫	中序遍历整棵，跳层多	叶链顺序扫，更干净	优于无链表的纯 B
溢出策略	满则分裂（约一半一半）	同左，叶分裂并上推/复制分隔键	先与兄弟再分配；两兄弟都满才一起分裂成三，填充约 $\ge 2/3$
DB 实践	理论与部分文件系统/历史引擎	InnoDB、多数 RDBMS 索引主流	思想影响实现细节，名称不如 B+ 常考

与 BST / AVL / 红黑对照（为何不是它们做磁盘索引）

	内存树（AVL / 红黑）	磁盘树（B / B+）
设计目标	降低比较次数、保持 $O(\log n)$	降低块 I/O 次数
结点大小	一个键量级	对齐磁盘页（KB 级）
平衡手段	旋转	分裂 / 合并 /（B*）再分配
典型场景	进程内 map、语言运行时	数据库索引、部分文件系统目录

AVL/红黑在内存中很优秀；直接当磁盘索引会因树高与随机读过多而不合适。B+ 是「为块设备改写的多路平衡树」。

B 与 B+：同一趟查找差在哪

▸查键 $K$

B 树：下行时若某内部结点就含 $K$，可立刻跟随记录指针结束——点查有时更短。

B+ 树：内部即使看见等于 $K$ 的分隔键，仍只当作路标，继续下到叶取唯一的数据入口。

换范围查询「$K$ 到 $K+1000$」：B+ 从叶起点沿链走；B 树需中序绕树，缓存局部性与实现复杂度通常更差。OLTP/OLAP 混合负载下，范围与排序扫描极常见 → 引擎倾向 B+。

B*：更「挤」的结点

经典 B/B+ 分裂后两兄弟大约半满，空间利用率期望约 50% 量级起跳。B* 的典型改动：

1. 溢出时不立刻把当前结点劈成两个半满，而是看右（或左右）兄弟是否还有空位；
2. 有空则键与指针再分配（匀一匀），只改父中少量分隔键；
3. 两结都满，才把两结的键合起来分裂为三个结点，使填充约 $\ge 2/3$。

效果：平均页更满 → 同样数据占用更少页、树更矮；单次插入可能多碰一个兄弟页，写放大略增。考试记住「先挤兄弟，再三分」即可。

聚簇 B+ 与二级索引（实现向）

形态	叶存什么	范围扫时
聚簇 / 主键索引（如 InnoDB 聚簇）	整行或主键序的数据页	叶链扫 ≈ 按主键顺序读表
二级 / 辅助索引	搜索键 + 主键（或行指针）	先扫索引叶，再按主键回表；乱序回表易随机 I/O

覆盖索引（查询列都在二级索引叶上）可免回表——概念速查表中「覆盖索引」同此。

选型小结

需求	更合适
数据库表索引、既要等值又要范围	B+
理解多路平衡、证明与教材定义	B 与 B+ 对照学
强调空间利用率 / 分裂策略考题	提到 B*
纯内存有序映射	AVL / 红黑 / 跳表等
只要等值、几乎不要范围	哈希索引（见下节）

与本课其它章的关系

B+ 树本身是数据结构；放进「数据库系统」是因为它几乎就是 InnoDB 一类引擎里索引页的组织方式。前面学的分裂/叶链，是在为后面的 SQL 怎么变快、代价公式里的 $h_i$ 从哪来 做准备。

▸一张图：B+ 卡在整门课的哪一环

逻辑层（前面各章）              物理层（本章起）
─────────────────              ────────────────────────────
关系代数 / SQL 写出要什么
        │
        ▼
查询优化：要不要走索引？        ← 第 9 章；候选计划里常有「Index Scan」
        │
        ▼
查询处理：用哪种扫描/连接       ← 第 8 章；$h_i$、辅助索引随机 I/O
        │
        ▼
【索引 = 多棵 B+】              ← 第 7 章（当前）
        │
        ▼
物理存储：页、缓冲、文件        ← 第 6 章；B+ 一个结点 ≈ 一个磁盘页
        │
        ▼
事务/恢复：改叶也要写日志       ← 第 10～12 章；索引页与数据页一样进 WAL

★一句话：SQL 是「点菜」，B+ 是「后厨怎么按号快速取盘子」；没有 B+，每道菜都得把整库桌子扫一遍（全表扫描）。

▸从一条 SQL 落到一棵 B+

设表 student(sid PK, name, score)，引擎用 聚簇 B+ 按 sid 组织行（叶上直接是整行，或主键序数据页）。

用户写的 SQL	引擎大致在 B+ 上做什么
SELECT * FROM student WHERE sid = 20	沿主键 B+ 点查到叶，取出该行
SELECT * FROM student WHERE sid BETWEEN 20 AND 50	点查定位起点，再沿 叶链顺序读
SELECT * FROM student WHERE score = 90	若 score 无索引 → 往往 全表/全聚簇扫；若有 score 上的二级 B+ → 先在该树叶上找到主键，再回主键 B+ 回表
CREATE INDEX idx_score ON student(score)	再建一棵以 score 为键的 B+；之后优化器才可能选它
INSERT / UPDATE / DELETE	维护所有相关 B+：叶插入可能分裂，与前文手算同一套规则

★易错：以为「表」和「B+」是两样无关的东西。在聚簇引擎里，表的主存储常常就是那棵主键 B+；二级索引是额外的 B+，「表」并不是另存一份无序堆那么简单（堆表引擎另说，概念课以聚簇理解为主）。

▸和本章前面名词怎么对上号

索引章开头的术语，在 B+ 里的落点：

前面的说法	在 B+ 里是什么
搜索键	B+ 结点里比较用的键（主键或 score 等）
索引项 (键, 指针)	内部：键 + 孩子页号；叶：键 + 行指针/主键
多级索引 outer/inner	B+ 的内部各层 = 自动维护的多级稀疏目录
稠密索引	二级 B+ 叶上通常每个键值都有项（非唯一则多条）
稀疏索引	聚簇 B+ 可按「每数据页一个键」理解稀疏思想；经典稀疏一级索引是 B+ 的简化前身
主索引 / 聚簇	叶顺序 = 行的物理（或主键）顺序的那棵 B+
辅助 / 非聚簇	另一棵 B+；叶不直接持有完整行，需回表

★「多级索引思想通向 B+」：手工建 outer 索引很脆；B+ 用分裂/合并保证层数平衡，并把叶拉成链，范围查不用反复从根走。

▸和《物理存储》章：为何结点大小像「一页」

第 6 章强调：磁盘按块/页读写，缓冲管理器按页置换。B+ 把「一个结点」做成「一页」的大小，于是：

• 下行一层 ≈ 读一页（或命中缓冲则 0 次磁盘）；
• 树高 3～4 ⇒ 点查几次 I/O，与存储章的代价口径一致；
• 根页几乎总在缓冲里，实际常比「高度」少一次物理读。

算扇出 $n\approx\lfloor B/(a+b)\rfloor$ 时，$B$ 就是页大小——公式不是抽象数学，是「一页能塞多少路标」。

▸和《查询处理 / 优化》章：计划里的 Index 从哪来

第 8 章选择代价表里的「主索引等值 ≈ $h_i+1$」：

• $h_i$ = 该 B+ 的高度（根到叶）；
• 「+1」常对应读到数据页（聚簇时叶可能已是数据；二级索引则是回表）。

「辅助索引可能每条匹配一次随机 I/O」：二级 B+ 叶上主键乱序时，回表像随机翻书——这就是优化器有时宁可全表扫的原因（匹配行太多时）。

第 9 章优化：等价计划包括「全表扫 vs 走哪棵 B+」。有索引 ≠ 一定用；选择性差（如性别）时全表可能更便宜。B+ 提供的是「可选的高速通路」，不是强制通路。

▸和《事务 / 恢复》章：改索引也是改数据库

插入一行若导致叶分裂，会改多个索引页。这些页与数据页一样：

• 经缓冲读写；
• 遵循 WAL：页刷盘前日志先落稳；
• 崩溃恢复时索引页也要 redo/undo，否则树结构会坏。

并发下，事务锁的粒度可以是行，也可以涉及索引页/间隙（间隙锁与幻读相关）。细节在并发章；此处只需建立印象：B+ 不是只读目录，写语句会改它，也在 ACID 边界内。

▸对照复习：三层模式里 B+ 属于哪一层

层次	用户看到什么	B+ 在哪
外模式 / 视图	SELECT 结果、视图	一般不可见
概念 / 逻辑模式	CREATE TABLE、键、约束	只声明「有主键 / 有索引」，不写树形
内模式 / 物理	文件、页、索引实现	B+ 长在这里

CREATE INDEX 改的是内模式；逻辑上的「学生表」模式可不变 → 呼应导论里的物理数据独立性：换一种索引实现，SQL 文本往往不用改，只是计划与快慢变了。

▸读课顺序上的「断裂感」从哪来

感觉	实际关系
前面全是关系代数/范式，突然冒出树	逻辑设计保证「表设计得对」；B+ 保证「大表上查得动」——问题域不同，都在 DBMS 里
手算分裂与 SQL 无关	每个 INSERT 都可能在引擎里做同款分裂；手算是为看懂 $h_i$ 与维护代价
聚簇 / 二级那张表像另一门课	正是「一表多树」：1 棵主键 B+ + 若干二级 B+；SQL 条件决定走哪棵
哈希索引怎么又杀出来	同属「索引」大类；等值友好、范围弱；和 B+ 是并列选项，不是 B+ 的一种

建议复习路径：导论三层模式 → 本段「SQL→B+」表 → 完整建树走查 → 查询处理里带 $h_i$ 的代价行 → 回到本段自检。

哈希索引

用哈希函数把搜索键映射到桶。等值点查平均 $O(1)$，范围查询弱。静态哈希桶数固定；动态哈希（Dynamic Hashing） / 可扩展哈希（Extendable Hashing） 随数据量调整。教材强调：哈希索引通常作辅助索引形态出现（具体产品另论）。

扇出与块数估算

设块大小 $B$，指针大小 $a$，搜索键大小 $b$。B+ 内部节点近似：

$$
n \approx \Big\lfloor \frac{B-a}{a+b}\Big\rfloor + \text{（按讲义精确式取整）}
$$

（指针比搜索键多一个，写计算过程时与 PPT 公式对齐。）再由记录数估计叶块数与高度上下界（全满 / 半满）。

▸选型直觉

• 等高值点查、几乎无范围：哈希可考虑。
• 需要 BETWEEN、排序扫描、前缀匹配：B+ 树。
• 主键聚集：主索引 B+；其余常用辅助索引。

查询处理

流水线

1. 解析与翻译（Parsing & Translation） ：SQL → 关系代数树
2. 优化（Optimization） ：在等价计划中按代价选优
3. 求值（Evaluation） ：执行引擎跑物理算子

代价主体：磁盘块传输 + 寻道（CPU 相对次要，考题常忽略或另给）。缓冲越大，重复读越少；估代价常按可用内存偏紧的最坏情形。

记：$b_r$ 为关系 $r$ 的块数；$t_T$ 块传输时间；$t_S$ 寻道时间。

▸符号总表（本章公式共用）

符号	含义	形象
$r,,s$	两张表（关系）	外层常叫 $r$，内层常叫 $s$
$n_r,,n_s$	表的元组（行）数	「有多少条记录」
$b_r,,b_s$	表占磁盘的块（页）数	「占多少页」；通常 $b_r \approx \lceil n_r / \text{每块行数}\rceil$
$M$	排序/连接可用的内存块数	缓冲里能同时放下几页
$h_i$	索引（B+）高度	根到叶大约几层
$c$	对内表做一次索引查找的代价	常取约 $h_i$（再加回表则更大）
$t_T$	传一块的时间	考题若只数「块次数」可不展开
$t_S$	一次寻道时间	随机读多时寻道很贵

★易错：$n_r$ 与 $b_r$ 不是一回事。嵌套循环公式里对外表用 $n_r$、对内表用 $b_s$，因为「每个外层元组」要扫一遍内表的「所有块」。

选择代价（大纲级）

算法	典型代价（数量级）
线性扫描	$\approx b_r$ 次传输 + 1 次寻道；等值且唯一搜索键可平均 $b_r/2$
主索引 + 等值（搜索键）	约 $h_i + 1$ 次读写相关（$h_i$ 索引高度）
主索引 + 非唯一	索引高度 + 连续多块扫描
辅助索引	可能每条匹配记录一次随机 I/O，选择性差时极慢

▸选择代价：字母怎么代入

设 $b_r=1000$，$h_i=3$，查唯一主键。

• 线性扫描：最坏读完表 ≈ $1000$ 次块传输；若记录均匀且命中唯一键，平均约读一半 ≈ $500$。
• 主索引等值：沿 B+ 下行约 $h_i=3$ 次，再读 1 个数据页 → 约 $3+1=4$。这就是「$h_i+1$」的来历（聚簇叶已是数据时，讲义可能写成约 $h_i$）。
• 辅助索引：先付约 $h_i$ 找到主键列表；若有 $k$ 条匹配且行散落，最坏再加约 $k$ 次随机读数据页 —— 所以 $k$ 很大时可能不如全表扫。

外排序

外部归并：内存 $M$ 块时，生成初始 run，再多路归并。归并趟数约 $\lceil\log_{M-1}(b_r/M)\rceil$ 量级；总磁盘访问约 $2b_r(1+\text{趟数})$（与讲义公式对齐记忆）。

▸外排序在干什么（公式背后的故事）

表太大，内存装不下，不能一次 sort。做法分两阶段：

1. 造初始 run：每次读入最多 $M$ 块到内存，排好序写回磁盘，得到一段有序的 run。整表 $b_r$ 块 → 大约 $\lceil b_r/M\rceil$ 个初始 run。
2. 多路归并：内存留 1 块给输出，其余约 $M-1$ 块各读一个 run 的头 → 一次最多归并 $M-1$ 路。run 太多就多趟，直到并成一个有序文件。

★为何底数是 $M-1$：一路输入占一块缓冲，输出还要一块，故同时打开的输入 run 数 ≈ $M-1$。

▸趟数公式拆开：$\lceil\log_{M-1}(b_r/M)\rceil$

零件	含义
$b_r/M$	初始 run 个数（约）
底数 $M-1$	每一趟能把多少个 run 合成 1 个
$\log_{M-1}(\cdots)$	要多少趟才能把「许多 run」收成「1 个」
外层 $\lceil,\rceil$	趟数向上取整

数字：$b_r=1000$，$M=100$。

• 初始 run 数 ≈ $1000/100=10$。
• 每趟最多并 $M-1=99$ 路，$10\le 99$ → 1 趟就并完。
• $\lceil\log_{99}(10)\rceil=\lceil\text{很小的数}\rceil=1$，一致。

若 $b_r=10^6$，$M=100$，初始 run ≈ $10^4$；$\lceil\log_{99}(10^4)\rceil=\lceil 2.00\ldots\rceil=3$ 量级（手算用换底公式 $\ln/\ln$）。
★易错：写成 $\log_M$ 或 $\log_2$ —— 底必须是 $M-1$（多路个数）。

▸总访问 $2b_r(1+\text{趟数})$：那个 2 和 1 从哪来

每一趟（含最初造 run）大致要把整个表 读一遍 + 写一遍 → 系数 2。

• 造初始 run：读 $b_r$ + 写 $b_r$ → $2b_r$（公式里的「1」对应这一阶段）
• 之后每一趟归并：再读 $b_r$ + 写 $b_r$ → 每趟又是 $2b_r$
• 共「1 + 趟数」个这样的阶段 → $2b_r(1+\text{趟数})$

接上例 $b_r=1000$，$M=100$，趟数 $=1$：总块传输 ≈ $2\times 1000\times(1+1)=4000$。
★「趟数」只计归并趟，不含造 run；造 run 已单独算进那个 1。若某讲义把造 run 也叫第 0 趟，数字会差一截，以课堂定义为准。

连接算法

连接：把满足条件的 $r$ 行与 $s$ 行拼在一起（如 $r.a=s.a$）。下面代价默认数 块传输次数；寻道另计时会更大。

嵌套循环

对 $r$ 每元组扫 $s$：传输约 $n_r\cdot b_s + b_r$，寻道很多。适合 $r$ 极小。

▸元组嵌套循环：$n_r\cdot b_s + b_r$

算法：for 每一行 $t\in r$：把 $s$ 整表扫一遍，看哪些行能和 $t$ 拼上。

项	为何出现
$b_r$	外表 $r$ 本身要读进来（扫一遍外表）
$n_r\cdot b_s$	外表有 $n_r$ 行，每行都让内表 $s$ 的 $b_s$ 块再读一遍

数字：$n_r=1000$，$b_r=50$（每块约 20 行），$b_s=200$。
传输 ≈ $1000\times 200 + 50 = 200050$。几乎是「内表被扫一千遍」。
★为何用 $n_r$ 不用 $b_r$：循环粒度是元组，不是块；同一块里的 20 行会触发 20 次「扫遍 $s$」。
★适用：$r$ 极小（几行）时还能忍；否则改块嵌套 / 索引 / 哈希 / 归并。

块嵌套循环

以块为单位：最坏约 $b_r\cdot b_s + b_r$ 次传输。可用 $M-2$ 块作外层单元降低扫内表次数。

▸块嵌套：$b_r\cdot b_s + b_r$，以及 $M-2$

算法（内存只够各放 1 块时）：每次读 $r$ 的 1 块进内存，对这一块去扫遍 $s$ 的所有块；再换 $r$ 的下一块。

项	为何出现
$b_r$	读完外表所有块
$b_r\cdot b_s$	外表每一块，都把内表 $b_s$ 块扫一遍

同上数字：$b_r=50$，$b_s=200$ → ≈ $50\times 200 + 50 = 10050$，比元组嵌套的 $200050$ 小一个数量级（因为一块里的多行共享同一次扫 $s$）。

内存有 $M$ 块时：留 1 块给内表当前页、1 块给输出，其余 $M-2$ 块一次装入外表的一大段。内表被完整扫描的次数变成约 $\lceil b_r/(M-2)\rceil$，传输约

$$
\lceil b_r/(M-2)\rceil\cdot b_s + b_r
$$

（与后文「代价公式速查」一致。）$M$ 越大，扫内表次数越少。
★易错：块嵌套公式里是 $b_r\cdot b_s$，元组嵌套是 $n_r\cdot b_s$ —— 多一个「每块行数」的差别。

索引嵌套循环

内表有索引：对外表每元组做一次索引查找，代价 $\approx b_r + n_r\cdot c$，$c$ 为一次选择代价。

▸索引嵌套：$b_r + n_r\cdot c$

算法：扫外表 $r$；对每一行，用内表连接列上的 索引（常为 B+） 点查匹配行，不必扫遍 $s$。

项	含义
$b_r$	把外表读一遍
$n_r$	外表行数；每行触发一次索引查找
$c$	一次索引查找的块代价，例如主索引等值约 $h_i$ 或 $h_i+1$；辅助索引还要加回表

数字：$b_r=50$，$n_r=1000$，$c=4$（B+ 高 3 + 数据页 1）。
代价 ≈ $50 + 1000\times 4 = 4050$。
对比块嵌套最坏 $10050$：有好索引且 $c$ 小时，索引嵌套更优；若几乎每行都匹配大量内表行，$c$ 变大或回表爆炸，优化器可能改选别的。
★$c$ 不是常数魔法，而是「选择代价」那一行套进 B+ 的 $h_i$。

归并连接

两表在连接属性上有序（或先排序）：一次扫描完成等值/自然连接。传输约 $b_r+b_s$（不含排序）。

▸归并连接：$b_r+b_s$（不含排序）

前提：两表已按连接属性排好序（或一边是索引顺序扫）。

算法：两个指针从左往右走，像合并两个有序数组；相等则输出匹配，谁小谁前进。各读一遍即可。

项	含义
$b_r+b_s$	各顺序读一遍的块数之和
「不含排序」	若事先无序，还要加上文外排序代价 $2b_r(1+\text{趟数}_r)+2b_s(1+\text{趟数}_s)$

数字：$b_r=50$，$b_s=200$，已有序 → 传输 ≈ $250$。非常便宜。
★考题若写「归并连接代价 $b_r+b_s$」，默认有序前提已满足；否则必须把排序加回去。

哈希连接

按连接属性哈希分区再匹配。内存足够时可很高效；需估计分区与探测阶段读写。

▸哈希连接：在算什么（提纲级）

思想：用同一哈希函数 $h$ 把两表的连接键分到若干桶；只需在同号桶之间做匹配（不同桶不可能等值连接）。

典型两阶段（经典 Grace Hash Join 直觉）：

1. 分区（Partition）：扫描 $r$（再扫描 $s$），按 $h$ 写出各桶文件 —— 大约各读一遍、写一遍量级。
2. 探测（Probe）：对每个桶，把较小侧装进内存哈希表，扫另一侧探测匹配。

内存够把一侧（构建端）完全放下时，可简化成「构建 + 探测」两遍扫描，非常快。
内存不够则分区变多、可能递归分区，代价上升。考试常记：等值连接 + 内存尚可 → 哈希连接常是优选；范围连接用不了哈希。

★与归并比：哈希不要求事先有序，但对「$<$ / BETWEEN」类谓词无直接帮助；归并/索引顺序扫更擅长顺序与范围。

▸五种连接怎么选（同一组数直觉）

沿用 $n_r=1000$，$b_r=50$，$b_s=200$，$c=4$，已有序时：

算法	块传输粗估	何时倾向用
元组嵌套	$\approx 200050$	几乎不用
块嵌套（$M$ 很小）	$\approx 10050$	无索引、无序、内存紧
索引嵌套	$\approx 4050$	内表连接列有好索引
归并（已有序）	$\approx 250$	两表已序或排序可分摊
哈希	常若干倍 $(b_r+b_s)$ 量级	等值连接、内存够

优化器比较的就是这类数量级（再加寻道、CPU、结果大小）。

▸物化与流水线

物化（Materialization） ：每步写出中间关系再读入。流水线（Pipelining） ：算子间流水传递元组，减少中间落盘。

上面公式多假设算子独立、中间结果落盘再读；若流水线直接把连接输出喂给下一算子，可少算一部分写回与再读。

查询优化

两种层面

1. 选等价的逻辑表达式（关系代数变换）
2. 选物理算子与执行策略（索引、连接算法、连接顺序）

基于代价的优化（Cost-based Optimization） ：枚举（或动态规划）计划 → 用统计信息估中间结果大小 → 选最小代价。统计量包括：$n_r$、$b_r$、元组大小、$V(A,r)$（属性不同值个数）等。

▸优化在干什么（接上一章）

SQL 只说「要什么」，不说「怎么取」。引擎大致两步：

1. 逻辑优化：把关系代数树改成结果相同、但往往更小中间结果的形状（如下推选择）。
2. 物理优化：同一逻辑树，选全表扫还是走 B+、选哪种连接（嵌套/归并/哈希）、先连哪两张表——用上一章的 块传输公式 估代价，取最小者。

★「等价」= 算出来的表一样（集合/多重集语义下）；「更优」= 磁盘 I/O（及 CPU）更少。优化器可能估错统计，但思路是代价比较。

▸优化专用符号（在 $n_r,b_r$ 之外）

符号	含义	形象
$V(A,r)$	关系 $r$ 在属性 $A$ 上的不同值个数	score 只有 0～100 则 $V\le 101$
$n_r / V(A,r)$	等值选择后的估计行数（均匀假设）	「平均每个取值摊到几行」
$\sigma$ / $\Pi$ / $\times$ / $\bowtie$	选择 / 投影 / 笛卡尔积 / 连接	见关系代数章
选择率	选择后行数 / 原行数	越小越「严」

统计量来自数据字典 / 直方图；考试常直接给 $n_r$、$V(A,r)$ 让代入。

重要等价规则

• $\sigma_{\theta_1\land\theta_2}(E)=\sigma_{\theta_1}(\sigma_{\theta_2}(E))$；选择可交换。
• 嵌套投影只保留最外层需要的属性。
• $\sigma_\theta(E_1\times E_2)=E_1\bowtie_\theta E_2$。
• 自然连接交换律、结合律；注意左右深树空间。
• 选择下推：若条件只涉及 $E_1$ 属性，则 $\sigma(E_1\bowtie E_2)=\sigma(E_1)\bowtie E_2$。
• 投影可下推到连接两侧（保留连接属性）。
• 并、交的交换结合；选择对差/并等的分配（按规则表）。

▸规则逐条：式子在说什么

1. 合取拆开 / 选择可交换

$$
\sigma_{\theta_1\land\theta_2}(E)=\sigma_{\theta_1}(\sigma_{\theta_2}(E))=\sigma_{\theta_2}(\sigma_{\theta_1}(E))
$$

「同时满足两个条件」= 先滤一个再滤另一个，顺序可换，结果行集相同。优化时常先做选择率更小的那个，让后面更轻。

2. 嵌套投影只留最外层需要的列

$\Pi_a(\Pi_{a,b}(E))$ 与 $\Pi_a(E)$ 一样。中间多投影的列若最终不要，可早丢掉以减小元组宽度（每块多装几行）。

3. 笛卡尔积 + 选择 = 条件连接

$$
\sigma_\theta(E_1\times E_2)=E_1\bowtie_\theta E_2
$$

左边：先爆炸成 $|E_1|\cdot|E_2|$ 行再过滤（极贵）。右边：连接算法直接按 $\theta$ 匹配（上一章那些公式）。★写法等价，实现绝不能真先做大叉乘。

4. 连接交换 / 结合

$r\bowtie s = s\bowtie r$（自然/等值连接结果行集合相同，列顺序或实现细节另说）。
$(r\bowtie s)\bowtie t = r\bowtie(s\bowtie t)$。
三表以上时，先连哪一对会大幅改变中间结果大小与代价——这是物理优化要搜的空间。

5. 选择下推（最重要的启发式之一）

若谓词 $\theta$ 只涉及 $E_1$ 的列，则

$$
\sigma_\theta(E_1\bowtie E_2)=\sigma_\theta(E_1)\bowtie E_2
$$

形象：先在小表里扔掉不合格行，再去连接，避免「先连出一张大表再删」。
例：student ⋈ SC 且 WHERE student.dept='CS' → 应先 $\sigma_{\mathrm{dept=CS}}(\mathrm{student})$ 再连接。

6. 投影下推

连接前可先丢掉与连接键、最终输出无关的列（但连接属性必须保留）。目的：行变更窄，I/O 更少。

7. 并 / 交的交换结合

与集合运算一样可换序；选择对并等有分配律（$\sigma(E_1\cup E_2)=\sigma(E_1)\cup\sigma(E_2)$），便于把过滤推到并的两侧。

▸小查询：下推前后差多少行

设 $|student|=10000$，$|SC|=50000$，CS 系学生约 $500$ 人，每生平均 5 门课。

• 先连接再选：中间约接近 $10000$ 与选课的匹配规模（可达数万行），再滤 dept。
• 先选再连接：学生侧先剩 $500$ 行，再连 SC，中间约 $500\times 5=2500$ 量级。

逻辑结果相同；I/O 与 CPU 差一个数量级很常见——这就是「为何要等价变换」。

启发式

• 尽早选择（减小中间结果）
• 尽早投影（减小元组宽度）
• 先做最严格的选择 / 小结果连接
• 多表连接常用左深树（Left-deep） 以便流水与动态规划

▸启发式对照「代价公式」

口诀	对应原因
尽早选择	中间 $
尽早投影	行变更短 → 每块行数↑ → 同样行数对应更小 $b_r$
先严后松	选择率小的条件先做，尽快缩基数
先连小结果	避免早期就搞出巨大中间表再往下连

左深树：三表连接只考虑形如 $((r_1\bowtie r_2)\bowtie r_3)\bowtie\cdots$ 的计划，而不枚举所有二叉树形状。计划数从「卡特兰数爆炸」降到可动态规划；且左孩子常是上一连接的流水输出，利于流水线。
★左深不一定全局最优，但是教材与许多优化器的实用搜索空间。

▸逻辑优化 vs 物理优化（别混）

	逻辑	物理
改什么	$\sigma/\Pi/\bowtie$ 树的形状与顺序	扫描方式、连接算法、是否用索引
依据	等价规则 + 启发式	代价模型（上一章 $b_r\cdot b_s$ 等）
输出	更好的代数表达式	可执行的 query plan

结果大小估计（常用）

• $\sigma_{A=x}(r)$ 约 $n_r / V(A,r)$（均匀假设）
• 自然连接：若 $R\cap S$ 为 $R$ 的键，则结果元组数 $\le n_s$；一般估计用 $n_r n_s / \max(V(A,r),V(A,s))$ 等形式（与 PPT 一致即可）
• 投影大小约 $V(A,r)$；分组聚集类似
• 外连接：自然连接规模加上未被匹配的一侧元组

▸公式 $\,n_r / V(A,r)\,$：每个字母怎么用

场景：SELECT * FROM r WHERE A = 常量。

符号	代入
$n_r$	表总行数
$V(A,r)$	列 $A$ 有多少种不同值
估计结果行数	$n_r / V(A,r)$

假设：每个取值出现次数差不多（均匀）。若 $n_r=10000$，$V(\mathrm{dept},r)=10$，则 dept='CS' 估 $10000/10=1000$ 行。
★若实际 CS 占一半人，均匀假设会估错；真实系统用直方图。考试按均匀算。
★选择率 $= 1/V(A,r)$（等值、均匀、假设每个值都出现）。

▸自然连接估计：$n_r n_s / \max(V(A,r),V(A,s))$

场景：在公共属性 $A$ 上做自然/等值连接（教材常用估计）。

直觉：

• 结果行数「大约」像：取一侧每个 $A$ 值，去另一侧找匹配行再叉起来；
• 分母用 $\max(V(A,r),V(A,s))$，避免把不同值集合大小估得过于乐观（与 Silberschatz 等教材口径一致；有的讲义用 $\min$ 或更细公式，以 PPT 为准）。

数字：$n_r=1000$，$n_s=5000$，$V(A,r)=50$，$V(A,s)=100$。
估 $|r\bowtie s| \approx 1000\times 5000 / \max(50,100) = 5\times 10^6 / 100 = 50000$。

特殊：若 $A$ 是 $R$ 的键（每个 $r$ 行的 $A$ 唯一）：
每个 $s$ 行至多匹配 1 个 $r$ 行 → $|r\bowtie s| \le n_s$（常常 ≈ 能匹配上的那些 $s$ 行数）。
对称地，若 $A$ 是 $S$ 的键 → $\le n_r$。
★「键」让估计从「除 $V$」变成「不超过另一侧行数」——更紧、更好算。

▸投影 / 外连接 / 合取（其余几行）

投影 $\Pi_A(r)$：集合语义下去重后，不同 $A$ 值最多 $V(A,r)$ 行，故大小约 $V(A,r)$（若 $A$ 多列则更复杂，常估不同组合数）。

合取 $\sigma_{\theta_1\land\theta_2}$：独立假设下选择率相乘。
例：两条件选择率各 $0.1$，合取消约 $0.01\cdot n_r$ 行。相关性强时会不准。

外连接：以左外为例 ≈（自然连接行数）+（左表未匹配上行数）。未匹配部分用来补 NULL。估计时先估内连接，再按「左表有多少没对上」加进去（考试给比例或假定即可）。

▸串起来：从估计行数到选计划

1. 用 $n_r/V$ 等估每个算子输出多少行 → 再换成块数 $b$（除以每块行数）。
2. 对候选计划套上一章公式（如块嵌套 $b_r b_s+b_r$、索引嵌套 $b_r+n_r c$）。
3. 取代价最小者。

没有「大小估计」，代价公式里的 $n_r,b_r$ 就没有数可代——所以优化章与处理章是一套。

▸易错

★	误解	纠正
1	等价变换改变答案	只改执行过程，结果应相同
2	有索引就一定走索引	选择性差时全表扫可能更便宜
3	$V(A,r)$ 当行数	$V$ 是不同值个数，$n_r$ 才是行数
4	连接估计公式背错分母	先盯准讲义是 $\max$ 还是 $\min$
5	忘了键时的特例 $	,\cdot,

事务

定义与 ACID

ACID（Atomicity / Consistency / Isolation / Durability）为事务的四条性质。事务（Transaction） ：构成单一逻辑功能的操作序列。经典例子：A 账户扣款与 B 账户入账必须同成同败。

性质	含义
Atomicity 原子性	全做或全不做
Consistency 一致性	孤立执行时保持完整性约束（显式键约束 + 隐式业务约束）
Isolation 隔离性	并发事务互不感知中间态
Durability 持久性	提交后变更在故障后仍存在

读/写模型：read(X)、write(X) 在事务工作区与数据库之间传送。

状态

Active → Partially Committed → Committed；或 Active → Failed → Aborted（回滚后可重启或杀死）。

并发异常

异常	现象
Lost Update 丢失修改	两事务写同一项，后者覆盖前者，效果丢失
Dirty Read 脏读	读到未提交写，对方若回滚则读值无效
Unrepeatable Read 不可重复读	同一事务两次读同一项结果不同（对方已提交更新）
Phantom 幻读	范围查询两次结果行集不同（对方插入/删除满足条件行）

调度与可串行化

调度（Schedule） ：多事务指令的交错序列，保留各事务内部顺序。

冲突：不同事务、同一数据项，至少一方为写的两操作。可通过交换非冲突操作得到的调度称冲突等价。

冲突可串行化（Conflict Serializability） ：与某串行调度冲突等价。判定：建前驱图（Precedence Graph） ——若 $T_i$ 与 $T_j$ 冲突且 $T_i$ 的操作在前，则边 $T_i\to T_j$；无环 iff 冲突可串行化；拓扑序即等价串行序。

▸前驱图

调度片段：$r_1(A),\ w_2(A),\ r_2(B),\ w_1(B)$。

• $r_1(A)$ 与 $w_2(A)$ 冲突 → $T_1\to T_2$
• $w_1(B)$ 与 $r_2(B)$ 冲突且 $r_2$ 在前 → $T_2\to T_1$
  出现环 → 非冲突可串行化。

视图可串行化（View Serializability） 更宽（允许某些盲写情形），判定更难；考研以冲突可串行化为主。

隔离级别与异常对应

级别	脏读	不可重复读	幻读
Read Uncommitted	可能	可能	可能
Read Committed	否	可能	可能
Repeatable Read	否	否	可能（实现相关）
Serializable	否	否	否

可恢复与无级联

• 可恢复调度（Recoverable Schedule） ：若 $T_j$ 读了 $T_i$ 写的值，则 $T_i$ 必须在 $T_j$ 提交之前提交。
• 级联回滚（Cascading Rollback） ：一事务中止导致其他已读其脏数据的事务连锁中止。
• 无级联调度（Cascadeless Schedule） ：读操作之前，写者必须已提交。无级联 $\Rightarrow$ 可恢复。

SQL 隔离级别（概念）

从低到高大致：Read Uncommitted → Read Committed → Repeatable Read → Serializable。级别越低允许的异常越多，并发度通常越高。具体产品实现（锁 / MVCC）有差异，考研抓定义与异常对应。

并发控制

锁

• 共享锁（Shared Lock，S / lock-S） ：只读。
• 排他锁（Exclusive Lock，X / lock-X） ：读写。

相容：S 与 S 相容；S-X、X-X 不相容。不相容则请求方等待。

两阶段锁 2PL

两阶段锁协议（Two-Phase Locking，2PL） ：

• 增长阶段（Growing Phase） ：可加锁，不可解锁。
• 收缩阶段（Shrinking Phase） ：可解锁，不可再加锁。

锁点（Lock Point） ：获得最后一个锁的时刻。2PL 保证冲突可串行化，串行序与锁点序一致。2PL 不能单独消除死锁。

变体：

协议	要求	作用
严格 2PL（Strict 2PL）	所有 X 锁持有到提交/中止	可恢复、避免级联
强 2PL（Rigorous 2PL）	所有锁持有到提交/中止	按提交序串行化；实现中常见

锁升级（S→X）与降级需仍服从两阶段约束。

▸2PL 非充要

存在冲突可串行化但不满足 2PL 的调度。无额外信息时，2PL 是保证冲突可串行化的实用充分协议。

死锁

死锁（Deadlock） ：循环等待导致无人能进展。处理：

1. 预防
   • 一次加锁（predeclaration）：开始前锁齐所需项，易降低并发。
   • 图/序协议：数据项偏序，按序加锁破环。
   • Wait-Die（等待-死亡） ：老事务可等新事务；新事务与老冲突则自杀回滚（被动）。
   • Wound-Wait（伤害-等待） ：老事务冲突时伤害（中止）新事务；新事务等老事务（主动）。
   • 超时：简单，但可能误杀与饥饿。
2. 检测：构造 等待图（Wait-for Graph） （$T_i$ 等待 $T_j$ 释放则 $T_i\to T_j$），有环则死锁。
3. 恢复：选牺牲者 total/partial rollback；反复牺牲同一事务会造成饥饿，选择策略需计入回滚次数。

饥饿（Starvation） ：一事务长期等 X 锁，而共享锁不断被新事务获得——锁升级策略与队列公平性需限制。

多粒度锁

粒度层次：数据库 → 表/区域 → 文件/页 → 记录。细粒度并发高、开销大；粗粒度相反。

意向锁（Intention Lock） ：

模式	含义
IS	子孙将加 S
IX	子孙将加 X 或 S
SIX	本节点 S + 子孙 IX

加下层锁前先在祖先加相容的意向锁。相容矩阵以讲义为准记忆：IS 与 IS/IX/S 等组合。

其他协议

• 时间戳排序（Timestamp Ordering） ：每事务时间戳；读写遵守 $W\text{-}timestamp$、$R\text{-}timestamp$ 规则，违则回滚并可能带新戳重启（Thomas 写规则可忽略过时写）。
• 乐观 / 验证（Optimistic / Validation） ：读–验证–写；验证失败则重启。冲突少时优。
• 多版本并发控制（MVCC，Multi-Version Concurrency Control） ：读可见版本快照，写建新版本；快照隔离需警惕写偏斜（Write Skew） 。

锁管理器直觉

锁表（hash）记录持有与等待队列；兼容则授权，否则排队。事务中止时释放其全部锁并可能唤醒等待者。read/write 常自动请求 S/X（及升级）。

恢复

故障分类

类型	例子
事务故障	逻辑错误、死锁中止
系统崩溃	内存丢失、磁盘完好
介质故障	磁盘损坏

恢复算法须在正常运行时写下足够信息，故障后重建符合原子性与持久性的状态。

数据访问模型

磁盘物理块 ↔ 内存缓冲块（input/output）。事务工作区通过 read/write 与缓冲交互。不能假设 write 立刻落盘。

WAL 与日志记录

WAL（Write-Ahead Logging，预先写日志） ：数据页刷盘前，相应日志必须已进稳定存储。

典型记录：<Ti start>；更新 <Ti, X, V_old, V_new>（或延迟策略下仅新值）；<Ti commit> / <Ti abort>。

两条关键规则：

• Logging rule：旧值进入日志不晚于新值进入数据库。
• Commit rule：提交前，提交所需信息（至少 commit 日志）须在稳定存储上。

延迟修改 vs 立即修改

策略	做法	崩溃后
Deferred	commit 前不改数据库，只记日志；commit 后按日志写库	有 start+commit 则 redo；无需 undo（库中无未提交脏写）
Immediate	可在 commit 前就把更新写入缓冲/磁盘（仍先记日志）	已提交 redo；仅有 start 无 commit 则 undo

Redo / Undo 必须幂等：执行多次效果同一次。

检查点

周期：刷日志 → 刷脏页（经典 检查点（Checkpoint） ）→ 写 <checkpoint L>（$L$ 为当时活跃事务表）。恢复时从最近 checkpoint 向前决定 redo/undo 集合：checkpoint 之前已落盘的提交工作可大幅跳过。

示意：若 checkpoint 时活跃含 $T_2,T_3$，之后 $T_4$ 未提交——则 $T_1$（更早且已结束）可忽略；$T_2,T_3$ 若随后提交则 redo、若未提交则 undo；$T_4$ undo。

恢复两阶段（教材基本算法）

1. Redo 阶段：从最近 checkpoint 向前扫描，重做已出现在日志中的更新（或按策略只重做已提交），并维护 undo-list。
2. Undo 阶段：自尾向前，对 undo-list 中事务写回旧值，写 CLR/abort，直至 undo-list 空。

单事务回滚：自尾向该事务 start 扫描，按旧值撤销。

ARIES 提纲

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）。与基本算法差异（考研常考思想）：

• 每条日志 LSN（Log Sequence Number，日志序列号） ；每页 PageLSN 记录已应用到该页的最大 LSN，避免重复 redo。
• 脏页表（Dirty Page Table） ：PageLSN、RecLSN，缩小 redo 起点。
• 模糊检查点（Fuzzy Checkpoint） ：不必在 checkpoint 时刷光脏页，只记录元数据。
• CLR（Compensation Log Record，补偿日志记录） ：undo 时写 redo-only 补偿记录，UndoNextLSN 指向下一条待 undo，保证崩溃重启可继续。

三相：分析（Analysis） （重建脏页表与事务表）→ 重做（Redo） （从候选点重复历史）→ 撤销（Undo） （反向撤销失败者）。

复习对照

与文件夹资料对齐

资料	用途
数据库系统-孙健伶 zju.md	概念、关系代数、SQL、ER、范式主线
习题.md	关系代数书写、SQL 全称量化、NOT EXISTS
PPT ch1–7, 12–18	存储、索引、处理、优化、事务、并发完整大纲
前辈复习整理 / 小角龙笔记	公式、代价、B+ 计算、并发细节互校
开发参考.md	ODBC/JDBC 外链（实现向，非理论核心）

高频题型清单

1. 关系代数书写（含改名、连接、除法思想）
2. 候选键 / 闭包 / 无损 / BCNF·3NF 分解
3. ER 转换（弱实体、M:N、多值属性）
4. B+ 树高度与块数；选择/连接代价估算
5. 前驱图与冲突可串行化；2PL 与死锁 wait-for
6. SQL：GROUP BY、嵌套、NOT EXISTS 表达“全部”

XML

课程大纲含 XML 结构、Schema、查询（XPath/XQuery 级）。若考试范围声明包含，另补专用短章；默认理论主干以关系模型与事务并发为重。

▸SQL 下一站

独立文档 SQL详解：基础查询到复杂嵌套、窗口函数与面试题，例子密度按面试与作业双标准组织。

代价公式速查

考试常直接套用（符号与 Silberschatz / 浙大 PPT 对齐）。

▸符号与推导

$n_r/b_r$、$M$、$h_i$、$c$、外排序 $2b_r(1+\text{趟数})$、各连接公式的「每一项为什么」见前文 查询处理 章（符号总表 + 各 EXAMPLE）。本节约为答题默写清单。

选择

• 线性扫描：$b_r$ 次块传输 + $1$ 次寻道；唯一搜索键平均约 $b_r/2$ 传输。
• 主索引等值（唯一）：约 $(h_i+1)$ 次块访问量级（$h_i$ 为索引高度）。
• 主索引等值（非唯一）：$h_i$ + 连续 $b$ 个数据块。
• 辅助索引 $n$ 条匹配：最坏约 $h_i+n$ 次随机 I/O（记录分散时）。

外排序（默写）

• 趟数 ≈ $\lceil\log_{M-1}(b_r/M)\rceil$
• 总块访问 ≈ $2b_r(1+\text{趟数})$

嵌套循环（默写）

• 元组嵌套：≈ $n_r\cdot b_s + b_r$
• 块嵌套最坏：≈ $b_r\cdot b_s + b_r$
• 索引嵌套：≈ $b_r + n_r\cdot c$

块嵌套循环连接

最坏块传输约 $b_r\cdot b_s + b_r$，寻道约 $b_r + b_r\cdot b_s$（内存仅容每表一块时）。内存 $M$ 块时，外表每次读 $M-2$ 块，传输约 $\lceil b_r/(M-2)\rceil\cdot b_s + b_r$。

归并连接

已排序时传输约 $b_r+b_s$。若需外排序，加上排序代价。

哈希连接（提纲）

分区阶段读写各约一遍关系；探测阶段再读。内存能容纳构建端时可省分区。

结果基数

• $\sigma_{A=v}(r)$：约 $n_r/V(A,r)$
• 合取选择：在独立假设下用选择率连乘
• 自然连接：若交属性为 $R$ 键，则 $|r\bowtie s|\le n_s$；一般约 $n_r n_s/\max(V(A,r),V(A,s))$

B+ 树演算补充

分裂直觉

叶最大存放 $n-1$ 个搜索键。插入导致 $n$ 个搜索键时分裂为两叶，上推分隔键。内部节点指针数超过 $n$ 则分裂。根分裂时树高加一。

▸与前文「插入逐步」对照

演算题常问：插入某键后哪一叶分裂、父中新出现哪个分隔键、树高是否加一。步骤固定为：定位叶 → 判断是否满 → 分裂并上推 → 必要时级联 → 仅根分裂时高度 $+1$。B* 变体则先问「右兄弟是否还有空位」，有则再分配而非立刻二分分裂。

高度界

$K$ 个搜索键、阶参数 $n$：高度不超过约 $\lceil\log_{\lceil n/2\rceil}K\rceil$ 量级。估块数时分别按叶“全满”与“半满”算上下界。

▸扇出

块 $4\mathrm{KB}=4096\mathrm{B}$，搜索键 $8\mathrm{B}$，指针 $8\mathrm{B}$。内部节点近似最多指针数 $n=\lfloor(4096)/(8+8)\rfloor$ 一类公式（按讲义是否预留页头再减）。$n\approx 200$ 时，百万级搜索键高度往往仍很小。

▸叶块数上下界（答题模板）

设共 $K$ 个搜索键，叶最多放 $n_{\mathrm{leaf}}$ 个键、最少约 $\lceil n_{\mathrm{leaf}}/2\rceil$ 个（根除外时的填充约定与讲义对齐）。

• 叶块数下界（尽量塞满）：$\lceil K / n_{\mathrm{leaf}}\rceil$
• 叶块数上界（尽量半满）：约 $\lceil K / \lceil n_{\mathrm{leaf}}/2\rceil\rceil$

再对内部层用扇出 $n$ 估计：最矮时每层孩子尽量满，最高时按半满堆叠，从而夹出整树高度区间。与索引章「高度 $O(\log_{\lceil n/2\rceil} K)$」同一思想。

▸点查 I/O 粗估

树高为 $h$（根到叶的边数或层数，按题目定义）时，冷缓存点查大约 $h$ 次块读（聚簇叶上已有行则不必再回表；二级索引常再加若干次回表 I/O）。根命中缓冲时可减 1。范围查再加「叶链扫过的块数」。

高级 SQL 要点

（PPT ch5；语句细节仍以《SQL详解》为主。）

• 过程与函数：CREATE PROCEDURE / FUNCTION，控制流、异常；用于封装业务，与声明式查询分工。
• 嵌入式 SQL / API：静态嵌入、动态 SQL；应用侧经 ODBC/JDBC 传语句与绑定参数。见课程 开发参考.md 外链。
• 触发器与断言：主笔记完整性节与《SQL详解》示例。
• 递归查询：WITH RECURSIVE 表达账单展开、组织树、（有限）路径。

XML 提纲

若考试大纲包含：

• XML 半结构化；元素嵌套、属性。
• Schema / DTD 约束结构。
• 查询：XPath 路径、XQuery FLWOR；与关系映射（shredding / publishing）概念。

默认复习优先级低于范式与事务并发。

综合演算

函数依赖与范式

设 $R=(A,B,C,D,E)$，$F={A\rightarrow BC,\ CD\rightarrow E,\ B\rightarrow D,\ E\rightarrow A}$。

1. 求候选键：算闭包。
   • $A^+=ABCDE$（因 $A\rightarrow BC$，再 $B\rightarrow D$，再 $CD\rightarrow E$）→ $A$ 为超键。
   • $E^+=EABCD$（$E\rightarrow A$ 后同 $A$）→ $E$ 亦为超键。
   • $B^+=BD\neq R$；$C$、$D$ 单独都不是。
   • 验证极小：单属性超键即候选键 → 候选键 $A$、$E$。
2. 是否 BCNF：看 $B\rightarrow D$。$B^+\neq R$，$B$ 非超键 → 否。
3. 用 $B\rightarrow D$ 分解：$(B,D)$ 与 $(A,B,C,E)$，再在各片上继续检验直至 BCNF，并另做依赖保持检查。

冲突可串行化与 2PL

调度：$r_1(X),\ r_2(X),\ w_1(X),\ r_2(Y),\ w_2(Y),\ w_1(Y)$。

前驱图：

• $r_2(X)$ 与 $w_1(X)$：$T_2\to T_1$（读后写，$T_2$ 在前）
• $w_1(Y)$ 与 $r_2(Y)$：$T_2\to T_1$ 或 $T_1\to T_2$ 取决于谁先——此处 $r_2(Y)$ 在 $w_1(Y)$ 前 → $T_2\to T_1$

仅有 $T_2\to T_1$，无环 → 冲突可串行化，序 $T_2,T_1$。

若某调度在锁点序上无法由 2PL 产生（提前解锁后再加锁），则纵使可串行化，也不是 2PL 可生成调度。

ER 转换检查表

检查项	动作
每个强实体	一表
每个弱实体	一表；主键含主人键
每个多值属性	一表
每个 M:N	一联系表
1:N	外键放 N 端
联系属性	放入对应联系表或 N 端

关系代数：同宿舍不同系

对 student 自笛卡尔积后改名：

$$
\Pi_{\mathrm{name}_1,\mathrm{name}_2}\big(\sigma_{\mathrm{department}_1\neq\mathrm{department}_2\land\mathrm{building}_1=\mathrm{building}_2\land\mathrm{room}_1=\mathrm{room}_2}(\rho_{1}(\mathrm{student})\times\rho_{2}(\mathrm{student}))\big)
$$

实现时用下标或 AS 消歧，并常加 $\mathrm{sid}_1<\mathrm{sid}_2$ 避免无序对重复。

408与讲义补强

▸本章定位

对照 408 / 《数据库系统概论》高频口径与浙大讲义、习题，对前文做增量补强（不替换既有章节）。侧重：完整性、依赖细分、异常、三级封锁、设计步骤、安全性、关系演算、更多演算例。

三类完整性

关系模型三类完整性约束（408 填空/简答高频）：

类型	规则
实体完整性（Entity Integrity）	主键属性不能取 NULL；主键唯一标识元组
参照完整性（Referential Integrity）	外键为空，或等于被参照关系中某候选键/主键值
用户定义完整性（User-defined Integrity）	领域、CHECK、断言、触发器等业务约束

违反参照完整性时的策略（讲义 Cascading）：NO ACTION / RESTRICT、CASCADE、SET NULL、SET DEFAULT（依产品）。

主属性与非主属性

• 主属性（Prime Attribute） ：出现在任何一个候选键中的属性。
• 非主属性（Nonprime Attribute） ：不在任何候选键中的属性。

判断 2NF/3NF 时必须先分清主/非主，否则容易把“主属性之间的依赖”误判成违反 3NF（其实可能只违反 BCNF）。

完全、部分与传递依赖

设 $X\rightarrow Y$ 成立且 $Y\not\subseteq X$（非平凡）。

1. 完全函数依赖（Full Functional Dependency） $X\xrightarrow{F} Y$：对 $X$ 的任一真子集 $X’$，都有 $X’\nrightarrow Y$。
2. 部分函数依赖（Partial Functional Dependency） $X\xrightarrow{P} Y$：$X\rightarrow Y$ 但不是完全依赖（存在真子集也能决定 $Y$）。
3. 传递函数依赖（Transitive Functional Dependency） ：若 $X\rightarrow Y$，$Y\rightarrow Z$，且 $Y\nrightarrow X$（避免平凡转回），$Z\not\subseteq Y$，则称 $Z$ 对 $X$ 传递依赖。记法教材常写作 $X\xrightarrow{T} Z$。

▸选课模式

$R(\mathrm{学号},\mathrm{课程号},\mathrm{成绩},\mathrm{学分})$，
$F={ {\mathrm{学号},\mathrm{课程号} }\rightarrow\mathrm{成绩},\ \mathrm{课程号}\rightarrow\mathrm{学分} }$。

• 候选键：$(\mathrm{学号},\mathrm{课程号})$
• $\mathrm{成绩}$ 对键完全依赖
• $\mathrm{学分}$ 对键部分依赖（只依赖课程号）→ 非 2NF
• 分解后若仍有非主属性经另一非主属性依赖键 → 再查 3NF

范式口诀（408 口径）

范式	消除的对象（常见表述）
1NF	非原子属性
2NF	非主属性对候选键的部分函数依赖
3NF	非主属性对候选键的传递函数依赖
BCNF	主属性对候选键的部分/传递依赖；任何决定因素皆为超键
4NF	非平凡多值依赖（决定因素须为超键）
5NF（Fifth Normal Form，第五范式）	非候选键蕴含的连接依赖（了解）

关系：$1\mathrm{NF}\supset 2\mathrm{NF}\supset 3\mathrm{NF}\supset \mathrm{BCNF}\supset 4\mathrm{NF}\supset 5\mathrm{NF}$（在相应依赖假设下，集合含义为“满足更高范式的模式集合更小”）。

▸3NF 与 BCNF 差在哪里

3NF 允许：非超键 $\alpha\rightarrow A$，但 $A$ 是主属性。BCNF 不允许这种“主属性被非超键决定”。故存在满足 3NF 不满足 BCNF 的模式；分解到 BCNF 可能牺牲依赖保持。

不好模式的三类异常

以 SC(学号, 姓名, 系名, 系主任, 课程号, 成绩)，$F={\mathrm{学号}\rightarrow\mathrm{姓名},\mathrm{系名};\ \mathrm{系名}\rightarrow\mathrm{系主任};\ {\mathrm{学号},\mathrm{课程号} }\rightarrow\mathrm{成绩} }$ 为例。

异常	表现
插入异常	系尚无学生时，无法插入系主任信息（学号为主键一部分却不存在）
删除异常	删掉某系最后一名学生，系主任信息一并丢失
更新异常	系主任变更需改多行，易漏改导致不一致
数据冗余	同一系主任随每个学生重复存储

规范化通过无损（且尽量保持依赖）的分解削弱上述问题。

数据库设计步骤

经典六步（408 / 软考口径）：

1. 需求分析：数据、处理、安全性与完整性需求
2. 概念结构设计：E-R（或扩展 E-R）
3. 逻辑结构设计：E-R → 关系模式，规范化，优化
4. 物理结构设计：存储结构、索引、聚簇
5. 数据库实施：建库、装数、调试、试运行
6. 运行维护：备份恢复、性能、重组重构

逻辑设计中“属性还是实体”经验：要单独描述、有多个实例、或自身有属性/联系时，倾向实体；仅作描述字段则倾向属性。

关系演算（提纲）

与关系代数表达能力等价（安全表达式下）：

• 元组关系演算：{ t | P(t) }，变量为元组。
• 域关系演算：{ <x1,...,xn> | P(x1,...,xn) }，变量为域元素。

安全限制：结果元组须来自表达式中出现的域之有限活跃域，避免无限关系。SQL 更接近域/元组演算的声明风格。

等值连接与自然连接

• 等值连接：$\sigma_{R.A=S.B}(R\times S)$，结果保留两列 $A,B$（值相等）。
• 自然连接：要求同名属性上等值，结果中同名列只留一列；是特殊等值连接再投影。

▸行数直觉

$R$ 有 5 行、$S$ 有 5 行，无条件笛卡尔积 25 行。自然连接行数 $\le 25$，取决于匹配；投影后再 DISTINCT 语义下去重。习题中“形参 p1”与表中键值 p1 勿混淆。

外连接小表

设 teaches 与 instructor 左外连接：左表每位教师一行；无授课记录则课程侧为 NULL。全外连接再并上“有课无对应教师”（若数据脏）的行。用于报表“列出全部教师及其课（含未开课）”。

视图作用（简答模板）

1. 简化用户操作与查询书写
2. 多角度看待同一数据（外模式）
3. 提供一定逻辑数据独立性
4. 安全：授权可只授视图
5. 可作导出数据的清晰接口

可更新视图条件严格（通常单基表、无聚集/去重等），详见《SQL详解》。

安全性补强

• 自主访问控制 DAC：属主用 GRANT/REVOKE 授权；WITH GRANT OPTION 可转授。
• 强制访问控制 MAC：主客体安全级，级别比较决定可否读/写（了解）。
• 审计：记录谁在何时访问何对象。
• 视图 + 列级特权：缩小可见面。

DBMS 安全与 OS、网络共同构成纵深。

三级封锁协议（王道/教材口径）

在 S/X 锁基础上，国内教材常用“几级封锁协议”对应能排除的异常：

级别	规则要点	能防止
一级	写前加 X 锁，至事务结束才释放	丢失修改
二级	一级 + 读前加 S 锁，读完可放 S	再加：脏读
三级	一级 + 读前加 S 锁，事务结束才放 S	再加：不可重复读

幻读需谓词锁 / 串行化隔离等更高机制。三级封锁与隔离级别、严格 2PL 有对应关系，但不等同于“只要三级就无死锁”——死锁仍可能。

▸与 2PL 的关系

三级封锁协议中，持锁至结束的写法接近严格/强两段锁思想。两段锁保证冲突可串行化（充分不必要）；三级封锁更直接按“异常”教学。

活锁与死锁再强调

• 活锁：事务反复被“插队”，长期得不到锁（如总有新事务获 S，某事务一直等 X）。处理：先来先服务队列。
• 死锁：循环等待。预防（一次申请、顺序加锁、Wait-Die、Wound-Wait）、检测（wait-for 图）、解除（回滚牺牲者）。

可串行化判定步骤（答题卡）

1. 列出冲突对（异事务、同对象、至少一写）
2. 画前驱图：先发生冲突操作的事务 → 后发生者
3. 有环？有则非冲突可串行化；无则拓扑序即等价串行序
4. 若问“能否由 2PL 产生”：检查是否存在解锁后再加锁；或按锁点论证

视图可串行化包含盲写等更广情形，判定难，408 以冲突可串行化为主。

故障与恢复对照表

故障	典型恢复动作
事务内部故障	undo 该事务
系统崩溃（磁盘完好）	重启后用日志 redo 已提交 + undo 未提交；配合 checkpoint
介质故障	备份还原 + 日志向前恢复（redo 备份点之后已提交）

静态转储 / 动态转储、海量与增量备份：了解名词即可。

习题全文演算

Quiz1 关系代数（宿舍）

模式见前文。答案要点：

1. CS 且白沙1幢 213：选择再投影 name。
2. 王小强室友：先投影其 (building,room)，再与 student 自然连接，去掉本人姓名。
3. 不同系同宿舍：自笛卡尔积 + 选择（系不等且楼房号等）+ 投影姓名对；注意改名。
4. 住满宿舍：按房间聚集 COUNT(sid)，与 dorm.capacity 等值连接后投影。可用扩展聚集记号书写。

Quiz2 SQL 关键词

题意	手法
CS 且舞蹈社	三表 JOIN + WHERE
JL SUN 所有俱乐部成员	双重 NOT EXISTS
只有女生的俱乐部	NOT EXISTS 非女成员
每个系百分比	GROUP BY + 子查询分母
年龄差最大	自连接 + ORDER BY + LIMIT

完整语句见《SQL详解》与原始 习题.md。

随堂：笛卡尔积行数

5 元组关系自连接笛卡尔积 → 25 行；满足条件的配对再投影去重，行数分别计量，勿把“变量名 p1”当成表中同一实体。

再判范式例（408 风格）

$R(A,B,C,D)$，$F={A\rightarrow B,\ B\rightarrow C,\ D\rightarrow B}$。

1. 候选键：求闭包。$AD^+=ABCD$，$A$、$D$ 单独不行 → 候选键 $AD$（验证：$BD^+=BCD\neq R$）。
2. 主属性：$A,D$；非主：$B,C$。
3. $A\rightarrow B$：决定因素 $A$ 非超键 → 非 BCNF。$B\rightarrow C$：$B$ 非超键且 $C$ 非主 → 非 3NF。键为 $AD$ 时，$D\rightarrow B$ 使非主属性 $B$ 部分依赖于 $AD$ → 非 2NF。
4. 分解思路：先按部分依赖拆（如 $(D,B)$、$(A,D,\ldots)$），再处理传递，直至目标范式，并检查无损与依赖保持。

▸答题顺序建议

先找候选键 → 标主/非主 → 自低到高问“是否 kNF” → 指出违背的依赖 → 给出分解与验证。

时间戳协议补几句

事务 $T_i$ 时间戳 $TS(T_i)$。数据项 $Q$ 维护 $R\text{-}timestamp(Q)$、$W\text{-}timestamp(Q)$。

• 读：$TS(T_i)<W\text{-}ts(Q)$ 则拒绝读并回滚；否则允许并更新 $R\text{-}ts$。
• 写：$TS(T_i)<R\text{-}ts$ 或 $<W\text{-}ts$ 则拒绝写并回滚；否则写并更新 $W\text{-}ts$。
• Thomas 写规则：过时写可直接忽略而不回滚，仍保证视图可串行化一类正确性（按教材表述记忆）。

乐观并发（验证协议）

三阶段：读（含本地写缓冲）→ 验证（与并发事务冲突检查）→ 写。冲突稀少时减少锁开销；冲突多则反复重启。

概念速查

术语	一句话
模式 / 实例	型 / 值
DDL / DML / DCL	定义 / 操纵 / 控制（授权等）
超键（Superkey） / 候选键（Candidate Key） / 主键（Primary Key）	能唯一 / 极小超键 / 选定之候选键
阻塞因子（Blocking Factor）	一块容纳的记录数
聚簇索引（Clustering Index）	数据顺序与索引顺序一致
覆盖索引（Covering Index）	查询所需列都在索引中，免回表
左深树（Left-deep Tree）	连接树形态，便于流水与 DP
WAL（Write-Ahead Logging）	先日志后脏页落盘
CLR（Compensation Log Record）	ARIES 补偿日志，redo-only

参考链接

• 浙大课程材料：DB-ZJU 讲义与 PPT ch1–7、12–18
• 关系代数直观：简书·关系代数
• 除法白话：CSDN·除法运算
• SQL 基础：菜鸟教程 SQL
• 刷题：牛客 SQL
• 408 范式与封锁口径参见王道《计算机网络》同系列计组/计网之外的数据结构与组成原理配套数据库分册及《数据库系统概论》教材相应章