数据库系统原理

数据库系统原理#

基本介绍#

平常我们经常提及的数据库指的是存储数据的仓库，其物理体现就是一个个的文件，实质是一个个的表（DB tables）。这些表的维护由一个叫做数据库管理系统（DBMS）来完成，它保证了数据库的安全性和完整性，并为我们提供了 CRUD 接口。底层由 DBMS 支持，借助 DBMS 提供的事务管理和 CRUD 接口，上层应用的具体业务实现则需要我们编写 SQL 语句手工实现。 Fig. 1 展示了数据库软件的交互过程。

../_images/db_overview.svg — Fig. 1 数据库软件交互过程#

按照数据库类型进行分类，我们可以将其分为关系型和非关系型两大类：

关系数据库是一种用于存储相互关联的数据点并提供数据点访问的数据库。它采用关系模型，直接、直观地在表中展示数据。在关系数据库中，表中的每一行都代表一条记录，每条记录都具有一个唯一的 ID（又被称为键），而表中的列则用于存储数据的属性。每条记录的每一个属性通常都有一个值。借此，用户可以轻松地在数据点之间建立关联 ¹ ¹关系数据库是什么 | Oracle 中国 https://www.oracle.com/cn/database/what-is-a-relational-database/。

NoSQL 数据库（意即“不仅仅是 SQL”）并非表格格式，其存储数据的方式与关系表不同。 NoSQL 数据库的类型因数据模型而异，主要类型包括文档、键值、宽列和图形。它们提供了灵活的模式，可以随大量数据和高用户负载而轻松扩展 ² ²NoSQL 是什么 - MongoDB https://www.mongodb.com/zh-cn/nosql-explained。

关系型数据库的代表有：MySQL、Oracle、SQL Server、SQLite。

非关系型数据库的代表有：Redis、MongoDB、Neo4j、HBase。

专业术语扫盲#

³如何理解数据库的三级模式 https://www.zhihu.com/question/38737183/answer/93294527⁴SQL 四种语言 https://www.cnblogs.com/henryhappier/archive/2010/07/05/1771295.html

名词	备注
列 / 字段 / 属性 / 数据项	column / field / attribute / data item
行 / 元组 / 记录	row / tuple / record
（关系）模式 = 表名 + 表头	关系模式是关系的结构
关系 / 表 = 模式 + 表内容	关系是关系模式在某一时刻的数据
超键（super key）	在关系中能唯一标识元组的属性集称为关系模式的超键
候选键（candidate key）	不含有多余属性的超键称为候选键，同一个元组可能有多个候选键
主键（primary key）/ 主码	用户挑选出来的用于标识元组的一个候选键称为主键。需要注意的是，这种描述在数据库原理课本上是适用的，但是理论并不是完全照搬地应用于实践，在数据库设计时，通常增加一个 `id` 列作为主键，而不是挑选候选键
外键（foreign key）/ 外码	关系 \(R\) 中的一个属性组，它不是 \(R\) 的候选键，但它与另一个关系 \(S\) 的候选键相对应，则称这个属性组为 \(R\) 的外码或外键
主属性与非主属性	包含在任意一个候选键中的属性被称作主属性，而其他属性被称作非主属性
实体完整性	关系的主键中的属性值不能为空值
参照完整性	如果关系 \(R_1\) 的外键 \(F_k\) 与关系 \(R_2\) 的主键 \(P_k\) 相对应，则 \(R_1\) 中的每一个元组的 \(F_k\) 值或者等于 \(R_2\) 中某个元组的 \(P_k\) 值，或者为空值
用户自定义的完整性	用户针对具体的应用环境定义的完整性约束条件。如 \(S\#\) 要求是 \(10\) 位整数，其中前四位为年度，当前年度与他们的差必须在 \(4\) 以内
三级模式 ³ ³如何理解数据库的三级模式 https://www.zhihu.com/question/38737183/answer/93294527	外模式 / 局部模式 / External Schema / View 概念模式 / 全局模式 / 逻辑模式 / 模式 / Schema / Conceptual View 内模式 / 存储模式 / 物理模式 / Internal Schema = Internal View
两层映像	\(\text{E-C}\) 映像（\(\text{E-C Mapping}\)）实现逻辑独立性 \(\text{C-I}\) 映像（\(\text{C-I Mapping}\)）实现物理独立性
四种 SQL 语言 ⁴ ⁴SQL 四种语言 https://www.cnblogs.com/henryhappier/archive/2010/07/05/1771295.html	数据库定义语言（DDL，Data Definition Language）定义 SQL 模式、基本表、视图、索引等。 `CREATE`、`ALTER`、`DROP`、`TRUNCATE`、`COMMENT`、`RENAME`。数据库操纵语言（DML，Data Manipulation Language）由 DBMS 提供。`SELECT`、`INSERT`、`UPDATE`、`DELETE`、`MERGE`、`CALL`、`EXPLAIN PLAN`、`LOCK TABLE`。数据库控制语言（DCL，Data Control Language）授权、角色控制等。`GRANT`、`REVOKE`。事务控制语言（TCL，Transaction Control Language）设置保存点、回滚等。`SAVEPOINT`、`ROLLBACK`、`SET TRANSACTION`。
数据模型	层次模型（一种用树形结构描述实体及其之间关系的数据模型）网状模型（允许一个结点可以同时拥有多个双亲结点和子结点）关系模型（采用二维表格结构表达实体类型及实体间联系的数据模型）

关系代数#

一个完备的数据库语言，应当同时具备三种运算能力：关系代数、关系演算（包括元组演算和域演算）。

关系代数：以集合为对象进行操作，由集合到集合的变换。
元组演算：以元组为对象进行操作，取出表中的每一个元组进行验证（有多个元组变量需要多个循环）。
域演算：以域变量为对象进行操作，取出域的每一个变量进行验证看其是否满足条件。

对比这三种运算，域演算的非过程性最好，元组演算次之，关系代数最差。从安全性上考虑，关系代数是一种安全的集合运算，而关系演算不一定是安全的。

操作名称	操作语句
并	\(R \cup S = \{ t \| t \in R \vee t \in S \}\)
差	\(R - S = \{ t \| t \in R \wedge t \notin S \}\)
积	\(R \times S = S \times R\) \(R \times S\) 表示 \(R\) 中的每一个元组和 \(S\) 中的所有元组串接，\(S \times R\) 表示 \(S\) 中的每一个元组和 \(R\) 中的所有元组串接。因此，它们的结果相同，列的顺序不影响结果。
选择	\(\sigma_{con}(R) = \{ t \| t \in R \wedge con(t) = true \}\)
投影	\(\Pi_{A_{i1}, A_{i2}, \dots, A_{ik}}(R) = \{ < t[A_{i1}], t[A_{i2}], \dots, t[A_{ik}] > \| t \in R \}\) 投影可将列属性重新排列
更名（针对列）	\(\rho_{\text{new_column_name}}(\text{old_column_name})\) 当一个表需要和其自身进行连接运算时，通常要使用更名操作
交	\(R \cap S = \{ t \| t \in R \wedge t \in S \} = R - (R - S) = S - (S - R)\) 注意，差运算的括号不能省略
自然连接	\(R \bowtie S = \sigma_{t[B]=s[B]}(R \times S)\) 自然连接会筛选出两个表相同属性组上值相等的元组
内连接（\(\theta\)-连接）	\(R \mathop{\bowtie}\limits_{A \theta B}^{} S = \sigma_{t[A]\ \theta\ s[B]}(R \times S)\) 内连接是自然连接更一般的情况
外连接	左外连接 \(R ⟕ S\)，右外连接 \(R ⟖ S\)，全外连接 \(R ⟗ S\) 外连接 = 自然连接或 \(\theta\)-连接 + 失配的元组与全空元组形成的连接
除	\(R \div S = \Pi_{R-S}(R)-\Pi_{R-S}((\Pi_{R-S}(R) \times S)-R)\) 注意，这里的 \(R - S\) 指的是属性做差，前面讲的是元组做差。除法比较难理解，从结果往回看比较好理解。结果的表头是 \(R\) 的表头的一部分，但不在 \(S\) 的表头中，结果与 \(S\) 做笛卡尔积又都在 \(R\) 中。除法经常用于求解“查询……全部的 / 所有的……”问题

SQL-DDL 基本语句#

-- 创建数据库
create database `数据库名`;

-- 打开或关闭数据库
use `数据库名`;
close `数据库名`;

-- 创建基本表（概念模式的数据）
create table if not exists ​`表名`(
  `列名1` 数据类型 primary key unique not null auto_increment,
  `列名2` 数据类型 not null,
  index (`列名1`)
);

-- 创建视图（外模式的数据）
create view `视图名`
as 子查询
with check option;

-- 修改表结构
alter table `表名`
add `列名1` 数据类型, `列名2` 数据类型
modify `列名1` 数据类型, `列名2` 数据类型
add constraint 完整性约束条件
drop 完整性约束条件;

-- 删除索引
drop index `列名1`;

-- 删除基本表
drop table `表名`;

-- 删除数据库
drop database `数据库名`;

SQL-DML 基本语句#

-- 单一元组新增（列名可省略不写）
insert into `表名` (`列名1`, `列名2`)
  values(值1, 值2);

-- 批元组新增
insert into `表名` (`列名1`, `列名2`)
values(值1, 值2);

-- 单表查询
select distinct `列名1`, `列名2`
from `表名`
where 检索条件
group by 分组条件
having 分组过滤条件
order by `列名1` desc  -- 默认升序
not like 正则表达式;

-- 多表联合查询（笛卡尔积）
select `列名1` as `列别名1`, `列名2`
from `表名1` inner join `表名2` as `表别名2`  -- as 可以省略
             right outer join `表名3`
             on `表名3`.`列名3` = `表名1`.`列名1`
where `表名1`.`列别名1` = `表别名2`.`列名2`;  -- theta-连接，等值连接

-- 使用变量
select `列名1` into @变量名 from `表名1` where `列名2` = 表达式或子查询;
select `列名3` from `表名2` where `列名4` = 表达式或子查询 and `列名1` = @变量名;

-- 元组更新
update `表名`
set `列名1` = 表达式或子查询, `列名2` = 表达式或子查询
where 检索条件;

-- 元组删除
delete from `表名`
where 检索条件; -- 如果 where 条件省略，则删除所有元组

复杂查询和视图#

复杂查询会使用到子查询。子查询是指 where 子句中的 select 语句。

使用复杂查询，我们能够实现的业务有（因为都是判断条件，返回值为 true 或 false）：

判断某一元素是否是某一个集合的成员（[not] in (子查询)）
判断某一个集合是否包含另一个集合（表达式 [\(\theta\) some | \(\theta\) all] (子查询)）
判断集合是否为空（[not] exists (子查询)）
判断集合是否存在重复元组（[not] exists (子查询)）

为了实现上述目标，我们可以将子查询分三种类型：IN-子查询、\(\theta\)-SOME / \(\theta\)-ALL 子查询、EXISTS-子查询。

注意，in 判断的是集合中是否包含某一个元素，而 exists 判断的是集合是否为空，它们是不一样的。

\(\theta\) 表示的是比较符，可以是 <，>，<=，>=，=，<> 中的任意一个。 \(\theta\) some 如果有一个值满足 \(\theta\) 关系，返回值就是真，\(\theta\) all 所有的值都满足 \(\theta\) 关系，返回值才为真。

按照层次结构划分，子查询分为外层和内层查询。如果内层查询需要用到外层查询的变量，那么这种查询方式叫 相关子查询。另一种方式则是内外层相互独立的查询，不涉及相关参数的传递，那么这种方式称为 非相关子查询。根据变量的作用域原则，子查询用到的变量可以是父查询传递过来的，反过来则不行。

例题（难点）求至少使用了工程 S1 供应的全部零件的工程号 ⁵ ⁵王珊, 张俊. 数据库系统概论 (第5版) 习题解析与实验指导[M]. 高等教育出版社, 2015.。

要想回答这个问题，如果直接采用常规思路，将很难理解解题过程。根据语义转化，我们可以把它描述为：在 S1 生产的_全部零件_中，不存在一个它不使用的零件。因为这个语义中含有两个否定，因此需要两个 not exist 来完成从自然语言到 SQL 语言的转化。

select distinct 工程号
from SPJ SPJZ
where not exists (        -- 4. 它不使用
  select *                -- 1. 在 S1 生产的全部零件中，
  from SPJ SPJX
  where SNO = 'S1'
  and not exists (        -- 2. 不存在
    select *              -- 3. 有一个零件
    from SPJ SPJY
    where SPJY.零件号 = SPJX.零件号 and SPJY.工程号 = SPJZ.工程号
  )
);

这道题看过好几遍了，每次看都不是很理解，现在也不是很理解。所以说，exists 可真是个难点。

SQL-DCL 基本语句#

数据库控制语言将为数据库的完整性和安全性保驾护航。

完整性：指的是 DBMS 保证在任何情况下的 DB 都是正确的、有效的、一致的。
安全性：访问规则、权利和授权。

SQL 语言支持的完整性约束包括：静态约束（列完整性和表完整性）和动态约束（触发器）。

不知道你注意到没有，我们在创建表的时候，其实是有完整性约束的，从关键字上的体现就是 primary key、not null、unique。它们保证了列完整性约束（或域完整性）。

当然，MySQL 还为我们提供了更多用于列完整性约束的关键字，比如 constraint，check()（保证条件为真），references，on delete {cascade | set null}。

表完整性约束和列完整性约束的关键字是一样的，可以把列完整性约束看做是表完整性约束的特例。列完整性约束作用于某一个列上，而表完整性约束可以指定多个列服从某个约束，比如 unique(列名1, 列名2)。

trigger（触发器）是一种过程完整性约束（相比之下，create table 中定义的都是非过程性约束）。触发器是一段程序，该程序可以在特定的时刻被自动触发执行，比如一次更新操作之前或之后。

create trigger `触发器名` before   -- 也可以是 after
update of `列名`                   -- 也可以是 insert delete
on `表名`
referencing 程序段中的变量声明
for each row                      -- 对更新操作的每一条结果检查约束，也可以对整个更新操作检查
when (检查条件)                  -- 检查条件如果满足，就执行下面的程序
  -- 单行程序直接写在这里
  -- 多行程序要用下面的方式
  begin atomic
    -- 程序段代码语句 1;
    -- 程序段代码语句 2;
  end

在安全控制方面，我们可以通过在数据字典或系统目录中保存存取规则，限制用户对 DB 的访问权利。当用户量大时，可以按用户组建立访问规则。

访问的粒度：字段、元组、关系、数据库。
访问的权利：增、删、查、改。
访问的谓词：拥有权利需要满足的条件。

视图是安全控制的重要手段，如下所示。

create EmpView1 as select * from Employee -- 通过视图，限制用户对关系中某些数据项的存取
create EmpView2 as select * from Employee where P#=:UserId -- 视图与谓词结合，限制访问

从安全控制的角度来看，我们通常把用户分成三种类型：普通用户、程序员用户、DBA。

普通用户：具备 select 数据库、表、元组、字段的能力。
程序员用户：具备 insert、update、delete 元组的能力。
DBA：具备 create、alter、drop 表空间、模式、表、索引、视图的能力。

-- 授权命令
grant all privileges      -- 或者是 select insert update delete
on `表名`                 -- 或者是 视图名
to `用户账户ID1`, `ID2`;  -- 或者是 public
with grant option         -- 默认是不应该授予普通用户 grant 权限的

-- 收回授权
revoke all privileges
on `表名`
from `用户账户ID1`, `ID2`;

数据库设计#

数据库设计是指根据数据库模型确定数据的组织方式 ⁶ ⁶Database design basics. (n.d.). Database design basics. Retrieved May 1, 2010, from https://support.office.com/en-US/article/Database-design-basics-EB2159CF-1E30-401A-8084-BD4F9C9CA1F5。Fig. 2 展示了数据库设计的详细步骤：

../_images/db_design.svg — Fig. 2 数据库设计流程 ⁷ ⁷数据库系统原理习题与解析 https://kdocs.cn/l/cnw25Tq3UVuU#

一个设计良好的数据库，应该尽可能消除数据冗余，但是又不是完全严格地按照三大范式来约束。因为在规范和性能之间，总会需要有一个取舍，如果数据严格满足规范，那么必然需要一些联表查询，进而导致性能下降。因此，在数据库设计时，允许有一定的数据冗余，以保证性能。

另外一点，设计良好的数据库应当尽可能避免使用物理外键，也就是说，尽量不要在数据表中使用外键字段。因为这会导致在后续业务中给维护表结构带来额外的负担。比如，有了外键后，删除和更新数据都会变得很麻烦。

不同类型的数据应当放在不同的数据库中，比如结构化数据放在 MySQL 中，视频流放在 MongoDB 中，评论放在 Redis 中。

数据库设计中需要用到的数据类型：

数值：tinyint   smallint    mediumint  int    bigint    float     double     decimal
       1字节     2字节       3字节     4字节    8字节                         金融常用

字符串： char      varchar   tinytext    text
        0-255     0-65536    2^8-1      2^16-1

时间日期：date    time       datetime      timestamp     year

空值      null

数据规范：每个表中都应该包含以下 5 个字段。

id      version    is_delete     gmt_create     gmt_update
主键    乐观锁      伪删除        创建时间        修改时间

函数依赖定理#

在关系数据库理论中，函数依赖（FD）是关系数据库中两个属性集合之间的一种约束。

在数据库设计的过程中，我们设计的关系模式可能存在如下问题：

数据冗余：某个字段的属性值多次被重复存储
不一致性：由于数据存储冗余，当更新某些数据项时，就有可能一部分字段修改了，而另一部分没有修改
插入异常：对于非空字段，没有合适的值，导致与其关联的其他字段也无法成功插入
删除异常：涉及到级联删除时，由于表之间的耦合太强，无法成功删除

这是因为关系中的某些属性之间存在数据依赖。现在人们已经提出了许多类型的数据依赖，其中最重要的是函数依赖和多值依赖。

我们的目标就是消除关系模式中的函数依赖。本节我们将介绍几个函数依赖的定义：

名词	注解
函数依赖	设有关系模式 \(R(A_1, A_2, \dots, A_n)\) 或简记为 \(R(U)\)，\(X\)，\(Y\) 是 \(U\) 的子集，\(r\) 是 \(R\) 的任一具体关系。如果对于 \(r\) 的任意两个元组 \(t_1, t_2\)，由 \(t_1[X]=t_2[X]\) 导致 \(t_1[Y]=t_2[Y]\)，则称 \(X\) 函数决定 \(Y\)，或 \(Y\) 函数依赖于 \(X\)，记为 \(X \rightarrow Y\)。
平凡函数依赖	设 \(X \rightarrow Y\) 是一个函数依赖，若 \(Y \subseteq X\)，则 \(X \rightarrow Y\) 是一个平凡函数依赖
完全函数依赖	设 \(X \rightarrow Y\) 是一个函数依赖，并且对于任何 \(X' \subset X, X' \rightarrow Y\) 都不成立，则称 \(X \rightarrow Y\) 是一个完全函数依赖。即 \(Y\) 函数依赖于整个 \(X\)，记为 \(X \overset{F}{\rightarrow} Y\)。
部分函数依赖	设 \(X \rightarrow Y\) 是一个函数依赖，但不是完全函数依赖，则称 \(X \rightarrow Y\) 是一个部分函数依赖，或称 \(Y\) 函数依赖于 \(X\) 的某个真子集，记为 \(X \overset{P}{\rightarrow} Y\)。
传递函数依赖	设 \(R(U)\) 是一个关系模式，\(X, Y, Z \subseteq U\)，如果 \(X \rightarrow Y, Y \rightarrow Z\) 且 \(Y \nrightarrow X, Z - Y \ne \emptyset, Y - X \ne \emptyset\) 成立，则称 \(Z\) 传递函数依赖于 \(X\)，记为 \(X \overset{T}{\rightarrow} Y\)。
逻辑蕴涵	设 \(F\) 是关系模式 \(R\) 的一个函数依赖集，\(X, Y\) 是 \(R\) 的属性子集，如果从 \(F\) 中的函数依赖能够推出 \(X \rightarrow Y\)，则称 \(F\) 逻辑蕴含 \(X \rightarrow Y\)。
闭包	由被 \(F\) 逻辑蕴含的函数依赖的全体构成的集合，称为 \(F\) 的闭包，记为 \(F^+\)。

现在对这几个概念有了一个大概的认识，那么我们在实际工程应用中，应当 熟练应用这些概念来判断某个关系模式存在哪些函数依赖关系，具体来讲，你需要做一些练习题 [7]，学习如何对某个关系求等价的最小依赖集，如何求闭包。在求出这些东西后，我们能用来做什么呢？答案是 筛选属性，更好地设计表字段。

范式分解理论#

对存在数据冗余、插入异常、删除异常问题的关系模式，应采取将一个关系模式分解为多个关系模式的方法进行处理。在分解处理中会涉及一些新问题，为使分解后的模式保持原模式所满足的特性，要求分解处理具有无损连接性和保持函数依赖性。

无损连接性指的是对关系模式分解时，原关系模式下任一合法的关系实例在分解之后应能通过自然连接运算恢复起来。如果 \(R\) 的分解为 \(\rho = \{R_1, R_2\}\)，\(F\) 为 \(R\) 所满足的函数依赖集合，则分解 \(\rho\) 具有无损连接性的充要条件为：

\[ R_1 \cap R_2 \rightarrow (R_1 - R_2) \text{ 或 } R_1 \cap R_2 \rightarrow (R_2 - R_1) \]

若单从定义上来理解保持依赖，具有一定的难度，但我们还是把定义写在这里：

设有关系模式 \(R\)，\(F\) 是 \(R\) 的函数依赖集，\(Z\) 是 \(R\) 的一个属性集合，则称 \(Z\) 涉及的 \(F^+\) 中的所有函数依赖为 \(F\) 在 \(Z\) 上的投影，记为 \(\Pi_Z(F)\)，有：

\[ \Pi_Z(F)=\{x \rightarrow y \ | \ x \rightarrow y \in F^+ \text{且} x, y \subseteq z \} \]

我们把关系模式 \(R\) 的一个分解 \(\rho = \{ R_1, R_2, \dots, R_k \}\)，\(F\) 是 \(R\) 的依赖集，如果 \(F\) 等价于 \(\Pi_{R1}(F) \cup \Pi_{R2}(F) \cup \dots \cup \Pi_{Rk}(F)\)，则称分解 \(\rho\) 具有保持依赖性。

当然，无损连接和保持依赖这两个概念理解起来还是比较抽象，做个习题，会更好理解一些 [7]。

例 1：设有关系模式 \(R<U, F>\)，其中：

\[ U = \{ A, C, D \}, F = \{ A \rightarrow B, C \rightarrow B \} \]

判断一个分解 \(\rho = \{ AC, BC \}\) 是否具有无损连接性。

解：

\(\rho\) 的无损连接性判断结果如下表所示，由此判断它具有无损连接性。

关系模式	A	B	C
AC	a1	a2	a3
BC	b21	a2	a3

如果你不能理解上表，应该阅读本文末尾的参考文献 [7]。

⁸保持函数依赖的分解 https://kdocs.cn/l/cltqjwG6HTLW

例 2：设有关系模式 \(R(ABCD)\)，\(R\) 上的 FD 集为 ⁸ ⁸保持函数依赖的分解 https://kdocs.cn/l/cltqjwG6HTLW：

\[ F = \{ A \rightarrow B, B \rightarrow C, D \rightarrow B \} \]

求 \(\Pi_{ACD}(F)\) 和 \(\Pi_{BD}(F)\)。

解：

\(\Pi_{ACD}(F) = \{ A \rightarrow C, D \rightarrow C \}\)

\(\Pi_{BD}(F) = \{ D \rightarrow B \}\)

由于 \(\Pi_{ACD}(F) \cup \Pi_{BD}(F)\) 丢失了 \(A \rightarrow B\) 和 \(B \rightarrow C\)，故分解 \(\rho = {ACD, BD}\) 不保持依赖。

既然已经理解了无损连接和保持依赖的求解方法，那么它们有什么指导意义呢？

无损连接	保持依赖	说明
\(\checkmark\)	\(\checkmark\)	最好（不丢失数据和依赖）
\(\checkmark\)	\(\times\)	可接受（丢失依赖，会导致异常）
\(\times\)	\(\checkmark\)	不能接受（丢失数据）
\(\times\)	\(\times\)	不能接受（丢失数据）

物理存储#

关于数据库的物理存储，我们希望合理地组织数据，以实现高效存取。机械硬盘的物理结构如下：

../_images/db_disk_model.png — Fig. 3 磁盘的物理结构（台湾叫法与大陆略有不同） ⁹ ⁹国立联合大学, 磁盘管理, 幻灯片 http://debussy.im.nuu.edu.tw/sjchen/OS/97Spring/Ch_10.pdf#

在上面这张图上，有一组概念，我们需要弄清楚：

名词	注解
扇区（sector，磁区）	可以从磁盘读取或写入的最小信息单位
磁盘块（block）	若干连续扇区，大小固定，通常是 512 字节，读取到内存的最小单位
磁道（track，磁轨）	以轴线为中心的圆环，不同的半径即代表不同的磁道
盘面（platter，磁盘）	在同一水平面上，所有的磁道构成一个盘面
柱面（cylinder，磁柱）	在竖直面上，所有具有相同半径的磁道构成一个柱面
读写头（read-write head）	以磁性方式将信息存储在扇区上

我们知道，Windows 操作系统支持 NTFS、FAT32、exFAT 三种不同的文件系统。文件系统是系统对文件的存放排列方式，不同格式的文件系统关系到数据如何在磁盘进行存储。

那么，MySQL 组织文件的方式与操作系统有何不同？

操作系统以文件的方式（FAT）组织数据和存取数据，MySQL 则以磁盘块为单位来组织数据和存取数据。通常来讲，一个磁盘块的大小等于一个内存页的大小，这对于将磁盘块加载到内存中效率较高。因此，如果我们想要在一个块中找到某条记录，方式就是页面的 基地址:偏移地址。

存取时间是物理存储性能的评价指标，以块为单位读取数据，那么总的时间计算方式就是：

\[ \text{总的存取时间 = 寻道时间 + 旋转时间 + 传输时间} \]

明确了优化目标——时间、可靠性、可用性，现在常用的是 RAID 技术。 RAID 全称独立磁盘冗余阵列，是由许多价格便宜的磁盘组成一个容量巨大的磁盘组、以提升存储性能或提高数据安全的技术。这项技术一方面可以提高存取性能，另一方面也提高了数据库的可靠性。

RAID 又分为了好多种，我们只介绍几种常用的，其他类型需要参考文末的参考文献 ¹⁰ ¹⁰维基百科, 独立硬盘冗余阵列 https://zh.wikipedia.org/wiki/RAID：

1、RAID 0（又称为 Stripe 或 Striping——分条）

RAID 0 的缺点是不提供数据冗余，因此一旦用户数据损坏，损坏的数据将无法得到恢复。

2、RAID 1（又称为 Mirror 或 Mirroring——镜像）

提供最高的数据安全保障，但磁盘利用率为 50%，故成本最高。

3、RAID 5（RAID 0 和 RAID 1 的折中方案）

没有完全采用 RAID 1 的镜像理念，而是使用“奇偶校验信息”作为数据恢复的方式，但这与下面的 RAID 10 不同。

4、RAID 10（RAID 0 和 RAID 1 的折中方案）

RAID 10 也被称为镜像阵列条带，提供最好的性能和更好的可靠性。

按照数据的类型来说，有记录、表、文件三类，对应的数据库组织方式可以有：

对于一条记录，可选的存储方式有：

定长记录，还是变长记录（靠分隔符区分开始与结束）
记录是非跨块存储，还是跨块存储（靠指针连接）

对于一张表，可选的存储方式是：

连续分配：数据块被分配到连续的磁盘块上（存在扩展困难的问题）
链接分配：数据块中包含指向下一数据块的指针（存在访问速度问题）
按簇分配：簇是若干连续的磁盘块，簇之间靠指针连接（簇有时候也称片段Segment或盘区extent）
索引分配：索引块中存放指向实际数据块的指针

对于一个文件，可选的组织方式：

堆文件（Heap 或 Pile file）：无序，检索效率差；删除文件后需要重新组织数据库
排序文件（Sequential）：有序，更新效率差；文件溢出后需要重新组织数据库
散列文件（Hash file）：散列到桶中，桶内按顺序检索，难点在于如何让每个桶尽量均匀
聚簇文件（Clustering file）：将具有相似或相同属性值的记录存放在连续的磁盘簇块中

根据文件的组织方式，我们可以对文件建立 B+ 树索引或散列索引。

综上，没有一个十分完美的方案，经常是在鱼和熊掌之间做取舍，因此，符合业务场景的就是合适的。

查询的实现#

讲到查询的实现，不可避免地要涉及索引的概念，比如 InnoDB 的默认索引就是 B+ 树。索引是定义在存储表基础上、无需检查所有记录即可快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项组成。

合理地对某些字段建立索引，能提高效率，那么我们对哪些字段建立索引呢？答案是对经常出现在检索条件、连接条件、分组计算条件中的属性。 MySQL 支持建立的索引类型有四种：

主键索引 primary key：只能有一个列作为主键，不可重复。
唯一索引 unique key：可以有多个列声明为唯一索引，可以重复。
常规索引 key / index：可以由多个列声明为常规索引。
全文索引 fulltext index：并不是所有的引擎都支持全文索引，比如 MyISAM。

为了能够对后面的概念有一个清晰的认识，我们将常用概念在这里列举出来，以备后续翻阅。

概念	注解
索引文件	存储索引项的文件
主文件	存储表的文件
稠密索引	对主文件中的每个记录，都有一个索引项和它对应，指明该记录所在的位置
稀疏索引	对主文件中的部分记录，有索引项和它对应
主索引	每个存储块对应一个索引项。由于可能多个记录存储在同一个块上，因此主索引是稀疏索引。主索引通常建立在主码/排序码上，因此可以用主索引重新组织主文件数据
辅助索引	定义在主文件的任一或多个非排序字段上的辅助存储结构，辅助索引是稠密索引，因此检索效率相当高
聚簇索引	索引中邻近的记录在主文件中也是邻近存储的，这一点很像主索引。它们的区别在于，聚簇索引的聚簇字段不必是主键的排序字段，而主索引的必须建立在主键上。因此，主索引通常是聚簇索引，辅助索引通常是非聚簇索引
非聚簇索引	索引中邻近的记录在主文件中不一定是邻近存储的
倒排索引	正排：`#doc1, {word1, word2}`，倒排：`word1, {#doc1, #doc2}`
多级索引	当索引项比较多时，可以对索引再建立索引，依此类推，形成多级索引，常见形式为 B 树、B+ 树

通常，每个索引块由两部分组成：

索引字段：由 table 中某些列（通常是 1 列）中的值串接而成。
行指针：指向 table 中包含索引字段值的记录的记录在磁盘上的存储位置。

下面具体描述一下 B+ 树的数据结构，在本节末尾补充一下 B 树的介绍。

B+ 树索引：一种以树形结构来组织索引项的多级索引。对于一个 B+ 树结点，它的数据结构如下所示：

在 B+ 树的基本数据结构中，一个索引项指的是一个 (Ki, Pi) 对。 Ki 是索引字段值，Pi 是指针，指向索引块、数据块或数据块中记录的指针。最后一个 Pn 指向下一个 B+ 树结点。

以 n = 3 为例，B+ 树的非叶结点和叶结点的数据结构如下所示：

我们把一个叶结点和非叶结点完整地串起来，那么它们看起来会像下图所示（n = 3）：

每个索引块实际使用的索引指针的个数 \(d\) 满足下式（根结点除外）：

\[ n/2 \leq d \leq n \]

因此，每个索引块的指针利用率都在 50% 到 100% 之间。

B 树的数据结构和 B+ 树略有不同，具体表现如下：

以上是数据库的存储结构的介绍，那么在具体的实现中，我们是如何进行操作的呢？举例来说，操作分成两个步骤：先将主文件记录所在的磁盘块加载到内存中，然后采用循环的方式对比结果。大体的伪代码如下所示：

for i in 磁盘块
  将第 i 块磁盘加载到内存区 mem1 中
  for j in 磁盘块
    将第 j 个磁盘块加载到内存 mem2 中
    for p in 内存区 mem1
      读取第 p 条记录
      for q in 内存区 mem2
        读取第 q 条记录
        对比 p 和 q 的属性值，是否满足条件
        存入结果集

当然，这是一个很朴素的想法，有很大的优化空间，想在这里讲明白也不是一件容易的事，后面有机会再补充。

查询的优化#

所谓查询优化，指的是“如何使数据库查询的执行时间最短”。有三条启发式的优化原则供参考：

尽可能早地做选择
尽可能早地做投影
尽可能早地做选择和投影的合并

为了能够更好地理解查询优化的具体实现手段，我建议做一些练习巩固一下 [7]。

事务处理#

我们书写的每一条（一组）SQL 语句都可以看作一个事务。多个看似并行的事务，实际上是交叉执行的（并发）。那么如何保证数据的一致性，就是本节需要讨论的话题。

为什么需要事务？在一个提供服务的程序中，事务可能会由于 CPU 调度在执行到一半时被抢占，或由于断电、系统崩溃而中断。各种看似常规的操作都可能造成数据不一致，因此事务是必须的。

按照解决数据不一致性的方法来看，主要有两种：

基于封锁的方法（两段封锁算法）
基于时间戳的方法，时间戳小的事务先执行

为了更加方便地展开描述上面的两种方法，我们先了解一下什么是事务调度。

事务调度是指一组事务的基本步骤（读、写、加锁、解锁等控制操作）的一种执行顺序。表达事务调度的一种模型可以定义为：

\[\begin{split} \text{rT(A) ：事务 T 读 A}\\ \text{wT(A) ：事务 T 写 A} \end{split}\]

冲突是指调度中的一对连续动作，它们满足：如果交换顺序，那么涉及的事务中至少有一个的行为会改变。因此，有冲突的两个操作不能交换次序，而没有冲突的两个操作可以交换次序。

冲突可串行性则是指：一个调度如果能够通过交换相邻两个无冲突的操作转换成某个串行调度，则称此调度为冲突可串行化的。

例：一开始，事务 1 和 2 交替执行：

\[ \text{r1(A); w1(A); r2(A); w2(A); r1(B); w1(B); r2(B); w2(B);} \]

串行化操作：

\[\begin{split} \text{r1(A); w1(A); r2(A);} \mathbf{r1(B); w2(A);} \text{w1(B); r2(B); w2(B);}\\ \text{r1(A); w1(A);} \mathbf{r1(B); r2(A);} \text{w2(A); w1(B); r2(B); w2(B);}\\ \text{r1(A); w1(A); r1(B); r2(A);} \mathbf{w1(B); w2(A);} \text{r2(B); w2(B);}\\ \text{r1(A); w1(A); r1(B);} \mathbf{w1(B); r2(A);} \text{w2(A); r2(B); w2(B);} \end{split}\]

最后，调度变成了先执行事务 1、再执行事务 2。

冲突可串行性判别算法：

构造一个有向图
结点是每一个事务 Ti，如果 Ti 的一个操作与 Tj 的一个操作发生冲突，且 Ti 在 Tj 前执行，则绘制一条边，由 Ti 指向 Tj
检查有向图，若没有环，则冲突是可串行化的

封锁协议之锁的类型：

排他锁 X：只能有一个事务读、写，其他事务不能读、写。
共享锁 S：所有事务都可以读，但任何事务都不能写。
更新锁 U：初始读，以后可以升级为写。
增量锁 I：用于增量更新（例如 A = A + x），以区分增量更新和其他类型的更新。

有了以上几把锁，我们可以选择合适的时机加锁和解锁，因此出现了以下几个等级的封锁协议：

有了这几个等级的协议之后，程序员可以自主选择 SQL 的隔离级别（应该可以配置）：

读未提交，相当于 0 级封锁协议：对有写要求的数据对象 A 加排他锁，不再访问后即刻解锁。
读已提交，相当于 1 级封锁协议：对有写要求的数据对象 A 加排他锁，事务提交时刻解锁。
可重复读，相当于 2 级封锁协议：对有写要求的数据对象 A 加排他锁，事务提交时刻解锁。有读要求的数据对象 B 加共享锁，不再访问后即刻解锁。
可串行化，相当于 3 级封锁协议：对有写要求的数据对象 A 加排他锁，事务提交时刻解锁。有读要求的数据对象 B 加共享锁，事务提交时刻解锁。

隔离级别越高，数据的安全性越高，但是数据库的效率越低，如何取舍要根据业务来定：

隔离级别	脏读	不可重复读	幻读
读未提交	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
读已提交	\(\times\)	\(\checkmark\)	\(\checkmark\)
可重复读	\(\times\)	\(\times\)	\(\checkmark\)
可串行化	\(\times\)	\(\times\)	\(\times\)

注：每个等级的协议都可防止丢失修改。

两阶段锁中的“两阶段”是指加锁阶段和解锁阶段：加锁阶段不能有解锁操作，解锁阶段不能有加锁操作。读写数据之前要先获得锁，每个事务中所有的加锁请求都先于任何解锁请求。

两阶段锁协议是可以保证冲突可串行化的，但是可能产生死锁。

数据库转储#

如果已经在 Windows 上安装了 MySQL 数据库，在安装路径（如 D:\Program Files\mysql-5.7.37-winx64）的 data 文件夹下：

如果使用 MyISAM 引擎，可以找到 .frm（表结构）、.MYD（数据文件）、.MYI（索引文件）文件。
如果使用 InnoDB 引擎，可以找到 .frm 文件和 ibdata1 表空间文件。

因此，一种转储方式就是直接复制这些文件，另一种方式是使用 mysqldump 命令。