# 1 树的升级
## 二叉树
**优点**: 可以通过二分法快速查询。
**缺点**: 树的深度太深,容易形成链表。
## 平衡二叉树
**优点**: 优化了二叉树深度问题,最长子树的节点和最最短相差1个节点。
**缺点**: 为了维持树的平衡,需要频繁的旋转树。
## 红黑树
**优点**: 为了优化平衡二叉树频繁的旋转,修改了最长子树和最短子树相差节点为2倍,并且每条树路径上的黑色节点数一样,减少了旋转次数。
**缺点**: 还是深度太深,二叉树都不适用大数据查询。
## b树
**优点**: 适合存储大数据文件,树结构改动小。
**缺点**: 进行范围查找等,还需要跳层查找。
## b+树(mysql结构)
**优点**:根节点不存储数据,可以有跟多的数据指向。叶子节点为有序列表,解决跳层查找的问题。
## b*树
**优点**: 父节点也有了链表结构,提高了查询速度。
# 2 引擎
## MyISAM
- 只有表级锁(table-level locking)
- 不提供事务支持。
- 不支持外键
- 不支持数据恢复
## Innodb
- 支持行级锁(row-level locking)和表级锁, 默认为行级锁。
- 提供事务支持,具有提交(commit)和回滚(rollback)事务的能力。
- 支持外键
- 支持数据恢复,通过redo log(重做日志)保证事物持久性,undo log(回滚日志)保证事物原子性。
- MVCC:一个更新版本,一个删除版本
# 3 索引
在mysql文件中可以看到,Innodb索引为一个文件。MyIsam的索引文件为三个。
## 索引分类
- hash:
- 会产生hash冲突
- Hash索引不支持顺序和范围查询(Hash 索引不支持顺序和范围查询是它最大的缺点。
- B树: 节点存放data和key,导致key的指针容量变少,分叉变少
- B+树: 父节点只存放key,叶子节点存放data,并且是有序双向链表,在查询效率上比B树高,因为B树的范围查询需要回溯父节点。
## 聚簇索引和非聚簇索引
- **聚簇索引**:数据和索引存放在一起的为聚簇索引。
- 缺点:更新数据比较慢,因为需要更新索引
- **非聚簇索引**:数据和索引分开存放的为非聚簇索引。
- 缺点:会产生回表
## 索引优化
**索引覆盖**: 如果查询结果没有被索引覆盖,会出现回表。
**索引下推**: 在联合索引中,5.7版本之后引入了索引下推,查询更快。
**谓词下推**: join查询等,先过滤,在join。
**最左前缀**: 在构建索引中,要按照最左前缀构建(ABC:A,AB,ABC),并且要按照业务,把数据结构所占字节小的可以设置为单个索引。
## 索引失效
- 不遵循最左匹配原则
- 范围查询(<>,like)后的索引会失效
- 索引做计算,函数,类型转换会失效
- is null 和 is not null 无法使用
- like 语句%开头的会失效,%结尾没有影响
- or 可能会导致合并数据的时候失效
# 4 InnoDB 锁
- 表锁
- 默认隐式
- 显式通过for update加表锁
- Record lock:单个行记录上的锁
- 只有通过索引条件检索数据,InnoDB 才使用行级锁,否则,InnoDB 将使用表锁!不论是使用主键索引、唯一索引或普通索引,InnoDB 都会使用行锁来对数据加锁。
- Gap lock:间隙锁,锁定一个范围,不包括记录本身
- 当我们用范围条件而不是相等条件检索数据,并请求共享或排他锁时,InnoDB会给符合条件的已有数据记录的索引项加锁;对于键值在条件范围内但并不存在的记录,叫做“间隙(GAP)”,InnoDB也会对这个“间隙”加锁,这种锁机制就是所谓的间隙锁(Next-Key锁)。
- 很显然,在使用范围条件检索并锁定记录时,InnoDB这种加锁机制会阻塞符合条件范围内键值的并发插入,这往往会造成严重的锁等待。因此,在实际应用开发中,尤其是并发插入比较多的应用,我们要尽量优化业务逻辑,尽量使用相等条件来访问更新数据,避免使用范围条件。
## 显式锁定
```sql
select ... lock in share mode //共享锁
select ... for update //排他锁
```
# 5 事物
## 什么是事物?
要么全都不执行,要么全都执行。
## 事物带来的问题?
- 脏读(Dirty read): 当一个事务正在访问数据并且对数据进行了修改,而这种修改还没有提交到数据库中,这时另外一个事务也访问了这个数据,然后使用了这个数据。因为这个数据是还没有提交的数据,那么另外一个事务读到的这个数据是“脏数据”,依据“脏数据”所做的操作可能是不正确的。
- 丢失修改(Lost to modify): 指在一个事务读取一个数据时,另外一个事务也访问了该数据,那么在第一个事务中修改了这个数据后,第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失,因此称为丢失修改。 例如:事务 1 读取某表中的数据 A=20,事务 2 也读取 A=20,事务 1 修改 A=A-1,事务 2 也修改 A=A-1,最终结果 A=19,事务 1 的修改被丢失。
- 不可重复读(Unrepeatableread): 指在一个事务内多次读同一数据。在这个事务还没有结束时,另一个事务也访问该数据。那么,在第一个事务中的两次读数据之间,由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况,因此称为不可重复读。
- 幻读(Phantom read): 幻读与不可重复读类似。它发生在一个事务(T1)读取了几行数据,接着另一个并发事务(T2)插入了一些数据时。在随后的查询中,第一个事务(T1)就会发现多了一些原本不存在的记录,就好像发生了幻觉一样,所以称为幻读。
## 事物分类
- read uncommit:最低的隔离级别,允许读取尚未提交的数据变更,可能会导致脏读、幻读或不可重复读。
- read commit:允许读取并发事务已经提交的数据,可以阻止脏读,但是幻读或不可重复读仍有可能发生。
- repeat read(mysql默认):对同一字段的多次读取结果都是一致的,除非数据是被本身事务自己所修改,可以阻止脏读和不可重复读,但幻读仍有可能发生。
- serialize:最高的隔离级别,完全服从 ACID 的隔离级别。所有的事务依次逐个执行,这样事务之间就完全不可能产生干扰,也就是说,该级别可以防止脏读、不可重复读以及幻读。
## 各种事物的应用
MySQL InnoDB 的 REPEATABLE-READ(可重读)并不保证避免幻读,需要应用使用加锁读来保证。而这个加锁度使用到的机制就是 Next-Key Locks。
因为隔离级别越低,事务请求的锁越少,所以大部分数据库系统的隔离级别都是 READ-COMMITTED(读取提交内容) ,但是你要知道的是 InnoDB 存储引擎默认使用 REPEAaTABLE-READ(可重读) 并不会有任何性能损失。
InnoDB 存储引擎在 分布式事务 的情况下一般会用到 SERIALIZABLE(可串行化) 隔离级别。
# 6 集群
## 模式分类
- MMM: Master-Master replication manager for MySQL
- 一套支持双主故障切换和双主日常管理的脚本程序
- 实现故障切换和多slave的read负载均衡
- MMM无法完全保证数据一致性;monitor为单节点(可以结合keepalive实现高可用);不支持分片
- MHA: Master High Availability
- 分MHA Manager和MHA Node,一般一主多从,主down备同步主数据后升级为主;
- 故障切换时间0-30s
- 如果主机硬件故障,则只进行故障转移,可能丢失最新数据;不支持分片
- MGR: MySQL Group Replication
- 基于分布式paxos协议实现组复制,保证数据一致性。
- 自动检测机制,只要不是大多数节点都宕机就可以继续工作,内置防脑裂保护机制。
- 节点的增加与移除会自动更新组成员信息,新节点加入后,自动从其他节点同步增量数据,直到与其他节点数据一致。
- 提供单主模式和多主模式,单主模式在主库宕机后能够自动选主,所有写入都在主节点进行,多主模式支持多节点写入。
## 主从复制
- binlog(二进制日志文件):io thread 定时访问master的binlog,发生变化后,把变化的数据放入slave的relayLog中,然后由sql thread执行sql。
- relayLog:解决顺序io和随机io,解决安全问题
- MTS:mysql5.7后使用了MTS并行复制,解决主从同步延时。
# 7 分库分表
- 水平分库:一般不考虑
- 垂直分库:按照业务分库
- 水平分表:按照索引来进行水平分,例如id,age等
- 垂直分表:按照业务,拆分业务
- 冷热数据分离:
# 8 中间件
- mycat
- sharding-shark
- sharding-sphere
# 9 其他
## 内置查询优化工具(profile, explain)
```sql
# 开启profile
set profiling=1
# 执行的sql
# 查看profiles
show profiles;
# 查看profile详情
show profiles for Query #{id};
# 查看当前运行sql的状态
show processlist
# sql的预分析
explain (sql)
# select_type :区分查询类型
# type:判断查询快慢的,const最快,最少也要是range,all最慢。
# key:查询中用到的索引
# key_len:索引的长度,根据索引类型计算的。
# rows: 实际查询的行数。
# Extra:额外信息,例如:Using where。
# 显示的行数越少越好(步数越少越好)。
```
## SQL优化
- in 和 or的查询速度差不多,union all 最慢。
- exist中必须是一个子查询。for循环每一行去exist中判断。
- 范围列可以用到索引,但是范围列后面的列无法用到索引,索引最多用于一个范围列。
- 强制类型转换会全表扫描,例如:int类型,where num='123',这样就不会用索引。
- 更新十分频繁的字段,不宜建立索引,b+树维护成本高。
- 创建索引的列,不允许为null。
- 如果预期知道有一条结果,可以用limit 1提高效率,慎用limit进行大数据查询,指针会扫描前面全部的数据行。
- 单表索引建议控制在5个以内,否则树查询速度会变慢。
## 索引监控
```
# 显示索引的监控语句
show status like 'Handler_read%'
# 详细列表
1 / Handle_read_first / 3
2 / Handle_read_key / 15
3 / Handle_read_last / 0
4 / Handle_read_next / 0
5 / Handle_read_prev / 0
6 / Handle_read_rnd / 0
7 / Handle_read_rnd_next / 1355
# 主要看2 和 7 如果这两个值没有数据,则索引使用率很差。
```

Mysql 篇(冲向架构师)