MySQL学习记录(三)

2022-12-23 07:24:31

这一部分主要记录一下MySQL的一些本身的知识。

1、B树、B+树、红黑树

1、B Tree

B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。
M=3 的 B树：
MySQL学习记录(三)

B树（B-树）
   是一种多路搜索树（并不是二叉的）：
   1.定义任意非叶子结点最多只有M个儿子；且M>2；
   2.根结点的儿子数为[2, M]；
   3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
   4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
   5.非叶子结点的关键字个数=指向儿子的指针个数-1；
   6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
   7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
   8.所有叶子结点位于同一层；

2、B+ Tree

B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。
M = 3 的B+树：
MySQL学习记录(三)

B+树是B-树的变体，也是一种多路搜索树：
   1.其定义基本与B-树同，除了：
   		2.非叶子结点的子树指针与关键字个数相同；
   		3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
   		5.为所有叶子结点增加一个链指针；
   		6.所有关键字都在叶子结点出现；

操作B+树：

进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。
直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，
需要对树进行分裂、合并、旋转等操作来维护平衡性。

3、红黑树：红黑树

红黑树是自平衡的二叉查找树，进行插入、删除等可能破坏树的平衡的操作时，需重新自处理达到平衡状态。满足以下性质：

1、每个节点要么黑色，要么红色。
2、根节点是黑色。
3、每个叶子节点是黑色。
4、每个红色节点的两个子节点一定都是黑色。
5、任意一节点到每个叶子节点的路径包含数量相同的黑色节点。
5.1、如果一个节点存在黑色子节点，那么该节点肯定有两个子节点。

自平衡的三种操作：

1、左旋：
	以某个结点作为支点-旋转节点，其右子节点变为旋转节点的父节点。
	右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。
2、右旋：
	以某个节点作为支点-旋转节点，其左子节点变为旋转节点的父节点。
	左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变。
3、变色：节点的颜色由红变黑或由黑变好。

MySQL学习记录(三)

B+ 树与红黑树对比：

红黑树等平衡树也可以实现索引，但是文件系统及数据库系统普遍使用B+ 树作为索引结构，因为使用B+树访问磁盘数据性能更高。

1、B+ 树有更低的树高
平衡树的树高 O(h)=O(logdN)，其中 d 为每个节点的出度。红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多。

2、磁盘访问原理
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。

如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+ 树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以 B+ 树更适合磁盘数据的读取。

3、磁盘预读特性
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入。

2、MyISAM和InnoDB存储引擎

InnoDB

1、是 MySQL 默认的事务型存储引擎，只有在需要它不支持的特性时，才考虑使用其它存储引擎。
2、实现了四个标准的隔离级别，默认级别是可重复读（REPEATABLE READ）。
在可重复读隔离级别下，通过多版本并发控制（MVCC）+ Next-Key Locking 防止幻影读。
3、主索引是聚簇索引，在索引中保存了数据，从而避免直接读取磁盘，因此对查询性能有很大的提升。

4、内部做了很多优化，包括从磁盘读取数据时采用的可预测性读、能够加快读操作并且自动创建的自适应哈希索引、能够加速插入操作的插入缓冲区等。
5、支持真正的在线热备份。其它存储引擎不支持在线热备份，要获取一致性视图需要停止对所有表的写入，而在读写混合场景中，停止写入可能也意味着停止读取。

MyISAM

1、设计简单，数据以紧密格式存储。对于只读数据，或者表比较小、可以容忍修复操作，则依然可以使用它。
2、提供了大量的特性，包括压缩表、空间数据索引等。
3、不支持事务。
4、不支持行级锁，只能对整张表加锁，读取时会对需要读到的所有表加共享锁，写入时则对表加排它锁。但在表有读取操作的同时，也可以往表中插入新的记录，这被称为并发插入（CONCURRENT INSERT）。
5、可以手工或者自动执行检查和修复操作，但是和事务恢复以及崩溃恢复不同，可能导致一些数据丢失，而且修复操作是非常慢的。
6、如果指定了 DELAY_KEY_WRITE 选项，在每次修改执行完成时，不会立即将修改的索引数据写入磁盘，而是会写到内存中的键缓冲区，只有在清理键缓冲区或者关闭表的时候才会将对应的索引块写入磁盘。这种方式可以极大的提升写入性能，但是在数据库或者主机崩溃时会造成索引损坏，需要执行修复操作。

比较

1、事务：InnoDB 是事务型的，可以使用 Commit 和 Rollback 语句。
2、并发：MyISAM 只支持表级锁，而 InnoDB 还支持行级锁。
3、外键：InnoDB 支持外键。
4、备份：InnoDB 支持在线热备份。
5、崩溃恢复：MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多，而且恢复的速度也更慢。
6、其它特性：MyISAM 支持压缩表和空间数据索引。

3、多版本并发控制

多版本并发控制（Multi-Version Concurrency Control, MVCC）是 MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式，用于实现读已提交和可重复读两种隔离级别。
读未提交隔离级别总是读取最新的数据行，要求很低，无需使用MVCC。
串行化隔离级别需要对所有读取的行都加锁，单纯使用MVCC无法实现。

1、基本思想：

加锁可以解决多个事务同时执行时出现的并发一致性问题。
但是在实际场景中读操作往往多于写操作，因此可以使用读写锁避免不必要的加锁操作。
读读之间没有互斥关系，读和写操作之间仍然是互斥的。
MVCC利用多版本的思想，写操作更新最新的版本快照，读操作则读旧版本快照，没有互斥关系，类似CopyOnWrite。

在MVCC中事务的修改操作(delete、insert、update)会为数据行新增一个版本快照。

脏读和不可重复读最根本的原因是事务读取到其它事务未提交的修改。
在事务进行读取操作时，为了解决脏读和不可重复读问题，MVCC 规定只能读取已经提交的快照。
当然一个事务可以读取自身未提交的快照，这不算是脏读。

2、版本号

系统版本号 SYS_ID：是一个递增的数字，每开始一个新的事务，系统版本号就会自动递增。
事务版本号 TRX_ID ：事务开始时的系统版本号。

3、Undo 日志

MVCC 的多版本指的是多个版本的快照。
快照存储在 Undo 日志中，该日志通过回滚指针 ROLL_PTR 把一个数据行的所有快照连接起来。

例子：
在 MySQL 创建一个表 t，包含主键 id 和一个字段 x。
我们先插入一个数据行，然后对该数据行执行两次更新操作。

INSERT INTO t(id, x) VALUES(1, "a");
UPDATE t SET x="b" WHERE id=1;
UPDATE t SET x="c" WHERE id=1;

没有使用 START TRANSACTION 将上面的操作当成一个事务来执行，根据 MySQL 的 AUTOCOMMIT 机制，每个操作都会被当成一个事务来执行，所以上面的操作总共涉及到三个事务。
快照中除了记录事务版本号 TRX_ID 和操作之外，还记录了一个 bit 的 DEL 字段，用于标记是否被删除。
MySQL学习记录(三)
INSERT、UPDATE、DELETE 操作会创建一个日志，并将事务版本号 TRX_ID 写入。
DELETE 可以看成是一个特殊的 UPDATE，还会额外将 DEL 字段设置为 1。

4、ReadView

MVCC 维护了一个 ReadView 结构，主要包含了当前系统未提交的事务列表 TRX_IDs {TRX_ID_1, TRX_ID_2, …}，还有该列表的最小值 TRX_ID_MIN 和 TRX_ID_MAX。
MySQL学习记录(三)
在进行 SELECT 操作时，根据数据行快照的 TRX_ID 与 未提交事务列表的TRX_ID_MIN 和 TRX_ID_MAX 之间的关系，从而判断数据行快照是否可以使用：

1、TRX_ID < TRX_ID_MIN，表示该数据行快照时在当前所有未提交事务之前进行更改的，因此可以使用。
2、TRX_ID > TRX_ID_MAX，表示该数据行快照是在事务启动之后被更改的，因此不可使用。
3、TRX_ID_MIN <= TRX_ID <= TRX_ID_MAX，需要根据隔离级别再进行判断：
	提交读：如果 TRX_ID 在 TRX_IDs 列表中，表示该数据行快照对应的事务还未提交，则该快照不可使用。
			否则表示已经提交，可以使用。
	可重复读：都不可以使用。因为如果可以使用的话，那么其它事务也可以读到这个数据行快照并进行修改，
			那么当前事务再去读这个数据行得到的值就会发生改变，也就是出现了不可重复读问题。

在数据行快照不可使用的情况下，需要沿着 Undo Log 的回滚指针 ROLL_PTR 找到下一个快照，再进行上面的判断。

5、快照读与当前读

1、快照读
MVCC 的 SELECT 操作是快照中的数据，不需要进行加锁操作。

2、当前读
MVCC 其它会对数据库进行修改的操作（INSERT、UPDATE、DELETE）需要进行加锁操作，从而读取最新的数据。可以看到 MVCC 并不是完全不用加锁，而只是避免了 SELECT 的加锁操作。

在进行 SELECT 操作时，可以强制指定进行加锁操作。
以下第一个语句需要加 S 锁，第二个需要加 X 锁：

	SELECT * FROM table WHERE ? lock in share mode;
	SELECT * FROM table WHERE ? for update;

4、Next-Key Locks

Next-Key Locks 是 MySQL 的 InnoDB 存储引擎的一种锁实现。

MVCC 不能解决幻读问题，Next-Key Locks 就是为了解决这个问题而存在的。
在可重复读（REPEATABLE READ）隔离级别下，使用 MVCC + Next-Key Locks 可以解决幻读问题。

1、Record Locks

锁定一个记录上的索引，而不是记录本身。
如果表没有设置索引，InnoDB 会自动在主键上创建隐藏的聚簇索引，因此 Record Locks 依然可以使用。

2、Gap Locks

锁定索引之间的间隙，但是不包含索引本身。
例如当一个事务执行以下语句，其它事务就不能在 t.c 中插入 15。

SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;

3、Next-Key Locks

它是 Record Locks 和 Gap Locks 的结合，不仅锁定一个记录上的索引，也锁定索引之间的间隙。
它锁定一个前开后闭区间，例如一个索引包含以下值：10, 11, 13, and 20，那么就需要锁定以下区间：

(-∞, 10]
(10, 11]
(11, 13]
(13, 20]
(20, +∞)

5、切分

1、水平切分

水平切分又称为 Sharding，它是将同一个表中的记录拆分到多个结构相同的表中。
当一个表的数据不断增多时，Sharding 是必然的选择，它可以将数据分布到集群的不同节点上，从而缓存单个数据库的压力。
MySQL学习记录(三)
2、垂直切分

垂直切分是将一张表按列切分成多个表，通常是按照列的关系密集程度进行切分，也可以利用垂直切分将经常被使用的列和不经常被使用的列切分到不同的表中。

在数据库的层面使用垂直切分将按数据库中表的密集程度部署到不同的库中，例如将原来的电商数据库垂直切分成商品数据库、用户数据库等。

MySQL学习记录(三)
3、Sharding 策略

哈希取模：hash(key) % N；
范围：可以是 ID 范围也可以是时间范围；
映射表：使用单独的一个数据库来存储映射关系。

4、Sharding 存在的问题

1. 事务问题
	使用分布式事务来解决，比如 XA 接口。
2. 连接
	可以将原来的连接分解成多个单表查询，然后在用户程序中进行连接。
3. ID 唯一性
	使用全局唯一 ID（GUID）
	为每个分片指定一个 ID 范围
	分布式 ID 生成器 (如 Twitter 的 Snowflake 算法)

6、复制

主从复制

主要涉及三个线程：binlog 线程、I/O 线程和 SQL 线程。

binlog 线程 ：负责将主服务器上的数据更改写入二进制日志（Binary log）中。
I/O 线程 ：负责从主服务器上读取二进制日志，并写入从服务器的中继日志（Relay log）。
SQL 线程 ：负责读取中继日志，解析出主服务器已经执行的数据更改并在从服务器中重放（Replay）。

MySQL学习记录(三)
读写分离

主服务器处理写操作以及实时性要求比较高的读操作，而从服务器处理读操作。

读写分离能提高性能的原因在于：
1、主从服务器负责各自的读和写，极大程度缓解了锁的争用；
2、从服务器可以使用 MyISAM，提升查询性能以及节约系统开销；
3、增加冗余，提高可用性。

读写分离常用代理方式来实现，代理服务器接收应用层传来的读写请求，然后决定转发到哪个服务器。

MySQL学习记录(三)

上一篇：mysql 出现了 Waiting for table metadata lock的解决方案


下一篇：mysql锁以及配置优化