MySQL-慢查询日志优化SQL

  1. 查看慢查询日志开关是否打开

    1
    mysql> show variables like 'slow_query%';
    1
    2
    3
    4
    5
    6
    7
    8
    mysql> show variables like 'slow_query%';
    +---------------------+-----------------------------------------------------+
    | Variable_name | Value |
    +---------------------+-----------------------------------------------------+
    | slow_query_log | OFF |
    | slow_query_log_file | /var/lib/mysql/zjz-VMware-Virtual-Platform-slow.log |
    +---------------------+-----------------------------------------------------+
    2 rows in set (0.01 sec)

发现慢查询日志未打开

  1. 打开慢查询日志

    1
    set slow_query_log=ON
    1
    2
    3
    4
    5
    mysql> set slow_query_log=ON
    -> ;
    ERROR 1229 (HY000): Variable 'slow_query_log' is a GLOBAL variable and should be set with SET GLOBAL
    mysql> set global slow_query_log = ON;
    Query OK, 0 rows affected (0.04 sec)

    发现报错,需要设置全局global,这个配置会影响全局,而不是仅影响此次会话

    1
    set global slow_query_log = ON;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    mysql> set global slow_query_log = ON;
    Query OK, 0 rows affected (0.04 sec)

    mysql> show variables like 'slow_query%';
    +---------------------+-----------------------------------------------------+
    | Variable_name | Value |
    +---------------------+-----------------------------------------------------+
    | slow_query_log | ON |
    | slow_query_log_file | /var/lib/mysql/zjz-VMware-Virtual-Platform-slow.log |
    +---------------------+-----------------------------------------------------+
    2 rows in set (0.01 sec)
  2. 设置慢查询时间,超过该时间则记录日记

    1
    2
    3
    4
    5
    6
    7
    mysql> show variables like 'long_query%';
    +-----------------+-----------+
    | Variable_name | Value |
    +-----------------+-----------+
    | long_query_time | 10.000000 |
    +-----------------+-----------+
    1 row in set (0.00 sec)

    经过查询发现,默认慢查询时间为10s,我们设置为0.1s,这个设置仅限于当前会话,对于其他会话无效

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    mysql> set long_query_time=0.1;
    Query OK, 0 rows affected (0.00 sec)

    mysql> show variables like 'long_query%';
    +-----------------+----------+
    | Variable_name | Value |
    +-----------------+----------+
    | long_query_time | 0.100000 |
    +-----------------+----------+
    1 row in set (0.00 sec)
  3. 执行sql,时间达到记录时间,记入日记

    1
    2
    3
    4
    5
    6
    7
    mysql> select * from t_user where password = '1000000';
    +---------+-------------------+----------+
    | id | email | password |
    +---------+-------------------+----------+
    | 1309956 | 1000000@gmail.com | 1000000 |
    +---------+-------------------+----------+
    1 row in set (11.93 sec)
  4. 使用root用户权限查看

    1
    2
    3
    sudo -i
    cd /var/lib/mysql
    ll

    发现如下文件

    1
    -rw-r-----  1 mysql mysql       433 Nov 16 17:17  zjz-VMware-Virtual-Platform-slow.log

    内容如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /usr/sbin/mysqld, Version: 8.0.40-0ubuntu0.24.04.1 ((Ubuntu)). started with:
    Tcp port: 3306 Unix socket: /var/run/mysqld/mysqld.sock
    Time Id Command Argument
    # Time: 2024-11-16T09:17:17.497445Z
    # User@Host: root[root] @ localhost [] Id: 8
    # Query_time: 11.924735 Lock_time: 0.000342 Rows_sent: 1 Rows_examined: 2000000
    use school;
    SET timestamp=1731748625;
    select * from t_user where password = '1000000';
  5. 使用explain分析sql,优化查询

  6. 打开profiling,用于查看sql运行的具体时间,正常情况下sql的运行时间只显示两位小数,会显示0.00,我们无法查看具体时间

    1
    show variables like 'profiling';
    1
    2
    3
    4
    5
    6
    7
    mysql> show variables like 'profiling';
    +---------------+-------+
    | Variable_name | Value |
    +---------------+-------+
    | profiling | OFF |
    +---------------+-------+
    1 row in set (0.12 sec)

    打开profiling

    1
    set profiling= on;
    1
    2
    mysql> set profiling= on;
    Query OK, 0 rows affected, 1 warning (0.00 sec)

    运行profiling查看时间

    1
    show profiles;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    mysql> SELECT * FROM student WHERE age < 18 OR name = 'zhangsan';
    +-----+----------+-----+-----+
    | uid | name | age | sex |
    +-----+----------+-----+-----+
    | 1 | zhangsan | 18 | M |
    +-----+----------+-----+-----+
    1 row in set (0.01 sec)

    mysql> show profiles;
    +----------+------------+-----------------------------------------------------------+
    | Query_ID | Duration | Query |
    +----------+------------+-----------------------------------------------------------+
    | 1 | 0.00756475 | SELECT * FROM student WHERE age < 18 OR name = 'zhangsan' |
    +----------+------------+-----------------------------------------------------------+
    1 row in set, 1 warning (0.00 sec)

    mysql>

MySQL-事务

一、基本概念

一个事务是由一条或者多条对数据库操作的SQL语句所组成的一个不可分割的单元,只有当事务中的所 有操作都正常执行完了,整个事务才会被提交给数据库;如果有部分事务处理失败,那么事务就要回退 到最初的状态,因此,事务要么全部执行成功,要么全部失败。可以将事务理解为一个原子操作,事务中的任务是不可分割的,事务执行过程中,有的SQL出现错误,那么事务必须要回滚(rollback)到最初的状态;事务的所有SQL语句全部执行成功,才能提交(commit)事务,把结果写回磁盘上。

二、相关知识

  1. MyISAM存储引擎是不支持事务的

  2. InnoDB存储引擎支持事务,同时支持行锁

  3. 查询MySQL事务的提交状态

    1
    select @@autocommit;
    1
    2
    3
    4
    5
    6
    7
    mysql> select @@autocommit;
    +--------------+
    | @@autocommit |
    +--------------+
    | 1 |
    +--------------+
    1 row in set (0.01 sec)

    1表示自动提交,一般我们需要设置为0,改为手动提交

    1
    set autocommit = 0;
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    mysql> set autocommit = 0;
    Query OK, 0 rows affected (0.01 sec)

    mysql> select @@autocommit;
    +--------------+
    | @@autocommit |
    +--------------+
    | 0 |
    +--------------+
    1 row in set (0.00 sec)

    mysql>
  4. 事务处理:

    1. BEGIN; 开启一个事务
    2. COMMIT; 提交一个事务
    3. ROLLBACK; 回滚一个事务到初始的位置
    4. SAVEPOINT point1; 设置一个名字为point1的保存点
    5. ROLLBACK TO point1; 事务回滚到保存点point1,而不是回滚到初始状态

三、事务的ACID特性

  1. 事务的原子性(Atomic)

    事务是一个不可分割的整体,事务必须具有原子特性,及当数据修改时,要么全执行,要么全不执行, 即不允许事务部分的完成。

  2. 事务的一致性(Consistency)

    一个事务执行之前和执行之后,数据库数据必须保持一致性状态。数据库的一致性状态必须由用户来负 责,由并发控制机制实现。就拿网上购物来说,你只有让商品出库,又让商品进入顾客的购物车才能构 成一个完整的事务。

  3. 事务的隔离性(Isolation)

    当两个或者多个事务并发执行时,为了保证数据的安全性,将一个事物内部的操作与其它事务的操作隔 离起来,不被其它正在执行的事务所看到,使得并发执行的各个事务之间不能互相影响。

  4. 事务的持久性(Durability)

    事务完成(commit)以后,DBMS保证它对数据库中的数据的修改是永久性的,即使数据库因为故障出 错,也应该能够恢复数据!

    这里有一个场景:

    事务commit以后直接就返回了,但此时数据并不是真的写入到了磁盘中,这些数据还在内存中(脏数据),因为写入数据涉及到磁盘IO,时间较长,commit不会等待,但是如果在从内存写入磁盘的这一过程中,出现停电,重启等问题,那么如何保证数据的可恢复呢?MySQL的redo logundo log机制解决了这一问题,这一机制保证了数据的持久性,所有说MySQL数据库重经典的一句话就是:MySQL最重要的不是数据,而是日志!

    事务的ACID特性:

    ACD:由MySQL的redo log和undo log机制保证

    I:由MySQL事务的锁机制保证

四、事务并发存在的问题

  1. 脏读(Dirty Read)一个事务读取了另一个事务未提交的数据。例如当事务A和事务B并发执行时,当 事务A更新后,事务B查询读取到A尚未提交的数据,此时事务A回滚,则事务B读到的数据就是无效的脏 数据。(事务B能够读取事务A尚未提交的数据),脏读一定是不被允许的。
  2. 不可重复读(NonRepeatable Read)一个事务的操作导致另一个事务前后两次读取到不同的数据。 例如当事务A和事务B并发执行时,当事务B查询读取数据后,事务A更新操作更改事务B查询到的数据, 此时事务B再次去读该数据,发现前后两次读的数据不一样(事务B能够读取事务A已提交的数据,换句话说就是其他事务完成的操作能够影响到当前事务)。没有错误,可以接受,但是需要视业务而定
  3. 虚读(Phantom Read)幻读一个事务的操作导致另一个事务前后两次查询的结果数据量不同。例如 当事务A和事务B并发执行时,当事务B查询读取数据后,事务A新增或者删除了一条满足事务B查询条件 的记录,此时事务B再去查询,发现查询到前一次不存在的记录,或者前一次查询的一些记录不见了。 (事务B读取了事务A新增加的数据或者读不到事务A删除的数据)没有错误,可以接受,但是需要视业务而定

1、事务的隔离级别

  1. READ-UNCOMMITTED。未提交读。说明在提交前一个事务可以看到另一个事务 的变化。这样读脏数据,不可重复读和虚读都是被允许的。
  2. READ-COMMITTED。已提交读。说明读取未提交的数据是不允许的。这个级别仍然允许不可重复读和虚读产生
  3. REPEATABLE-READ。可重复读。说明事务保证能够再次读取相同的数据而不会失败,但虚读仍然会出现。
  4. SERIALIZABLE。串行化。是最高的事务级别,它防止读脏数据,不可重复读和虚读。(单线程执行)
隔离级别 脏读 不可重复读 幻读
未提交读 可以 可以 可以
已提交读 不可以 可以 可以
可重复读 不可以 不可以 可以(可以防止delete和insert,但无法防止update)
串行化 不可以 不可以 不可以
  1. 事务隔离级别越高,为避免冲突所花费的性能也就越多。
  2. 在“可重复读”级别,实际上可以解决部分的虚读问题,但是不能防止update更新产生的虚读问题,要禁 止虚读产生,还是需要设置串行化隔离级别。
  • 设置隔离级别:

    1
    2
    SET GLOBAL transaction_isolation = 'REPEATABLE-READ'; -- 示例:全局设置为可重复读,可能需要断开重连才能生效
    SET SESSION transaction_isolation = 'READ-COMMITTED'; -- 示例:当前会话设置为已提交读
  • 查询事务的隔离级别

    1
    2
    SELECT @@transaction_isolation;#MySQL 8.0
    select @@tx_isolation;#MySQL 5.7
    1
    2
    3
    4
    5
    6
    7
    8
    9
    mysql> SELECT @@transaction_isolation;
    +-------------------------+
    | @@transaction_isolation |
    +-------------------------+
    | REPEATABLE-READ |
    +-------------------------+
    1 row in set (0.03 sec)

    mysql>

    MySQL默认隔离级别为REPEATABLE-READ,只允许虚读产生,不允许脏读和不可重复读

  • 查看全局隔离级别,可能需要断开重连才能生效

    1
    SHOW GLOBAL VARIABLES LIKE 'transaction_isolation';

1、READ_UMCOMMIT

PixPin_2024-11-21_16-42-42

首先,我们先执行在右边执行查询数据

1
select * from student where name = 'zhangsan';

再从左边修改数据

1
update student set age = 19 where name = 'zhangsan';

最后在右边再次查询

1
select * from student where name = 'zhangsan';

发现数据发生了脏读,右边的事务读取到了左边尚未完成事务的数据,如果左边事务发生错误,就会导致数据错误!

2、READ-COMMITTED

PixPin_2024-11-21_16-56-43

从上面可知,在左边事务未commit之前,右边是无法查看修改的数据的,在左边事务commit后,右边即可查看,但存在不可重复读的情况,即其他事务提交后当前事务可以访问到变化后的数据。

3、REPEATABLE-READ

PixPin_2024-11-21_17-09-59

可以看见,在可重复读级别下,其他事务提交的数据无法影响到当前事务,读取的数据都是相同的。

PixPin_2024-11-21_17-18-29

可以发现,可重复读在一定程度上能够防止幻读的发生,但只能防止insert和delete,无法防止update

PixPin_2024-11-21_17-30-14

我们发现,虽然我们第七步使用select查询不到bbb这个人,但是我们还是能够对其修改,经过修改以后,能够查询到这个人,所以前后结果数量不一致,导致虚读发生。

4、SERIALIZABLE

PixPin_2024-11-21_17-40-29

可以发现,在插入时已经阻塞住了,无法执行写操作。

MySQL-事务隔离级别实现原理

  1. 事务隔离级别(隔离性实现底层)实现原理 = 锁 + MVCC(mvcc处理这两种级别:REPEATABLE-READ和READ-COMMITTED)
  2. SERIALIZABLE需要依赖间隙锁,即解决幻读问题
  3. 原子性,一致性,持久性:undo log(回滚日志) + redo log(重做日志)

一、表级锁&行级锁

  • 表级锁:对整张表加锁。开销小,加锁快,不会出现死锁;锁粒度大,发生锁冲突的概率高,并发度低。

  • 行级锁:对某行记录加锁。开销大,加锁慢,会出现死锁;锁定粒度最小,发生锁冲突的概率最低,并发度高。

  • 显示加锁:select … lock in share mode强制获取共享锁,select … for update获取排它锁

二、排他锁和共享锁

  • 排它锁(Exclusive),又称为X锁,写锁。
  • 共享锁(Shared),又称为S锁,读锁。

X和S锁之间有以下的关系: SS可以兼容的,XS、SX、XX之间是互斥的

  • 一个事务对数据对象 O 加了 S 锁,可以对 O 进行读取操作但不能进行更新操作。加锁期间其它事 务能对O 加 S 锁但不能加 X 锁。
  • 一个事务对数据对象 O 加了 X 锁,就可以对 O 进行读取和更新。加锁期间其它事务不能对 O 加任 何锁。

示例:注意这里的隔离级别是REPEATABLE-READ,在SERIALIZABLE这种隔离级别中情况并不同。后面会看到

PixPin_2024-11-25_17-27-05

从图中我们可以看出,InnoDB是支持行锁的。其中,第五步失败的原因是被右边第四步的共享锁阻塞了,因为第五步申请的是排他锁,排他锁和共享锁是互斥的,所以第五步会失败。如下面,共享锁是兼容的,所有第五步会成功,第四步会失败。

PixPin_2024-11-25_18-43-28

示例二

PixPin_2024-11-25_17-50-20

​ 从图中可以看出,我们只是修改了where的过滤字段,使用name作为过滤字段,但是使用以后,发现行锁好像不起作用了?我们查询zhangsanlisi是不同的行数据,发现是失败的。这是因为,Innodb的行锁是加在索引项上面的,是给索引加锁,而不是单纯的在行数据上面加锁,如果过滤条件没有索引的话,InnoDB使用的是表锁而不是行锁!,只有在使用索引作为过滤条件时才会使用行锁,这里的name是没有索引的,所有这里使用的是表锁。如下图所示,给name字段添加了辅助索引,便能够使用行锁了

PixPin_2024-11-25_18-00-17

由于InnoDB的行锁实现是针对索引(主键索引)字段添加的锁,不是针对行记录加的锁,因此虽然访问的是 InnoDB引擎下表的不同行,但是如果使用相同的索引字段作为过滤条件,依然会发生锁冲突,只能串行进行,不能并发进行。

PixPin_2024-11-25_18-06-13

即使SQL中使用了索引,但是经过MySQL的优化器后,如果认为全表扫描比使用索引效率更高,此 时会放弃使用索引,因此也不会使用行锁,而是使用表锁,比如对一些很小的表,MySQL就不会去使用索引。

下面使用SERIALIZABLE隔离级别,在SERIALIZABLE隔离级别中,查询操作会自动加上共享锁,写操作会自动加上排他锁

PixPin_2024-11-25_18-20-53

从上面可以看到,我们使用SERIALIZABLE的隔离级别,发现共享锁和共享锁时是兼容的,所以第一步和第二步可以得到结果,由于共享锁和排他锁不兼容,所以第四,第五和第六步失败了(这个解释错了,看下面的解释)。其中,第三和第四步,虽然使用不同的索引,但实际上,InnoDB的所有锁最终是加在主键索引上面的,我们使用name作为索引,他会发生回表在主索引树上查找数据,最终使用的是主键作为索引,所以第三和第四步不会成功,他们都被右边共享锁阻塞住了。再看第五步,刚开始我是很懵逼的,为什么两边都无法执行写操作。后面才知道共享锁是可以叠加的,在开始的两次select操作,两边的会话都加上了共享锁。所以左边的第三和第四步被右边会话的共享锁阻塞,而右边的第五步被左边的共享锁阻塞,所有两边都无法执行写操作。

PixPin_2024-11-25_18-29-59

从这里我们可以知道,第二步能成功是因为在同一个会话中且只有一个共享锁进行加锁,所有第二部的写操作是能够成功的,而第三步被第二步的排他锁阻塞。

  1. InnoDB行锁是通过给索引上的索引项加锁来实现的,而不是给表的行记录加锁实现的,这就意味着只有通过索引条件检索据,InnoDB才使用行级锁,否则InnoDB将使用表锁。
  2. 由于InnoDB的行锁实现是针对索引(主键索引)字段添加的锁,不是针对行记录加的锁,因此虽然访问的是 InnoDB引擎下表的不同行,但是如果使用相同的索引字段作为过滤条件,依然会发生锁冲突,只能串行进行,不能并发进行。
  3. 即使SQL中使用了索引,但是经过MySQL的优化器后,如果认为全表扫描比使用索引效率更高,此时会放弃使用索引,因此也不会使用行锁,而是使用表锁,比如对一些很小的表,MySQL就不会去使用索引。

三、间隙锁(gap lock)

1、范围查询

在串行化隔离级别下会使用到间隙锁

当我们用范围条件而不是相等条件检索数据(使用next-key lock,next-key lock = record lock + gap lock ),并请求共享或排他锁时,InnoDB 会给符合条件的已有数据记录的索引项加锁(这些锁称为行锁(record lock));对于键值在条件范围内但并不存在的记录,叫做间隙(GAP) ,InnoDB 也会对这个“间隙”加锁,这种锁机制就是所谓的间隙锁(gap lock)。举例来说, 假如 user 表中只有 101 条记录, 其 userid 的值分别是 1,2,…,100,101, 下面的 SQL:

1
select * from user where userid > 100 for update;

是一个范围条件的检索,InnoDB 不仅会对符合条件的 userid 值为 101 的记录加锁(行锁),也会对userid 大 于 101(但是这些记录并不存在)的”间隙”加锁(间隙锁),防止其它事务在表的末尾增加数据。

InnoDB使用间隙锁的目的,为了防止幻读,以满足串行化隔离级别的要求,对于上面的例子,要是不使用间隙锁,如果其他事务插入了 userid 大于 100 的任何记录,那么本事务如果再次执行上述语句, 就会发生幻读。

示例:

PixPin_2024-11-26_14-21-28

在串行化(SERIALIZABLE)隔离级别下,查询操作都会加上共享锁,写操作都会添加排他锁。在这里,我们使用select * from user where id > 3进行范围查询,这时,InnoDB会为添加间隙锁,即大于id>3的数据都会被上锁,即使没有这个数据。

间隙锁的锁的范围是左开右闭的,所以上面的加锁范围如下:(3,4],(4,5],(5,无穷大],加上锁以后,他会对该大于该id后面的写操作都会被间隙锁阻塞。所以上面的第五步会失败。

行级共享读锁 (S Lock):在你进行 SELECT 时,InnoDB 会为每一行数据加上共享读锁,防止其他事务修改这些行。

间隙锁 (Gap Lock):如果你的查询是带范围的(如 SELECT * FROM user WHERE id > 3;),InnoDB 可能会在符合条件的行之间的“间隙”上加锁,阻止其他事务在这些间隙插入数据,防止幻读。

同样的道理,在 SERIALIZABLE 隔离级别下,如果执行 SELECT * FROM user;,在事务未提交之前,其他事务对 user 表的数据进行 写操作(如 INSERTUPDATEDELETE)是会被间隙锁阻塞的。所以下面的第五步会失败。

PixPin_2024-11-26_14-30-40

存在的问题:我们这里的id是主键,这个是不会重复的,那么使用辅助索引的情况是怎么?辅助索引是允许重复的。

例如使用age作为辅助索引,如果age相等,那么就会比较主键大小,主键按升序排序。这就意味着,如果在不指定id的情况下,一般后面插入的数据排在后边,这就会出现下面这种情况。

例如:我们使用select * from user where age > 16;锁住大于16区间的数据

PixPin_2024-11-26_17-50-09

我们会加锁的区域有:(16,无穷大]

  • 我们首先插入数据的的age = 15,不在加锁区域,能够插入

  • 但是age = 16无法插入,按理说16不应该在这个加锁区间才是。但是就是失败了

    PixPin_2024-11-26_17-48-23

    这是因为虽然新插入的数据age是16,但是他是后插入的,且没有指定id,所以在插入数据排序时,他会排在原本数据jianzhe行的右边,即图中(16,5)的后边,但是他的右边已经被锁住了,所以无法插入成功,所以对于间隙的范围要了解清楚

2、等值查询

在串行化下,如果使用主键或者唯一键作为等值查询的条件,是不会产生幻读现象的,这是因为插入操作会执行失败,删除和更新操作会被共享锁阻塞,所以需要考虑的是辅助索引作为等值查询条件的情况。

在使用辅助索引作为插入条件时,数据要么插入到该数据的左边,要么插入到该数据的右边,所以,要避免幻读的发生,InnoDB就会在该值的左右两边的间隙加上间隙锁,例如:我们插入一条age = 18的数据,insert into user(name,age,sex) values('aaa',18,'M'),假设表数据如下,他就会在(15,18]和(18,19]之间加上间隙锁,防止有插入age等于18的 数据。但是这时,如果我们插入age等于15, 16,17,19的数据也会失败(age = 15如果不指定id的情况下会失败,但是在age = 15且id < 23的时候会成功,19同理)

PixPin_2024-11-26_18-08-58 PixPin_2024-11-26_18-15-40

四、意向共享锁和意向排他锁

意向锁是存储引擎自己加的,并不需要我们手动添加。

  • 意向共享锁(IS锁):事务计划给记录加行共享锁,事务在给一行记录加共享锁前,必须先取得该表的 IS 锁。

  • 意向排他锁(IX锁):事务计划给记录加行排他锁,事务在给一行记录加排他锁前,必须先取得该表的 IX 锁。

X IX S IS
X Conflict Conflict Conflict Conflict
IX Conflict 兼容 Conflict 兼容
S Conflict Conflict 兼容 兼容
IS Conflict 兼容 兼容 兼容
  1. 意向锁是由InnoDB存储引擎获取行锁之前自己获取的
  2. 意向锁之间都是兼容的,不会产生冲突
  3. 意向锁存在的意义是为了更高效的获取表锁(表格中的X和S指的是表锁,不是行锁!!!)
  4. 意向锁是表级锁,协调表锁和行锁的共存关系。主要目的是显示事务正在锁定某行或者试图锁定某 行。

意向锁存在的目的:针对表锁

如果一个事务需要修改很多的数据,涉及多张表,那么如果使用行锁时很容易导致死锁且效率较低,这时使用表锁的效率反而更高,要获取表的共享锁或排他锁,就需要确保两件事:

  1. 这张表没有被其他事务获取过X锁
  2. 这张表里面的数据没有被其他事务获取过行锁x锁

其中,最主要的是第二条,如果表的数据量很大,如有1千万条数据,那么要判断有没有行锁x锁,这个效率是很低的,所以意向锁的目的就是解决这个查找效率问题。

如果意向排他锁已经被获取了,那就说明表中有数据被其他事务添加了行锁x锁,所以当要获取表的X锁时,不需要检查表中的哪些行已经加上了行(X或S)锁,只需要快速检查IX和IS锁即可。

五、MVCC

已提交读和可重复读的底层原理:MVCC(多版本并发控制),并发读取方式:快照读

InnoDB的两种读取操作:

  1. 锁定读(SX),需要加锁

  2. 非锁定读,即不需要加锁(MVCC提供的快照读,底层为undo log回滚日志),如select,其中,已提交读和可重复读都依赖于非锁定读,即快照读

MVCC提供的读操作:

  1. 快照读(snapshot read):读的是记录的可见版本,不用加锁。如select,已提交读和可重复读都依赖于非锁定读,即快照读
  2. 当前读(current read):读取的是记录的最新版本,并且当前读返回的记录。如insert,delete,update,select…lock in share mode/for update

六、undo log 回滚日志

  • 事务发生错误时回滚日志 rollback

  • 提供MVCC的非锁定读(快照读)

    PixPin_2024-11-28_15-38-36

    如图所示,undo log使用链表将每一次修改的数据的操作串在一起,这些数据存放于缓存中。通过将历史数据串起来实现回滚的效果。

    • DB_TRX_ID是InnoDB为每一个事务提供的唯一的ID值
    • DB_ROLL_PTR是上一个数据存放的地址,如果发生错误,会根据这个地址回滚数据
    • DB_ROW_ID是InnoDB默认提供的索引,如果建表时没有创建索引,InnoDB就会提供这么一个索引
  • 已提交读和可重复读

    1. 已提交读每次执行select语句的时候都重新生成一次快照 (Read View),但是只有事务已经成功commit以后才能 放入快照中,如果事务还未commit,则不会放入快照中。解决了脏读问题。但是存在不可重复读和幻读的现象,即最新查询的数据内容与前面的的不一致。换句话说:其他事务更新后而且已经提交的数据,可以实时反馈给当前事务的select结果当中。

    2. 可重复读:**同一个事务开始的时候生成一个当前事务全局性的快照(Read View),只在事务开始时生成一次快照。**这样既能解决脏读,也解决不可重复读的问题。但还是存在幻读的问题。 例如:事务A开启时生成了一个快照,此时事务B插入了一个数据并成功提交,此时如果事务A查询时并不会查询到数据,这是因为数据会从快照中读取,但是,如果事务A对新插入数据进行update操作是会成功的,再一次查询时,会查询到了新的数据,发生了幻读现象。原因是一个事务内所有的操作对于事务自己是可见的,事务进行select操作时不仅会查询快照,还会根据自己的事务ID(DB_TRX_ID)查询修改过的数据(查询时不仅使用快照,还会检查事务自身产生的修改)。这里事务进行update操作是在最新数据中修改的(将新数据的事务ID变为A的事务ID),而不是在快照中修改的。所以update操作能成功,从而能查询到修改后的数据。

      快照内容读取原则:

      1. 版本未提交无法读取,无法生成快照
      2. 版本已提交,但是在快照创建后提交的,无法读取
      3. 版本已提交,但是在快照创建前提交的,可以读取
      4. 当前事务内自己的更新,可以读到,通过查询当前事务ID号的操作

七、redo log重做日志

redo log是为了保证了数据的持久性和崩溃恢复而设计的,记录的是物理变更信息,即页级的操作,在事务begin开始时就开始记录,不管事务是否提交都会记录下来,在异常发生时,如数据持久化过程中发生掉电,InnoDB会使用redo log恢复到掉电前的时刻,保证数据的完整性。其中,undo log也会写入在redo log中。

八、redo logundo log的区别

  • Redo Log(重做日志)
    • redo log记录的是物理变更信息(如写入、更新、删除等),即页级的操作而不记录原始的SQL语句。它可以确保即使系统崩溃,数据库也能根据这些日志进行恢复。它是为了保证事务的持久性(Durability)和崩溃恢复而设计的。
    • 由于它记录的是数据页级别的修改,因此我们有时称它为物理日志
  • Undo Log(回滚日志)
    • undo log记录的是逻辑操作(记录了对数据的反向操作),即记录的是事务对数据的撤销操作(例如,原始数据的值),用于在事务回滚时撤销之前的操作。
    • 例如,在一个UPDATE语句执行时,undo log会记录更新前的数据值。这样如果事务回滚时,InnoDB可以使用undo log来恢复到操作之前的状态。
    • undo log并不是用来恢复数据的物理状态,而是恢复事务的逻辑操作。因此我们把它称为逻辑日志

小结

  • Redo Log是物理日志,记录数据页的修改,保证持久性和崩溃恢复。它用于记录操作的物理变更(例如写入数据页),并在数据库恢复时重新应用这些变更。
  • Undo Log是逻辑日志,记录撤销操作,确保事务的原子性和一致性。它用于回滚事务时恢复数据的原始状态。
  • 在事务提交时,redo log会先写入磁盘,保证数据的一致性和持久性。然后,事务状态标记为commit,而数据页的刷写通常是异步进行的。

九、InnoDB的Buffer

PixPin_2024-12-03_14-55-55 PixPin_2024-12-03_15-51-52

InnoDB 在处理 SQL 语句时,涉及两个重要的内存结构:InnoDB Logger BufferInnoDB Buffer Pool Cache。这两个内存结构的作用、分配和使用是为了优化事务处理、数据的缓存和磁盘 I/O 操作。

  1. InnoDB Buffer Pool Cache(缓冲池)

    Buffer Pool 是 InnoDB 存储引擎中的关键内存组件,主要用于存储表数据页、索引页、undo log 页和其他数据。它的作用是提高磁盘 I/O 性能,减少对磁盘的直接访问,将经常使用的数据保存在内存中。Buffer Pool 的大小对数据库性能有重要影响。

Buffer Pool 的使用场景

  • 数据和索引的缓存:在处理 SQL 查询时,数据页和索引页会被加载到 Buffer Pool 中。当执行查询(例如 SELECT)时,InnoDB 会首先检查 Buffer Pool 是否已经缓存了所需的数据和索引。如果数据已经在内存中,就可以直接访问,避免了磁盘 I/O 操作。
  • 事务中的数据修改:当执行更新、删除或插入等写操作时,修改的数据页会被加载到 Buffer Pool 中。这些修改的数据页不会立刻写入磁盘,而是保存在内存中,直到合适的时机(例如 Buffer Pool 满了或者定期刷新)才会被写入磁盘。
  1. InnoDB Logger Buffer(日志缓冲区)

    Logger Buffer 是用来存储事务的 redo log 信息的内存缓冲区。每当一个事务对数据做出修改时,InnoDB 会将修改的操作记录在 redo log 中,这些日志是物理日志,用于恢复数据库的一致性。

Logger Buffer 的使用场景

  • 每次发生数据修改时,InnoDB 会将修改操作记录到 Logger Buffer,并等待最终的写入操作。写入日志的操作通常会被延迟,以减少磁盘 I/O 操作。

  • 在事务提交时,Logger Buffer 会被刷新到磁盘中,确保 redo log 文件的持久性。

Buffer Pool 和 Logger Buffer 的区别与配合

  • Buffer Pool 主要负责缓存和存储数据库的数据页和索引页。它帮助减少磁盘 I/O,提高查询和写操作的性能。
  • Logger Buffer 主要负责缓存 redo log 记录,确保事务的持久性。在事务提交时,Logger Buffer 中的内容会被刷新到磁盘中的 redo log 文件。

配合使用的流程

  1. SQL 语句执行时:当执行 SELECT 查询时,InnoDB 会先检查所需的数据页是否在 Buffer Pool 中;如果不在内存中,则会从磁盘加载。如果是修改数据的语句(例如 UPDATE),数据会先在 Buffer Pool 中进行修改。
  2. 事务开始时:当事务开始时,所有对数据的修改都会先记录到 Logger Buffer,然后在提交时将这些日志写入磁盘。
  3. 事务提交时:当事务提交时,Logger Buffer 中的日志会被刷新到磁盘中的 redo log 文件,这样可以确保在系统崩溃时,已经提交的事务能够通过 redo log 恢复。与此同时,修改的数据页也会从 Buffer Pool 刷写到磁盘中,确保数据的持久性。

十、事务提交过程的详细说明

  1. 事务的prepare阶段

    • 当事务执行COMMIT时,InnoDB首先会在内存中记录该事务的redo log。此时,事务的状态变为PREPARE

    • PREPARE阶段,InnoDB已经将redo log(包括更新的数据页信息)写入到日志缓冲区,但尚未将修改的实际数据写入磁盘。

    • 这时,事务的操作还没有完全持久化到磁盘,InnoDB通过redo log记录了关于数据变更的物理操作(即页级的操作信息),这些信息将用于崩溃恢复时的回滚或重做操作。

  2. 事务的commit阶段

    • 当事务的redo log成功地刷新到磁盘后,InnoDB会标记该事务为COMMIT状态。

    • 在此时,修改的数据页(实际上是缓冲池中的数据)并没有立即刷新到磁盘。数据在InnoDB的Buffer Pool中仍然存在,InnoDB会异步地将这些数据写入磁盘。这个过程通过flush操作完成,但它是延迟的,具体时机由innodb_flush_log_at_trx_commit等配置项控制。

十一、 崩溃恢复过程

MySQL重启后,InnoDB会执行崩溃恢复。这个过程分为以下几个阶段

  • Redo Log重做(Recovery Phase):InnoDB会通过读取redo log,恢复所有已提交事务的操作。因为redo log记录的是物理变更,它确保所有已提交的事务能够重做(即应用)到磁盘上的数据中。换句话说,尽管数据页没有及时刷写到磁盘,只要事务已经提交并且redo log被持久化,重启后InnoDB会通过redo log将修改恢复到数据页
  • Undo Log回滚(Rollback Phase):InnoDB会回滚所有尚未提交的事务(即PREPARE状态的事务)。这些未提交事务的操作在崩溃前已经被记录到redo log,但是由于它们没有提交,InnoDB会通过undo log撤销这些事务的操作,确保数据库恢复到一致性状态。

崩溃在COMMIT之前:InnoDB会通过redo log回滚事务的变更,确保未提交的事务不会影响最终的数据一致性。

崩溃在COMMIT之后:InnoDB会通过redo log重做已提交事务的变更,恢复数据库数据,即使数据页未写入磁盘。

undo logredo log 在崩溃恢复和回滚操作中是配合使用的,但它们的作用和使用场景有所不同。简要来说,undo log 用于回滚未提交事务的操作,而 redo log 用于重做已提交事务的操作。它们在恢复过程中各司其职。

现在我们知道,InnoDB存储引擎事务操作的实际上是redo log日志,并不是真正的数据,如今可以根据redo log恢复,所以说MySQL最重要的就是日志。

MySQL-索引

索引是创建在表上的,是对数据库表中一列或者多列的值进行排序的一种结果。索引的核心是提高查询的速度!

一、索引的优缺点:
  • 索引的优点: 提高查询效率

  • 索引的缺点: 索引并非越多越好,过多的索引会导致CPU使用率居高不下,由于数据的改变,会造成索引文件的改动,过多的磁盘I/O造成CPU负荷太重

二、索引类型
  1. 普通索引:没有任何限制条件,可以给任何类型的字段创建普通索引
  2. 唯一性索引:使用UNIQUE修饰的字段,使用unique自动创建索引(MyISAM, InnoDB),值不能够重复,主键索引就隶属于唯一性索引
  3. 主键索引:使用Primary Key修饰的字段会自动创建索引(MyISAM, InnoDB)
  4. 单列索引:在一个字段上创建索引
  5. 多列索引:在表的多个字段上创建索引 (uid+cid,多列索引必须使用到第一个列,才能用到多列索引,否则索引用不上)
三、索引操作:
  1. 创建索引

    1
    2
    create index 索引名 on 表名(要添加索引的字段(索引长度))
    #CREATE INDEX idx_username ON users(username(10));
  2. 删除索引

    1
    2
    DROP INDEX 索引名 ON 表名;
    #DROP INDEX idx_username ON users;
四、索引使用的注意事项:
  1. 经常作为where条件过滤的字段考虑添加索引
  2. 字符串列创建索引时,可以规定索引的长度,避免索引值的长度key_len过长,可以提高速度,但存在风险(见5.8)
  3. 索引字段涉及类型强转、mysql函数调用、表达式计算等,索引就用不上了

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
mysql> select count(*) from t_user;
+----------+
| count(*) |
+----------+
| 2000000 |
+----------+
1 row in set (2.58 sec)

mysql> show create table t_user\G
*************************** 1. row ***************************
Table: t_user
Create Table: CREATE TABLE `t_user` (
`id` int NOT NULL AUTO_INCREMENT,
`email` varchar(255) DEFAULT NULL,
`password` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=4000001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.02 sec)

mysql> select * from t_user where password = 1000000;
+---------+-------------------+----------+
| id | email | password |
+---------+-------------------+----------+
| 1309956 | 1000000@gmail.com | 1000000 |
+---------+-------------------+----------+
1 row in set (1.41 sec)

mysql> explain select * from t_user where password = 1000000;
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
| 1 | SIMPLE | t_user | NULL | ALL | NULL | NULL | NULL | NULL | 1977287 | 10.00 | Using where |
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
1 row in set, 1 warning (0.03 sec)

mysql> create index passwd_index on t_user(password(20));
Query OK, 0 rows affected (14.03 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> show create table t_user\G
*************************** 1. row ***************************
Table: t_user
Create Table: CREATE TABLE `t_user` (
`id` int NOT NULL AUTO_INCREMENT,
`email` varchar(255) DEFAULT NULL,
`password` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `passwd_index` (`password`(20))
) ENGINE=InnoDB AUTO_INCREMENT=4000001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.01 sec)

mysql> select * from t_user where password = 1000000;
+---------+-------------------+----------+
| id | email | password |
+---------+-------------------+----------+
| 1309956 | 1000000@gmail.com | 1000000 |
+---------+-------------------+----------+
1 row in set (1.85 sec)

mysql> explain select * from t_user where password = 1000000;#发现没有使用索引,原因是使用了强转,password是字符串类型,而这里使用的是数字
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
| 1 | SIMPLE | t_user | NULL | ALL | passwd_index | NULL | NULL | NULL | 1977287 | 10.00 | Using where |
+----+-------------+--------+------------+------+---------------+------+---------+------+---------+----------+-------------+
1 row in set, 3 warnings (0.01 sec)

mysql> select * from t_user where password = '1000000';
+---------+-------------------+----------+
| id | email | password |
+---------+-------------------+----------+
| 1309956 | 1000000@gmail.com | 1000000 |
+---------+-------------------+----------+
1 row in set (0.00 sec)

mysql> explain select * from t_user where password = '1000000';#成功使用到索引
+----+-------------+--------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+--------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | t_user | NULL | ref | passwd_index | passwd_index | 83 | const | 1 | 100.00 | Using where |
+----+-------------+--------+------------+------+---------------+--------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

在最后的explain中,我们发现key_len为83,这是因为我们使用的是 utf8mb4 字符集,而在 utf8mb4 中,每个字符占用最多 4 个字节。因此,索引长度为 20 个字符时,实际的字节长度计算为:20 * 4 = 80; 在 MySQL 中,NULL 值的字段通常会占用额外的 1 到 3 个字节来存储 NULL 标记。因此,最终索引长度计算可能会增加到 83 个字节,3 个字节用于处理 NULL 标记。

五、索引的底层原理:
1、索引底层原理

首先,MySQL先分析sql语句,如select * from user where uid = 3如果涉及到索引,MySQL会通过使用B+树减少磁盘IO,存储引擎会请求kennel从磁盘中读取索引和数据信息,构建索引树,提高搜索效率

2、聚集索引和非聚集索引
  • 聚集索引:主键索引和数据存储在一起的存储结构就是聚集索引,聚集索引不会发生回表

  • 非聚集索引:主键索引和数据没有存储在一起,可能会发生回表

  • 什么是回表?

    “回表”特指查询时通过二级索引找到主键值后,再回到主键索引树中查询完整的行数据。二级索引 -> 主键值 -> 主键索引树 -> 行数据。,Innodb的二级索引树可能会导致回表的发生,这是因为 InnoDB 的二级索引 data 部分存储的是主键值,而数据存储在主键索引树中,因此需要额外的一次访问操作

3、主键索引和二级索引
  • 对于Innodb

    主键索引(聚集索引):

    • 构成:主键索引树的 key 是主键字段,data 是整行数据。
    • 特点:
      • 主键索引和数据存储在一起,因此称为 聚集索引
      • 每张表只能有一个主键索引。
      • 数据行物理上按照主键值顺序存储,插入数据时会根据主键值调整存储顺序。

    二级索引(辅助索引):

    • 构成:二级索引树的 key 是二级索引字段,data 是该记录对应的主键值。

    • 特点:

      • 二级索引是 非聚集索引

      • 查询时,若仅依赖二级索引字段可以直接获取数据,否则需要通过存储的主键值在主键索引树中再次查找整行数据,这称为 回表。

      • 优化:合理设计查询,尽量使 SELECT 子句中需要的字段全部包含在索引覆盖中,减少回表操作。索引覆盖是指当查询所需的所有数据都包含在索引中时,数据库引擎可以直接从索引中获取数据而无需回表

        假设有一个用户表:

        1
        2
        3
        4
        5
        6
        7
        8
        CREATE TABLE users (
        id INT PRIMARY KEY,
        name VARCHAR(100),
        age INT,
        city VARCHAR(100),
        INDEX idx_name_age (name, age)
        );

        情况1:需要回表,虽然使用了idx_name_age索引,但需要获取所有字段(包括不在索引中的city),必须回表查询完整记录

        1
        SELECT * FROM users WHERE name = '张三';

        情况2:索引覆盖,查询的字段nameage都包含在idx_name_age索引中,引擎可以直接从索引获取数据,无需回表

        1
        SELECT name, age FROM users WHERE name = '张三';

    总结:

    • 主键索引:聚集索引,key 是主键,data 是整行数据。
    • 二级索引:非聚集索引,key 是索引字段,data 是主键值。
  • 对于MyISAM

    主键索引和二级索引:

    • 构成:索引树的 key 是索引字段,data 是对应数据的文件地址(即指向数据存储文件的偏移量)。
    • 特点:
      • 无论是主键索引还是二级索引,其存储结构是相同的,索引都仅存储数据的地址,而不存储实际数据
      • MyISAM 中数据和索引是分开存储的,因此其索引树始终是 非聚集索引
      • 主键和普通索引在存储上没有区别,只是主键要求唯一且不可为空。

    查询特点:

    • 查询时,先根据索引找到数据地址,然后根据地址直接读取对应的行数据。

    总结:

    • 主键索引和二级索引在存储结构上没有区别,都是非聚集索引。
    • key 是索引字段,data 是数据的物理地址。
    特性 InnoDB 主键索引 InnoDB 二级索引 MyISAM 主键索引 MyISAM 二级索引
    索引树结构 聚集索引 非聚集索引 非聚集索引 非聚集索引
    key 主键字段 二级索引字段 主键字段 二级索引字段
    data 行数据 主键值 数据的地址 数据的地址
    数据与索引存储是否分离
    是否可能回表 不会 可能 不会 不会

    虽然MyISAM的data存储的不是行数据而是地址,但严格来说这并不算回表,回表是需要经过主索引树再一次查询

4、二级索引树和回表

PixPin_2024-11-15_16-49-40

索引分为主键索引和二级索引,由他们构建的索引树分别叫做主键索引树和二级索引树(或者辅助索引树)

其中,主键索引树和索引树有所区别

  1. 主键索引树的key是主键,data的内容是所在行的全部数据。
  2. 而辅助索引树的key是辅助索引的值,data是所在记录行的主键值(不是行的全部数据)。

这个data保存数据的差异,就会导致在使用二级索引时,会出现回表的问题,什么是回表,回表就是在二级索引树上找不到数据,需要根据主键值在主索引树上再一次查找,它导致了更多的查询数据和更多的磁盘IO

例如下面的sql,name字段是有索引的

1
select name from student where name = 'zhangsan';

这里的name是一个二级索引,我们只查询name,可以直接从他的二级索引树上得到,下面的也是,uid和name都能直接从二级索引树上得到

1
select uid,name from student where name = 'zhangsan';

但是,下面这个就不行,这条语句还查询了sex,age等信息,我们是无法从二级索引树上得到了,索引只能在主索引树上查找,这就涉及到了回表

1
select * from student where name = 'zhangsan'

image-20250329015034541

所以,select 后边的字段尽量不要直接使用*,而是明确的使用字段名,一个是为了减少回表的发生,第二个是减少以后添加新字段时,不会影响现有的查询sql查询的结果,以产生意料之外的bug。

5、B+树索引和哈希索引

image-20250329010958816

创建哈希索引

1
create index name_index on student(name) using hash;

在Innodb中,上面的sql会生成一个警告且并不会创建哈希索引,这是因为Innodb并不支持哈希索引,他会默认生成一个B+树索引,只有 Memory 存储引擎支持显式的 HASH 索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mysql> create index name_index on student(name) using hash;
Query OK, 0 rows affected, 1 warning (0.40 sec)
Records: 0 Duplicates: 0 Warnings: 1

mysql> show create table student\G
*************************** 1. row ***************************
Table: student
Create Table: CREATE TABLE `student` (
`uid` int unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`age` tinyint unsigned NOT NULL,
`sex` enum('M','W') NOT NULL,
PRIMARY KEY (`uid`),
KEY `name_index` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.00 sec)

查看表的索引,使用show create table student\G查看并不准确,应该使用如下sql

1
show indexes from student;
1
2
3
4
5
6
7
8
mysql> show indexes from student;
+---------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| student | 0 | PRIMARY | 1 | uid | A | 5 | NULL | NULL | | BTREE | | | YES | NULL |
| student | 1 | name_index | 1 | name | A | 5 | NULL | NULL | | BTREE | | | YES | NULL |
+---------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
2 rows in set (0.09 sec)

哈希索引和B+树索引对比:

  1. 使用场景:
    • 哈希索引一般用于数据不需要写入磁盘的,主要用于内存存储引擎,只在内存中使用,不适合需要排序或范围查询的场景。适用于等值查询场景,主要用于高性能的等值查询(内存优先).
    • B+树索引一般需要写入磁盘,适用于范围查询、排序、等值查询等多种场景,适用性更广
  2. 磁盘IO
    • 哈希索引的磁盘IO次数较多,每一个节点需要一次磁盘IO
    • B+树索引磁盘IO次数少,一次磁盘IO能够写入多个数据
  3. 搜索和排序
    • 哈希索引底层使用散列表实现,需要计算哈希值,无法对数据排序,对于范围搜索和排序的场景不适用,只能用于等值查询,如name = ‘zhangsan’
    • B+树索引底层是平衡树,在构建索引树时对数据排序,适用于范围查询和排序等场景

总体来说,哈希索引使用较少。

特性 哈希索引 B+树索引
使用场景 等值查询,内存优先 通用场景,支持磁盘存储
磁盘 I/O 较多(哈希冲突增加负担) 较少(设计减少磁盘访问)
搜索复杂度 O(1)(等值查询) O(log(n))
排序支持 不支持 天然支持
范围查询 不支持 高效支持
6、B树

如果MySQL使用B树,B树相比于AVL树(二叉平衡树)的优点是什么?

假设在一个2000万个数据的场景中,使用**AVL树**(自平衡二叉树)时,由于每个节点只存储一个数据项,树的高度大约为25层。最坏情况下,每次查找操作需要进行25次磁盘I/O,因为每层都需要读取一个磁盘块(读磁盘是按块为单位读取的)。而如果使用**B树**(阶数为500的平衡树),每个节点可以存储多达500个数据项,因此树的高度只有约3层,查找同样的数据仅需要进行3次磁盘I/O。B树通过每个节点存储多个数据项,极大地减少了树的深度和磁盘I/O次数.`最主要的就是减少了磁盘IO的次数`
7、B+树

B树的缺点:

  1. 每个节点中有key,也有data,但是每一个节点的存储空间是有限的,如果data数据较大时会导致每个节点能存储的key的数据很小
  2. 当存储的数据量很大时,会导致节点增多,B-树的高度变大,磁盘IO次数花费增大,效率降低
  3. 查询时间不稳定,离根节点近的查询速度快,离根节点远的查询速度慢
  4. 在B-树上如果做区间查找,遍历的节点是非常多的

image-20250329012334382

B+树的特点:

  1. 非叶子节点只存储索引,不会存储数据,意味着一个节点包含的索引更多,索引树的节点更少,层数更少,磁盘IO次数更少
  2. 索引的数据都放在叶子节点并使用链表串起来,是一个有序链表,查询时会通过索引定位数据起始的位置,查询时间更稳定
  3. 由于数据都被串成一个有序链表,所以在范围收缩时,只需要根据索引树定位起始节点,便可以直接遍历链表获取数据,比B树更加高效
8、创建索引的坑!

存在问题,我自己查询的时候,extra字段全部都是using where,并不像图中那样显示using index 或者null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
mysql> show create table student\G
*************************** 1. row ***************************
Table: student
Create Table: CREATE TABLE `student` (
`uid` int unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`age` tinyint unsigned NOT NULL,
`sex` enum('M','W') NOT NULL,
PRIMARY KEY (`uid`),
KEY `name_index` (`name`(20))
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.07 sec)

mysql> select name from student where name='zhangsan';
+----------+
| name |
+----------+
| zhangsan |
+----------+
1 row in set (0.03 sec)

mysql> explain select name from student where name='zhangsan';#为什么没有使用到索引,Using index?
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | name_index | name_index | 82 | const | 1 | 100.00 | Using where |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select age,name from student where name='zhangsan';#为什么extra不为null
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | name_index | name_index | 82 | const | 1 | 100.00 | Using where |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select name from student;#离谱,为什么没有使用到索引
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------+
| 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 5 | 100.00 | NULL |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)

问题出现的原因:

查询字段与索引不匹配,我们是这么创建索引的

1
create index name_index on student(name(20))

我们为name的索引设置了长度,这是一个前缀索引,前缀索引意味着我们这个索引并不全!它只对 name 列的前 20 个字符进行了索引,并没有索引完整的 name 列,因此,MySQL 没有使用该索引来加速查询。

所以我们应该这么设置索引,不应该设置索引的长度

1
create index name_index on student(name)

最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
mysql> show create table student\G
*************************** 1. row ***************************
Table: student
Create Table: CREATE TABLE `student` (
`uid` int unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`age` tinyint unsigned NOT NULL,
`sex` enum('M','W') NOT NULL,
PRIMARY KEY (`uid`),
KEY `name_index` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.06 sec)

mysql> select name from student where name='zhangsan';
+----------+
| name |
+----------+
| zhangsan |
+----------+
1 row in set (0.02 sec)

mysql> explain select name from student where name='zhangsan';
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | name_index | name_index | 202 | const | 1 | 100.00 | Using index |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

mysql> explain select age,name from student where name='zhangsan';#age不在二级索引树上,产生了回表,extra为null
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------+
| 1 | SIMPLE | student | NULL | ref | name_index | name_index | 202 | const | 1 | 100.00 | NULL |
+----+-------------+---------+------------+------+---------------+------------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select name from student;
+----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | index | NULL | name_index | 202 | NULL | 5 | 100.00 | Using index |
+----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

mysql>
11、联合索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
mysql> show create table student\G
*************************** 1. row ***************************
Table: student
Create Table: CREATE TABLE `student` (
`uid` int unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`age` tinyint unsigned NOT NULL,
`sex` enum('M','W') NOT NULL,
PRIMARY KEY (`uid`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.00 sec)

mysql> select * from student where age = 20 order by name;
+-----+---------+-----+-----+
| uid | name | age | sex |
+-----+---------+-----+-----+
| 2 | gaoyang | 20 | W |
| 6 | weiwie | 20 | M |
+-----+---------+-----+-----+
2 rows in set (0.01 sec)

mysql> explain select * from student where age = 20 order by name;
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
| 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 5 | 20.00 | Using where; Using filesort |
+----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

mysql>

如何优化上面的查询场景

  1. 首先,我们是对age进行查询,所以试着给age添加一个索引

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    mysql> create index age_index on student(age);
    Query OK, 0 rows affected (0.12 sec)
    Records: 0 Duplicates: 0 Warnings: 0

    mysql> explain select * from student where age = 20 order by name;
    +----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+----------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+----------------+
    | 1 | SIMPLE | student | NULL | ref | age_index | age_index | 1 | const | 2 | 100.00 | Using filesort |
    +----+-------------+---------+------------+------+---------------+-----------+---------+-------+------+----------+----------------+
    1 row in set, 1 warning (0.01 sec)

    mysql>

    发现使用了索引,但是还是存在using filesort,这该如何解决

  2. 由于一次查询只能用到一个索引,所以使用联合索引,为age和name创建联合索引,这里将age放在前面,这是因为我们先对age查询,如果将name放在前边,则达不到效果

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    mysql> drop index age_index on student;
    Query OK, 0 rows affected (0.06 sec)
    Records: 0 Duplicates: 0 Warnings: 0

    mysql> create index age_name_index on student(age,name);
    Query OK, 0 rows affected (0.08 sec)
    Records: 0 Duplicates: 0 Warnings: 0

    mysql> explain select * from student where age = 20 order by name;
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    | 1 | SIMPLE | student | NULL | ref | age_name_index | age_name_index | 1 | const | 2 | 100.00 | NULL |
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    1 row in set, 1 warning (0.00 sec)

    mysql>

    成功取消using filesort,这是在构建索引树时就已经对name排序了

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    mysql> explain select name,age from student where name = 'zhangsan' order by age;
    +----+-------------+---------+------------+-------+----------------+----------------+---------+------+------+----------+--------------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+----------------+----------------+---------+------+------+----------+--------------------------+
    | 1 | SIMPLE | student | NULL | index | age_name_index | age_name_index | 203 | NULL | 5 | 20.00 | Using where; Using index |
    +----+-------------+---------+------------+-------+----------------+----------------+---------+------+------+----------+--------------------------+
    1 row in set, 1 warning (0.01 sec)

    mysql> explain select * from student where name = 'zhangsan';#未使用到索引
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    | 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 5 | 20.00 | Using where |
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    1 row in set, 1 warning (0.00 sec)

    mysql> explain select * from student where age = 20;#使用到索引,但存在回表
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    | 1 | SIMPLE | student | NULL | ref | age_name_index | age_name_index | 1 | const | 2 | 100.00 | NULL |
    +----+-------------+---------+------------+------+----------------+----------------+---------+-------+------+----------+-------+
    1 row in set, 1 warning (0.01 sec)

    mysql>

    只使用name无法使用索引,而使用age可以使用索引,所以索引的先后很重要的!

12、like,not in,or

有些资料提示like,not in这些用不到索引,实际上,经过MySQL的优化后,还是能使用索引的

  1. like

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    mysql> select * from student where name like 'zhang%';
    +-----+----------+-----+-----+
    | uid | name | age | sex |
    +-----+----------+-----+-----+
    | 1 | zhangsan | 18 | M |
    +-----+----------+-----+-----+
    1 row in set (0.00 sec)

    mysql> explain select * from student where name like 'zhang%';#这里使用前缀索引进行索引查找
    +----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
    | 1 | SIMPLE | student | NULL | range | name_index | name_index | 202 | NULL | 1 | 100.00 | Using index condition |
    +----+-------------+---------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
    1 row in set, 1 warning (0.02 sec)

    mysql> explain select * from student where name like '%zhang%';#无法使用前缀索引进行查找,无法使用索引
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    | 1 | SIMPLE | student | NULL | ALL | NULL | NULL | NULL | NULL | 5 | 20.00 | Using where |
    +----+-------------+---------+------------+------+---------------+------+---------+------+------+----------+-------------+
    1 row in set, 1 warning (0.00 sec)

    mysql>
  2. not in

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    mysql> create index age_index on student(age);
    Query OK, 0 rows affected (0.18 sec)
    Records: 0 Duplicates: 0 Warnings: 0

    mysql> select * from student where age not in(18,20);
    +-----+----------+-----+-----+
    | uid | name | age | sex |
    +-----+----------+-----+-----+
    | 5 | liuxiang | 19 | W |
    | 4 | linfeng | 21 | W |
    | 3 | chenwei | 22 | M |
    +-----+----------+-----+-----+
    3 rows in set (0.00 sec)

    mysql> explain select * from student where age not in(18,20);
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    | 1 | SIMPLE | student | NULL | range | age_index | age_index | 1 | NULL | 4 | 100.00 | Using index condition |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    1 row in set, 1 warning (0.01 sec)

    mysql> explain select age from student where age not in(18,20);
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    | 1 | SIMPLE | student | NULL | range | age_index | age_index | 1 | NULL | 4 | 100.00 | Using where; Using index |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    1 row in set, 1 warning (0.00 sec)

    mysql>
  3. or

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    mysql> explain select age from student where age <18 or age > 20;
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    | 1 | SIMPLE | student | NULL | range | age_index | age_index | 1 | NULL | 3 | 100.00 | Using where; Using index |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
    1 row in set, 1 warning (0.00 sec)

    mysql> explain select * from student where age <18 or age > 20;
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    | 1 | SIMPLE | student | NULL | range | age_index | age_index | 1 | NULL | 3 | 100.00 | Using index condition |
    +----+-------------+---------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
    1 row in set, 1 warning (0.00 sec)

    mysql>
13、Innodb自适应哈希索引

我们知道,在使用二级索引树的时候,可能会产生回表。当某些查询频繁访问二级索引且模式固定(如 WHERE name = 'zhangsan' 的查询),InnoDB 会在内存中基于 B+ 树的二级索引创建一个哈希索引。自适应哈希索引的作用是加速特定查询,避免二级索引树和主键索引树的回表过程。

一般情况下,二级索引会先查询二级索引树,如果二级索引树无法满足,就会到主键索引树上查找,这产生了回表,而如果生成了自适应哈希索引,那么在使用二级索引时,会直接根据哈希索引找到对应的数据页得到数据,跳过了二级索引树和主键索引树的收缩过程。

image-20250329015255357

当然,自适应哈希索引并不是所有情况都能提高速度,因为自适应哈希索引的维护也是需要消耗性能的,当达到一定的数据量时,并不一定能提高速度,所以需要根据实际情况开关。如果很多线程经常阻塞在哈希索引锁上,就应该视情况关闭自适应哈希索引

  • 查看自适应哈希索引是否打开

    1
    show variables like 'innodb_adaptive_hash_index'
    1
    2
    3
    4
    5
    6
    7
    mysql> show variables like 'innodb_adaptive_hash_index';
    +----------------------------+-------+
    | Variable_name | Value |
    +----------------------------+-------+
    | innodb_adaptive_hash_index | ON |
    +----------------------------+-------+
    1 row in set (0.62 sec)
  • 查看自适应哈希索引的分区,每一个分区有自己的一把锁

    1
    show variables like 'innodb_adaptive_hash_index_parts'
    1
    2
    3
    4
    5
    6
    7
    8
    9
    mysql> show variables like 'innodb_adaptive_hash_index_parts';
    +----------------------------------+-------+
    | Variable_name | Value |
    +----------------------------------+-------+
    | innodb_adaptive_hash_index_parts | 8 |
    +----------------------------------+-------+
    1 row in set (0.01 sec)

    mysql>
  • 查看自适应哈希索引使用情况

    1
    show engine innodb status\G
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
     mysql> show engine innodb status\G
    *************************** 1. row ***************************
    Type: InnoDB
    Name:
    Status:
    =====================================
    2024-11-21 02:29:15 123599813867200 INNODB MONITOR OUTPUT
    =====================================
    Per second averages calculated from the last 2 seconds
    -----------------
    BACKGROUND THREAD
    -----------------
    srv_master_thread loops: 8 srv_active, 0 srv_shutdown, 18035 srv_idle
    srv_master_thread log flush and writes: 0
    ----------
    SEMAPHORES
    ----------
    OS WAIT ARRAY INFO: reservation count 69
    OS WAIT ARRAY INFO: signal count 65
    RW-shared spins 0, rounds 0, OS waits 0
    RW-excl spins 0, rounds 0, OS waits 0
    RW-sx spins 0, rounds 0, OS waits 0
    Spin rounds per wait: 0.00 RW-shared, 0.00 RW-excl, 0.00 RW-sx
    ------------
    TRANSACTIONS
    ------------
    Trx id counter 4020774
    Purge done for trx's n:o < 4020771 undo n:o < 0 state: running but idle
    History list length 0
    LIST OF TRANSACTIONS FOR EACH SESSION:
    ---TRANSACTION 405074790583512, not started
    0 lock struct(s), heap size 1128, 0 row lock(s)
    ---TRANSACTION 405074790582704, not started
    0 lock struct(s), heap size 1128, 0 row lock(s)
    ---TRANSACTION 405074790581896, not started
    0 lock struct(s), heap size 1128, 0 row lock(s)
    --------
    FILE I/O
    --------
    I/O thread 0 state: waiting for completed aio requests (insert buffer thread)
    I/O thread 1 state: waiting for completed aio requests (read thread)
    I/O thread 2 state: waiting for completed aio requests (read thread)
    I/O thread 3 state: waiting for completed aio requests (read thread)
    I/O thread 4 state: waiting for completed aio requests (read thread)
    I/O thread 5 state: waiting for completed aio requests (write thread)
    I/O thread 6 state: waiting for completed aio requests (write thread)
    I/O thread 7 state: waiting for completed aio requests (write thread)
    I/O thread 8 state: waiting for completed aio requests (write thread)
    Pending normal aio reads: [0, 0, 0, 0] , aio writes: [0, 0, 0, 0] ,
    ibuf aio reads:
    Pending flushes (fsync) log: 0; buffer pool: 0
    1306 OS file reads, 705 OS file writes, 321 OS fsyncs
    0.00 reads/s, 0 avg bytes/read, 0.00 writes/s, 0.00 fsyncs/s
    -------------------------------------
    INSERT BUFFER AND ADAPTIVE HASH INDEX
    -------------------------------------
    Ibuf: size 1, free list len 0, seg size 2, 0 merges
    merged operations:
    insert 0, delete mark 0, delete 0
    discarded operations:
    insert 0, delete mark 0, delete 0
    Hash table size 34679, node heap has 3 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    Hash table size 34679, node heap has 1 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    Hash table size 34679, node heap has 0 buffer(s)
    0.00 hash searches/s, 0.00 non-hash searches/s
    ---
    LOG
    ---
    Log sequence number 1666873789
    Log buffer assigned up to 1666873789
    Log buffer completed up to 1666873789
    Log written up to 1666873789
    Log flushed up to 1666873789
    Added dirty pages up to 1666873789
    Pages flushed up to 1666873789
    Last checkpoint at 1666873789
    Log minimum file id is 508
    Log maximum file id is 509
    286 log i/o's done, 0.00 log i/o's/second
    ----------------------
    BUFFER POOL AND MEMORY
    ----------------------
    Total large memory allocated 0
    Dictionary memory allocated 536507
    Buffer pool size 8191
    Free buffers 6788
    Database pages 1399
    Old database pages 497
    Modified db pages 0
    Pending reads 0
    Pending writes: LRU 0, flush list 0, single page 0
    Pages made young 184, not young 492
    0.00 youngs/s, 0.00 non-youngs/s
    Pages read 1257, created 143, written 327
    0.00 reads/s, 0.00 creates/s, 0.00 writes/s
    No buffer pool page gets since the last printout
    Pages read ahead 0.00/s, evicted without access 0.00/s, Random read ahead 0.00/s
    LRU len: 1399, unzip_LRU len: 0
    I/O sum[0]:cur[0], unzip sum[0]:cur[0]
    --------------
    ROW OPERATIONS
    --------------
    0 queries inside InnoDB, 0 queries in queue
    0 read views open inside InnoDB
    Process ID=1526, Main thread ID=123599193114304 , state=sleeping
    Number of rows inserted 0, updated 0, deleted 0, read 0
    0.00 inserts/s, 0.00 updates/s, 0.00 deletes/s, 0.00 reads/s
    Number of system rows inserted 47, updated 331, deleted 45, read 5318
    0.00 inserts/s, 0.00 updates/s, 0.00 deletes/s, 0.00 reads/s
    ----------------------------
    END OF INNODB MONITOR OUTPUT
    ============================

    1 row in set (0.06 sec)

    mysql>

    其中有两个重要参数:

    • RW-latch: 等待的线程数量(自适应哈希索引默认分配了8个分区),同一个分区等待的线程数量过多,下面并没有显示RW-latch,如果等待线程过多,应该关闭自适应哈希索引

      1
      2
      3
      4
      5
      6
      7
      8
      9
      ----------
      SEMAPHORES
      ----------
      OS WAIT ARRAY INFO: reservation count 69
      OS WAIT ARRAY INFO: signal count 65
      RW-shared spins 0, rounds 0, OS waits 0
      RW-excl spins 0, rounds 0, OS waits 0
      RW-sx spins 0, rounds 0, OS waits 0
      Spin rounds per wait: 0.00 RW-shared, 0.00 RW-excl, 0.00 RW-sx
    • 自适应哈希索引的使用情况

      1
      INSERT BUFFER AND ADAPTIVE HASH INDEX
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      -------------------------------------
      INSERT BUFFER AND ADAPTIVE HASH INDEX
      -------------------------------------
      Ibuf: size 1, free list len 0, seg size 2, 0 merges
      merged operations:
      insert 0, delete mark 0, delete 0
      discarded operations:
      insert 0, delete mark 0, delete 0
      Hash table size 34679, node heap has 3 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      Hash table size 34679, node heap has 1 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      Hash table size 34679, node heap has 0 buffer(s)
      0.00 hash searches/s, 0.00 non-hash searches/s
      ---

      这里显示查询结果使用哈希索引和没有使用哈希索引的使用比例,如果哈希索引使用较少,应该视情况关闭自适应哈希索引,如果自适应哈希索引使用较多,则确实达到了加速效果。

数据库表的设计范式

范式最主要的好处就是能够减少冗余存储,其他都是附加的,如消除异常(插入异常,更新异常和删除异常)

第一范式

表中的每一列都应该是不可再分的原子值,也就是说,每一个字段必须包含单一的值,而不能是一个复合值或多值属性.

让我们看看下面这个表的设计

员工表
EmployeeID
departmentName
Name
Address
job
jobDescription
skill
departmentDescription
email

从第一范式我们可以看出,表字段Address实际上还可以细分,我们不能直接了当的使用如“湖南省湘潭市雨湖区xxx”等作为地址,应该继续细分,这在我们以后需要统计xxx省,xxx市,xxx区的数据时很有帮助,所以上述表应该设计成下面这样

员工表
EmployeeID
departmentName
Name
addressID
job
jobDescription
skill
departmentDescription
email
员工地址表
addressID
city
country
street

第二范式

表中所以非主键字段必须要和所有主键字段都有关联关系,第二范式一般在出现联合主键的时候分析

例如一个学生选课表:

里面有六个字段,分别是学号,名字,年龄,课程名称,成绩,学分。其中,学号和课程名词作为联合主键,但是我们会发现,姓名和年龄两个字段和课程并没有关联关系,学分和学号也没有关联关系,在因此,这些字段不适合放在同一张表,而应该分开,这个表的设计不符合第二范式。

我们继续分析,学分字段的数据就是冗余存储,不同的学号选择同一门课程的学分都是相同的,并不需要重复存储,同样,年龄和名字不会因为选择不同课程而会导致不同,存在冗余,随着学生年级的提示,课程的数量不断增加,这张表的冗余数据就会非常多

首先,学生和课程是多对多的关系,所以需要引入一张中间表,学生选课表

学生表:学号,姓名,年龄

课程表:课程id,课程名称,学分

选课表:学号,课程id,成绩

同理,我们再分析下面这个,使用EmployeeID和departmentName作为联合主键,发现其余字段并不符合第二范式的设计

分析部门和员工的关系,是一对多的关系,一个部门有多个员工

image-20250329003729120

第三范式

在单主键中,属性不依赖于其他非主属性,非主键部分必须依赖于主键

image-20250329003952937

一般满足第三范式即可,还有其他范式,例如:BC范式,第四范式,但是这些范式会导致sql查询的复杂度,降低数据库的查询性能,需要权衡

数据库表的设计

1、一对一关系

子表中添加外键列关联父表的主键

2、一对多关系

一个实体可以关联多个其他实体实例,但每个实例只能属于一个父实体,在”多”的一方表中添加外键列关联”一”的一方的主键

3、多对多关系

创建中间表(关联表),包含两个外键分别关联两个表的主键

例子:电商系统

  1. 用户user
  2. 商品:product
  3. 订单:order

分析:

  1. 用户-商品:没有关系
  2. 用户-订单:一对多
  3. 商品-订单:多对多

各表初始设计:

  • 用户user
uid name age sex
1000 zhang 20 M
1020 liu 21 W
2010 wang 22 M
  • 商品product
pid pname price amount
1 手机 600.0 100
2 笔记本 2000.0 199
3 电池 10 200
  • 订单order
orderid uid pid number money totalprice addrinfo
O1000 1000 1 1 600 4640 海淀区
O1000 1000 2 2 4000 4640 海淀区
O1000 1000 3 4 40 4640 海淀区
O2000 1020 2 1 2000 2000 海南

在订单表的最初设计中,订单表的很多行的列内容都是相同的,如果要添加一个商品,就需要同时修改很多行的内容,如总价格这一列,每一行都要修改totalprice这一列,这就是数据冗余存储,一个操作会导致大面积的相同数据的大面积修改,我们不需要存同一份订单的多个uid,totalprice和addrinfo,这些信息只需要存放一次就足够了


由于于订单和商品是多对多关系,可以增加一张中间表orderlist,用于存放订单内容,下面是修改后,order表和orderlist表的设计

订单order

orderid uid totalprice addrinfo
O1000 1000 4640 海淀区
O2000 1020 2000 海南

订单内容orderlist

orderid pid number money
O1000 1 1 600
O1000 2 2 4000
O1000 3 4 40

epoll简单使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cerrno>
#include <cstdlib>
#include <sys/epoll.h>
#include <unistd.h>
#include <sys/socket.h>
#include <cstdio>
#include <fcntl.h>
#include <netinet/in.h>
#include <csignal>
#include <cstring>

int main()
{
//创建监听套接字
int listenfd = socket(AF_INET,SOCK_STREAM,0);
if(listenfd == -1)
{
perror("socket");
exit(EXIT_FAILURE);
}
//设置端口复用
int opt = 1;
if(setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt))==-1)
{
perror("setsockopt");
close(listenfd);
return EXIT_FAILURE;
}
//将监听套接字设置为非阻塞
int flag = fcntl(listenfd,F_GETFL,0);
if (flag == -1) {
perror("fcntl F_GETFL");
close(listenfd);
return EXIT_FAILURE;
}
if (fcntl(listenfd, F_SETFL, flag | O_NONBLOCK) == -1) {
perror("fcntl F_SETFL");
close(listenfd);
return EXIT_FAILURE;
}
//绑定端口
sockaddr_in serverAddr{};
serverAddr.sin_family = AF_INET;
serverAddr.sin_addr.s_addr = htonl(INADDR_ANY);
serverAddr.sin_port = htons(12332);

if (bind(listenfd, reinterpret_cast<sockaddr*>(&serverAddr), sizeof(serverAddr)) == -1) {
perror("bind");
close(listenfd);
return EXIT_FAILURE;
}

//开始监听
if (listen(listenfd, SOMAXCONN) == -1) {
perror("listen");
close(listenfd);
return EXIT_FAILURE;
}

//创建epoll实例
int epollfd = epoll_create1(0);
if(epollfd == -1)
{
perror("epoll_create");
return EXIT_FAILURE;
}
//将监听描述服放到epoll树上
epoll_event event;
event.events = EPOLLIN|EPOLLET;
event.data.fd = listenfd;
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, listenfd, &event) == -1) {
perror("epoll_ctl listenfd");
close(listenfd);
close(epollfd);
return EXIT_FAILURE;
}
//创建事件数组
epoll_event events[1024];
int count = 0;
while(true)
{
count = epoll_wait(epollfd,events,1024,-1);
for(int i = 0; i < count; ++i)
{
if(events[i].data.fd == listenfd)
{
//建立连接
sockaddr_in clientAddr{};
socklen_t clientsize = sizeof(clientAddr);
int clientfd = accept(listenfd,reinterpret_cast<sockaddr*>(&clientAddr),&clientsize);
if (clientfd == -1) {
if (errno == EAGAIN || errno == EWOULDBLOCK) break;
perror("accept");
continue;
}
//将客户端的文件描述服设置为非阻塞
int clientFlags = fcntl(clientfd, F_GETFL,0);
if (clientFlags == -1) {
perror("fcntl F_GETFL");
close(listenfd);
continue;
}
if (fcntl(clientfd, F_SETFL, clientFlags | O_NONBLOCK) == -1) {
perror("fcntl client");
close(clientfd);
continue;
}
//将监听描述服上树
epoll_event clientEvent{};
clientEvent.events = EPOLLIN|EPOLLET|EPOLLRDHUP;
clientEvent.data.fd = clientfd;
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, clientfd, &clientEvent) == -1) {
perror("epoll_ctl client");
close(clientfd);
}
}
else{
int clientfd = events[i].data.fd;
//EPOLLERR 和 EPOLLHUP 事件如果发生,总是会被报告,无论这些事件是否在 events 中被指定
if(events[i].events & (EPOLLRDHUP | EPOLLHUP | EPOLLERR)) {
printf("Client %d disconnected abnormally\n", clientfd);
epoll_ctl(epollfd, EPOLL_CTL_DEL, clientfd, nullptr);
close(clientfd);
continue;
}
// 循环读取全部数据(边缘触发模式必须)
while(1) {
char buffer[1024];
ssize_t num_bytes = recv(clientfd, buffer, sizeof(buffer), 0);

if(num_bytes > 0) {
buffer[num_bytes] = '\0';
printf("Received %zd bytes from client %d: %s\n",
num_bytes, clientfd, buffer);
}
else if(num_bytes == 0) {
printf("Connection closed by client: %d\n", clientfd);
epoll_ctl(epollfd, EPOLL_CTL_DEL, clientfd, nullptr);
close(clientfd);
break;
}
else { // num_bytes == -1
if(errno == EAGAIN || errno == EWOULDBLOCK) {
// 数据读取完毕
printf("EAGAIN/EWOULDBLOCK encountered for client %d - no more data to read\n", clientfd);
break;
}
perror("recv");
epoll_ctl(epollfd, EPOLL_CTL_DEL, clientfd, nullptr);
close(clientfd);
break;
}
}
}
}
}
close(listenfd);
close(epollfd);
return 0;
}

测试:

方式1:

1
nc localhost 12332

方式2:

1
telnet localhost 12332

二叉树遍历

作者: 苏丙榅
链接: https://subingwen.cn/data-structure/binary-tree/#4-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
来源: 爱编程的大丙

  1. 前序遍历:先访问根节点,然后前序遍历左子树,最后前序遍历右子树
  2. 中序遍历:中序遍历左子树,然后访问根节点,最后中序遍历右子树
  3. 后序遍历:后序遍历左子树,然后后序遍历右子树,最后访问根节点

通过三种遍历方式的定义可知,前、中、后其实是相对于根节点而言的,并且二叉树的左子树和右子树的遍历也是递归的,同样遵循前序、中序、后序的规则,在遍历过程中如果树为空,直接返回,递归结束。

一、先序遍历

1.1、递归遍历

1
2
3
4
5
6
7
8
void preorder(TreeNode* root)
{
if (root == nullptr)
return;
std::cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}

1.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void preorderTraversal(TreeNode* root)
{
if (root == nullptr)
return;
// 利用栈先进后出的特性,现将右子树入站,再将左子树入站
// 这样会先弹出左子树,达到先处理左子树再处理右子树的特点
std::stack<TreeNode*> nodeStack;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node = nodeStack.top();
nodeStack.pop();

std::cout << node->val << " ";
if(node->right)
{
nodeStack.push(node->right);
}
if(node->left)
{
nodeStack.push(node->left);
}
}
}

二、中序遍历

2.1、递归遍历

1
2
3
4
5
6
7
8
void inorder(TreeNode* tree)
{
if (tree == nullptr)
return;
inorder(tree->left);
std::cout << tree->val << " ";
inorder(tree->right);
}

2.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void inorderTraversal(TreeNode* tree)
{
if (tree == nullptr)
return;
std::stack<TreeNode*> nodeStack;
TreeNode* current = tree;
while (current != nullptr || !nodeStack.empty())
{
// 先将当前节点的所有左子树入栈
while (current)
{
nodeStack.push(current);
current = current->left;
}
current = nodeStack.top();
nodeStack.pop();
std::cout << current->val << " ";
// 处理右子树
current = current->right;
}
}

二、后序遍历

3.1、递归遍历

1
2
3
4
5
6
7
8
void postorder(TreeNode* tree)
{
if (tree == nullptr)
return;
postorder(tree->left);
postorder(tree->right);
std::cout << tree->val << " ";
}

3.2、非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void postorderTraversal(TreeNode* tree)
{
std::stack<TreeNode*> stack1,stack2;
stack1.push(tree);
while(!stack1.empty())
{
TreeNode* current = stack1.top();
//根据栈先进后出的特点,将根节点先入栈,根节点会后输出
stack1.pop();
stack2.push(current);
//现将左子树放入stack1,再放入右子树,这样压入stack2的顺序就是先压入右子树,再压入左子树
// 最后会先输出左子树,再输出右子树,最后输出根节点
if(current->left)
{
stack1.push(current->left);
}
if(current->right)
{
stack1.push(current->right);
}
}
while(!stack2.empty())
{
std::cout << stack2.top()->val << " ";
stack2.pop();
}
}

四、层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void levelOrder(TreeNode* tree)
{
if (tree == nullptr)
return;
std::queue<TreeNode*> q;
q.push(tree);
while(!q.empty())
{
int size = q.size();
for(int i = 0; i < size; ++i)
{
TreeNode* current = q.front();
std::cout << current->val << " ";
if(current->left)
{
q.push(current->left);
}
if(current->right)
{
q.push(current->right);
}
q.pop();
}
std::cout << "\n";
}
}

五、释放树节点

使用先序遍历、中序遍历还是后序遍历的方式创建二叉树,在释放资源的时候一定使用的是后续遍历的方式,也就是从下往上。

1
2
3
4
5
6
7
8
9
10
11
12
13
void freeTree(TreeNode* root)
{
if (root == nullptr)
{
return;
}
// 先释放左子树
freeTree(root->left);
// 再释放右子树
freeTree(root->right);
// 最后释放根节点
delete root;
}

C++生成随机数

一、random_device

创建随机设备对象,通过本设备的随机数生成器生成随机种子,而不是使用时间生产随机种子

1
std::random_device rd;

二、mt19937

创建随机数引擎对象,参数是创建的随机设备对象random_device,随机设备对象重载了(),rd()在这里是可调用对象

1
std::mt19937 gen(rd());

三、uniform_int_distribution

创建随机数分布对象-均匀分布,参数是范围,最小值和最大值的范围,范围是闭区间

1
std::uniform_int_distribution<int> dis(min,max);

四、生成随机数

1
int randomNumber = dis(gen);

完整代码

生成一个随机数数组

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<int> generateRandomArray(int size)
{
std::vector<int> arr;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(0, 10000);
for (size_t i = 0; i < size; i++)
{
arr.push_back(dis(gen));
}
return arr;
}

排序算法

From: 爱编程的大丙
Author: 爱编程的大丙
原文链接:八大排序算法

一、冒泡排序

  1. 冒泡排序是稳定排序,原因是相等的值不交换,且只与相邻元素交换,不会打乱原有顺序
  2. 做法:每次都从待排序的部分挑选出一个最大值放在最后(挑选的方式是相邻元素都比较一次)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void bubble_sort(std::vector<int>& arr)
{
int length = arr.size() - 1;
// isSwap用于减少循环轮数,防止已经排好序后继续排序
bool isSwap = false;
// i 控制循环轮数
for (int i = 0; i < length; ++i)
{
isSwap = false;
// j不能从j=i+1开始,一次完整的内循环只能将最大的数字放在相对最后的位置,并没有对左边的数字进行排序
for (int j = 0; j < length - i; ++j)
{
if (arr[j] > arr[j + 1])
{
std::swap(arr[j], arr[j + 1]);
isSwap = true;
}
}
if (!isSwap)
{
break;
}
}
}

二、选择排序

  1. 选择排序是不稳定排序 原因是会出现长距离交换,会打乱原有的顺序
  2. 做法:每次都从待排序的部分找到最大或最小值的位置然后交换放在相对最前的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void selected_sort(std::vector<int>& arr)
{
int length = arr.size() - 1;
// i 控制循环轮数
for (int i = 0; i < length; ++i)
{
int minPos = i;
// 找到最大或最小值的位置
for (int j = i + 1; j <= length; ++j)
{
if (arr[minPos] > arr[j])
{
minPos = j;
}
}
if (minPos != i)
{
std::swap(arr[i], arr[minPos]);
}
}
}

三、插入排序

  1. 插入排序是稳定排序, 原因是我们是根据待排序数组的顺序进行排序的,且与相邻元素比较,不会出现长距离交换的情况
  2. 做法:从待排序的数组中选出第一个元素A,让这个元素和已排好序的数组的最后一个进行比较B,如果A<B,则将A后移一位覆盖数据,从此往复,知道找到小于B的元素,然后将B插入到该位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort(std::vector<int>& arr)
{
int length = arr.size() - 1;
// i表示待排序的数组
for (int i = 1; i <= length; ++i)
{
// 使用一个临时的变量存储待排序的第一个元素,方便后续插入数据和移动覆盖数据
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = temp;
}
}

四、 希尔排序

  1. 插入排序的优化版 但并不是稳定排序 原因是:交换的元素并不是相邻的元素,存在长距离交换的情况
  2. 做法:利用插入排序趋向排好序的数组排序速度快的特点,将一个大数组分为一个个小数组对其进行插入排序,又因为每一个小数组都趋向于有序,所以排序速度很快,最后会导致整个大数组都趋向于有序,这样就能提高排序速度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shell_sort(std::vector<int>& arr)
{
int length = arr.size();
for (int gap = length / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < length; ++i)
{
int temp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > temp)
{
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
}
}

五、快速排序

  1. 快速排序是不稳定排序,原因是因为交换的元素并不是相邻的元素,会出现长距离交换元素的情况
  2. 做法:快速排序采用分治法,通常在中间取一个基准数,然后将比基准数小的元素放在左边,比基准数大的元素放在右边,如果左边的元素比基准数大,右边的元素比基准数小,则交换这两个元素的位置,直到所有元素都排好序,即left>right停止,然后重新划分子数组,通过不断递归的方式,当所有的子数组都排好序后,整个数组也就排好序了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void quick_sort(std::vector<int>& arr)
{
if (arr.empty())
{
return;
}
quick_sort(arr, 0, arr.size() - 1);
}
void quick_sort(std::vector<int>& arr, int left, int right)
{
if (left >= right)
{
return;
}
// 基准数 取中间元素作为基准数,left + (right - left) / 2是为了防止left+right溢出
int pivotValue = arr[left + (right - left) / 2];

int begin = left - 1, end = right + 1;
while (begin < end)
{
do
{
begin++;
} while (arr[begin] < pivotValue);
do
{
end--;
} while (arr[end] > pivotValue);

if (begin < end)
{
std::swap(arr[begin], arr[end]);
}
}
quick_sort(arr, left, end);
// 下面这个的left参数不能使用begin+1,否则会导致一个元素会排序两次
quick_sort(arr, end + 1, right);
}

六、归并排序

  1. 归并排序是稳定排序, 原因是:交换的是相邻的元素且是有序的,相等的元素不会交换位置
  2. 通过不断递归将数组分到不可再分为止,最后每一个子数组都是一个元素,然后将具有同一个分支的两个子数组进行合并,合并成一个有序数组最后,当所有的子数组都合并成一个有序数组后,整个数组也就排好序了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void merge_sort(std::vector<int>& arr)
{
if (arr.empty())
{
return;
}
std::vector<int> temp(arr.size());
merge_sort(arr, temp, 0, arr.size() - 1);
}
void merge_sort(std::vector<int>& arr, std::vector<int>& temp, int left, int right)
{
if (left >= right)
{
return;
}
int mid = left + (right - left) / 2;
// 递归分割数组
merge_sort(arr, temp, left, mid);
merge_sort(arr, temp, mid + 1, right);
// 合并同一个分支上的两个有序数组(开始时每一个子数组都是1个元素)
int i = left, j = mid + 1, index = 0;
while (i <= mid && j <= right)
{
if (arr[i] < arr[j])
{
temp[index++] = arr[i++];
}
else
{
temp[index++] = arr[j++];
}
}
// 将剩余的元素放入临时数组,只会有一个while循环执行
while (i <= mid)
{
temp[index++] = arr[i++];
}
while (j <= right)
{
temp[index++] = arr[j++];
}

// 将临时数组中的元素放入原数组
for (int k = 0; k < index; ++k)
{
arr[left + k] = temp[k];
}
}

七、堆排序

  1. 堆排序是不稳定排序,因为顶部元素和最后一个非叶子节点交换时是长距离交换,会打乱顺序
  2. 做法:先构建大根堆,通过将第一个元素和最后一个元素交换后,最后一个元素就是最大的元素,然后将剩下的元素进行再次堆排序,直到所有的元素都排好序为止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void head_sort(std::vector<int>& arr, int length, int parent)
{
// 不需要构建满二叉树,我们默认数组就是满二叉树
int maxIndex = parent;
int leftChild = 2 * parent + 1;
int rightChild = 2 * parent + 2;
// 找到最大值的索引
if (leftChild < length && arr[leftChild] > arr[maxIndex])
{
maxIndex = leftChild;
}
if (rightChild < length && arr[rightChild] > arr[maxIndex])
{
maxIndex = rightChild;
}
// 如果最大值不是父节点,则交换父节点和最大值的值
if (maxIndex != parent)
{
std::swap(arr[parent], arr[maxIndex]);
// 继续递归调整交换后的子树,继续比较其与其子树的大小
head_sort(arr, length, maxIndex);
}
}
void head_sort(std::vector<int>& arr)
{
if (arr.empty())
{
return;
}
// 由于大根堆的性质,父节点的值大于等于子节点的值,所以我们从最后一个非叶子节点开始调整
// 逐个向上比较全部的非叶子节点,直到将最大的非叶子节点调整到根节点,此时根节点就是最大值
// 然后将根节点和最后一个叶子节点交换(将最大值放在最后),然后重新构建大根堆
// 循环这个过程,直到所有的非叶子节点都调整完毕

//arr.size()/2-1就是最后一个元素的父节点,构建大根堆
for (int i = arr.size() / 2 - 1; i >= 0; --i)
{
head_sort(arr, arr.size(), i);
}
//开始排序操作
for (int i = arr.size() - 1; i > 0; --i)
{
// 交换根节点和最后一个叶子节点,i就是最后一个叶子节点的索引
std::swap(arr[0], arr[i]);
// 重新构建大根堆,length是去掉最后一个叶子节点的长度,即去掉节点i后的长度
head_sort(arr, i, 0);
}
}

推荐链接:六大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序