[数据结构与算法]08MySql索引

表和数

哈希表（哈希冲突）：

? 哈希表可以完成索引的存储，每次添加索引得时候，需要指定列得hash值，取模运算后计算下标，将元素插入下标位置即可。

? 适合场景：

? 等值查询

? 表中得数据是无序数据（范围查找得时候比较浪费时间，需要挨个进行遍历操作）。在企业中多数是范围查询，所以此时hash表不是特别适合，

hash表在使用得时候，需要将全部得数据加载到内存，比较耗费内存的空间，也不是很合适

树：

多叉树，二叉树（二分查找），AVL树（平衡树），红黑树

【在树的结构中，左子树必须小于根节点，右子树必须大于跟节点，如果是多叉树的话，从左到有是有序的】

AVL树：是一颗严格意义的平衡树，最高子树跟最低子树高度只差不能超过1，因此在进行元素插入的时候，会进行 1-N 次旋转，因此严重影响插入的性能。

红黑树：是基于AVL树的一个升级，损失了部分查询的性能，来提升插入的性能，在红黑树中最低子树跟最高子树之差，小于两倍即可，在插入的时候，不需要进行N多次的旋转操作，而且加入了变色的特性，来满足插入和查询的性能平衡

二叉树及其N多的变种，都不能支撑索引，原因在于，树的深度无法控制，或者插入数据的性能比较低

B树

B树的特点：

1. 所以键值分布在整颗树中
2. 搜索有可能在非叶子结点结束，在关键字内做一次查找，性能逼近二分查找
3. 每个节点最多拥有m个子树
4. 根节点至少有2个子树
5. 分支节点只要拥有m/2棵子树（除根节点和叶子节点都是分支节点）
6. 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排序

缺点：

1. 每个节点都有key，同时也包含了data，而每个页存储空间有限，如果data比较大的话会导致每个节点存储的key数量变小
2. 当村粗的数据量很大的时候会导致深度较大，增大查询的磁盘的io次数，进而影响查询性能

B+树

B+Tree是在B Tree的基础之上做的一种优化，变化如下：

1. B+Tree每个节点可以包含更多的节点，这个做的原因有两个
   1. 为了降低树的高度
   2. 将数据范围变为多个区间，区间越多，数据检索越快
2. 非叶子节点存储key，叶子节点存储key和数据
3. 叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查询性更高

注意：在B+Tree 上有两个头指针，一个指向根节点，另一个指向关系最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构，因此可以对 B+Tree 进行两种查找运算

• 对于主键的范围查找和分页查找
• 从根节点开始，进行随机查找

MySql存储引擎

mysql InnoDB–B+Tree

? 叶子节点直接放置数据 【回表】

注意：

1. InnoDB是通过B+Tree结构对主键创建索引，然后叶子节点存储记录，如果没有主键，那么会选择唯一键，如果没有唯一键，那么会生成一个6位的row_id来作为主键
2. 如果创建索引是其他字段，那么在叶子节点存储时该记录的主键，然后再通过主键索引找到相应的记录，叫做回表

数据结构学习网站

https://www.geeksforgeeks.org
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
https://visualgo.net/zh

mysql MyISAM --B+Tree

叶子节点存放的地址，对应的data数据

索引的分类

? ：主键索引、唯一索引、普通索引和全文索引、组合索引

• 主键索引

  – 主键是一种唯一性索引，但它必须指定为PRIMARY KEY，每个表只能有一个主键。

• 唯一索引

  – 索引列的所有值都只能出现一次，即必须唯一，值可以为空。

• 普通索引

  – 基本的索引类型，值可以为空，没有唯一性的限制。（覆盖索引）

• 全文索引

  – 全文索引的索引类型为FULLTEXT。全文索引可以在varchar、char、text类型的列上创建。检索“关键字”

• 组合索引

  – 多列值组成一个索引，专门用于组合搜索（最左匹配原则）

索引维护

? 索引在插入新的值的时候，为了维护索引的有序性，必须要维护， 在维护索引的时候需要需要分以下集中情况：

– 1、如果插入一个比较大的值，直接插入即可，几乎没有成本

– 2、如果插入的是中间的某一个值，需要逻辑上移动后续的元素，空出位置

– 3、如果需要插入的数据页满了，就需要单独申请一个新的数据页，然后移 动部分数据过去，叫做页分裂，此时性能会受影响同时空间的使用率也会降 低，除了页分裂之外还包含页合并

? 尽量使用自增主键作为索

MySQL架构

连接器

? 连接器负责跟客户端建立连接，获取权限、维持和管理连接

– 用户名密码验证

– 查询权限信息，分配对应的权限

– 可以使用show processlist查看现在的连接

– 如果太长时间没有动静，就会自动断开，通过wait_timeout控制，默认8小时

? 连接可以分为两类：

– 长连接：推荐使用，但是要周期性的断开长连接

– 短链接:

查询缓存

? 当执行查询语句的时候，会先去查询缓存中查看结果，之前执行 过的sql语句及其结果可能以key-value的形式存储在缓存中，如 果能找到则直接返回，如果找不到，就继续执行后续的阶段。

? ? 但是，不推荐使用查询缓存：

– 1、查询缓存的失效比较频繁，只要表更新，缓存就会清空

– 2、缓存对应新更新的数据命中率比较低

分析器

? 词法分析：Mysql需要把输入的字符串进行识别每个部分代表什 么意思

– 把字符串 T 识别成 表名 T

– 把字符串 ID 识别成 列ID

? 语法分析：

? 根据语法规则判断这个sql语句是否满足mysql的语法，如果不符 合就会报错“You have an error in your SQL synta”

优化器

? 在具体执行SQL语句之前，要先经过优化器的处理

? – 当表中有多个索引的时候，决定用哪个索引

	– 当sql语句需要做多表关联的时候，决定表的连接顺序 

? – 等等

? 不同的执行方式对SQL语句的执行效率影响很大

? – RBO:基于规则的优化

? – CBO:基于成本的优化

日志

Redo日志–innodb存储引擎日志文件 【前滚】

• 当发生数据修改的时候，innodb引擎会先将记录写到redo log中， 并更新内存，此时更新就算是完成了，同时innodb引擎会在合适 的时机将记录操作到磁盘中
• Redolog是固定大小的，是循环写的过程
• 有了redolog之后，innodb就可以保证即使数据库发生异常重启， 之前的记录也不会丢失，叫做crash-safe

Undo log 【回滚】

• Undo Log是为了实现事务的原子性，在MySQL数据库InnoDB存储引擎中， 还用Undo Log来实现多版本并发控制(简称：MVCC)
• 在操作任何数据之前，首先将数据备份到一个地方（这个存储数据备份的地方 称为Undo Log）。然后进行数据的修改。如果出现了错误或者用户执行了 ROLLBACK语句，系统可以利用Undo Log中的备份将数据恢复到事务开始之 前的状态

注意：undo log是逻辑日志，可以理解为：

? – 当delete一条记录时，undo log中会记录一条对应的insert记录

? – 当insert一条记录时，undo log中会记录一条对应的delete记录

? – 当update一条记录时，它记录一条对应相反的update记录

回滚到原来状态

binlog–服务端的日志文件

归档日志，或者二进制日志

? Binlog是server层的日志，主要做mysql功能层面的事情

? 与redo日志的区别:

? – 1、redo是innodb独有的，binlog是所有引擎都可以使用的

? – 2、redo是物理日志，记录的是在某个数据页上做了什么修改，binlog是逻 辑日志，记录的是这个语句的原始逻辑

? – 3、redo是循环写的，空间会用完，binlog是可以追加写的，不会覆盖之前 的日志信息

• Binlog中会记录所有的逻辑，并且采用追加写的方式
• 一般在企业中数据库会有备份系统，可以定期执行备份，备份的 周期可以自己设置

恢复数据的过程：

1. 找到最近一次的全量备份数据
2. 从备份的时间点开始，将备份的binlog取出来，重放到要恢复的那个时刻

执行顺序

1. 执行器先从引擎中找到数据，如果在 内存中直接返回，如果不在内存中，查 询后返回
2. 执行器拿到数据之后会先修改数据， 然后调用引擎接口重新吸入数据
3. 引擎将数据更新到内存，同时写数据 到redo中，此时处于prepare阶段，并通 知执行器执行完成，随时可以操作
4. 执行器生成这个操作的binlog
5. 执行器调用引擎的事务提交接口，引 擎把刚刚写完的redo改成commit状态， 更新完成

Redo loh 的两阶段提交

? ? 先写redo log后写binlog:假设在redo log写完，binlog还没有写完的时候，MySQL进程 异常重启。由于我们前面说过的，redo log写完之后，系统即使崩溃，仍然能够把数据恢复 回来，所以恢复后这一行c的值是1。但是由于binlog没写完就crash了，这时候binlog里面 就没有记录这个语句。因此，之后备份日志的时候，存起来的binlog里面就没有这条语句。 然后你会发现，如果需要用这个binlog来恢复临时库的话，由于这个语句的binlog丢失，这 个临时库就会少了这一次更新，恢复出来的这一行c的值就是0，与原库的值不同。

? ? 先写binlog后写redo log:如果在binlog写完之后crash，由于redo log还没写，崩溃恢复 以后这个事务无效，所以这一行c的值是0。但是binlog里面已经记录了“把c从0改成1”这个 日志。所以，在之后用binlog来恢复的时候就多了一个事务出来，恢复出来的这一行c的值 就是1，与原库的值不同
备份日志的时候，存起来的binlog里面就没有这条语句。 然后你会发现，如果需要用这个binlog来恢复临时库的话，由于这个语句的binlog丢失，这 个临时库就会少了这一次更新，恢复出来的这一行c的值就是0，与原库的值不同。

? ? 先写binlog后写redo log:如果在binlog写完之后crash，由于redo log还没写，崩溃恢复 以后这个事务无效，所以这一行c的值是0。但是binlog里面已经记录了“把c从0改成1”这个 日志。所以，在之后用binlog来恢复的时候就多了一个事务出来，恢复出来的这一行c的值 就是1，与原库的值不同