文档展示

Mysql面试题

一、Mysql搜索引擎

1.1、Mysql的体系架构

image-20210929094921084

MySQL从概念上可以分为四层，顶层是接入层，不同语言的客户端通过mysql的协议与mysql服务器进行连接通信，接入层进行权限验证、连接池管理、线程管理等。下面是mysql服务层，包括sql解析器、sql优化器、数据缓冲、缓存等。再下面是mysql中的存储引擎层，mysql中存储引擎是基于表的。最后是系统文件层，保存数据、索引、日志等。

1.2、Mysql搜索引擎

Mysql5.5以后默认使用InnoDB为搜索引擎。

在这里插入图片描述

InnoDB 引擎：InnoDB 引擎提供了对数据库 acid 事务的支持，并且还提供了行级锁和外键的约束，它的设计的目标就是处理大数据容量的数据库系统。MySQL 运行的时候，InnoDB 会在内存中建立缓冲池，用于缓冲数据和索引。但是该引擎是不支持全文搜索，同时启动也比较的慢，它是不会保存表的行数的，所以当进行 select count() from table 指令的时候，需要进行扫描全表。由于锁的粒度小，写操作是不会锁定全表的,所以在并发度较高的场景下使用会提升效率的。

MyIASM 引擎：MySQL 的默认引擎，但不提供事务的支持，也不支持行级锁和外键。因此当执行插入和更新语句时，即执行写操作的时候需要锁定这个表，所以会导致效率会降低。不过和 InnoDB 不同的是，MyIASM 引擎是保存了表的行数，于是当进行 select count() from table 语句时，可以直接的读取已经保存的值而不需要进行扫描全表。所以，如果表的读操作远远多于写操作时，并且不需要事务的支持的，可以将 MyIASM 作为数据库引擎的首选。

1.3、数据库的事务

事务就是「一组原子性的SQL查询」，或者说一个独立的工作单元。如果数据库引擎能够成功地对数据库应用该组查询的全部语句，那么就执行该组查询。如果其中有任何一条语句因为崩溃或其他原因无法执行，那么所有的语句都不会执行。也就是说，事务内的语句，要么全部执行成功，要么全部执行失败。

张三给李四转账，只有当张三账户的钱转走了，并且李四账户的钱收到了之后转账事务才能提交。如果原子性无法保证，就会出现张三的钱转走了，李四却没收到钱的情况！ 这时候就需要事务。

1.3.1、事务的四大特性（事务的ACID）

1、原子性(Atomicity)

2、一致性(Consistency)

3、隔离性(Isolation)

4、持久性(Durability)

ACID其实是事务特性的英文首字母缩写，具体的含义是这样的：

  • 原子性(ATOMICITY)，定义: 一个事务必须被视为一个不可分割的最小工作单元，整个事务中的所有操作要么全部提交成功，要么全部失败，对于一个事务来说，不可能只执行其中的一部分操作
  • 一致性(CONSISTENCY)，定义: 一致性是指事务讲数据库从一种一致性状态转换到另外一种一致性状态，在事务开始之前和事务结束后数据库数据的完整性没有被破坏
  • 隔离性(ISOLATION)，定义： 隔离性要求一个事务对数据库中数据的修改，在未提交完成前对于其它事务是不可见的
  • 持久性（DURABILITY），定义： 一旦事务提交，则其所做的修改就会永久保存到数据库中。此时即使系统崩溃，已经提交的修改数据也不会丢失。

1.3.2、Mysql的四种隔离级别

  • Read Uncommitted（读取未提交内容）

    在该隔离级别，所有事务都可以看到其他未提交事务的执行结果。本隔离级别很少用于实际应用，因为它的性能也不比其他级别好多少。读取未提交的数据，也被称之为脏读（Dirty Read）。

  • Read Committed（读取提交内容）

    这是大多数数据库系统的默认隔离级别（但不是MySQL默认的）。它满足了隔离的简单定义：一个事务只能看见已经提交事务所做的改变。

    这种隔离级别也支持所谓的不可重复读（Nonrepeatable Read），因为同一事务的其他实例在该实例处理其间可能会有新的commit，所以同一select可能返回不同结果。

  • Repeatable Read（可重读）

    这是MySQL的默认事务隔离级别，它确保同一事务的多个实例在并发读取数据时，会看到同样的数据行。不过理论上，这会导致另一个棘手的问题：幻读 （Phantom Read）。

    简单的说，幻读指当用户读取某一范围的数据行时，另一个事务又在该范围内插入了新行，当用户再读取该范围的数据行时，会发现有新的“幻影” 行。InnoDB和Falcon存储引擎通过多版本并发控制（MVCC，Multiversion Concurrency Control）机制解决了该问题。

  • Serializable（可串行化）

    这是最高的隔离级别，它通过强制事务排序，使之不可能相互冲突，从而解决幻读问题。简言之，它是在每个读的数据行上加上共享锁。在这个级别，可能导致大量的超时现象和锁竞争。

这四种隔离级别采取不同的锁类型来实现，若读取的是同一个数据的话，就容易发生问题。例如：

  • 脏读(Drity Read)：某个事务已更新一份数据，另一个事务在此时读取了同一份数据，由于某些原因，前一个RollBack了操作，则后一个事务所读取的数据就会是不正确的。
  • 不可重复读(Non-repeatable read):在一个事务的两次查询之中数据不一致，这可能是两次查询过程中间插入了一个事务更新的原有的数据。
  • 幻读(Phantom Read):在一个事务的两次查询中数据笔数不一致，例如有一个事务查询了几列(Row)数据，而另一个事务却在此时插入了新的几列数据，先前的事务在接下来的查询中，就有几列数据是未查询出来的，如果此时插入和另外一个事务插入的数据，就会报错。

在MySQL中，实现了这四种隔离级别，分别有可能产生问题如下所示：

img

测试Mysql的隔离级别：

下面，将利用MySQL的客户端程序，我们分别来测试一下这几种隔离级别。

测试数据库为demo，表为test；表结构：

CREATE TABLE  `test`(
   `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
   `num` int(11) NOT NULL DEFAULT 0,
    PRIMARY KEY(`id`)
)ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=UTF8;

insert into test (id,num) values (1,1),(2,2),(3,3);

两个命令行客户端分别为A，B；不断改变A的隔离级别，在B端修改数据。

（1）将A的隔离级别设置为read uncommitted(未提交读)

 set session transaction isolation level read uncommitted;

A：启动事务，此时数据为初始状态

mysql> select @@tx_isolation;
+------------------+
| @@tx_isolation   |
+------------------+
| READ-UNCOMMITTED |
+------------------+

mysql> select * from test;
+----+-----+
| id | num |
+----+-----+
|  1 |   1 |
|  2 |   2 |
|  3 |   3 |
+----+-----+

img

B：启动事务B，更新数据，但不提交

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> update test set num=10 where id=1;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0

mysql> select * from test;
+----+-----+
| id | num |
+----+-----+
|  1 |  10 |
|  2 |   2 |
|  3 |   3 |
+----+-----+
3 rows in set (0.00 sec)

img

A事务中：再次读取数据，发现数据已经被修改了，这就是所谓的“脏读”

img

B：回滚事务

img

A：再次读数据，发现数据变回初始状态

img

经过上面的实验可以得出结论，事务B更新了一条记录，但是没有提交，此时事务A可以查询出未提交记录。造成脏读现象。未提交读是最低的隔离级别。

（2）将客户端A的事务隔离级别设置为read committed(已提交读)

 set session transaction isolation level read committed;

img

A：启动事务A，此时数据为初始状态

mysql> start transaction;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from test;
+----+-----+
| id | num |
+----+-----+
|  1 |   1 |
|  2 |   2 |
|  3 |   3 |
+----+-----+
3 rows in set (0.00 sec)

img

B：启动事务B，更新数据，但不提交

img

A：再次读数据A，发现数据未被修改

img

B：提交事务

img

A：再次读取数据，发现数据已发生变化，说明B提交的修改被事务中的A读到了，这就是所谓的“不可重复读”

img

经过上面的实验可以得出结论，已提交读隔离级别解决了脏读的问题，但是出现了不可重复读的问题，即事务A在两次查询的数据不一致，因为在两次查询之间事务B更新了一条数据。

已提交读只允许读取已提交的记录，但不要求可重复读。

（3）将A的隔离级别设置为repeatable read(可重复读)

img

A：启动事务，此时数据为初始状态

img

B：启动事务，更新数据，但不提交

img

A：再次读取数据，发现数据未被修改

img

B：提交事务

img

A：再次读取数据，发现数据依然未发生变化，这说明这次可以重复读了

img

B：插入一条新的数据，并提交

img

A：再次读取数据，发现数据依然未发生变化，虽然可以重复读了，但是却发现读的不是最新数据，这就是所谓的“幻读”

img

A：提交本次事务，再次读取数据，发现读取正常了

img

由以上的实验可以得出结论，可重复读隔离级别只允许读取已提交记录，而且在一个事务两次读取一个记录期间，其他事务部的更新该记录。但该事务不要求与其他事务可串行化。

例如，当一个事务可以找到由一个已提交事务更新的记录，但是可能产生幻读问题(注意是可能，因为数据库对隔离级别的实现有所差别)。像以上的实验，就没有出现数据幻读的问题。

（4）将A的隔离级别设置为可串行化(Serializable)

img

A：启动事务，此时数据为初始状态

img

B：发现B此时进入了等待状态，原因是因为A的事务尚未提交，只能等待（此时，B可能会发生等待超时）

img

A：提交事务

img

B：发现插入成功

img

serializable完全锁定字段，若一个事务来查询同一份数据就必须等待，直到前一个事务完成并解除锁定为止。是完整的隔离级别，会锁定对应的数据表格，因而会有效率的问题。

常见面试题

生产用哪种隔离级别？

答Read Commited或者Repeatable都行，有道理即可。例如，我用了Read Commited,因为这个隔离级别够用了，用不上间隙锁！

另外，额外记住Repeatable是默认的隔离级别即可！至于另外两个隔离级别，Read uncommitted，一个事务能读到另一个事务未提交的数据，隔离性都无法满足，不用这个隔离级别。另外一个隔离级别Seriallzable,在这个隔离级别下，MVCC机制都无法满足，数据库并发性非常差，不用这个隔离级别。

ps:这个问题其实考察的是你对各个隔离级别的理解，所以务必牢记各个隔离级别的区别！

什么是大事务以及如何处理

运行时间比较长，操作的数据比较多的事务称为大事务

1. 锁定太多的数据，造成大量的阻塞和锁超时
2. 回滚时所需时间比较长
3. 执行时间长，容易造成主从延迟

如何处理大事务

1. 避免一次处理太多的数据
2. 移出不必要在事务中的SELECT操作

二、索引

2.1、什么是索引

一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。

索引在MySQL中也叫做“键”，是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级。

img

首先数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，要从 500 万行数据里面检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。 但是有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。 就像我们从一本 500 页的书里面去找特定的一小节的内容，肯定不可能从第一页开始翻。那么这本书有专门的目录，它可能只有几页的内容，它是按页码来组织的，可以根据拼音或者偏旁部首来查找，只要确定内容对应的页码，就能很快地找到我们想要的内容。

可视化工具open in new window

2.2、二分查找

双十一过去之后，你女朋友跟你玩了一个猜数字的游戏。猜猜我昨天买了多少钱，给你五次机会。10000？低了。30000？高了。接下来你会猜多少？ 20000。为什么你不猜 11000，也不猜 29000 呢？

其实这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。 所以第一个，我们可以考虑用有序数组作为索引的数据结构。有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。所以，有没有可以使用二分查找的链表呢？为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了。

2.3、二叉树

二叉查找树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下性质：

1、任意节点左子树不为空,则左子树的值均小于根节点的值；

2、任意节点右子树不为空,则右子树的值均大于于根节点的值；

3、任意节点的左右子树也分别是二叉查找树；

4、没有键值相等的节点；

img

上图为一个普通的二叉查找树，按照中序遍历的方式可以从小到大的顺序排序输出：2、3、5、6、7、8。

对上述二叉树进行查找，如查键值为5的记录，先找到根，其键值是6，6大于5，因此查找6的左子树，找到3；而5大于3，再找其右子树；一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需求3次。用同样的方法在查找键值为8的这个记录，这次用了3次查找，而顺序查找需要6次。计算平均查找次数得：顺序查找的平均查找次数为（1+2+3+4+5+6）/ 6 = 3.3次，二叉查找树的平均查找次数为（3+3+3+2+2+1）/6=2.3次。二叉查找树的平均查找速度比顺序查找来得更快。

应用

例如，我现在想要查找数值为14的节点。由于二叉查找树的特性，我们可以很快着找到它，其过程如下：

1、和根节点9比较

img

2、由于 14 > 9，所以14只可能存在于9的右子树中，因此查看右孩子13

img

3、由于 14 > 13，所以继续查看13的右孩子15

img

4、由于 14 < 15，所以14只可能存在于15的左孩子中，因此查找15的左孩子14

img

5、这时候发现14正是自己查找的值，于是查找结束。

这种查找二叉树的查找正是二分查找的思想，可以很快着找到目的节点，查找所需的最大次数等同于二叉查找树的高度。

在插入的时候也是一样，通过一层一层的比较，最后找到适合自己的位置。

缺点

二叉查找树既能够实现快速查找，又能够实现快速插入。但是二叉查找树有一个问题：就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成O(n)。

一个二叉查找树是由n个节点随机构成，所以，对于某些情况，二叉查找树会退化成一个有n个节点的线性链。大家看上图，如果我们的根节点选择是最小或者最大的数，那么二叉查找树就完全退化成了线性结构。上图中的平均查找次数为（1+2+3+4+5+5）/6=3.16次，和顺序查找差不多。显然这个二叉树的查询效率就很低，因此若想最大性能的构造一个二叉查找树，需要这个二叉树是平衡的（这里的平衡从一个显著的特点可以看出这一棵树的高度比上一个输的高度要大，在相同节点的情况下也就是不平衡），从而引出了一个新的定义-平衡二叉树AVL。

初始的二叉查找树只有三个节点：

img

然后我们按照顺序陆续插入节点 4，3，2，1，0。插入之后的结构如下：

img

它会变成链表（我们把这种树叫做“斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。造成它倾斜的原因是什么呢？因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树（AVL 是发明这个数据结构的人的名字）。

2.4、平衡树(AVL)

2.4.1、平衡树的介绍

AVL树是相比于"二叉查找树"，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

img

上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。 如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理。学AVL树，重点的地方也就是它的旋转算法；在后文的介绍中，再来对它进行详细介绍。

img

img

2.4.2、插入与旋转

平衡二叉树是一种比查找二叉树还特别的树，这种树就可以帮助我们解决二叉查找树刚才的那种所有节点都倾向一边的缺点的。具有如下特性：

  1. 具有二叉查找树的全部特性。
  2. 每个节点的左子树和右子树的高度差至多等于1。

例如：图一就是一颗AVL树了，而图二则不是(节点右边标的是这个节点的高度)。

img

img

对于图二，因为节点9的左孩子高度为2，而右孩子高度为0。他们之间的差值超过1了。这种树就可以保证不会出现大量节点偏向于一边的情况了。听起来这种树还不错，可以对于图1，如果我们要插入一个节点3，按照查找二叉树的特性，我们只能把3作为节点4的左子树插进去，可是插进去之后，又会破坏了AVL树的特性，那我们那该怎么弄？

我们在进行节点插入的时候，可能会出现节点都倾向于左边的情况，例如：

img

我们把这种倾向于左边的情况称之为左-左型。这个时候，我们就可以对节点9进行右旋操作，使它恢复平衡。

img

即：顺时针旋转两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

再举个例子：

img

节点4和9高度相差大于1。由于是左孩子的高度较高，此时是左-左型，进行右旋。

img

这里要注意，节点4的右孩子成为了节点6的左孩子了

我找了个动图，尽量这个动图和上面例子的节点不一样。

img

左旋

左旋和右旋一样，就是用来解决当大部分节点都偏向右边的时候，通过左旋来还原。例如：

img

我们把这种倾向于右边的情况称之为右-右型。

我也找了一张动图。

img

举个例子：

初始状态如下：

img

然后我们主键插入如下数值：1,4,5,6,7,10,9,8

插入 1

img

左-左型，需要右旋调整。

img

插入4

img

继续插入 5

img

右-右型，需要左旋转调整。

img

继续插入6

img

右-右型，需要进行左旋

img

继续插入7

img

右-右型，需要进行左旋

img

继续插入10

img

继续插入9

img

出现了这种情况怎么办呢?对于这种 右-左型的情况，单单一次左旋或右旋是不行的，下面我们先说说如何处理这种情况。

img

这种我们就把它称之为右-左 型吧。处理的方法是先对节点10进行右旋把它变成右-右型。

img

然后在进行左旋。

img

所以对于这种右-左型的，我们需要进行一次右旋再左旋。

同理，也存在左-右型的，例如：

img

对于左-右型的情况和刚才的 右-左型相反，我们需要对它进行一次左旋，再右旋。

img

回到刚才那道题

img

对它进行右旋再左旋。

img

到此，我们的插入就结束了。

在插入的过程中，会出现一下四种情况破坏AVL树的特性，我们可以采取如下相应的旋转。

1、左-左型：做右旋。

2、右-右型：做左旋转。

3、左-右型：先做左旋，后做右旋。

4、右-左型：先做右旋，再做左旋。

注意：通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

B树，B+树：它们特点是一样的，是多路查找树，一般用于数据库中做索引，因为它们分支多层数少，因为磁盘IO是非常耗时的，而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。

2.4.3、平衡二叉树查询原理

在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

它应该存储三块的内容：

  1. 索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
  2. 数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
  3. 因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

img

缺点：

当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次 IO。 InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。 那么，一个树的节点就是 16K 的大小。 如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个 或者几十个字节，它远远达不到 16K 的容量，所以访问一个树节点，进行一次 IO 的时候， 浪费了大量的空间。 所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多 的节点，意味着跟磁盘交互次数就会过多。 如果是机械硬盘时代，每次从磁盘读取数据需要 10ms 左右的寻址时间，交互次数 越多，消耗的时间就越多。

比如上面这张图，我们一张表里面有 6 条数据，当我们查询 id=37 的时候，要查询两个子节点，就需要跟磁盘交互 3 次，如果我们有几百万的数据呢？这个时间更加难以 估计。

所以我们的解决方案是什么呢？

第一个就是让每个节点存储更多的数据。

第二个，节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有 更多的分叉（我们把它叫做“路数”）。 因为分叉数越多，树的深度就会减少（根节点是 0）。 这样，我们的树是不是从原来的高瘦高瘦的样子，变

2.4.4、B树（多路平衡查找树）

Balanced Tree 这个就是我们的多路平衡查找树，叫做 B Tree（B 代表平衡）。跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点：分叉数（路数）永远比关键字数多 1。比如我们画的这棵树，每个节 点存储两个关键字，那么就会有三个指针指向三个子节点。

注意B-树就是B树，-只是一个符号。

下图是一个三路平衡查找树

img

B Tree 的查找规则是什么样的呢？比如我们要在这张表里面查找 15。因为 15 小于 17，走左边。因为 15 大于 12，走右边。在磁盘块 7 里面就找到了 15，只用了 3 次 IO。

比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候， 本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针， 子节点会变成 4 路，所以这个时候必须进行分裂。把中间的数据 2 提上去，把 1 和 3 变 成 2 的子节点。

如果删除节点，会有相反的合并的操作。 注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的。 我们继续插入 4 和 5，B Tree 又会出现分裂和合并的操作。

img

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以 解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。 节点的分裂和合并，其实就是 InnoDB 页的分裂和合并。

2.4.5、B+树（加强版多路平衡查找树）

B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了 B+Tree 呢？ 总体上来说，这个 B 树的改良版本解决的问题比 B Tree 更全面。

我们来看一下 InnoDB 里面的 B+树的存储结构：

img

非叶子节点（比如1，28，66）只是一个key（索引），实际的数据存在叶子节点上（1，8，9）才是真正的数据或指向真实数据的指针。

MySQL 中的 B+Tree 有几个特点：

  1. 它的关键字的数量是跟路数相等的；

  2. B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜索 到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一 层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶 子节点。

    举个例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。非叶 子节点可以存储多少个指针？ 假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。非叶子节点（一页）可以存储 16384/14=1170 个这样的 单元（键值+指针），代表有 1170 个指针。

    树 深 度 为 2 的 时 候 ， 有 1170^2 个 叶 子 节 点 ， 可 以 存 储 的 数 据 为 1170117016=21902400。

    img

    在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询 数据最多需要访问 3 次磁盘。 所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。

  3. B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数 据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

  4. 它是根据左闭右开的区间 [ )来检索数据。

    我们来看一下 B+Tree 的数据搜寻过程：

1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是叶子节点，所以 会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然 后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后 在叶子节点上找到了需要的数据。

2）第二个，如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只 需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。

总结一下，InnoDB 中的 B+Tree 的优点：

  1. 它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。

  2. 扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵 B+Tree 拿到所有的数据）

  3. B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区， 所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）

  4. 排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）

  5. 效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）

2.5、红黑树

我们知道ALV树是一种严格按照定义来实现的平衡二叉查找树，所以它查找的效率非常稳定，为O(log n),由于其严格按照左右子树高度差不大于1的规则，插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡（左旋和右旋），因此ALV树适用于大量查询，少量插入和删除的场景中

那么假设现在假设有这样一种场景：大量查询，大量插入和删除，现在使用ALV树就不太合适了，因为ALV树大量的插入和删除会非常耗时间，那么我们是否可以降低ALV树对平衡性的要求从而达到快速的插入和删除呢？

答案肯定是有的，红黑树这种数据结构就应运而生了（因为ALV树是高度平衡的，所以查找起来肯定比红黑树快，但是红黑树在插入和删除方面的性能就远远不是ALV树所能比的了）

红黑树是一种特殊的二叉查找树，每个结点都要储存位表示结点的颜色，或红或黑

红黑树的特性：

1、节点分为红色或者黑色。

2、根节点必须是黑色的。

3、叶子节点都是黑色的 NULL 节点。

4、红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）。

5、从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。

插入：60、56、68、45、64、58、72、43、49

img

基于以上规则，可以推导出：

从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 2 倍。

为什么Mysql的索引不选择不用红黑树结构？

1、只有两路；

2、不够平衡。

红黑树应用比较广泛：

广泛用在C++的STL中。map和set都是用红黑树实现的。

著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

epoll在内核中的实现，用红黑树管理事件块

nginx中，用红黑树管理timer等

Java的TreeMap实现

2.6、哈希索引

哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

在这里插入图片描述

hash所以速度比B+树要快很多 ，Mysql为什么不用hash索引呢？

  1. 它的时间复杂度是 O(1)，查询速度比较快。但是哈希索引里面的数据不是 按顺序存储的，所以不能用于排序。

  2. 我们在查询数据的时候要根据键值计算哈希码，所以它只能支持等值查询 （= IN），不支持范围查询（> < >= <= between and）。

  3. 如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决），效率会降低。

三、MySQL的索引存储

3.1、不同存储引擎的存储原理

索引是占据物理空间的，在不同的存储引擎中，索引存在的文件也不同。存储引擎是基于表的，以下分别使用MyISAM和InnoDB存储引擎建立两张表。

MySQL 的数据都是文件的形式存a的，我们可以找到这个数据目录 的地址。在 MySQL 中有这么一个参数，我们来看一下：

show VARIABLES LIKE 'datadir';

存储引擎是基于表的，以下建立两张别使用MyISAM和InnoDB引擎的表，看看其在文件系统中对应的文件存储格式。

3.1.1、MyISAM

在 MyISAM 里面，另外有两个文件： 一个是.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录，比如我 们的 user_myisam 表的所有的表数据。 一个是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我们在 id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。 也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。 那我们怎么根据索引找到数据呢？ MyISAM 的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索 引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。

img

这里是主键索引，如果是辅助索引，有什么不一样呢？ 在 MyISAM 里面，辅助索引也在这个.MYI 文件里面。 辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件 里面找到磁盘地址，然后到数据文件里面获取数据。

img

3.1.2、InnoDB

InnoDB 只有一个文件（.ibd 文件），那索引放在哪里呢？在 InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文 件是同一个文件，都在.ibd 文件里面。在 InnoDB 的主键索引的叶子节点上，它直接存储了我们的数据。

img

3.2、索引分类

MySQL 的索引有两种分类方式：逻辑分类和物理分类。

3.2.1、逻辑分类

有多种逻辑划分的方式，比如按功能划分，按组成索引的列数划分等

（1）按功能划分

  • 主键索引：一张表只能有一个主键索引，不允许重复、不允许为 NULL；

image-20210923115857766

  • 唯一索引：数据列不允许重复，允许为 NULL 值，一张表可有多个唯一索引，索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须唯一。

    image-20210923115923757

  • 普通索引：一张表可以创建多个普通索引，一个普通索引可以包含多个字段，允许数据重复，允许 NULL 值插入；

    image-20210923115943345

  • 全文索引：它查找的是文本中的关键词，主要用于全文检索。

（2）按列数划分

  • 单例索引：一个索引只包含一个列，一个表可以有多个单例索引。
  • 组合索引：一个组合索引包含两个或两个以上的列。

在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先（查询条件精确匹配索引的左边连续一列或几列，则构建对应列的组合索引树），在检索数据时也从联合索引的最左边开始匹配。

3.2.2、物理分类

分为聚簇索引和非聚簇索引（有时也称辅助索引或二级索引）

（1）聚集索引

聚簇索引（clustered index）不是单独的一种索引类型，而是一种数据存储方式。这种存储方式是依靠B+树来实现的，根据表的主键构造一棵B+树且B+树叶子节点存放的都是表的行记录数据时，方可称该主键索引为聚簇索引。聚簇索引也可理解为将数据存储与索引放到了一块，找到索引也就找到了数据。

在这里插入图片描述

可以看到叶子节点包含了完整的数据记录，这就是聚簇索引。因为InnoDB的数据文件（.idb）按主键聚集，所以InnoDB必须有主键（MyISAM可以没有）。

另一个问题，如果一张表没有主键怎么办？

1、如果我们定义了主键(PRIMARY KEY)，那么 InnoDB 会选择主键作为聚集索引。

2、如果没有显式定义主键，则 InnoDB 会选择第一个不包含有 NULL 值的唯一索引作为主键索引。

3、如果也没有这样的唯一索引，则 InnoDB 会选择内置 6 字节长的 ROWID 作为隐 藏的聚集索引，它会随着行记录的写入而主键递增。

select _rowid name from t2;

所以PK查询非常快，直接定位行记录。

主键索引结构分析：

  • B+树单个叶子节点内的行数据按主键顺序排列，物理空间是连续的（聚簇索引的数据的物理存放顺序与索引顺序是一致的）；
  • 叶子节点之间是通过指针连接，相邻叶子节点的数据在逻辑上也是连续的（根据主键值排序），实际存储时的数据页（叶子节点）可能相距甚远。

（2）非聚簇索引

非聚簇索引：数据和索引是分开的，B+树叶子节点存放的不是数据表的行记录。

在 InnoDB 里面，它组织数据的方式叫做（聚集）索引组织表（clustered index organize table），所以主键索引是聚集索引，非主键都是非聚集索引。 比如我们在 name 字段 上面建的普通索引，又是怎么存储和检索数据的呢？

InnoDB 中，主键索引和辅助索引是有一个主次之分的。

在聚簇索引之外创建的索引（不是根据主键创建的）称之为辅助索引，辅助索引访问数据总是需要二次查找。辅助索引叶子节点存储的不再是行数据记录，而是主键值。首先通过辅助索引找到主键值，然后到主键索引树中通过主键值找到数据行。

img

辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主 键索引中查询，最终取得数据。比如我们用 name 索引查询 name= '青山'，它会在叶子节点找到主键值，也就是 id=1，然后再到主键索引的叶子节点拿到数据。这就是所谓的回表查询，先定位主键值，再定位行记录，它的性能较扫一遍索引树更低。

为什么在辅助索引里面存储的是主键值而不是主键的磁盘地址呢？如果主键的数据 类型比较大，是不是比存地址更消耗空间呢？我们前面说到 B Tree 是怎么实现一个节点存储多个关键字，还保持平衡的呢？是因为有分叉和合并的操作，这个时候键值的地址会发生变化，所以在辅助索引里 面不能存储地址。

（3）MyISAM索引实现

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址

（1）主键索引：

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

img

这里设表一共有三列，假设我们以Col1为主键，图myisam1是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

2）辅助索引（Secondary key）

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

img

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

MyISM使用的是非聚簇索引，非聚簇索引的两棵B+树看上去没什么不同，节点的结构完全一致只是存储的内容不同而已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独立的地方，这两颗B+树的叶子节点都使用一个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独立的，通过辅助键检索无需访问主键的索引树。

为了更形象说明这两种索引的区别，我们假想一个表如下图存储了4行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

img

问题1：主键索引是聚集索引还是非聚集索引？

在Innodb下主键索引是聚集索引，在Myisam下主键索引是非聚集索引

问题2：聚簇索引和非聚簇索引的区别

聚簇索引的叶子节点存放的是主键值和数据行，**支持覆盖索引**；二级索引的叶子节点存放的是主键值或指向数据行的指针。

由于节子节点(数据页)只能按照一颗B+树排序，故**一张表只能有一个聚簇索引**。辅助索引的存在不影响聚簇索引中数据的组织，所以一张表可以有多个辅助索引

（4）覆盖索引

在辅助索引里面，不管是单列索引还是联合索引，如果 select 的数据列只用从索引 中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免 了回表。

如何实现索引覆盖？

常见的方法是：将被查询的字段，建立到联合索引里去。

例子：

create table user (
    id int primary key,
    name varchar(20),
    sex varchar(5),
    index(name)
)engine=innodb;

第一个SQL语句：

imgopen in new window

select id,name from user where name='shenjian';　

能够命中name索引，索引叶子节点存储了主键id，通过name的索引树即可获取id和name，无需回表，符合索引覆盖，效率较高。

第二个SQL语句：

imgopen in new window

select id,name,sex from user where name='shenjian';

能够命中name索引，索引叶子节点存储了主键id，但sex字段必须回表查询才能获取到，不符合索引覆盖，需要再次通过id值扫码聚集索引获取sex字段，效率会降低。

如果把(name)单列索引升级为联合索引(name, sex)就不同了。

create table user (
    id int primary key,
    name varchar(20),
    sex varchar(5),
    index(name, sex)
)engine=innodb;

imgopen in new window

可以看到：

select id,name ... where name='shenjian';
select id,name,sex ... where name='shenjian';

都能够命中索引覆盖，无需回表。

很明显，因为覆盖索引减少了 IO 次数，减少了数据的访问量，可以大大地提升查询 效率。

【引用文章1】open in new window 【引用文章2】open in new window【引用文章3】open in new window

四、数据库范式

为了建立冗余较小、结构合理的数据库，设计数据库时必须遵循一定的规则。在关系型数据库中这种规则就称为范式。范式是符合某一种设计要求的总结。要想设计一个结构合理的关系型数据库，必须满足一定的范式。

在实际开发中最为常见的设计范式有三个：

1．第一范式(确保每列保持原子性)

第一范式是最基本的范式。如果数据库表中的所有字段值都是不可分解的原子值，就说明该数据库表满足了第一范式。

第一范式的合理遵循需要根据系统的实际需求来定。比如某些数据库系统中需要用到“地址”这个属性，本来直接将“地址”属性设计成一个数据库表的字段就行。但是如果系统经常会访问“地址”属性中的“城市”部分，那么就非要将“地址”这个属性重新拆分为省份、城市、详细地址等多个部分进行存储，这样在对地址中某一部分操作的时候将非常方便。这样设计才算满足了数据库的第一范式，如下表所示。

img

上表所示的用户信息遵循了第一范式的要求，这样在对用户使用城市进行分类的时候就非常方便，也提高了数据库的性能。

2．第二范式(确保表中的每列都和主键相关)

第二范式在第一范式的基础之上更进一层。第二范式需要确保数据库表中的每一列都和主键相关，而不能只与主键的某一部分相关（主要针对联合主键而言）。也就是说在一个数据库表中，一个表中只能保存一种数据，不可以把多种数据保存在同一张数据库表中。

比如要设计一个订单信息表，因为订单中可能会有多种商品，所以要将订单编号和商品编号作为数据库表的联合主键，如下表所示。

订单信息表

img

这样就产生一个问题：这个表中是以订单编号和商品编号作为联合主键。这样在该表中商品名称、单位、商品价格等信息不与该表的主键相关，而仅仅是与商品编号相关。所以在这里违反了第二范式的设计原则。

而如果把这个订单信息表进行拆分，把商品信息分离到另一个表中，把订单项目表也分离到另一个表中，就非常完美了。如下所示。

img

这样设计，在很大程度上减小了数据库的冗余。如果要获取订单的商品信息，使用商品编号到商品信息表中查询即可。

3．第三范式(确保每列都和主键列直接相关,而不是间接相关)

第三范式需要确保数据表中的每一列数据都和主键直接相关，而不能间接相关。

比如在设计一个订单数据表的时候，可以将客户编号作为一个外键和订单表建立相应的关系。而不可以在订单表中添加关于客户其它信息（比如姓名、所属公司等）的字段。如下面这两个表所示的设计就是一个满足第三范式的数据库表。

img

这样在查询订单信息的时候，就可以使用客户编号来引用客户信息表中的记录，也不必在订单信息表中多次输入客户信息的内容，减小了数据冗余。

五、MVVC

MVCC(Multi Version Concurrency Control的简称)，代表多版本并发控制。与MVCC相对的，是基于锁的并发控制，Lock-Based Concurrency Control)。 MVCC最大的优势：读不加锁，读写不冲突。在读多写少的OLTP应用中，读写不冲突是非常重要的，极大的增加了系统的并发性能

5.1、MYSQL 事务日志

事务日志可以帮助提高事务的效率。使用事务日志，存储引擎在修改表的数据时只需要修改其内存拷贝，再把该修改行为记录到持久在硬盘上的事务日志中，而不用每次都将修改的数据本身持久到磁盘。事务日志采用的是追加的方式，因此写日志的操作是磁盘上一小块区域内的顺序I/O，而不像随机I/O需要在磁盘的多个地方移动磁头，所以采用事务日志的方式相对来说要快得多。事务日志持久以后，内存中被修改的数据在后台可以慢慢地刷回到磁盘。目前大多数存储引擎都是这样实现的，我们通常称之为预写式日志（Write-Ahead Logging），修改数据需要写两次磁盘。 如果数据的修改已经记录到事务日志并持久化，但数据本身还没有写回磁盘，此时系统崩溃，存储引擎在重启时能够自动恢复这部分修改的数据。

MySQL Innodb中跟数据持久性、一致性有关的日志，有以下几种：

  • Bin Log:是mysql服务层产生的日志，常用来进行数据恢复、数据库复制，常见的mysql主从架构，就是采用slave同步master的binlog实现的
  • Redo Log:记录了数据操作在物理层面的修改，mysql中使用了大量缓存，修改操作时会直接修改内存，而不是立刻修改磁盘，事务进行中时会不断的产生redo log，在事务提交时进行一次flush操作，保存到磁盘中。当数据库或主机失效重启时，会根据redo log进行数据的恢复，如果redo log中有事务提交，则进行事务提交修改数据。
  • Undo Log: 除了记录redo log外，当进行数据修改时还会记录undo log，undo log用于数据的撤回操作，它记录了修改的反向操作，比如，插入对应删除，修改对应修改为原来的数据，通过undo log可以实现事务回滚，并且可以根据undo log回溯到某个特定的版本的数据，实现MVCC。

5.2、MVCC实现

MVCC是通过在每行记录后面保存两个隐藏的列来实现的。这两个列，一个保存了行的创建时间，一个保存行的过期时间（或删除时间）。当然存储的并不是实际的时间值，而是系统版本号（system version number)。每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来和查询到的每行记录的版本号进行比较。 下面看一下在REPEATABLE READ隔离级别下，MVCC具体是如何操作的。

  • SELECT

    InnoDB会根据以下两个条件检查每行记录：

    1. InnoDB只查找版本早于当前事务版本的数据行（也就是，行的系统版本号小于或等于事务的系统版本号），这样可以确保事务读取的行，要么是在事务开始前已经存在的，要么是事务自身插入或者修改过的。
    2. 行的删除版本要么未定义，要么大于当前事务版本号。这可以确保事务读取到的行，在事务开始之前未被删除。

    只有符合上述两个条件的记录，才能返回作为查询结果

  • INSERT

    InnoDB为新插入的每一行保存当前系统版本号作为行版本号。

  • DELETE

    InnoDB为删除的每一行保存当前系统版本号作为行删除标识。

  • UPDATE

    InnoDB为插入一行新记录，保存当前系统版本号作为行版本号，同时保存当前系统版本号到原来的行作为行删除标识。 保存这两个额外系统版本号，使大多数读操作都可以不用加锁。这样设计使得读数据操作很简单，性能很好，并且也能保证只会读取到符合标准的行，不足之处是每行记录都需要额外的存储空间，需要做更多的行检查工作，以及一些额外的维护工作

举例说明

create table mvcctest( 
id int primary key auto_increment, 
name varchar(20));

transaction 1:

start transaction;
insert into mvcctest values(NULL,'mi');
insert into mvcctest values(NULL,'kong');
commit;

假设系统初始事务ID为1；

IDNAME创建时间过期时间
1mi1undefined
2kong1undefined

transaction 2:

start transaction;
select * from mvcctest;  //(1)
select * from mvcctest;  //(2)
commit

SELECT

假设当执行事务2的过程中，准备执行语句(2)时，开始执行事务3：

transaction 3:

start transaction;
insert into mvcctest values(NULL,'qu');
commit;
IDNAME创建时间过期时间
1mi1undefined
2kong1undefined
3qu3undefined

事务3执行完毕，开始执行事务2 语句2，由于事务2只能查询创建时间小于等于2的，所以事务3新增的记录在事务2中是查不出来的，这就通过乐观锁的方式避免了幻读的产生

UPDATE

假设当执行事务2的过程中，准备执行语句(2)时，开始执行事务4：

transaction session 4:

start transaction;
update mvcctest set name = 'fan' where id = 2;
commit;

InnoDB执行UPDATE，实际上是新插入了一行记录，并保存其创建时间为当前事务的ID，同时保存当前事务ID到要UPDATE的行的删除时间

IDNAME创建时间过期时间
1mi1undefined
2kong14
2fan4undefined

事务4执行完毕，开始执行事务2 语句2，由于事务2只能查询创建时间小于等于2的，所以事务修改的记录在事务2中是查不出来的，这样就保证了事务在两次读取时读取到的数据的状态是一致的

DELETE

假设当执行事务2的过程中，准备执行语句(2)时，开始执行事务5：

transaction session 5:

start transaction;
delete from mvcctest where id = 2;
commit;
IDNAME创建时间过期时间
1mi1undefined
2kong15

事务5执行完毕，开始执行事务2 语句2，由于事务2只能查询创建时间小于等于2、并且过期时间大于等于2，所以id=2的记录在事务2 语句2中，也是可以查出来的,这样就保证了事务在两次读取时读取到的数据的状态是一致的