前言

本复习提纲由Dart完成整理。

内容没有按题号来，主要按6+上课复习涉及到的知识点

1. B+树索引

1.1 B+树的结构

索引结构为树状层次结构，根节点会将数值分成若干区间，每个区间用指针指向下一层节点，下一层节点同样划分成若干区间，指向再下一层节点，依次往下

最底层的节点——叶节点，叶节点记录索引字段的值和此值所对应的基本表相关的记录存放的地址，将这个地址称为rowid

读取文件的步骤为：在b树中逐层向下找到rowid（索引的过程），之后根据rowid取读取基本表相关记录内容。读取每层节点的值都是一次io操作，下图中3次io操作是索引，再经历一次io操作查表即可获得基本表相关记录，即4次io

所有的叶节点都是按顺序在底层横向连接在一起，属于顺序存储的数据结构，对于搜索范围数据非常有用

B+

1.2 B+树索引能做什么，不能做什么，理由

  • 能做什么

    全键值查询（等值查询），每一次查询都是固定的次数的io操作（基于上图为4），3次索引+1次查表，不会受基本表大小的影响，效率一样

    范围查询，查询过程为：先通过等值查询找到范围最左侧的值对应的块，然后横向读取叶节点，直到读到范围最右侧的值对应的块为止，读完索引以后根据地址（rowid）找值即可。由于数据在叶节点中横向顺序查询，因此范围查询很方便，效率很高

    键前缀查询，与范围查询类似。

  • 不能做什么

    后缀查询

2. 索引

2.1 作用

索引是否合理取决于它是否有用，判断适用性的依据是检索比例（查询到的结果集在原数据中所占的比例，一般为10%，但是没有明确的分界线）

查询结果所占的百分比越低，称查询越具有选择性

越少的数据访问，越有必要通过索引来提升查询效率，如果比例过大，则可能还不如全表遍历

两种b树索引适用情况：

  • 仅需要访问基本表中很少一部分行可以使用索引

  • 访问基本表很多行，只使用索引，不使用表

    e.g

    1
    2
    3
    Select x,y
    From T
    where x

    即所需查询的数据中，select需要筛选的字段只有x,y,则可以通过复合键索引（见2.2），读完整个索引，查询结果可得，不需要查询基本表

2.2 复合键索引

复合键索引，即对多个字段构建的索引

e.g. index(x,y)

复合键索引本质上是按照排名第一的字段进行的索引，如上例中index(x)和index(x,y)本质是一样的，如果有index(x,y)，则不需要index(x)，因为二者组织方式是一样的

e.g. 对x,y进行复合键索引，本质上是对x构建索引一样，唯一的差别是在叶节点增加一列y的值，对每个x的取值，y进行排序

2.3 索引加外键的理由

对数据库的某些操作有影响：

e.g.表A student的外键参照了表B department的主键，两张表需要同时修改，stu表很大，而用户只是希望从department表删除一条记录，dbms为了避免表间依赖的不一致性，s tu需要检查stu表中是否包含了de表中待删除的记录，就会花费较多时间，并有可能影响到操作，而有索引之后会节省很多时间

对并发也有影响：

外键不加索引有可能会造成死锁，若无，查找子记录的速度就会很慢，参照表被锁住的时间会很长，阻塞更多的操作，两个进程互锁对方需要的参照表就会引发死锁，加外键的必要性在于可以避免枷锁时间过长，进程需要的时间缩短，降低了出现死锁的概率

什么时候不需要：

表b很少被修改，例如表b为字典表，其主键作为表a的外键不需要加索引，因为表b很难产生修改的情况，因而很难产生并发冲突

2.4 同一字段 多个索引 字段顺序问题

如果系统为外键自动增加索引，常常会导致同一字段属于多个索引的情况

e.g. 多对多的情况：一个订单包含多个商品，一个商品也在多个订单中出现，因此需要在中间建立关联表（Order_Details(Order_id,article_id)）

在索引中字段顺序很重要，可能会影响某引数量，导致多余索引的情况，从而影响性能

e.g. 在上例中，如果Order_id在前，表会缺省地构建一个order_id和article_id的复合键索引，然后要手动为外键构建索引，Order_id不需要索引，因为跟复合键索index（o,a）引本质一样，因此只需要构建article_id的索引，而article是商品表，不太被修改，符合字典表原则，因此不需要构建索引。综上，只需对复合键构建索引，不需单独索引，仅有一个索引

如果a在前，系统会构建一个a_id为主的复合键索引，同时要手工构建o_id的外键索引，因为order这张表要频繁更改，构建外键索引是必要的。综上，引入了额外的索引

2.5 自增字段 系统生成键

构建数据库有时需要唯一的流水号作为主键，往往用自增字段/系统生成键来实现

怎么实现

系统提供的自增字段性能很高，使用系统提供的自增字段是最佳选择，远好于自己实现，系统会自动为当前自增字段构建主键索引以保证其唯一性

  • 自己实现：

    需要存储一个最大值，而这个最大值势必成为资源竞争的节点，所有的插入必须先读取该最大值，然后进行+1，再存储，此时该字段值只能串行化，无法支持并发

资源竞争

如果用自增字段来实现系统生成键，可能会引发并发问题：插入并发性过高，在主键索引的创建操作上会发生严重的资源竞争问题

主键索引的主要作用是保障主键的唯一性，如果仅存在一个系统生成键的生成器，生成的序列号就会很接近，在插入键值的过程中，所有的进程都会争夺相同的索引的page和块，而请求需要串行化各个进程，利用合适锁定机制来避免一个进程的复写(overwrite)。尽管在基本表的插入中由于堆文件、随机文件的存在使得基本表可以支持高并发的同时写入，但在索引写入上只能支持串行，即一个接一个的操作，这时就会出现瓶颈

怎么解决

反向键索引/逆向索引（reverse index）

  • 特殊的函数索引，将字段值反过来（9527->7259）

    如果有连续的记录并发插入，他们大概率会在索引结构上同一个叶节点的块中，此时必须要排队竞争该具体块从而插入

    反向键索引使得连续的值变得相差很远，他们大概率会落在索引结构的不同叶节点上，这时可以同时插入不同的块，不需要竞争

哈希索引(hash index)

  • 组织形式与b树索引类似，将值与等长数值（哈希值）对应起来，将哈希值组成索引结构
  • 与上一个方法类似，本质是将连续的内容离散化
该不该用毫无意义的字段作为主键，会带来什么问题（内容来自网络）

优点：

  • 数据库自动编号，速度快，而且是增量增长，按顺序存放，对于检索非常有利；
  • 数字型，占用空间小，易排序，在程序中传递也方便；
  • 如果通过非系统增加记录时，可以不用指定该字段，不用担心主键重复问题

缺点：

  • 在系统集成或割接时，如果新旧系统主键不同是数字型就会导致修改主键数据类型，这也会导致其它有外键关联的表的修改，后果同样很严重
  • 高并发的情况下，竞争自增锁会降低数据库的吞吐能力
  • 导入旧数据时，可能会ID重复，导致导入失败
  • 分布式架构，多个Mysql实例可能会导致ID重复

3. SQL

3.1 执行顺序

解析最消耗资源，是高效执行/优化的切入口。解析对每一次的表达式进行等价变换，生成解析树进行评估，最终形成执行计划，将计划抛入执行引擎中，进行查询，解析+生成执行计划是查询优化器最重要的工作

执行顺序

3.2 优化方式

  • 使用好的过滤条件
  • 降低表连接的数量
过滤条件

  • 含义

    join过滤条件——on，用于连接表

    select过滤条件——where，与需求、业务相关

  • 过滤条件的好坏

    过滤条件是否高效：是否能够尽快减少必须处理的数据总量

    好的过滤条件需要先做，在复杂的、高并发的查询中，将好的过滤条件先做，可以有效减少中间结果集的大小，从而提高效率

用exists嵌套子查询摆脱distinct

子查询和外层select关系很密切，但会执行很多次，这时如果在exists前使用较高效的过滤条件可以有效减少exists的执行次数

in构建非关联子查询

在关联子查询中，相关字段要有索引，而非关联子查询不需要，因为要用到的索引是主键索引，内层查询不再依赖外层查询，只需要执行一次

3.3 表结构

回头看看订单和客户的例子
降低表连接数量->反范式/逆范式

反范式化为了提升查询效率而考虑把原本符合第三范式的表适当增冗余，减少表连接数量

合并1对1关系

  • 以全部参与的表为主，引入部分参入的表

    e.g. staff与nok(紧急联系人)是1对1，每个nok都对应一个staff，但不是每个staff都有nok，nok部分参与。对两表进行合并，以staff为主，引入nok

  • 问题：

    • 空值问题
    • 如果全部参与的表很大，部分参与的表很小，会造成空间浪费
    • 如果两个表对于彼此都是部分参与，那么还需手动引入主键

为减少连接操作，在1对多关系中复制非关键字属性

  • 注意复制过来的属性的更新，需要触发器来进行两张表的同步更新
  • 一般对于钱这种属性，都需要打破范式进行存储

为减少连接操作，在1对多关系中复制外部关键字

  • 与上述内容类似

为减少连接操作，在多对多关系中复制非关键字属性

引入重复组

  • 把重复组打包放进主表中（不通用）
  • 主表中存放缺省的一个值，等需要详细的全部内容时再访问相应的地址表和基本表

合并基本表和查找表，创建提取表

  • 将查询慢的表全部连接起来形成一张大表
  • 不到必要不要使用，虽然很强大，但会带来很大的复杂性

分区（存储层面的逆范式）

4. 数据库的事务隔离级别

表格

隔离级别

相关计算

脏读

一个事务读到另一个事务修改但未提交的数据时，就可能发生脏读

e.g. from ppt

1
2
3
4
5
6
7
8
9
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */
/*事务2*/
UPDATE users SET dept_id=2 WHERE id=1
/* No commit here */
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 2 */
不可重复读

（ppt）在当执行SELECT 操作时没有获得读锁或SELECT操作执行完后马上释放了读锁; 另外一个事务对数据进行了更新,读到了不同的结果

（网络版本）在对于数据库中的某个数据，一个事务范围内多次查询却返回了不同的数据值，这是由于在查询间隔，被另一个事务修改并提交了

e.g. 事务T1在读取某一数据，而事务T2立马修改了这个数据并且提交事务给数据库，事务T1再次读取该数据就得到了不同的结果，发送了不可重复读

1
2
3
4
5
6
7
8
9
10
11
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */
/*事务2*/
UPDATE users SET dept_id=2 WHERE id=1
COMMIT;
/* No commit here */
/*事务1*/
SELECT dept_id FROM users WHERE id=1
COMMIT;
/* 结果是 2 */

注意，虽然你知道事务2改了，但是事务1可能不知道，连读两次数不一样的场面就很惊悚

幻读

是不可重复读的一种特殊场景，主要针对增和删

  • 当事务1两次执行’’SELECT … WHERE’’检索一定范围内数据的操作中间

  • 事务2在这个表中创建了(如[[INSERT]])了一行新数据，这条新数据正好满足事务1的 “WHERE”子句。

e.g. from Internet

系统管理员A将数据库中所有学生的成绩从具体分数改为ABCDE等级，但是系统管理员B就在这个时候插入了一条具体分数的记录，当系统管理员A改结束后发现还有一条记录没有改过来，就好像发生了幻觉一样，这就叫幻读

三者比较

脏读：读到了别的事物未提交的数据

不可重复读：读到了其他事务已经提交的数据

幻读：不可重复读的特殊场景

  • 不可重复读与幻读都是读到其他事务已提交的数据，但是它们针对点不同.
  • 不可重复读:update.
  • 幻读:delete，insert

四种级别（如果你嫌弃我的例子炒前面的冷饭那就自己举！）

未提交读

是最低的隔离级别，在这种隔离级别下，如果一个事务 已经开始写数据，则另外一个事务则不允许同时进行写操作，但允许其他事务读此行数据

在此隔离级别下，一个事务能够读到其他事务未提交的数据，因此可能存在脏读问题

e.g. (前面脏读的例子罢了)

1
2
3
4
5
6
7
8
9
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */
/*事务2*/
UPDATE users SET dept_id=2 WHERE id=1
/* No commit here */
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 2 */

隔离级别低到连其他未提交的数据都可以读到，因此可重复读和幻读问题也不可避免，举例与上述幻读和不可重复读一致

已提交读

读取数据的事务允许其他事务继续访问该行数据，但是未提交的写事务将会禁止其他事务 访问该行，会对该写锁一直保持直到到事务提交

e.g. 

1
2
3
4
5
6
7
8
9
10
11
12
13
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */
/*事务2*/
UPDATE users SET dept_id=2 WHERE id=1
/* No commit here ,But locked*/
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* waiting waiting/
/*事务2*/
ROLLBACK;
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */

解释：在事务2更新某条数据的时候，如果没有commit，那么针对此条数据的写锁一直保持，当事务1想要读时会因为写锁被阻塞，直到事务2commit或者rollback，写锁解除，才可以读

但是防不了不可重复读的问题，即事务2 commit提交以后，事务1在前后两次读取相同行的内容是不同的

e.g. (前面不可重复读的例子罢了)

1
2
3
4
5
6
7
8
9
10
/*事务1*/
SELECT dept_id FROM users WHERE id=1
/* 结果是 1 */
/*事务2*/
UPDATE users SET dept_id=2 WHERE id=1
COMMIT;
/*事务1*/
SELECT dept_id FROM users WHERE id=1
COMMIT;
/* 结果是 2 */

幻读作为不可重复读的特殊场景同样在这一隔离级别难以被避免（笔者此时心态崩了，不想写了，反正就事务2插入了，然后事务1恍惚间发现多了一条数据，就很迷）

图

可重复读

从名字就可以知道，它可以避免不可重复读的问题

一个事务在执行过程中，可以访问其他事务成功提交的新插入的数据，但不可以访问成功修改的数据。读取数据的事务将会禁止写事务（但允许读事务），写事务则禁止任何其他事务。此隔离级别可有效防止不可重复读和脏读，但防不住幻读，下图应该很清楚了，我就不解释了

图

可串行化

提供严格的事务隔离。它要求事务序列化执行，事务只能一个接着一个地执行，不能并发执行。此隔离级别可有效防止脏读、不可重复读和幻读。但这个级别可能导致大量的超时现象和锁竞争，在实际应用中很少使用