mysql索引与B+树浅析

一、为什么B+树更适合用于索引

B+树特征：

• 有n棵子树的中间节点有n个元素，这些元素不存储数据，只存储索引信息
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素，InnoDB是最小元素

二、B+树的操作

【参考】

• https://developer.aliyun.com/article/9280
• https://www.cnblogs.com/nullzx/p/8729425.html

1、插入

1.1 插入过程

1、中间节点和叶子节点都没满 → 直接插入
2、叶子节点满了，中间节点没满 → 叶子节点分裂

• 中间值放入上一级中间节点
• 小于中间值的放入左边，大于等于的放入右边

3、中间节点和叶子节点都满了 → 先分裂叶子节点后分裂中间节点直至结构不违规

• 拆分叶子节点，同2
• 拆分中间节点，步骤同2

• 【example】以阶数为4的B+树为例：
  

1.2 InnoDB索引分裂优化

以上方式的分裂带来的问题？

• 分裂次数多
• 空间浪费 → 顺序插入的数据只会插入到后面的空

• 【example】假设一个节点只能放9条记录，顺序插入 1、2、3、4、5、6、7、8、9，再次插入10，则会分裂成:

• P1：1、2、3、4
• P2：5、6、7、8、9、10
  两个节点，在InnoDB中也就是使用两页进行存储，由于是顺序插入，分裂后P1将不会再有数据插入，导致空间的浪费，同时P2又会再次分裂。
  那么如何优化？

1.2.1 旋转

叶子节点已经满了，但是其兄弟节点没满，会将记录移动到其兄弟节点上，默认先向左移动

• 【example】可以看到15插入到第二个叶子节点，并将12移动到第一个子节点
  

1.2.2 顺序插入的优化

• 对于随机插入的数据，则取节点的中间记录作为分裂点的记录进行分裂。
• 若在同一个方向进行插入的记录数量大于等于5，首先会进行定位，定位记录是待插入记录位置的前面一条记录，若定位记录后面有超过三条记录，则分裂点为即为第三条记录，否则分裂点即为插入记录。

• 【example】
  

1.2.3 顺序插入分裂优化带来的Bug#67718

在特定的插入情况下，InnoDB的索引页利用率极低
bug的详细描述： https://bugs.mysql.com/bug.php?id=67718

• 【example】假设一页只能存5条记录，顺序插入1、2、3、4、5，假设这时候再插入100，这时候会导致索引页的分裂

• 索引页P1：1、2、3、4、5
• 索引页P2：100

这时候在插入9，由于InnoDB上层节点是记录的下级节点最小值，及1和100，则这时候9会被插入到索引页P1，再次发生分裂

• 索引页P1：1、2、3、4、5
• 索引页P3：9
• 索引页P2：100

同样，若在插入8，会再次分裂索引页：

• 索引页P1：1、2、3、4、5
• 索引页P4：8
• 索引页P3：9
• 索引页P2：100

导致索引页的空间利用率极低
目前mysql已修复
【参考】https://blog.csdn.net/weixin_35044595/article/details/113168956

2、删除

B+树的删除是根据填充因子（最小50%）来控制的

1、中间节点和叶子节点都不小于填充因子
直接删除，若该元素还是中间节点的元素，用该叶子节点最右边的元素代替
2、只有叶子节点小于填充因子
合并叶子节点和他的兄弟节点，同时更新中间节点
3、中间节点和叶子节点都小于填充因子
合并叶子节点和他的兄弟节点，更新中间节点，合并中间节点和他的兄弟节点

三、聚集索引和辅助索引

1、聚集索引

• 【定义】聚集索引是按照每张表的主键构造一棵B+树，同时叶子节点中存放的是整张表的行记录数据，同时也将聚集索引叶子节点称为数据页。
  若表没有主键，则以该表第一个唯一非空索引构造聚集索引。
  若既没有主键也没有唯一非空索引，则innodb会生成一个隐藏的6字节的列作为隐藏主键用于构建聚集索引。
• 【example】

CREATE TABLE t (
    a INT NOT NULL,
    b VARCHAR(8000),
    c INT NOT NULL,
    PRIMARY KEY (a),
    KEY idx_c (c)
) ENGINE=INNODB;
 
INSERT INTO t SELECT 1, REPEAT('a', 7000), -1;
INSERT INTO t SELECT 2, REPEAT('b', 7000), -2;
INSERT INTO t SELECT 3, REPEAT('c', 7000), -3;
INSERT INTO t SELECT 4, REPEAT('d', 7000), -4;
1
2
3
4
5
6
7
8
9
10
11
12

mysql的每页只有16kb，也就是每页最多存放两条记录，其聚集索引构造图如下图所示：

比如查询a=1的数据，通过根节点（索引页）找到a=3的数据所在页是0005，读取0005页，在此页读取a=3的数据（通过B+树索引找到数据所在数据页，在数据页中通过二分查找搜索指定数据）

2、辅助索引（非聚集索引）

对于辅助索引，叶子节点并不包含行记录的所有数据，叶子节点除了包含键值以外，每个叶子节点的索引行中还包含了相应行数据的聚集索引键。

• 【example】（用 三 1 中的表数据）辅助索引构造图如下图所示
  
  比如：SELECT * FROM t WHERE c = -3;
  先通过辅助索引找到主键索引3 ，然后在通过聚集索引查找数据，相比于通过聚集索引查询，通过辅助索引查询，需要二次查询。

3、索引管理

3.1 索引操作

• 创建：

方式1：ALTER TABLE table_name ADD index_type index_name(index_col_name,...);
方式2：CREATE index_type index_name ON table_name(index_col_name,...);
1
2

• 删除：

方式1：ALTER TABLE table_name DROP index_type index_name;
方式2：DROP index_type index_name ON table_name;
1
2

• 查看：

SHOW INDEX FROM table_name;
1

• 【example】
  

3.2 Cardinality值

3.2.1 定义

Cardinality值是索引中不重复记录数量的预估值，Cardinality除以表的行数越接近于1，说明索引的选择性越高。
Cardinality的大小mysql优化器对语句执行计划进行判定时依据，如果Cardinality的值越小，说明该索引的区分度越小， 优化器会认为，这个索引对语句没有太大帮助，而不使用索引， 如果Cardinality值越大，就意味着，使用索引能排除越多的数据，执行也更为高效， 这个值越大在做表连接的时候，就越有机会选择这个索引。

3.2.2 统计方式

生产环境，索引的更新非常频繁，如果每次索引更新都更新Cardinality值，将会给数据库带来很大的负担，另外如果表非常大，更新一次Cardinality值的时间会很长。

• 【统计时机】

• 自上次统计Cardinality值，表中1/16的数据已经发生变化
• 内部计数器stat_modified_counter（表示发生变化的次数）>2 000 000 000
• 手动触发统计（ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX以及访问INFORMATION_SCHEMA架构下的表TABLES和STATISTICS）

• 【统计方法 - 采样】

• 取得B+树叶子节点的个数，记为A
• 随机取得B+树索引中的8个叶子结点，统计出每个叶子结点的记录个数，P1,P2,P3,…,P8
• 根据采样信息计算出Cardinality值，Cardinality=(P1+P2+…+P8)/8*A

上述统计方法说明，每次得到的Cardinality值可能是不同的，若每次得到的Cardinality值都是一样的，说明表索引的叶子节点数量小于等于8个，每次采样都会取到这些页，每次得到的Cardinality值相同。

四、B+树索引的使用

1、联合索引

联合索引是指对表上的多个列进行索引。

• 【example】

CREATE TABLE t (
    a INT,
    b INT,
    c INT,
    PRIMARY KEY (a),
    KEY idx_b_c (b,c)
) ENGINE = INNODB
1
2
3
4
5
6
7

• 【联合索引的好处】

• “一个顶多个”，没多一个索引多会增加写操作的开销和磁盘空间的开销
  对于SELECT * FROM t WHERE b = 1 AND c = 2 和 SELECT * FROM t WHERE b = 1都可以使用联合索引idx_b_c，而对于SELECT * FROM t WHERE c = 1则不会使用联合索引idx_b_c，从图中可以看出，叶子节点中c的zhi为1、 2、1、4、1，是无序的，所以对于c的查询无法使用联合索引。
• 可以避免多一次排序操作
  因为联合索引已经对后面的键值进行了排序，比如SELECT * FROM t WHERE b = 1 ORDER BY c DESC LIMIT 3; 从表中可以看到对于分别建立索引b、c的查询需要额外进行一次排序操作

注：Using index condition是MySQL5.6引入，含义在取出索引的同时判断是否可以进行WHERE条件过滤，将WHERE部分的过滤操作放在了存储引擎层。

• 可以使用覆盖索引，减少回表查询
  覆盖索引即从辅助索引中就可以得到需要查询的数据，而不需要查询聚集索引中的记录。
  （1）对于key1,key2,…组成的联合索引，由于其叶子节点存储了（primary key1, primary key2, …, key1, key2, …），以下类似操作都可以通过使用一次辅助联合索引完成查询：

  SELECT  key2 FROM table WHERE key1 = xxx;
  SELECT primary key1, primary key2, key1, key2 FROM table WHERE key1 = xxx;
  1
  2

  （2）SELECT count(*) FROM table; 由于辅助索引远小于聚集索引，InnoDB引擎会选择辅助索引来进行统计。
  

2、优化器选择不使用索引的情况

在用户选取的数据是整行数据时，辅助索引不能覆盖到全部信息，通过辅助索引查询到指定数据后，还需要通过聚集索引进行一次查询获取全部数据，虽然辅助索引中的数据是顺序存放的，但是再一次通过聚集索引查找的数据是无序的，这就变成了磁盘上的离散度操作。

如果访问的数据量比较小，优化器仍然会选择辅助索引，但是当数据量比较大时（一般占整张表数据量20%），优化器会选择聚集索引或者不使用索引进行查找。

• 【example】可以看到possible_keys有两个辅助索引，但是最终未选择，type为ALL，key为空。
  

3、索引提示

MySQL支持索引提示（INDEX HINT），显示告诉优化器使用哪个索引。
命令：

• USE INDEX 告诉优化器可以选择该索引，但是优化器会根据自己的判断选择索引
• FORCE INDEX 强制使用某索引
  使用场景：
• MySQL数据库的优化器错误地选择了某个索引
• 可选择索引较多，优化器选择索引的时间大于SQL语句本身

五、MySQL索引优化

1、EXPLAIN命令

【参考】https://www.mysqlzh.com/doc/66/292.html

2、几个常用的索引优化

2.1 id分页赋予minId和maxId初始值

适用场景：

• 无法使用覆盖索引，需进行二次查询
• 辅助索引无法完全覆盖WHERE条件

【example】对于id分页第一页，

SELECT * FROM job_assign_detail WHERE job_id = 1100292 AND create_date > '2021-07-27 12:00:00' AND id >= 1 limit 20
1

由于create_date不在所用辅助索引中，需通过聚集索引读取到数据后进行过滤，若从id>=1开始，则通过辅助索引定位到聚集索引后，进行二次读取时有397825条不符合条件的数据被读取过滤，且数据量很大，会有离散读的情况，会造成慢查。

因此，先查通过辅助索引查出minId，SELECT min(id) FROM job_assign_detail WHERE job_id = 1100292 AND create_date > ‘2021-07-27 12:00:00’;查询minId只需要覆盖索引即可完成，不需要二次读取，执行速度快。

然后再进行查询SELECT * FROM job_assign_detail WHERE job_id = 1100292 AND create_date > ‘2021-07-27 12:00:00’ AND id >= #{minId} limit 20;

同样对于id分页最后一页，也有类似的情况。

2.2 只读取需要的字段，可通过覆盖索引避免二次回表查询

（四 1）中已举例

2.3 利用辅助索引排序，避免出现Using filesort

【example】可以看到第一张图的key_len为5，使用了全部的联合索引idx_create_source_status_end_date，未出现Using filesort，而第二张图所示的查询方式，需要进行额外的排序操作。

2.4 避免不走索引的情况

• 联合索引注意最左匹配原则
• 索引上不要做任何操作，比如计算、使用函数、类型转换等
• 联合索引中间字段使用了范围条件，后面的字段将不会走索引
• IS NULL、IS NOT NULL、<>、!=不会走索引
• LIKE条件通配符在开头不会走索引

2.5 唯一索引的取舍

普通索引和唯一索引的效率比较

• 查询
  对于普通索引来说，查找到第一条复合条件的记录后需要查找下一个记录，直到碰到不满足条件的记录。
  对于唯一索引来说，查找到第一个满足条件的记录后就会停止继续检索。
  由于MySQL是按页将数据拉到缓存中，在普通索引数据量不大的情况下，效率是差不多的
• 插入、更新
  对于普通索引，插入会使用Insert Buffer，更新会使用Change Buffer，等待merge操作写入磁盘，减少对磁盘的离散访问。

而对于唯一索引，其不会使用Insert Buffer和Change Buffer（因为每次都需要判断唯一性的约束，需要把数据读取到内存才能判断，数据已经在内存了，也就不需要Insert Buffer和Change Buffer了）。

因此对于内存中存在的数据，普通索引和唯一索引的更新都很快，而对于没在内存中的数据，唯一索引的插入和更新需要访问磁盘，而普通索引通过Insert Buffer和Change Buffer减少磁盘的访问。将数据从磁盘读入内存涉及随机 IO 的访问，是数据库里面成本最高的操作之一。因此在写多的情况下，普通索引的写入性能是优于唯一索引的。