MySQL 索引

索引模型

  • 哈希表
    • 适用于只有等值查询的场景，Memory引擎默认索引
    • InnoDB支持自适应哈希索引，不可干预，由引擎自行决定是否创建
  • 有序数组：在等值查询和范围查询场景中的性能都非常优秀，但插入和删除数据需要进行数据移动，成本太高。因此，只适用于静态存储引擎
  • 二叉平衡树：每个节点的左儿子小于父节点，父节点又小于右儿子，时间复杂度是 O(log(N))

  • 多叉平衡树：索引不止存在内存中，还要写到磁盘上。为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。因此，要使用“N 叉”树。

    B+Tree

    B-Tree 与 B+Tree

    B-Tree

    MySQL索引选择以及优化 - 图1

    B+Tree

    MySQL索引选择以及优化 - 图2
    InnoDB 使用了 B+ 树索引模型。假设有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引，如下所示：
    MySQL索引选择以及优化 - 图3

  • 主键索引：也被称为聚簇索引，叶子节点存的是整行数据

  • 非主键索引：也被称为二级索引，叶子节点内容是主键的值

    注意事项

  • 索引基于数据页有序存储，可能发生数据页的分裂(页存储空间不足)和合并(数据删除造成页利用率低)

  • 数据的无序插入会造成数据的移动，甚至数据页的分裂
  • 主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小

  • 索引字段越小，单层可存储数据量越多，可减少磁盘IO

    1. // 假设一个数据页16K、一行数据1K、索引间指针6字节、索引字段bigint类型(8字节)
    2. // 索引个数
    3. K = 16*1024/(8+6) =1170
    4. // 单个叶子节点记录数
    5. N = 16/1 = 16
    6. // 三层B+记录数
    7. V = K*K*N = 21902400

    :::info MyISAM也是使用B+Tree索引，区别在于不区分主键和非主键索引，均是非聚簇索引，叶子节点保存的是数据文件的指针 :::

    索引选择

    优化器选择索引的目的，是找到一个最优的执行方案，并用最小的代价去执行语句。在数据库里面，扫描行数是影响执行代价的因素之一。扫描的行数越少，意味着访问磁盘数据的次数越少，消耗的 CPU 资源越少。
    当然，扫描行数并不是唯一的判断标准，优化器还会结合是否使用临时表、是否排序等因素进行综合判断。

    扫描行数如何计算

    一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，称之为“基数”（cardinality）。

    1. -- 查看当前索引基数
    2. mysql> show index from test;
    3. +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    4. | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
    5. +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
    6. | test  |          0 | PRIMARY  |            1 | id          | A         |      100256 | NULL     | NULL   |      | BTREE      |         |               |
    7. | test  |          1 | index_a  |            1 | a           | A         |      98199  | NULL     | NULL   | YES  | BTREE      |         |               |
    8. +-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

    从性能的角度考虑，InnoDB 使用采样统计，默认会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。因此，上述两个索引显示的基数并不相同。
    而数据表是会持续更新的，索引统计信息也不会固定不变。所以，当变更的数据行数超过 1/M 的时候(innodb_stats_persistent=on时默认10，反之16)，会自动触发重新做一次索引统计。

    1. mysql> show variables like '%innodb_stats_persistent%';
    2. +--------------------------------------+-------------+
    3. | Variable_name                        | Value       |
    4. +--------------------------------------+-------------+
    5. -- 是否自动触发更新统计信息，当被修改的数据超过10%时就会触发统计信息重新统计计算
    6. | innodb_stats_auto_recalc             | ON          |
    7. -- 控制在重新计算统计信息时是否会考虑删除标记的记录
    8. | innodb_stats_include_delete_marked   | OFF         |
    9. -- 对null值的统计方法，当变量设置为nulls_equal时，所有NULL值都被视为相同
    10. | innodb_stats_method                  | nulls_equal | 
    11. -- 操作元数据时是否触发更新统计信息
    12. | innodb_stats_on_metadata             | OFF         |
    13. -- 统计信息是否持久化存储
    14. | innodb_stats_persistent              | ON          |
    15. -- innodb_stats_persistent=on，持久化统计信息采样的抽样页数
    16. | innodb_stats_persistent_sample_pages | 20          |
    17. -- 不推荐使用，已经被innodb_stats_transient_sample_pages替换
    18. | innodb_stats_sample_pages            | 8           |
    19. -- 瞬时抽样page数
    20. | innodb_stats_transient_sample_pages  | 8           |
    21. +--------------------------------------+-------------+

  • 除了因为抽样导致统计基数不准外，MVCC也会导致基数统计不准确。例如：事务A先事务B开启且未提交，事务B删除部分数据，在可重复读中事务A还可以查询到删除的数据，此部分数据目前至少有两个版本，有一个标识为deleted的数据。

  • 主键是直接按照表的行数来估计的，表的行数，优化器直接使用show table status like 't'的值

  • 手动触发索引统计：

    1. -- 重新统计索引信息
    2. mysql> analyze table t;

    排序对索引选择的影响

    1. -- 创建表
    2. mysql> CREATE TABLE `t` (
    3.         `id` int(11) NOT NULL,
    4.         `a` int(11) DEFAULT NULL,
    5.         `b` int(11) DEFAULT NULL,
    6.         PRIMARY KEY (`id`),
    7.         KEY `a` (`a`),
    8.         KEY `b` (`b`)
    9.       ) ENGINE=InnoDB;
    10. -- 定义测试数据存储过程
    11. mysql> delimiter ;
    12.       CREATE PROCEDURE idata ()
    13.       BEGIN
    14.       DECLARE i INT ;
    15.       SET i = 1 ;
    16.       WHILE (i <= 100000) DO
    17.        INSERT INTO t
    18.       VALUES
    19.        (i, i, i) ;
    20.       SET i = i + 1 ;
    21.       END
    22.       WHILE ;
    23.       END;
    24.       delimiter ;
    25. -- 执行存储过程，插入测试数据
    26. mysql> CALL idata ();
    27. -- 查看执行计划，使用了字段a上的索引
    28. mysql> explain select * from t where a between 10000 and 20000;
    29. +----+-------------+-------+-------+---------------+-----+---------+------+-------+-----------------------+
    30. | id | select_type | table | type  | possible_keys | key | key_len | ref  | rows  | Extra                 |
    31. +----+-------------+-------+-------+---------------+-----+---------+------+-------+-----------------------+
    32. |  1 | SIMPLE      | t     | range | a             | a   | 5       | NULL | 10000 | Using index condition |
    33. +----+-------------+-------+-------+---------------+-----+---------+------+-------+-----------------------+
    34. -- 由于需要进行字段b排序，虽然索引b需要扫描更多的行数，但本身是有序的，综合扫描行数和排序，优化器选择了索引b，认为代价更小
    35. mysql> explain select * from t where (a between 1 and 1000) and (b between 50000 and 100000) order by b limit 1;
    36. +----+-------------+-------+-------+---------------+-----+---------+------+-------+------------------------------------+
    37. | id | select_type | table | type  | possible_keys | key | key_len | ref  | rows  | Extra                              |
    38. +----+-------------+-------+-------+---------------+-----+---------+------+-------+------------------------------------+
    39. |  1 | SIMPLE      | t     | range | a,b           | b   | 5       | NULL | 50128 | Using index condition; Using where |
    40. +----+-------------+-------+-------+---------------+-----+---------+------+-------+------------------------------------+
    41. -- 方案1：通过force index强制走索引a，纠正优化器错误的选择，不建议使用（不通用，且索引名称更变语句也需要变）
    42. mysql> explain select * from t force index(a) where (a between 1 and 1000) and (b between 50000 and 100000) order by b limit 1;
    43. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    44. | id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra                                              |
    45. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    46. |  1 | SIMPLE      | t     | range | a             | a   | 5       | NULL |  999 | Using index condition; Using where; Using filesort |
    47. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    48. -- 方案2：引导 MySQL 使用我们期望的索引，按b,a排序，优化器需要考虑a排序的代价
    49. mysql> explain select * from t where (a between 1 and 1000) and (b between 50000 and 100000) order by b,a limit 1;
    50. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    51. | id | select_type | table | type  | possible_keys | key | key_len | ref  | rows | Extra                                              |
    52. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    53. |  1 | SIMPLE      | t     | range | a,b           | a   | 5       | NULL |  999 | Using index condition; Using where; Using filesort |
    54. +----+-------------+-------+-------+---------------+-----+---------+------+------+----------------------------------------------------+
    55. -- 方案3：有些场景下，我们可以新建一个更合适的索引，来提供给优化器做选择，或删掉误用的索引
    56. ALTER TABLE `t`
    57. DROP INDEX `a`,
    58. DROP INDEX `b`,
    59. ADD INDEX `ab` (`a`,`b`) ;

    索引优化

    索引选择性

    索引选择性 = 基数 / 总行数

    1. -- 表t中字段xxx的索引选择性
    2. select count(distinct xxx)/count(id) from t;

    索引的选择性，指的是不重复的索引值（基数）和表记录数的比值。选择性是索引筛选能力的一个指标，索引的取值范围是 0~1 ，当选择性越大，索引价值也就越大。
    在使用普通索引查询时，会先加载普通索引，通过普通索引查询到实际行的主键，再使用主键通过聚集索引查询相应的行，以此循环查询所有的行。若直接全量搜索聚集索引，则不需要在普通索引和聚集索引中来回切换，相比两种操作的总开销可能扫描全表效率更高。
    实际工作中，还是要看业务情况，如果数据分布不均衡，实际查询条件总是查询数据较少的部分，在索引选择较低的列上加索引，效果可能也很不错。

    覆盖索引

    覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段
    MySQL索引选择以及优化 - 图4

    1. -- 只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表
    2. select ID from T where k between 3 and 5
    3. -- 增加字段V，每次查询需要返回V，可考虑把k、v做成联合索引
    4. select ID,V from T where k between 3 and 5

    最左前缀原则+索引下推

    1. -- id、name、age三列，name、age上创建联合索引
    2. -- 满足最左前缀原则，name、age均走索引
    3. select * from T where name='xxx' and age=12
    4. -- Mysql自动优化，调整name、age顺序，，name、age均走索引
    5. select * from T where age=12 and name='xxx'
    6. -- name满足最左前缀原则走索引，MySQL5.6引入索引下推优化（index condition pushdown)，即索引中先过滤掉不满足age=12的记录再回表
    7. select * from T where name like 'xxx%' and age=12
    8. -- 不满足最左前缀原则，均不走索引
    9. select * from T where name like '%xxx%' and age=12
    10. -- 满足最左前缀原则，name走索引
    11. select * from T where name='xxx'
    12. -- 不满足最左前缀原则，不走索引
    13. select * from T where age=12

    联合索引建立原则：

  • 如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

  • 空间：优先小字段单独建立索引，例如：name、age，可建立(name,age)联合索引和(age)单字段索引

    前缀索引

    1. mysql> create table SUser(
    2. ID bigint unsigned primary key,
    3. name  varchar(64),   
    4. email varchar(64),
    5. ...
    6. )engine=innodb;
    7. -- 以下查询场景
    8. mysql> select name from SUser where email='xxx';
    9. -- 方案1：全文本索引，回表次数由符合条件的数据量决定
    10. mysql> alter table SUser add index index1(email);
    11. -- 方案2：前缀索引，回表次数由前缀匹配结果决定
    12. mysql> alter table SUser add index index2(email(6));

    前缀索引可以节省空间，但需要注意前缀长度的定义，在节省空间的同时，不能增加太多查询成本，即减少回表验证次数

    如何设置合适的前缀长度？

    1. -- 预设一个可以接受的区分度损失比，选择满足条件中最小的前缀长度
    2. select count(distinct left(email,n))/count(distinct email) from SUser;

    如果合适的前缀长度较长？

    比如身份证号，如果满足区分度要求，可能需要12位以上的前缀索引，节约的空间有限，又增加了查询成本，就没有必要使用前缀索引。此时可以考虑使用以下方式：

  • 倒序存储

    1. -- 查询时字符串反转查询
    2. mysql> select field_list from t where id_card = reverse('input_id_card_string');

  • 使用hash字段

    1. -- 创建一个整数字段，来保存身份证的校验码，同时在这个字段上创建索引
    2. mysql> alter table t add id_card_crc int unsigned, add index(id_card_crc);
    3. -- 查询时使用hash字段走索引查询，再使用原字段精度过滤
    4. mysql> select field_list from t where id_card_crc=crc32('input_id_card_string') and id_card='input_id_card_string'

    以上两种方式的缺点：

  • 不支持范围查询

  • 使用hash字段需要额外占用空间，新增了一个字段

  • 读写时需要额外的处理，reverse或者crc32等

    前缀索引对覆盖索引的影响？

    1. -- 使用前缀索引就用不上覆盖索引对查询性能的优化
    2. select id,email from SUser where email='xxx';

    唯一索引

    建议使用普通索引，唯一索引无法使用change buffer，内存命中率低

    索引失效

  • 不做列运算，包括函数的使用，可能破坏索引值的有序性

  • 避免 %xxx 式查询使索引失效
  • or语句前后没有同时使用索引，当or左右查询字段只有一个是索引，该索引失效
  • 组合索引ABC问题，最左前缀原则
  • 隐式类型转化
  • 隐式字符编码转换
  • 优化器放弃索引，回表、排序成本等因素影响，改走其它索引或者全部扫描