02-数据库

数据库

数据库架构

数据库的架构有一个存储模块，用来将数据持久化到磁盘中，因为需要组织这些数据，所以需要一个程序实例，用逻辑结构映射物理结构，在程序实例中

需要对数据的格式和文件风格进行统一管理的储管理模块
需要执行 SQL 的 SQL 解析器模块
需要减少 IO 操作、提高 SQL 编译的性能的缓存机制模块
需要数据库的主从同步和灾难恢复的日志管理模块和容灾机制模块
需要对危险操作加上一定的权限的权限划分模块
需要提高数据库的查询效率和并发效率的索引模块和锁模块

索引的数据结构

索引类似与字典目录，依靠目录中的关键信息，可以快速定位到要查询的数据，在数据量很大的情况下要避免全表扫描的发生，提高查询效率，一般主键、唯一键、普通键都可以作为索引

可以作为索引的数据结构有 hash、位图，二叉查找树，以及二叉查找树的变种 AVL 树、红黑树、B 树、B+树

二叉查找树、AVL 树、红黑树缺点是，只有两个子节点，假设所有节点都在磁盘中，每次搜索就都需要 IO 操作
MySQL 的 InnoDB 和 MyISAM 存储引擎不显示支持 hash 索引，hash 索引只需要经过 hash 计算，通过一次定位，就可以查询出数据所在的头节点
- 但是仅仅只能满足等值查询，不能用于范围查询
- 不能利用索引来避免排序操作和表扫描
- 也不能利用组合索引来进行部分索引的查询
- 当有大量的 hash 冲突时性能会受到影响
B 树（平衡多路查找树），他的定义是
- 树中每个节点最多包含 M 个孩子其中 M>=2，就是 M 阶的 B 树
- 根节点至少包括两个孩子，其他节点至少有 M/2 向上取整个孩子
- 所有叶子节点都位于同一层
- 单个节点中的关键字信息是升序排列的，并且个数比孩子的个数少一
- 子节点中所有关键字信息，都位于父节点关键字信息的间隙
B+树是 B 树的变体，在 B 树的基础上新增了一些限制
- 非叶子节点的孩子个数与关键字个数相同
- 非叶子节点只是用来做索引，数据都保存在叶子节点中
- 所有叶子节点都有一个链指针指，向下一个叶子节点

所以 B+树相对于其他数据结构在文件系统、数据库系统中更又优势

B+树对磁盘读写的代价更低，因为 B+树非叶子节点只存放索引信息，所以内部节点相对 B 树更小
B+树的查询效率更加稳定，因为叶子节点才存放数据，所以每次查询都需要从根节点开始，搜索到叶子节点
B+树更有利于对数据库的表扫描，因为叶子节点都有一个链指指针，指向下一个叶子节点，所以扫描所有叶子节点，就可以对数据库进行表扫描，更利于范围查询

MySQL 数据库不支持位图索引，但是 Oracle 支持，当一个字段只有几种值的时候，如果只是为了对该字段做高效的统计查询就可使用，结构类似与 B+树

叶子节点包含指定的位图段，就是不同值的种类
使用 01 比特串表示某行是否为该值

位图索引在修改的时候，在同一个位图上的其他操作都会被锁住，因为某行所在的位置顺序，有可能会因为数据的添加或删除，而发生改变，所以并不适合高并发的场景

密集索引和稀疏索引的区别

密集索引中每个搜索码的值都对应一个索引值，稀疏索引只对部分索引码的值建立索引

MySQL 的 InnoDB 存储引擎规定只有一个密集索引，索引和数据存放在同一个文件

如果有主键，主键就是密集索引
如果没有主键，那第一个非空索引就是密集索引
如果都没有，会生成一个隐藏主键作为密集索引

InnoDB 稀疏索引的叶子节点存储的是该行的主键值，所以在对非主键所以查询时，就包含了查找索引自身和查找主键两次查找，而 MyISAM 使用的都是稀疏索引，主键索引和非主键索引是相互独立的，索引和数据存放在不同的文件

联合索引前缀匹配原则的原因

MySQL 支持复合索引的前缀查询，MySQL 会一直向后匹配，直到遇到范围或模糊查询，才会停止匹配，等值匹配可以乱序，MySQL 查询优化器会进行顺序优化

MySQL 创建复合索引的规则是，首先对第一个字段进行排序，在第一个字段的排序基础上，再对第二个字段进行排序，以此类推，所以第一个字段是绝对有序的，而后面字段就可能不是有序的

如何定位并优化慢查询 SQL

可使用 MySQL 自带的工具或其他分析工具，根据慢日志定位慢查询 SQL
通过查看 SQL 的执行计划分析 SQL
修改 SQL 或尽量让 SQL 走索引

当数据量很小时无需建立索引，否则会增加额外索引查询和索引空间开销，并且数据的变更时也需要维护索引

MyISAM 和 InnoDB 的关于锁方面的区别

MyISAM 不支持事务，InnoDB 支持事务
MyISAM 默认用的是表级锁，不支持行级锁，InnoDB 默认是行级锁，也支持表级锁
- MyISAM 默认就为表增加了锁，也可以显示加锁解锁（lock tables 表名 read | write 语句增加共享锁或排他锁，unlock tables 解锁语句）
- InnoDB 如果没用到索引，就是使用的是表级锁，如果使用到索引，就使用的是行级锁或者 GAP 锁（在查询语句后显示增加 lock in share mode 或 for update 可增加行级共享锁或排他锁）
MyISAM 适合频繁执行全表 count 语句，因为 MyISAM 使用变量保存了表的具体行数，而 InnoDB 没有
MyISAM 还适合对数据增删改的频率不高，但对查询非常频繁，因为只支持表级锁、不支持密集索引
InnoDB 适合数据增删改查都频繁的场景，因为支持行级锁，所以大多数情况下可避免阻塞

数据库锁的分类

按照锁的粒度划分可分为表级锁、行级锁
按照锁的级别划分可分为[共享锁、排他锁](# 锁的分类)
按照加锁方式划分可分为自动锁、显示锁
按照操作划分可分为 DML 锁、DDL 锁
按照使用方式划分可分为乐观锁、悲观锁

数据库事务四大特性

只有 DML 才有事务机制的 ACID 原则

A：原子性：事务是最小的工作单元，不可再分
C：一致性：事务中多条 DML 语句同时成功或失败
I：隔离性：不同事务之间相互隔离
D：持久性：数据持久化到硬盘之后，事务才结束

隔离级别

更新已提交：两个事务对同一数据更新操作，都提交后，存在丢失更新现象，是应用程序层面的问题
读未提交（read uncommitted）：存在脏读现象（dirty read）另一个事务未提交，当前事务可以读另一个事务未提交数据
读已提交（read committed）：另一个事务提交后，当前事务就能读到，存在不可重复读现象（not repeatable read）相对于幻读侧重于对同一个数据的修改
可重复读（repeatable read）：不管另一个事务怎么修改，当前事务总是读到，开启事务时的数据没被修改过的状态，存在幻影读现象（phantom read），相对于不可重复读侧重于对数据条数增加和删除
序列化读（serializable）：事务排队执行，效率低

InnoDB 可重复读如何避免幻读

表面上是基于当前读和快照读两种操作，实际上是事务对数据加了 next-key 锁（行锁+间隙 GAP 锁）

当前读是，在查询语句后加 lock in share mode 或 for update，还有增删改语句，简单点说就是加了锁的增删改查语句，当前读读取的是记录的最新版本，同时还要保证其他并发事务不能修改当前读读到的记录，会对读取的记录进行加锁
快照读是，不加锁的查询语句，通过基于伪 MVCC（多版本并发控制机制）实现，避免了加锁操作，伪是因为没有多版本共存，由于是基于多版本，所以快照读可能读到的是数据的历史版本
GAP 是索引树中插入新记录的空隙，GAP 锁锁定的是一个范围，但不包括记录本身，GAP 锁的的分布是根据索引数据进行划分（左开右闭区间，这个区间还和主键有点关系）GAP 锁的目的是防止同一个事务进行两次当前读，从而解决幻读

在可重复读隔离级别下

当前读用到主键或唯一索引时，如果 where 条件全部命中，就是 where 条件中的记录都可以查到，只会加行锁，否则会加 GAP 锁
- 因为索引具有唯一性，就算当前事务使用这个索引去做当前读，另一个事务新增的数据，也一定会在当前读的范围之外，并不会产生幻读，所以只需要加行锁
如果用到非唯一索引，就会对要修改的周边加 GAP 锁
如果没用到索引，就会对全部间隙都加上 GAP 锁，因该避免这种情况

InnoDB 在读已提交和可重复读非阻塞读如何实现

每行数据除了存储数据外，还有一些隐藏字段，比如

最后一次事务修改的事务 ID（DB_TRX_ID）
指向 undo 日志链的回滚指针（DB_ROLL_PTR）
隐藏的自增的行号 ID（DB_ROW_ID，可能会被 InnoDB 作为密集索引）

对记录做了更新操作时，就会产生 undo 记录（旧数据），并加入到 undo 日志中，如果旧事务想要读旧数据时，就会顺着 undo 链找到满足该事务可见性的旧记录，undo 日志主要分为

Insert undo log：只在事务回滚时需要，事务提交后会被丢弃
Update undo log：在事务 delete 或 update 中产生的日志，在事务回滚时需要，在快照读中也需要，所以只有在数据库的所有快照读都不需要该记录时，才会被丢弃

当去执行快照读时，会根据查询数据创建出一个 read view，来决定当前事务能看到的是那个版本数据，read view 遵循可见性算法，将数据的事务修改 ID 与系统中其他活跃事务 ID 做对比，因为事务 ID 是根据开启时间而递增的，所以如果不小于这些活跃事务 ID，就通过回滚指针，取出 undo 日志中上一层记录的事务修改 ID，直到小于这些活跃事务 ID 为止，从而保证数据是当前可见版本