数据库系统期末复习提纲（按 chap12 总复习整理）

资料来源：C:/Users/Lenovo/Desktop/考试复习/数据库 中的 chap12 总复习及各章节课件文本提取。

0. 考试信息与复习优先级

考试形式：闭卷笔试
时间：2026-06-23 14:00-15:40
地点：沙河主教109M
题型：单选 20 题 × 2 分 = 40%；综合题 2 题 = 60%

客观题章节比例

章节	比例	chap12 指定重点
数据库系统导论	20%	数据信息基本概念；数据库主要特性、优点
关系模型	20%	关系基本概念；关系代数操作
ER 模型	10%	基本概念；ER 模型和关系模型相互转换
SQL 语言	10%	SQL 定义；SQL 操作（全文检索）；SQL 控制
事务	10%	基本概念；ACID；冲突/视图可串行化；冲突指令
关系规范化	10%	范式；函数依赖；多值依赖概念；Armstrong 公理
查询处理实现	10%	基本算法
数据存储	10%	索引与性能关系；位图索引；B+ 树索引

综合题重点

ER 模型设计
关系模型设计
SQL 语言
查询处理实现
数据库存储部分计算

一、数据库系统导论

1. 信息、数据、知识

信息

常考表述：

信息是不确定性的消除。
信息是负熵。
信息是系统有序程度的度量。
信息具有无限性、共享性、创造性、时效性、相对性。

数据

数据是对现实世界中客观事物的符号表示。计算机中的数据是能够输入计算机并被处理的符号序列，可包括数字、文本、图像、声音等。

数据与信息的关系

数据是信息的符号表示，是信息的载体。
信息是数据的内涵，是数据的语义解释。
数据是符号化的信息，信息是语义化的数据。

知识

知识是能辅助决策或行动的高价值信息形态，可理解为“行动的能力”。

2. 数据类型、数据结构、数据语义

数据类型：具有相同数据结构的数据属于同一类型。
数据结构：按逻辑关系组织起来并按一定方式存储的一批数据，同时定义相关运算。
数据语义：数据的含义。文件系统通常不理解数据语义，而数据库系统通过 DBMS 统一维护数据结构和语义。

3. 数据独立性

当数据结构变化时，通过系统映象功能使应用程序尽量不变。

类型	含义	对应映象
逻辑独立性	全局逻辑结构改变时，外部应用尽量不变	外模式/模式映象
物理独立性	存储结构改变时，逻辑结构和应用尽量不变	模式/内模式映象

4. 数据管理发展阶段

人工管理阶段

用户完全负责数据管理。
数据面向特定应用。
数据与程序没有独立性。
数据通常不长期保存。

文件系统阶段

优点：有文件系统统一管理文件，提供存储空间管理、目录管理、读写管理和文件保护。

缺点：

数据仍面向应用。
数据共享性差、冗余大。
数据与程序独立性差。
数据孤立，查询困难。
数据一致性和完整性难维护。

数据库系统阶段

有 DBMS 统一管理。
数据面向全组织和现实世界。
数据共享程度高，冗余低。
数据和程序独立性较强。
具有统一的数据控制功能。

5. 数据库系统的主要特性/优点

面向全组织的复杂数据结构。
数据服务整个组织而不是某个应用，能表达现实对象及其联系。
数据冗余度小，易扩充。
数据集中管理、共享，减少重复存储和不一致。
较高的数据和程序独立性。
数据定义与应用程序分离，用户不必关心底层存储路径。
统一的数据控制功能。
包括安全性控制、完整性控制、并发控制、恢复控制。

6. 数据模型

数据模型是数据库系统中用于提供信息表示和操作手段的形式框架。

类型	视角	示例
概念数据模型	用户观点，强调语义	E-R 模型
结构数据模型	计算机实现观点	层次模型、网状模型、关系模型、对象模型

结构数据模型三要素：数据结构、数据操作、数据约束条件。

7. 三级模式结构

层次	含义
外模式	用户的数据视图，局部逻辑结构
模式	全体用户公共数据视图，全局逻辑结构
内模式	数据物理结构和存储方式

8.数据库系统

数据库
数据库管理系统DBMS
数据库系统（包括硬件、软件、数据、人员——DBA）

二、关系模型

1. 关系基本概念

域：一组具有相同数据类型的值的集合。
笛卡尔积：D1 × D2 × ... × Dn 中每个元素是一个 n 元组。
关系：笛卡尔积的有意义子集，可表示为二维表。
元组：关系中的一行。
属性：关系中的一列。
分量：元组中的某个属性值。
关系模式（Schema）：关系的描述，记作 $R (A_{1}, A_{2}, ..., A_{n})$ 。关系是某一时刻的值。

2. 关系的性质

列是同质的。
不同列可来自同一域，但属性名应不同。
行顺序无关。
列顺序无关。
任意两个元组不能完全相同，因为关系是集合。
每个分量必须不可再分，即满足 1NF。

3. 码与完整性

码

候选码：能唯一标识元组且具有最小性的属性组。
主码：从候选码中选定的一个。
主属性：出现在候选码中的属性。
外码：本关系中的某属性组引用另一关系的码。

关系完整性

类型	含义
实体完整性	主码属性不能为空
参照完整性	外码要么为空，要么等于被参照关系中的某个主码值
用户定义的完整性	用户根据应用定义的约束，如取值范围、格式等

4. 关系代数操作

选择 σ

从行的角度选元组：

σF(R) = { t | t ∈ R 且 F(t) 为真 }

投影 π

从列的角度选属性：

πA(R) = { t[A] | t ∈ R }

注意：关系代数投影结果去重（因为是集合）；SQL 默认不去重，需要 DISTINCT。

更名 ρ

给关系或属性重命名，自连接时常用。

并、差、交

要求两个关系相容：属性个数相同，对应属性域相同。

R ∪ S：出现在 R 或 S 中的元组。
R - S：出现在 R 中但不在 S 中的元组。
R ∩ S：同时出现在 R 和 S 中的元组。

笛卡尔积

R × S 的度为 R 的度加 S 的度，元组数为两者元组数乘积。

θ 连接

R ⋈AθB S = σR[A]θS[B](R × S)。

θ可以是<,=,>…

θ取=时称作等值连接

自然连接

在相同属性上取值相等的元组连接，并去掉重复属性（即连接列不重复保留。也即对两个关系中同名属性进行等值匹配，并且结果中同名属性只保留一份。）。

等值连接：相等的分量不一定来自相同的属性组。

外连接

自然连接基础上保留未匹配元组，用 NULL 补齐。分为左外连接、右外连接、全外连接。

除法

适合表达“全部”“所有”。常见公式：

R(X,Y) ÷ S(Y) = πX(R) - πX((πX(R) × S) - R)

典型题：选修了所有课程的学生：

πS#,C#(SC) ÷ πC#(C)

除法强调“是否满足全部条件”。

赋值运算

赋值： $\leftarrow$

$t e m p 1 \leftarrow Π_{X} (R)$

5. 关系代数易错点

“同时选修 c1 和 c2”不能写成 C#='c1' AND C#='c2'，应使用交、自连接或分组思想。
“选了 A 没选 B”用差。
“没有选某课”的全集一般应来自学生表，而不是选课表。
“全部/所有”常用除法。
自然连接会去掉重复属性，等值连接不一定。

三、ER 模型

1. 基本概念

实体：客观存在并可相互区分的事物。
属性：实体具有的某一特性。
域：属性的取值范围。
实体型：实体名及属性名集合。
实体集：同型实体的集合。
联系：实体之间的相互关联；联系也可有属性。
联系的元：参与联系的实体集个数，如一元、二元、三元联系。
码（Key）
参与
存在依赖

2. ER 图符号

元素	表示
实体集	矩形
属性	椭圆
联系	菱形
主码属性	下划线
弱实体集的分辨符	下划虚线
多值属性	双椭圆
派生属性	虚椭圆
弱实体集	双边框矩形
标识性联系	双菱形
全部参与	双线
ISA	三角形

3. 属性类型

简单属性：不可再分。
复合属性：可拆分为更小属性，如出生日期可拆成年、月、日。
单值属性：每个实体只有一个值。
多值属性：每个实体可有多个值，应单独建表。
派生属性：可由其他属性计算得到，如平均成绩。
NULL属性值：表示无意义或值未知。

4. 联系类型

1:1：一边实体至多对应另一边一个实体。
1:N：一边一个实体可对应另一边多个实体。
M:N：两边都可多对多。
递归联系：同一实体集内部的联系，需要标角色。
多元联系：三个或更多实体集共同参与，不能随意拆成多个二元联系。

5. 弱实体集

若一个实体集的所有属性不足以形成主码，则称为弱实体集。

弱实体依赖强实体存在。
弱实体主码 = 所依赖强实体主码 + 弱实体分辨符。
存在依赖不一定导致弱实体，因为从属实体也可能有自己的主码。

6. ISA：特殊化与概括

特殊化：自顶向下，父类分成子类。
概括：自底向上，多个子类抽象为父类。
子类继承父类属性。
约束设计：不相交的/重叠的，全部的/部分的。

7. 聚集

当“联系本身还要参与另一个联系”时，可将联系看成高层实体集，即聚集。

8. ER 转关系模型规则

强实体集：转为一个关系，属性照抄，主码照抄。
复合属性：拆成组成属性。
多值属性：单独建表，包含原实体主码和多值属性。
1:N 联系：在 N 方加入 1 方主码作为外码，联系属性也放在 N 方。
M:N 联系：新建联系表，包含双方主码和联系属性，通常双方主码联合构成主码。
1:1 联系：若一方全部参与，可将另一方主码放入全部参与方；若双方均部分参与，可新建联系表。
弱实体：关系主码 = 强实体主码 + 弱实体分辨符。
ISA：一般建父类表和子类表，子类表含父类主码；若不相交且全部，可只建子类表并包含父类属性。
聚集：先把被聚集的联系按规则转换，再建立其与其他实体的联系表。

9. ER 设计题步骤

圈出名词，找实体。
找属性和主码。
圈出动词/业务规则，找联系。
判断联系类型：1:1、1:N、M:N、多元、递归。
判断参与约束：全部/部分。
识别弱实体、多值属性、复合属性、ISA、聚集。
转换为关系模式时标清主码和外码。

四、SQL 语言

1. DDL / DML / DCL

类别	作用	关键词
DDL	定义数据库结构	CREATE, ALTER, DROP
DML	查询和修改数据	SELECT, INSERT, UPDATE, DELETE
DCL	权限控制	GRANT, REVOKE

2. DDL 重点

CREATE TABLE

CREATE TABLE 表名 (
    列名 数据类型 [DEFAULT 默认值] [NOT NULL],
    PRIMARY KEY (列名),
    FOREIGN KEY (列名) REFERENCES 参照表(列名),
    CHECK (条件)
);

约束命名：constraint 约束名 <约束条件>

常见约束：PRIMARY KEY、UNIQUE、FOREIGN KEY、CHECK、DEFAULT、NOT NULL。

外码动作：RESTRICT/NO ACTION、CASCADE、SET NULL、SET DEFAULT。

ALTER / DROP / DELETE

ALTER TABLE 表名 ADD 列名 数据类型;
ALTER TABLE 表名 DROP COLUMN 列名;
DROP TABLE 表名;
 
DELETE FROM 表名
[WHERE 条件];

DROP 删除表结构和数据；DELETE 只删除元组。

索引

CREATE [UNIQUE] [CLUSTER] INDEX 索引名
ON 表名(列名 [ASC|DESC], ...);

索引可加快查询、连接、排序、分组，也能支持唯一性；但会增加空间开销并降低插入、删除、更新效率。

聚簇索引——表中数据记录的实际存储顺序按照某个索引键的顺序组织，一个表只能有一个。primary key会自动创建聚簇索引。

组合索引 (A,B,C) 通常主要支持按 A、A+B、A+B+C 检索。

视图

视图是虚表，只保存定义，不保存实际数据。

CREATE VIEW 视图名 AS 查询语句 [WITH CHECK OPTION];

作用：简化查询、提高安全性、提高逻辑独立性。

3. SELECT 查询

基本形式：

SELECT A1, A2
FROM R1, R2
WHERE 条件;

多表查询若缺少连接条件会产生笛卡尔积。

常用条件

=, <>, <, <=, >, >=, AND, OR, NOT, BETWEEN, IN, LIKE, IS NULL, EXISTS

NULL 判断必须用 IS NULL 或 IS NOT NULL，不能用 = NULL。

LIKE

%：零个或多个字符。
_：任意单个字符。
匹配 %、_ 本身时使用 ESCAPE。

连接

SELECT S.SNAME, C.CNAME, SC.GRADE
FROM S
JOIN SC ON S.S# = SC.S#
JOIN C ON C.C# = SC.C#;

外连接用于保留未匹配元组。注意：外连接右表条件若放在 WHERE 中，可能过滤 NULL 行，使外连接退化为内连接。

4. 聚集、分组、排序

常见聚集函数：AVG、MIN、MAX、SUM、COUNT。

COUNT(*) 统计所有行。
COUNT(列名) 只统计该列非 NULL 行。

WHERE 用于分组前筛选元组；HAVING 用于分组后筛选组。

SELECT S#, AVG(GRADE)
FROM SC
GROUP BY S#
HAVING AVG(GRADE) > 90;

GROUP BY 后，SELECT 中非聚集列必须出现在 GROUP BY 中。（即目标列必须是分组属性）

5. 嵌套查询

IN

判断某值是否属于子查询结果集合。

SOME / ALL

= SOME 等价于 IN。
<> ALL 等价于 NOT IN。
<> SOME 不等价于 NOT IN。

EXISTS

判断子查询结果是否非空，常用于相关子查询。

双重 NOT EXISTS：全部/所有

查询选修了全部课程的学生：

SELECT SNAME
FROM S AS S1
WHERE NOT EXISTS (
    SELECT *
    FROM C AS C1
    WHERE NOT EXISTS (
        SELECT *
        FROM SC
        WHERE SC.S# = S1.S#
          AND SC.C# = C1.C#
    )
);

口诀：不存在一门课程，使得该学生没有选。

6. 集合操作

UNION、INTERSECT、EXCEPT 默认去重，加 ALL 保留重复。

7. 数据修改

INSERT

INSERT INTO 表名(列名, ...)
VALUES (...);

或插入查询结果：

INSERT INTO EXCELLENT(S#, GRADE)
SELECT S#, AVG(GRADE)
FROM SC
GROUP BY S#
HAVING AVG(GRADE) > 90;

DELETE

DELETE FROM 表名 WHERE 条件;

忘记 WHERE 会删除全表元组。

UPDATE

UPDATE 表名
SET 列名 = 表达式
WHERE 条件;

忘记 WHERE 会更新全表。

8. 全文检索

普通 LIKE '%keyword%' 对长文本效率低，且通常难以利用普通 B+ 树索引，因此需要全文索引。

MySQL

CREATE FULLTEXT INDEX idx ON document(content);
SELECT * FROM document
WHERE MATCH(content) AGAINST('test' IN BOOLEAN MODE);

SQL Server

CREATE FULLTEXT CATALOG catalog_name;
CREATE FULLTEXT INDEX ON table_name(column_name)
KEY INDEX index_name ON catalog_name;

查询：

WHERE CONTAINS((title, abstract), 'graph mining')
WHERE FREETEXT(content, 'Adaptive Query Processing')

CONTAINS 偏精确条件匹配；FREETEXT 偏自然语言检索。

9. DCL

GRANT

GRANT SELECT, INSERT
ON S
TO Liming
WITH GRANT OPTION;

WITH GRANT OPTION 表示可继续转授权。

REVOKE

REVOKE INSERT
ON S
FROM Liming;

权限图中，一个用户拥有权限的条件是存在从 DBA 到该用户的授权路径；回收权限可能引起级联回收。

10. SQL 易错点

SQL 默认保留重复元组，要去重用 DISTINCT。
聚集函数不能直接写在 WHERE 中，应使用子查询或 HAVING。
GROUP BY 后 SELECT 非聚集列必须出现在 GROUP BY 中。
NULL 不能用 = NULL 判断。
NOT IN 遇到 NULL 可能异常，NOT EXISTS 更稳。
更新和删除要检查 WHERE。
DROP、DELETE、TRUNCATE 含义不同。
LIKE 与全文检索不是一回事。

五、关系规范化

1. 不良模式问题

数据冗余
插入异常
删除异常
更新异常

规范化目标是通过分解关系模式减少冗余并消除异常。

2. 函数依赖

设 R(U)，X、Y 为 U 的属性子集。若任意两个元组 t、s 满足：

t[X] = s[X] => t[Y] = s[Y]

则称 X -> Y，即 X 函数决定 Y。

类型

平凡函数依赖：Y ⊆ X。
非平凡函数依赖：Y ⊄ X。
完全函数依赖：X 决定 Y，且 X 的任意真子集不能决定 Y。
部分函数依赖：X 的某个真子集也能决定 Y。
传递函数依赖：X -> Y, Y -> Z, Y 不决定 X, Z 不属于 Y，则 Z 传递依赖于 X。

3. 码

超码：若 K -> U，K 是超码。
候选码：最小超码。
主属性：出现在候选码中的属性。
非主属性：不出现在任何候选码中的属性。

4. 范式

1NF

每个属性值不可再分。

2NF

在 1NF 基础上，每个非主属性完全函数依赖于码。核心是消除非主属性对码的部分依赖。

3NF

在 2NF 基础上，不存在非主属性对码的传递依赖。

等价判定：对每个非平凡依赖 X -> A，至少满足：X 是超码，或 A 是主属性。

BCNF

对每个非平凡函数依赖 X -> Y，X 都必须是超码。BCNF 强于 3NF。

4NF 与多值依赖

多值依赖只需掌握概念。若给定 X 时，Y 的一组值只依赖 X，与其他属性 Z 无关，则 X ↠ Y。

函数依赖是多值依赖的特例。4NF 要求每个非平凡多值依赖 X ↠ Y 中，X 含有码。

5. Armstrong 公理

基本公理：

自反律：若 Y ⊆ X，则 X -> Y。
增广律：若 X -> Y，则 XZ -> YZ。
传递律：若 X -> Y 且 Y -> Z，则 X -> Z。

常用推导规则：

合并律：X -> Y, X -> Z 推出 X -> YZ。
分解律：X -> YZ 推出 X -> Y 和 X -> Z。
伪传递律：X -> Y, WY -> Z 推出 WX -> Z。

6. 属性集闭包

计算 X+：

初始化 X+ = X。
扫描依赖集 F，若某依赖 A -> B 中 A ⊆ X+，则把 B 加入 X+。
重复直到 X+ 不再变化。

用途：

判断 X -> Y 是否成立：看 Y ⊆ X+。
判断 K 是否为超码：看 K+ = U。
求候选码。

7. 最小覆盖

步骤：

右部单属性化。
删除冗余函数依赖。
删除左部冗余属性。

8. 范式判定流程

判断是否 1NF。
求候选码。
标出主属性和非主属性。
判断是否存在非主属性对候选码的部分依赖：有则不是 2NF。
判断是否存在非主属性对码的传递依赖，或用 3NF 判定式。
判断 BCNF：所有非平凡依赖左部是否都是超码。
多值依赖只需掌握概念和 4NF 定义。

六、事务

1. 事务概念

事务是程序执行的一个单位，可以访问并可能更新数据库中的数据项。

典型转账事务：

read(A)
A := A - 50
write(A)
read(B)
B := B + 50
write(B)

2. ACID

特性	含义
Atomicity 原子性	要么全做，要么全不做
Consistency 一致性	事务执行前后数据库从一致状态到一致状态
Isolation 隔离性	并发事务互不看到对方中间状态
Durability 持久性	提交后结果永久保存

3. 事务状态

活动 Active、部分提交 Partially Committed、失败 Failed、中止 Aborted、提交 Committed。

4. 调度与可串行化

调度是并发事务操作的执行顺序，必须保持每个事务内部操作顺序。

若一个并发调度与某个串行调度等价，则称为可串行化。

5. 冲突指令

两个不同事务的指令冲突，当且仅当：

访问同一数据项；
至少一个是写操作。

操作	是否冲突
read-read	不冲突
read-write	冲突
write-read	冲突
write-write	冲突

同一数据项，至少一写，即冲突。

两个操作之间的冲突会强制要求他们之间存在一个（逻辑上的）时间顺序。

6. 冲突可串行化

如果调度可通过交换相邻不冲突指令变为某个串行调度，则是冲突可串行化。

判定：优先图无环当且仅当调度冲突可串行化。

优先图构造：

顶点为事务。
若 Ti 的某冲突操作先于 Tj，则画边 Ti -> Tj。
无环则可串行化，有环则不可。
无环时，拓扑排序给出等价串行顺序。

7. 视图可串行化

视图等价需满足：

读初值的事务相同。
读到某事务写入值的关系相同。
最终写每个数据项的事务相同。

关系：冲突可串行化一定是视图可串行化；视图可串行化不一定冲突可串行化。

8. 可恢复与无级联

可恢复调度：若 Tj 读了 Ti 写的数据，则 Ti 必须先于 Tj 提交。
无级联调度：Tj 只能读取已经提交事务 Ti 写的数据。
无级联调度一定可恢复。

七、查询处理实现

1. 查询处理流程

SQL 输入 → 语法分析 → 逻辑查询计划 → 查询优化 → 物理执行计划 → 执行结果。

2. 查询代价

课程中通常简化为磁盘块传送次数。

常用符号：

符号	含义
T(R)	R 的元组数
B(R)	R 占用的磁盘块数
S(R)	元组大小
V(R,A)	属性 A 的不同取值数
M	可用内存块数
HT(i)	索引层数

3. 选择运算

全表扫描

适用于任何条件，代价约 B(R)。

索引扫描

等值选择 + 主/聚簇索引：HT(i) + 匹配记录所在块数。
等值选择 + 辅助/非聚簇索引：HT(i) + 匹配记录数。
范围选择 + 有序主索引：HT(i) + 满足条件的块数。
范围选择 + 有序辅助索引：HT(i) + 满足条件的记录数。

4. 排序

若数据不能全部进入内存，使用外排序。

初始归并段数：N = ceil(B(R) / M)。
每趟最多 (M-1) 路归并。
归并趟数：ceil(log_(M-1) N)。
总 I/O：2B(R) * (1 + ceil(log_(M-1) ceil(B(R)/M)))。

5. 连接算法

嵌套循环连接

以 R 为外关系：T(R) * T(S) + T(R)。

适用任意连接条件，但代价高。

块嵌套循环连接

以 R 为外关系：B(R) * B(S) + B(R)。

若内存可一次读入外关系多个块，改进代价：

B(R) + ceil(B(R)/(M-1)) * B(S)

若保留输出缓冲，常用 M-2。

索引嵌套循环连接

适用于等值/自然连接，且内关系连接属性上有索引。

代价近似：B(外关系) + T(外关系) * 每次索引查找代价。

归并连接

适用于等值/自然连接，尤其是输入已按连接属性排序。

若已排序，代价约 B(R) + B(S)；若未排序，要加两个关系的排序代价。

散列连接

适用于等值/自然连接。用同一哈希函数把两关系按连接属性分桶，只比较对应桶。适合大表、无序、无索引场景。

6. 连接策略选择

小表 + 大表连接列有索引：索引嵌套循环连接。
两表已排序：归并连接。
两大表未排序、无索引：散列连接。
非等值连接：通常只能用嵌套循环连接。

7. 查询执行方式

物化执行：中间结果写入磁盘，简单但 I/O 开销大。
流水线执行：中间结果边产生边传给父操作，减少临时结果写盘。
火山模型：一次处理一行，适合 OLTP。
向量化执行：一次处理一批，适合 OLAP。

八、数据存储与索引

1. 磁盘访问时间

访问时间 = 寻道时间 + 旋转等待时间 + 传输时间

平均旋转等待时间约为旋转一周时间的一半。
传输时间 = 数据量 / 传输率。

2. RAID

RAID 0：块级拆分，无冗余，性能高但可靠性差。
RAID 1：镜像，可靠性高，空间开销大，适合日志文件。
RAID 5：数据和奇偶校验分布存储，读性能好，写一个块约需 2 读 + 2 写。
RAID 10：镜像 + 拆分，适合写多场景。

若每秒读 r 次、写 w 次：

RAID 1 I/O 约 r + 2w。
RAID 5 I/O 约 r + 4w。

3. 记录与文件组织

定长记录

若每条记录长度 n，第 i 条记录从 n*(i-1) 字节开始。

删除处理：后续记录前移、用最后记录填补、空闲列表。

变长记录

适合 varchar、多类型记录、重复字段等。常用 (offset, length) 表示变长属性，用 null-value bitmap 表示空值。

分槽页结构

页头保存记录入口数、空闲空间位置、记录位置和大小数组。适合变长记录，页内记录可移动。

文件组织形式

堆文件：记录放任意空闲位置。
顺序文件：按搜索码排序，适合顺序处理。
多表聚簇文件：相关关系记录放在一起，有利连接，不利单表扫描。
B+ 树文件组织：支持有序访问、插入、删除、范围查询。
哈希组织：适合等值查询，不适合范围查询。

4. 缓冲区管理

访问块时：若在缓冲区直接返回；否则分配空间，必要时替换块，修改过的块需写回，再读入目标块。

概念：

pinned block：被钉住的块，不允许替换。
forced output：强制写出，常用于恢复和提交。
LRU：替换最近最少使用块。
MRU：某些顺序扫描/嵌套循环场景中可用。

5. B+ 树索引

特点：

多路平衡树。
非叶节点只导航。
数据项或数据指针在叶节点。
叶节点按搜索码顺序链接。
树矮而胖，适合外存。
适合等值查询和范围查询。

插入/删除

插入满节点时分裂，可能向上传播，根分裂时树高增加。
删除后若节点不足，先尝试重分配，不能则合并，可能向上传播。

聚簇索引 vs 非聚簇索引

类型	特点	性能
聚簇索引	索引顺序就是数据物理顺序；叶节点是数据	范围查询好；一个表通常只有一个
非聚簇索引	叶节点存指向数据行的指针/RID	匹配记录多时可能大量随机 I/O

6. 散列索引

通过哈希函数 h(K)=B 把搜索码映射到桶。

适合等值查询，不适合范围查询。桶溢出原因包括桶数不足和数据分布偏斜，常用溢出链处理。

7. 位图索引

每个属性值对应一个位向量，位向量长度等于记录数；第 i 条记录取该值则第 i 位为 1。

适合：低基数列、数据仓库、多条件组合查询、读多写少。

不适合：高基数列、高频更新。

位图查询通过 AND/OR/NOT 做集合运算。例如：

Region='Asia' AND Type='Dealer' 可用两个位图按位 AND 得到结果。

位图索引空间计算

若表有 N 条记录，某列有 V 个不同取值：

位图大小：N * V bits
字节数：N * V / 8
页数：ceil((N*V/8) / PageSize)

8. 列存储

优点：只读需要的列、压缩率高、适合 OLAP/数据仓库/宽表/稀疏列。

缺点：多列重构元组代价高，插入更新代价较高。

九、综合题速查模板

1. ER 设计题

答题模板：

实体：列出实体集及属性，标主码。
联系：列出联系名、参与实体、联系类型、联系属性。
约束：标明 1:1、1:N、M:N、全部/部分参与。
特殊结构：弱实体、多值属性、ISA、聚集。
转关系：按 ER 转关系规则写关系模式，并标主码、外码。

2. 关系模型设计题

找实体和联系。
每个实体变关系，确定主码。
1:N 在 N 方加外码。
M:N 新建联系表。
多值属性单独建表。
检查实体完整性、参照完整性、用户定义完整性。

3. SQL 综合题

高频模式：

多表连接：JOIN 或 FROM 多表 + WHERE 连接条件。
每组统计：GROUP BY + 聚集函数。
组后筛选：HAVING。
最大/最小：子查询 = (SELECT MAX(...))。
同时满足多个条件：交、IN、自连接或 GROUP BY HAVING。
全部/所有：双重 NOT EXISTS。
没有：NOT EXISTS 通常比 NOT IN 更稳。

4. 查询处理计算题

常用公式：

全表扫描：B(R)。
块嵌套循环连接：B(R)B(S)+B(R)。
改进块嵌套循环：B(R)+ceil(B(R)/(M-1))*B(S)。
已排序归并连接：B(R)+B(S)。
外排序：2B(R)*(1+ceil(log_(M-1)ceil(B(R)/M)))。

做题顺序：先写已知量 T、B、M、索引类型；再判断算法适用条件；最后代入公式。

5. 存储计算题

表页数

每页记录数：floor(PageSize / RecordSize)
页数：ceil(RecordCount / 每页记录数)

位图索引

位图大小：记录数 × 不同取值数 bits。

RAID

RAID 1：r + 2w；RAID 5：r + 4w。

磁盘访问

寻道时间 + 平均旋转等待 + 传输时间。

十、最后复习顺序建议

先背 chap12 指定重点和比例，避免平均用力。
客观题优先：导论、关系模型、ER、范式、事务、索引。
综合题优先练：ER 转关系、SQL 查询、关系代数、查询代价、存储计算。
SQL 专门练双重 NOT EXISTS、GROUP BY/HAVING、NULL、外连接。
关系规范化专门练闭包、候选码、范式判定、Armstrong 公理。
事务专门练冲突指令和优先图判定。
查询处理和存储专门整理公式，做题时先判断适用条件再套公式。

LeoJellyfish

探索

数据库系统期末复习提纲