数据库面试相关
数据库面试相关。
事务
概念
事务指的是满足 ACID 特性的一组操作，可以通过 commit 提交一个事物，也可以使用 rollback 进行回滚。
ACID 是指：
Atomicity（原子性）
事务被视为不可分割的最小单元，事务内的所有操作要么全部提交成功，要么失败，就要全部回滚。
回滚通过回滚日志来实现，回滚日志记录着事务所执行的修改操作，在回滚时反向执行这些修改操作即可。
Consistency（一致性）
数据库在事务执行前后都保持一致性状态。在一致性状态下，所有事务对同一个数据的读取结果都是相同的。
Isolation（隔离性）
一个事务所做的修改在最终提交以前，对其他事务是不可见的。
Durability（持久性）
一旦事务提交，则其所做的修改将会永远保存到数据库中。即使系统发生崩溃，事务执行的结果也不能丢失。
使用重做日志来保证持久性。
对 ACID 补充的理解：
- 只有满足一致性，事务的执行结果才是正确的。
- 在无并发的情况下，事务串行执行，隔离性一定能够满足。此时只要能满足原子性，就一定能满足一致性。
- 在并发的情况下，多个事务并行执行，事务不仅要满足原子性，还需要满足隔离性，才能满足一致性。
- 事务满足持久化是为了应对数据库崩溃的情况。
补充：MySQL 默认采用自动提交模式。也就是说，如果不显式使用
START TRANSACTION语句来开始一个事务，那么每个查询都会被当作一个事务自动提交。
并发一致性问题
在并发环境下，事物的隔离性很难保证，因此会出现很多并发一致性的问题。
并发一致性的问题就是指在没有锁的情况下做的假设，按理说，数据库需要保证操作的原子性和隔离性，就要保证一个事物对相关数据进行更新操作的时候，别的事务不能访问这些数据。加锁就是为了提供这个保证，以下情况就是在无锁情况下发生的。
产生并发一致性的问题的主要原因就是破坏了事务的隔离性，解决办法是通过并发控制来保证隔离性。并发控制可以通过封锁来实现，但是封锁操作需要用户自己控制，相当复杂。数据库管理系统提供了事务的隔离级别，让用户以一种更轻松的方式处理并发一致性问题。
丢失修改
$T_1$ 和 $T_2$ 两个事务同时开始执行，加入有一个值 var，其值为 5。$T_1$ 读取了它的值，读到了5，$T_2$ 也读取了这个值，读到了5，然后 $T_1$ 对这个值加 1，之后在数据库中把这个值改为了 6。$T_2$ 对这个值加2，之后在数据库中把这个值改为 7。按理说，两个事务，一个对其加 1，一个对其加 2，按理说合在一起应该加 3，但是最后只加了 2，$T_1$ 对这个数据的修改相当于“丢失”了，所以叫“丢失修改”。
读脏数据
$T_1$ 修改了某个值，然后把这个值写入了硬盘，这个时候 $T_2$ 读取到了这个值，然后 $T_1$ 因为某种原因撤销了这个操作，但是 $T_2$ 并不能得知这个数据其实已经变了，我们就把 $T_2$ 读到的这个数据称为“脏数据”。
不可重复读
假如 $T_1$ 要修改某个数据，而 $T_2$ 这个事务中包含两次读取的操作，那么，如果 $T_1$ 和 $T_2$ 同时读取了数据的值，然后 $T_1$ 对数据进行了修改，那么 $T_2$ 在第二次读取数据的值的时候，这个值和第一次读取时候的值是不一样的。这就叫不可重复读。通俗的理解就是在同一个事务中，在当前事务并没有修改这个数据的情况下，两次读取到的值不一样。
幻读
$T_1$ 第一次操作读取了满足某个条件的一个范围内的数据，$T_2$ 插入了新的满足这个条件的数据，$T_1$ 第二次操作再次根据这个条件去读取某个范围内的数据，此时读取的结果和第一次读取的范围的大小不同，第二次读取出的范围更大一些。
封锁
封锁粒度
MySQL 中提供了两种封锁粒度：行级锁和表级锁。
应该只锁定需要修改的那一部分数据，而不是所有的数据。锁定的数据量越少，发生锁争用的可能性就越小，系统的并发程度就越高。
但是加锁需要消耗资源，锁的各种操作（包括获取锁、释放锁、以及检查锁状态）都会增加系统开销。因此封锁粒度越小，系统开销就越大。
在选择封锁粒度时，需要在锁开销和并发程度之间做一个权衡。
封锁类型
读写锁
- 排他锁（Exclusive），简写为 X 锁，又称写锁。
- 共享锁（Shared），简写为 S 锁，又称读锁。
有以下两个规定：
- 一个事务对数据对象 A 加了 X 锁，就可以对 A 进行读取和更新。加锁期间其他事务不能对 A 加任何锁。
- 一个事务对数据对象 A 加了 S 锁，可以对 A 进行读取操作，但是不能进行更新操作，加锁期间其他事务能对 A 加 S 锁，但是不能加 X 锁。
意向锁
使用意向锁（Intention Locks）可以更容易地支持多粒度封锁。
在存在行级锁和表级锁的情况下，事务 T 想要对表 A 加 X 锁，就需要先检测是否有其他事务对 A 或者表 A 中的任意一行加了锁，那么就需要对表 A 的每一行都检测一次，这是非常耗时的。
意向锁在原来的 X/S 锁之上引入了 IX/IS，IX/IS 都是表锁，用来表示一个事务想要在表中的某个数据行上加 X 锁或 S 锁。有以下两个规定：
- 一个事务在获得某个数据行对象的 S 锁之前，必须先获得表的 IS 锁或者更强的锁；
- 一个事物在获得某个数据行对象的 X 锁之前，必须先获得表的 IX 锁。
通过引入意向锁，事务 T 想要对表 A 加 X 锁，只需要先检测是否有其他事务对 A 加了 X/IX/S/IS 锁，如果加了就表示有其他事务正在使用这个表或者表中某一行的锁，因此事务 T 加 X 锁失败。
封锁协议
三级封锁协议
一级封锁协议
事务 T 要修改数据 A 时必须加 X 锁，直到 T 结束才释放锁。
可以解决丢失修改问题，因为不能同时有两个事务对同一个数据进行修改，那么事务的修改就不会被覆盖。
如图所示：
| T1 | T2 |
|---|---|
| lock-x(A) | |
| read A=20 | |
| lock-x(A) | |
| wait | |
| write A=19 | . |
| commit | . |
| unlock-x(A) | . |
| obtain | |
| read A=19 | |
| write A=21 | |
| commit | |
| unlock-x(A) |
$T_1$ 在对数据 A 进行修改的时候，加上了锁，这个时候 $T_2$ 是不能读取这个数据的，必须等到 $T_1$ 提交了事务之后，$T_2$ 才能读取到数据，所以 $T_1$ 的修改不会丢失。故可以防止丢失修改问题。
二级封锁协议
在一级的基础上，要求读取数据 A 时必须加 S 锁，读取完马上释放 S 锁。
可以解决读脏数据问题，因为如果一个事务在对数据 A 进行修改，根据一级封锁协议，会加 X 锁，那么就不能
二级封锁协议除了有一级封锁协议提供的防止丢失修改作用之外，还可以防止读脏数据。因为如果一个事务正在对某个数据进行修改，说明已经加上了 X 锁，而另外一个事务如果想读，必须要加 S 锁，但是在已经有 X 锁的情况下是无法加 S 锁的，所以读脏数据的条件就不成立了。
三级封锁协议
在二级的基础上，要求读取数据 A 时必须加上 S 锁，直到事务结束了才能释放 S 锁。
除了可以解决丢失修改和读脏数据，还可以解决不可重复读问题。
也就说说，如果一个事务中需要两次读取某个数据，而两次读取之间可能进行别的操作，那么就不要在第一次读取之后就释放锁，而是等到两次都读取完、整个事务执行完成之后再释放锁。
两段锁协议
加锁和解锁分为两个阶段进行。
可串行化调度是指，通过并发控制，使得并发执行的事务结果与某个串行执行的事务结果相同。
TODO 需要例子来增进理解。
MySQL 隐式与显式锁定
MySQL 的 InnoDB 存储引擎采用两段锁协议，会根据隔离级别在需要的时候自动加锁，并且所有的锁都是在同一时刻释放，这被称为隐式锁定。
隔离级别
未提交读（READ UNCOMMITED）
事务中的修改，即使没有提交，对其他事务也是可见的。
提交读（READ COMMITED）
一个事务只能读取已经提交的事务所做的修改。换句话说，一个事务所做的修改在提交之前对其他事务是不可见的。
可重复读（REPEATABLE READ）
保证在同一个事务中多次读取同样的数据的值是一样的。
可重复读隔离级别可以解决不可重复读的问题，但是按理来说，可重复读是不能解决幻读问题的，因为虽然可以对某个范围内的数据加锁，但是别的事务插入新的数据是不受限制的，那么如果别人插入了新的数据，那么两次读取出来的数据规模就不一样了。
但是，现在主流数据库都使用 MVCC（Multiversion concurrency control，多版本并发控制） ，使用之后RR（可重复读）隔离级别下是不会出现幻读的现象。
MVCC 的简单理解：
为了实现可串行化，同时避免锁机制存在的各种问题，我们可以采用基于多版本并发控制（Multiversion concurrency control，MVCC）思想的无锁事务机制。人们一般把基于锁的并发控制机制称成为悲观机制，而把MVCC机制称为乐观机制。这是因为锁机制是一种预防性的，读会阻塞写，写也会阻塞读，当锁定粒度较大，时间较长时并发性能就不会太好；而MVCC是一种后验性的，读不阻塞写，写也不阻塞读，等到提交的时候才检验是否有冲突，由于没有锁，所以读写不会相互阻塞，从而大大提升了并发性能。我们可以借用源代码版本控制来理解MVCC，每个人都可以自由地阅读和修改本地的代码，相互之间不会阻塞，只在提交的时候版本控制器会检查冲突，并提示merge。目前，Oracle、PostgreSQL和MySQL都已支持基于MVCC的并发机制，但具体实现各有不同。
可串行化（SERIALIZABLE）
强制事务串行执行。
以下表格表示在不同的隔离级别下是否会发生并发一致性问题：
| 隔离级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| 未提交读 | 会 | 会 | 会 |
| 提交读 | 不会 | 会 | 会 |
| 可重复读 | 不会 | 不会 | 会 |
| 可串行化 | 不会 | 不会 | 不会 |
多版本并发控制
多版本并发控制（Multi-Version Concurrency Control，MVCC）是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式，用于实现提交读和可重复读这两种隔离级别。而未提交读隔离级别总是读取最新的数据行，无需使用 MVCC。可串行化隔离界别需要对所有读取的行都加锁，单纯使用 MVCC 无法实现。
版本号
系统版本号：是一个递增的数字，每开始一个新的事务，系统版本号就会自动递增。
事务版本号：事务开始时的系统版本号。
隐藏的列
MVCC 在每行记录后面都保存两个隐藏的列，用来存储两个版本号：
- 创建版本号：指示创建一个数据行的快照时的系统版本号；
- 删除版本号：如果该快照的删除版本号大于当前事务版本号表示该快照有效，否则表示该快照已经被删除了。
Undo 日志
MVCC 使用到的快照存储在 Undo 日志中，该日志通过回滚指针把一个数据行（Record）的所有快照连接起来。
实现过程
TODO 待填坑。
关系数据库设计理论
函数依赖
记 A -> B 表示函数 A 决定 B，也可以说 B 函数依赖于 A。
如果 {$A_1,A_2,\cdots,A_n$} 是关系的一个或多个属性的集合，该集合函数决定了关系的其他所有属性并且是最小的，那么该集合就称为键码。
对于 A->B，如果能找到 A 的真子集 A’，使得 A’->B 就是部分函数依赖，否则就是完全函数依赖。
对于 A->B，B->C，则 A->C 是一个传递函数依赖。
异常
以下的学生课程关系的函数依赖为 Sno, Cname -> Sname, Sdept, Mname, Grade，键码为 {Sno, Cname}。也就是说，确定学生和课程之后，就能确定其它信息。
| Sno | Sname | Sdept | Mname | Cname | Grade |
|---|---|---|---|---|---|
| 1 | 学生-1 | 学院-1 | 院长-1 | 课程-1 | 90 |
| 2 | 学生-2 | 学院-2 | 院长-2 | 课程-2 | 80 |
| 2 | 学生-2 | 学院-2 | 院长-2 | 课程-1 | 100 |
| 3 | 学生-3 | 学院-2 | 院长-2 | 课程-2 | 95 |
不符合范式的关系，会产生很多异常，主要有以下四种异常：
- 冗余数据：例如
学生-2出现了两次。 - 修改异常：修改了一个记录中的信息，但是另一个记录中相同的信息却没有被修改。
- 删除异常：删除一个信息，那么也会丢失其它信息。例如删除了
课程-1需要删除第一行和第三行，那么学生-1的信息就会丢失。 - 插入异常：例如想要插入一个学生的信息，如果这个学生还没选课，那么就无法插入。
范式（Normal Form）
范式理论是为了解决以上提到的四种异常。
高级别范式依赖于低级别范式，1NF 是最低级别的范式。
1. 第一范式（1NF）
属性不可分。
2. 第二范式（2NF）
每个非主属性完全函数依赖于键码。
可以通过分解来满足。
如果非主属性不是完全函数依赖于键码，而是存在部分函数依赖，那么这些不是完全函数依赖于键码的属性就存在冗余。
3. 第三范式（3NF）
非主属性不传递函数依赖于键码。
等同于非主属性不能依赖于另外一个非主属性。
索引
B+树原理
1. 数据结构
B Tree 指的是 Balence Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。
B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。
在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指针的左右相邻的 key 分别是 $key_i$ 和 $key_{i+1}$，且不为 null，该指针指向节点的所有 $key$ 大于等于 $key_i$ 且小于等于 $key_{i+1}$。
2. 操作
进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 对应的data。
插入和删除操作会破坏树的平衡性，因此在插入删除操作之后，需要对树进行一个分裂、合并、旋转等操作来维护平衡性。
3. 与红黑树的比较
红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，主要有一下两个原因：
（一）更少的查找次数
平衡树查找操作的时间复杂度和树高 h 相关，$O(h)=O(log_d{N})$，其中 d 为每个节点的出度。
红黑树的出度为2，而B+ Tree的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree大非常多，查找的次数也就更多。
（二）利用磁盘预读特性
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，速度会非常快。
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。
MySQL 索引
MySQL 索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。
1. B+ Tree 索引
是大多数 MySQL 存储引擎的默认索引类型。
因为不再需要进行全表扫描，只需要对树进行搜索即可，所以查找速度会很快。
除了用于查找，还可以用于排序和分组。
可以指定多个列作为索引列，多个索引列共同组成键。
适用于全键值、键值范围和键前缀查找，其中键前缀查找只适用于最左前缀查找。如果不是按照索引列的顺序进行查找，则无法使用索引。
InnoDB 的 B+ Tree 索引分为主索引和辅助索引。主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找。
2. 哈希索引
哈希索引能以 $O(1)$ 时间进行查找，但是失去了有序性：
- 无法用于排序与分组；
- 只支持精确查找，无法用于部分查找和范围查找。
InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+ Tree 索引之上再创建一个哈希索引，这样就可以让 B+ Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。
3. 全文索引
MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。
查找条件使用 MATCH AGAINST，而不是普通的 WHERE。
全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射。
InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。
4. 空间数据索引
MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。
必须使用 GIS 相关的函数来维护数据。
索引优化
1. 独立的列
在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引。
例如下面的查询不能使用 actor_id 列的索引：
1 | SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5; |
2. 多列索引
在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。例如下面的语句中，最好把 actor_id 和 film_id 设置为多列索引。
1 | SELECT film_id, actor_ id |
3. 索引列的顺序
让选择性最强的索引列放在前面。
索引的选择性是指：不重复的索引值和记录总数的比值。最大值为1，此时每个记录都有唯一的索引与其对应。选择性越高，查询效率也越高。
4. 前缀索引
对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符。
对于前缀长度的选取需要根据索引选择性来确定。
5. 覆盖索引
索引包含所有需要查询的字段的指。
具有以下优点：
- 索引通常远小于数据行的大小，只读取索引能大大减少数据访问量。
- 一些存储引擎（例如MyISAM）在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用（通常比较耗时）
- 对于 InnoDB 引擎，若辅助索引能够覆盖索引，则无需访问主索引。
索引的优点
- 大大减少了服务器需要扫描的数据行数。
- 帮助服务器避免进行排序和分组，以及避免创建临时表（B+ Tree索引是有序的，可以用于 ORDER BY和 GROUP BY 操作。临时表主要是在排序和分组过程中创建，因为不需要排序和分组，也就不需要创建临时表）。
- 将随机 I/O 变为顺序 I/O（B+ Tree 索引是有序的，会将相邻的数据都存储在一起）。
索引的使用条件
对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效。
对于中到大型的表，索引就非常有效；
但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。
TODO - 搞清楚这个大中小的划分标准。
查询性能优化
使用 EXPLAIN 命令进行分析
Explain 用来分析 SELECT 查询语句，开发人员可以通过分析 Explain 结果来优化查询语句。在MySQL索引原理及慢查询优化 - 美团技术团队这篇文章中有很多案例。
存储引擎
InnoDB
InnoDB 是MySQL 默认的事务型存储引擎，只有在需要它不支持的特性时，才考虑使用其他搜索引擎。
实现了四个标准的隔离界别，默认级别是可重复读（REPEATABLE READ）。在可重复读隔离级别下，通过多版本并发控制（MVCC）+间隙锁（Next-Key Locking）防止幻读。
主索引是聚簇索引，在索引中保存了数据，从而避免直接读取磁盘，因此对查询性能有很大的提升。
内部做了很多优化，包括从磁盘读取数据时采用的可预测性读、能够加快读操作并且自动创建的自适应哈希索引、能够加速插入操作的插入缓冲区等。
支持真正的在线热备份。其他存储引擎不支持在线热备份，要获取一致性视图需要停止对所有表的写入，而在读写混合场景中，停止写入可能也意味着停止读取。
MyISAM
设计简单，数据以紧密格式存储。对于只读数据，或者表比较小、可以容忍修复操作，则依然可以使用它。
提供了大量的特性，包括压缩表、空间数据索引等。
不支持事务。
不支持行级锁，只能对整张表加锁，读取时会对需要读到的所有表加共享锁，写入时则对表加排他锁。但在表有读取操作的同时，也可以往表中插入新的记录，这被称为并发插入（Concurrent Insert）。可以手工或者自动执行检查和修复操作，但是和事务恢复以及崩溃恢复不同，可能导致一些数据丢失，而且修复操作是非常慢的。
如果指定了 DELAY_KEY_WRITE 选项，在每次修改执行完成时，不会立即将修改的索引数据写入硬盘，而是会写入到内存中的键缓冲区，只有在清理键缓冲区或者关闭表的时候才会将对应的索引块写入磁盘。这种方式可以极大的提升写入性能，但是在数据库或者主机崩溃时会造成索引损坏，需要执行修复操作。
比较
事务：InnoDB 是事务型的，可以使用 Commit 和 Rollback 语句。
并发：MyISAM 只支持表级锁，而 InnoDB 还支持行级锁。
外键：InnoDB 支持外键。
备份：InnoDB 支持在线热备份。
崩溃恢复：MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多，而且恢复的速度也更慢。
其他特性：MyISAM 支持压缩表和空间数据索引。
MySQL 官方提供的供测试使用的数据库
https://dev.mysql.com/doc/index-other.html
在上边网页的 Example Databases 中。
这是其中一个：