# 数据库系统原理 (db_principles)= ## 基本介绍 平常我们经常提及的数据库指的是存储数据的仓库，其物理体现就是一个个的文件，实质是一个个的表（DB tables）。 这些表的维护由一个叫做数据库管理系统（DBMS）来完成，它保证了数据库的安全性和完整性，并为我们提供了 CRUD 接口。 底层由 DBMS 支持，借助 DBMS 提供的事务管理和 CRUD 接口，上层应用的具体业务实现则需要我们编写 SQL 语句手工实现。 {numref}`db-overview` 展示了数据库软件的交互过程。 ```{figure} ../_static/images/db_overview.* :name: db-overview 数据库软件交互过程 ``` 按照数据库类型进行分类，我们可以将其分为关系型和非关系型两大类： 关系数据库是一种用于存储相互关联的数据点并提供数据点访问的数据库。 它采用关系模型，直接、直观地在表中展示数据。 在关系数据库中，表中的每一行都代表一条记录，每条记录都具有一个唯一的ID（又被称为键），而表中的列则用于存储数据的属性。 每条记录的每一个属性通常都有一个值。籍此，用户可以轻松在数据点之间建立关联 [^cite_ref-1]。 NoSQL 数据库（意即"不仅仅是SQL"）并非表格格式，其存储数据的方式与关系表不同。 NoSQL 数据库的类型因数据模型而异。 主要类型包括文档、键值、宽列和图形。 它们提供了灵活的模式，可以随大量数据和高用户负载而轻松扩展 [^cite_ref-2]。 如果对非关系型数据库进行细分，按照存储的数据的格式来看，又可以分为面向对象数据库和 XML 数据库。 关系型数据库的代表有：MySQL、Oracle、SQL Server、SQL Lite。 非关系型数据库的代表有：Redis、MongoDB、对象存储。 ## 专业术语扫盲 ```{list-table} :header-rows: 1 :name: 数据库常见术语 :widths: 30, 70 * - 名词 - 备注 * - 列 / 字段 / 属性 / 数据项 - 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$ 以内 * - 三级模式 [^cite_ref-8] - 外模式 / 局部模式 / 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 语言 [^cite_ref-4] - 数据库定义语言（DDL，Data Defination 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，Tranction Control Language）设置保存点、回滚等。`SAVEPOINT`、`ROLLBACK`、`SET TRANSACTION`。 * - 数据模型 - 层次模型（一种用树形结构描述实体及其之间关系的数据模型） 网状模型（允许一个结点可以同时拥有多个双亲结点和子结点） 关系模型（采用二维表格结构表达实体类型及实体间联系的数据模型） ``` ## 关系代数 一个完备的数据库语言，应当同时具备三种运算能力：关系代数、关系演算（包括元组演算和域演算）。 - 关系代数：以集合为对象进行操作，由集合到集合的变换。 - 元组演算：以元组为对象进行操作，取出表中的每一个元组进行验证（有多个元组变量需要多个循环）。 - 域演算：以域变量为对象进行操作，取出域的每一个变量进行验证看其是否满足条件。 对比这三种运算，域演算的非过程性最好，元组演算次之，关系代数最差。 从安全性上考虑，关系代数是一种安全的集合运算，而关系演算不一定是安全的。 ```{list-table} :header-rows: 1 :name: 关系代数之元组操作 :widths: 20, 80 * - 操作名称 - 操作语句 * - 并 - $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 基本语句 ```{code-block} mysql -- 创建数据库 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 基本语句 ```{code-block} text -- 单一元组新增（列名可省略不写） 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 供应的 _全部_ 零件的工程号 [^cite_ref-5]。 要想回答这个问题，如果我们直接用正常的思路，将很难理解解题过程。 根据语义的转化，我们可以描述为：在 S1 生产的 _全部零件_ 中，**不存在有一个** 零件它 **不** 使用。 因为这个语义中，含有两个否定，因此，需要两个 `not exist` 来完成从自然语言到 SQL 语言的转化。 ```{code-block} mysql 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 中定义的都是非过程性约束）。 触发器是一段程序，该程序可以在特定的时刻被自动触发执行，比如一次更新操作之前或之后。 ```{code-block} mysql create trigger `触发器名` before -- 也可以是 after update of `列名` -- 也可以是 insert delete on `表名` referencing 程序段中的变量声明 for each row -- 对更新操作的每一条结果检查约束，也可以对整个更新操作检查 when (检查条件) -- 检查条件如果满足，就执行下面的程序 -- 单行程序直接写在这里 -- 多行程序要用下面的方式 begin atomic -- 程序段代码语句 1; -- 程序段代码语句 2; end ``` 在安全控制方面，我们可以通过在数据字典或系统目录中保存存取规则，限制用户对 DB 的访问权利。 当用户量大时，可以按用户组建立访问规则。 - 访问的粒度：字段、元组、关系、数据库。 - 访问的权利：增、删、查、改。 - 访问的谓词：拥有权利需要满足的条件。 视图是安全控制的重要手段，如下所示。 ```{code-block} mysql create EmpView1 as select * from Employee -- 通过视图，限制用户对关系中某些数据项的存取 create EmpView2 as select * from Employee where P#=:UserId -- 视图与谓词结合，限制访问 ``` 从安全控制的角度来看，我们通常把用户分成三种类型：普通用户、程序员用户、DBA。 - 普通用户：具备 `select` 数据库、表、元组、字段的能力。 - 程序员用户：具备 `insert`、`update`、`delete` 元组的能力。 - DBA：具备 `create`、`alter`、`drop` 表空间、模式、表、索引、视图的能力。 ```{code-block} mysql -- 授权命令 grant all privileges -- 或者是 select insert update delete on `表名` -- 或者是 视图名 to `用户账户ID1`, `ID2`; -- 或者是 public with grant option -- 默认是不应该授予普通用户 grant 权限的 -- 收回授权 revoke all privileges on `表名` from `用户账户ID1`, `ID2`; ``` ## 数据库设计 数据库设计是指根据数据库模型确定数据的组织方式 [^cite_ref-3]。{numref}`db-design` 展示了数据库设计的详细步骤： ```{figure} ../_static/images/db_design.* :name: db-design 数据库设计流程 [^cite_ref-7] ``` 一个设计良好的数据库，应该尽可能消除数据冗余，但是又不是完全严格地按照三大范式来约束。 因为在规范和性能之间，总会需要有一个取舍，如果数据严格满足规范，那么必然需要一些联表查询，进而导致性能下降。 因此，在数据库设计时，允许有一定的数据冗余，以保证性能。 另外一点，设计良好的数据库应当尽可能避免使用物理外键，也就是说，尽量不要在数据表中使用外键字段。 因为这会导致在后续业务中给维护表结构带来额外的负担。比如，有了外键后，删除和更新数据都会变得很麻烦。 不同类型的数据应当放在不同的数据库中，比如结构化数据放在 MySQL 中，视频流放在 MongoDB 中，评论放在 Redis 中。 数据库设计中需要用到的数据类型： ```{code-block} text 数值：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 个字段。 ```{code-block} text id version is_delete gmt_create gmt_update 主键 乐观锁 伪删除 创建时间 修改时间 ``` ## 函数依赖定理 在关系数据库理论中，函数依赖（FD）是数据库的关系的两个属性集合之间的一种约束。 在数据库设计的过程中，我们设计的关系模式可能存在如下问题： - 数据冗余：某个字段的属性值多次被重复存储 - 不一致性：由于数据存储冗余，当更新某些数据项时，就有可能一部分字段修改了，而另一部分没有修改 - 插入异常：对于非空字段，没有合适的值，导致与其关联的其他字段也无法成功插入 - 删除异常：涉及到级联删除时，由于表之间的耦合太强，无法成功删除 这是因为关系中的某些属性之间存在数据依赖。 现在人们已经提出了许多类型的数据依赖，其中最重要的是函数依赖和多值依赖。 我们的目标就是消除关系模式中的函数依赖。在本节，我们将介绍几个函数依赖定义： ```{list-table} :header-rows: 1 :name: 函数依赖定理 :widths: 20, 80 - * 名词 * 注解 - * 函数依赖 * 设有关系模式 $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^+$。 ``` 现在对这几个概念有了一个大概的认识，那么我们在实际工程应用中，应当 **熟练应用这些概念来判断某个关系模式存在哪些函数依赖关系**，具体来讲，你需要做一些练习题 [^cite_ref-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$ 具有保持依赖性。 当然，无损连接和保持依赖这两个概念理解起来还是比较抽象，做个习题，会更好理解一些 [^cite_ref-7]。 :::{card} 例 1：设有关系模式 $R$，其中： $$ U = \{ A, C, D \}, F = \{ A \rightarrow B, C \rightarrow B \} $$ 判断一个分解 $\rho = \{ AC, BC \}$ 是否具有无损连接性。 解： $\rho$ 的无损连接性判断结果如下表所示，由此判断它具有无损连接性。 ```{list-table} :header-rows: 1 :name: 无损连接性判断表 - * * A * B * C - * **AC** * a1 * a2 * a3 - * **BC** * b21 * a2 * a3 ``` 如果你不能理解上表，应该阅读本文末尾的参考文献 [^cite_ref-7]。 ::: :::{card} 例 2：设有关系模式 $R(ABCD)$，$R$ 上的 FD 集为 [^cite_ref-10]： $$ 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}$ 不保持依赖。 ::: 理解了无损连接和保持依赖的求解方法，那么它们有什么指导意义呢？ ```{list-table} :header-rows: 1 :name: 无损连接和保持依赖的意义 :widths: 25, 25, 50 - * 无损连接 * 保持依赖 * 说明 - * $\checkmark$ * $\checkmark$ * 最好（不丢失数据和依赖） - * $\checkmark$ * $\times$ * 可接受（丢失依赖，会导致异常） - * $\times$ * $\checkmark$ * 不能接受（丢失数据） - * $\times$ * $\times$ * 不能接受（丢失数据） ``` ::: ## 物理存储 关于数据库的物理存储，我们希望合理地组织数据，来实现高效地存取。机械硬盘的物理结构如下： ```{figure} ../_static/images/db_disk_model.png 磁盘的物理结构（台湾叫法与大陆略有不同） [^cite_ref-6] ``` 在上面这张图上，有一组概念，我们需要弄清楚： ```{list-table} :header-rows: 1 :name: 磁盘常见术语 :widths: 30, 70 - * 名词 * 注解 - * 扇区（sector，磁区） * 可以从磁盘读取或写入的最小信息单位 - * 磁盘块（block） * 若干连续扇区，大小固定，通常是 512 字节，读取到内存的最小单位 - * 磁道（track，磁轨） * 以轴线为中心的圆环，不同的半径即代表不同的磁道 - * 盘面（platter，磁盘） * 在同一水平面上，所有的磁道构成一个盘面 - * 柱面（cylinder，磁柱） * 在竖直面上，所有具有相同半径的磁道构成一个柱面 - * 读写头（read-write head） * 以磁性方式将信息存储在扇区上 ``` 我们知道，Windows 操作系统支持 NTFS、FAT32、exFAT 三种不同{ref}`windows_file_system`。 文件系统是系统对文件的存放排列方式，不同格式的文件系统关系到数据如何在磁盘进行存储。 那么，MySQL 组织文件的方式与操作系统有何不同？ 操作系统则是以文件的方式（FAT）组织数据和存取数据，MySQL 以磁盘块为单位来组织数据和存取数据。 通常来讲，一个磁盘块的大小等于一个内存页的大小，这对于将磁盘块加载到内存中效率较高。 因此，如果我们想要在一个块中找到某条记录，方式就是页面的 `基地址:偏移地址`。 存取时间是物理存储性能的评价指标，以块为单位读取数据，那么总的时间计算方式就是： $$ \text{总的存取时间 = 寻道时间 + 旋转时间 + 传输时间} $$ 明确了优化目标 —— 时间、可靠性、可用性，现在常用的是 RAID 技术。 RAID 全称独立磁盘冗余阵列，由许多价格便宜的磁盘组成一个容量巨大的磁盘组，提升存储性能、或提高数据安全的技术。 这个技术，一方面可以提高存取时间，另一方面，也提高了数据库的可靠性。 RAID 又分为了好多种，我们只介绍几种常用的，其他类型需要参考文末的参考文献 [^cite_ref-9]： 1、RAID 0 （又称为 Stripe 或 Striping —— 分条） ```{figure} ../_static/images/db_raid_0.* :height: 200px ``` RAID 0 的缺点是不提供数据冗余，因此一旦用户数据损坏，损坏的数据将无法得到恢复。 2、RAID 1 （又称为 Mirror 或 Mirroring —— 镜像） ```{figure} ../_static/images/db_raid_1.* :height: 200px ``` 最高的数据安全保障，但是，磁盘利用率为 50%，故成本最高。 3、RAID 5 （RAID 0 和 RAID 5 的折中方案） ```{figure} ../_static/images/db_raid_5.* :height: 200px ``` 没有完全使用 RAID 1 镜像理念，而是使用了 "奇偶校验信息" 来作为数据恢复的方式，但与下面的 RAID 10 不同。 4、RAID 10（RAID 0 和 RAID 1 的折衷方案） :::{card} ```{figure} ../_static/images/db_raid_10.* :height: 200px ``` ::: :::{card} ```{figure} ../_static/images/db_raid_01.* :height: 200px ``` ::: RAID 10 也被称为镜象阵列条带。RAID 10 提供最好的性能、更好的可靠性。 按照数据的类型来说，有三类，记录、表、文件，那么数据库的组织方式可以有： 对于一条记录，可选的存储方式有： - 定长记录，还是变长记录（靠分隔符区分开始与结束） - 记录是非跨块存储，还是跨块存储（靠指针连接） 对于一张表，可选的存储方式是： - 连续分配：数据块被分配到连续的磁盘块上（会存在扩展困难的现象） - 连接分配：数据块中包含指向下一数据块的指针（访问速度问题） - 按簇分配：簇是若干连续的磁盘块，簇之间靠指针连接（簇有时候也称片段Segment或盘区extent） - 索引分配：索引块中存放指向实际数据块的指针 对于一个文件，可选的组织方式： - 堆文件（Heap 或 Pile file）无序，检索效率差，且删除文件后，需要重新组织数据库 - 排序文件（Sequential）有序，更新效率差，且溢出文件后，需要重新组织数据库 - 散列文件（Hash file）散列到桶中，桶内按照顺序检索，难点在于如何让每个桶尽量均匀 - 聚簇文件（Clustering file）将具有相似或相同属性值的记录存放在连续的磁盘簇块中 根据文件的组织方式，我们可以知道，能够对文件建立 B+ 树索引或散列索引。 综上，没有一个十分完美的方案，经常是在鱼和熊掌之间做取舍，因此，符合业务场景的就是合适的。 ## 查询的实现 讲到查询的实现，不可避免的要涉及到索引的概念，比如 InnoDB 的默认索引就是 B+ 树。 索引是定义在存储表基础上，无需检查所有记录，快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项组成。 合理地对某些字段建立索引，能提高效率，那么我们对哪些字段建立索引呢？ 答案是对经常出现在检索条件、连接条件、分组计算条件中的属性。 MySQL 支持建立的索引类型有四种： 1. 主键索引 `primary key` 只能有一个列作为主键，不可重复 2. 唯一索引 `unique key` 可以有多个列声明为唯一索引，可以重复 3. 常规索引 `key` / `index` 可以由多个常规索引 4. 全文索引 `fulltext index` 并不是所有的引擎都支持全文索引，比如 MyISM 为了能够对后面的概念有一个清晰的认识，我们将常用概念在这里列举出来，以备后续翻阅。 ```{list-table} :header-rows: 1 :name: 数据库索引概念一览表 :widths: 15, 85 * - 概念 - 注解 * - 索引文件 - 存储索引项的文件 * - 主文件 - 存储表的文件 * - 稠密索引 - 对主文件中的每个记录，都有一个索引项和它对应，指明该记录所在的位置 * - 稀疏索引 - 对主文件中的部分记录，有索引项和它对应 * - 主索引 - 每个存储块对应一个索引项。由于可能多个记录存储在同一个块上，因此主索引是稀疏索引。 主索引通常建立在主码/排序码上，因此可以用主索引重新组织主文件数据 * - 辅助索引 - 定义在主文件的任一或多个非排序字段上的辅助存储结构，辅助索引是稠密索引，因此检索效率相当高 * - 聚簇索引 - 索引中邻近的记录在主文件中也是邻近存储的，这一点很像主索引。 它们的区别在于，聚簇索引的聚簇字段不必是主键的排序字段，而主索引的必须建立在主键上。 因此，主索引通常是聚簇索引，辅助索引通常是非聚簇索引 * - 非聚簇索引 - 索引中邻近的记录在主文件中不一定是邻近存储的 * - 倒排索引 - 正排：`#doc1, {word1, word2}`，倒排：`word1, {#doc1, #doc2}` * - 多级索引 - 当索引项比较多时，可以对索引再建立索引，依此类推，形成多级索引，常见形式为 B 树、B+ 树 ``` 通常，每个索引块由两部分组成： - 索引字段：由 `table` 中某些列（通常是 1 列）中的值串接而成。 - 行指针：指向 `table` 中包含索引字段值的记录的记录在磁盘上的存储位置。 下面具体描述一下 B+ 树的数据结构，在本节末尾补充一下 B 树的介绍。 B+ 树索引：一种以树形结构来组织索引项的多级索引。对于一个 B+ 树结点，它的数据结构如下所示： ```{figure} ../_static/images/db_btree.* ``` 在 B+ 树的基本数据结构中，一个索引项指的是一个 `(Ki, Pi)` 对。 `Ki` 是索引字段值，`Pi` 是指针，指向索引块或数据块或数据块中记录的指针。 最后一个 `Pn` 指向下一个 B+ 树结点。 以 `n = 3` 为例，B+ 树的非叶结点和叶结点的数据结构如下所示： ```{figure} ../_static/images/db_b_plus_tree_node.* ``` 我们把一个叶结点和非叶结点完整地串起来，那么它们看起来会像下图所示（`n = 3`）： ```{figure} ../_static/images/db_btree_demo.* ``` 每个索引块实际使用的索引指针的个数 $d$ 满足下式（根结点除外）： $$ n/2 \leq d \leq n $$ 因此，每个索引块的指针利用率都在 50% 到 100% 之间。 B 树的数据结构和 B+ 树略有不同，具体表现如下： ```{figure} ../_static/images/db_btree_node.* ``` 以上是数据库的存储结构的介绍，那么在具体的实现中，我们是如何进行操作的呢？ 举例来说，需要分成两个步骤，将主文件记录所在的磁盘块加载到磁盘上，然后采用循环的方式对比结果。 大体的伪代码如下所示： ```{code-block} text for i in 磁盘块 将第 i 块磁盘加载到内存区 mem1 中 for j in 磁盘块 将第 j 个磁盘块加载到内存 mem2 中 for p in 内存区 mem1 读取第 p 条记录 for q in 内存区 mem2 读取第 q 条记录 对比 p 和 q 的属性值，是否满足条件 存入结果集 ``` 当然，这是一个很朴素的想法，有很大的优化空间，因此想要在这里讲明白也不是一件容易事，后面有机会再补充。 ## 查询的优化 所谓的查询优化，指的是 "如何使数据库查询的执行时间最短"。有三条启发式的优化原则供参考： - 尽可能早地做选择 - 尽可能早地做投影 - 尽可能早地做选择和投影的合并 为了能够更好地理解查询优化的具体实现手段，我建议做一些练习巩固一下 [^cite_ref-7]。 ## 事务处理 我们书写的每一条（一组） SQL 语句都可以看作是一个事务。 多个看似并行的事务，实际上是交叉执行的（并发），那么如何保证数据的一致性，是本节需要讨论的话题。 为什么需要事务？在一个能够提供服务的程序中，可能会由于 CPU 调度，执行到一半被抢占了 CPU，或由于断电、系统崩溃了。各种看似常规的操作，都可能造成数据不一致，因此，事务是必须的。 按照解决数据不一致性的方法来看，主要有两种： - 基于封锁的方法（两段封锁算法） - 基于时间戳的方法，时间戳小的事务先执行 为了更加方便地展开描述上面的三种方法，我们先了解一下什么是事务调度。 事务调度是指一组事务的基本步（读、写、其他控制操作如加锁、解锁等）的一种执行顺序。 表达事务调度的一种模型可以定义为： $$ \text{rT(A) ：事务 T 读 A}\\ \text{wT(A) ：事务 T 写 A} $$ 冲突是指，调度中的一对连续的动作，它们满足：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变。 因此，有冲突的两个操作时不能交换次序的，而没有冲突的两个事务可以交换次序。 冲突可串行性则是指，一个调度，如果通过交换相邻两个无冲突的操作能够转换到某个串行的调度，则称此调度为冲突可串行化的调度。 例：一开始，事务 1 和 2 交替执行： $$ \text{r1(A); w1(A); r2(A); w2(A); r1(B); w1(B); r2(B); w2(B);} $$ 串行化操作： $$ \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);} $$ 最后，变成了先执行事务 1 再执行事务 2。 冲突可串行性判别算法： - 构造一个有向图 - 结点是每一个事务 `Ti`，如果 `Ti` 的一个操作与 `Tj` 的一个操作发生冲突，且 `Ti` 在 `Tj` 前执行，则绘制一条边，由 `Ti` 指向 `Tj` - 检查有向图，若没有环，则冲突是可串行化的 ```{figure} ../_static/images/db_serialize_schedule.* ``` 封锁协议之锁的类型： - 排他锁 `X`，只能有一个事务读、写，其他事务不能读、写 - 共享锁 `S`，所有事务都可以读，但是任何事务都不能写 - 更新锁 `U`，初始读，以后可以升级为写 - 增量锁 `I`，增量更新（例如 `A = A + x`）区分增量更新和其他类型的更新 有了以上的几把锁，我们可以选择一个合适的加锁和解锁时机，因此出现了以下几个等级的协议： ```{figure} ../_static/images/db_lock_grade.* ``` 而在有了这几个等级的协议之后，程序员可以自主选择 SQL 的隔离级别（应该可以配置）： - 读未提交，相当于 0 级封锁协议：有写要求的数据对象 A 加排他锁，不再访问后即刻解锁。 - 读已提交，相当于 1 级封锁协议：有写要求的数据对象 A 加排他锁，事务提交时刻解锁。 - 可重复读，相当于 2 级封锁协议：有写要求的数据对象 A 加排他锁，事务提交时刻解锁。 有读要求的数据对象 B 加共享锁，不再访问后即刻解锁。 - 可串行化，相当于 3 级封锁协议：有写要求的数据对象 A 加排他锁，事务提交时刻解锁。 有读要求的数据对象 B 加共享锁，事务提交时刻解锁。 隔离级别越高，数据的安全性越高，但是数据库的效率越低，如何取舍要根据业务来定： ```{list-table} :header-rows: 1 :name: 数据库的隔离级别 * - - 脏读 - 不可重复读 - 幻读 * - 读未提交 - $\checkmark$ - $\checkmark$ - $\checkmark$ * - 读已提交 - $\times$ - $\checkmark$ - $\checkmark$ * - 可重复读 - $\times$ - $\times$ - $\checkmark$ * - 可串行化 - $\times$ - $\times$ - $\times$ ``` 注：每个等级的协议都可防止丢失修改。 两阶段锁中的两阶段是指加锁阶段和解锁阶段，具体指的是加锁阶段不能有解锁操作，解锁阶段不能有加锁操作。 读写数据之前要先获得锁，每个事务中所有的加锁请求都先于解锁任何一个解锁请求。 两阶段锁协议是可以保证冲突可串行行的，但是可能产生死锁。 ## 数据库转储 如果已经在 Windows 上安装了 MySQL 数据库，在安装路径 `D:\Program Files\mysql-5.7.37-winx64` 的 `data` 文件夹下： - 如果使用 MyISM 引擎，可以找见 `.frm`（表结构）`.MYD`（数据文件）`.MYI`（索引文件）文件。 - 如果使用 InnoDB 引擎，可以找见 `.frm` 和 `ibdata` 文件夹。 因此，其中一种转储方式就是直接复制这些文件，而另一种方式就是使用 `mysqldump` 命令。 ```{toctree} :titlesonly: :glob: :hidden: dbs/* ``` --- [^cite_ref-1]: 关系数据库是什么 | Oracle 中国 [^cite_ref-2]: NoSQL 是什么 - MongoDB [^cite_ref-3]: Database design basics. (n.d.). Database design basics. Retrieved May 1, 2010, from [^cite_ref-4]: SQL 四种语言 [^cite_ref-5]: 王珊, 张俊. 数据库系统概论 (第5版) 习题解析与实验指导[M]. 高等教育出版社, 2015. [^cite_ref-6]: 国立联合大学, 磁盘管理, 幻灯片 [^cite_ref-7]: 数据库系统原理习题与解析 [^cite_ref-8]: 如何理解数据库的三级模式 [^cite_ref-9]: 维基百科, 独立硬盘冗余阵列 [^cite_ref-10]: 保持函数依赖的分解