MySQL 索引原理

1、数据结构

B Tree指的是Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层，如下：

B+ Tree是基于B Tree和叶子节点的顺序访问指针进行实现，它具有B Tree的平衡性，并且通过顺序指针来提供查询的性能，如下图：

2、数据操作

DDL：从根节点开始进行二分查找，找到一个key的所在的指针，然后递归地在指针所指的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

DML：增删会破坏tree的平衡性，插入删除之后，需要对tree进行一个分裂、合并、旋转等操作来维护平衡性。

MySQL 索引类型

MySQL 的索引按照存储方式分为两类： 聚集索引：也称 Clustered Index。是指关系表记录的物理顺序与索引的逻辑顺序相同。由于一张表只能按照一种物理顺序存放，一张表最多也只能存在一个聚集索引。与非聚集索引相比，聚集索引有着更快的检索速度。

MySQL 里只有 INNODB 表支持聚集索引，INNODB 表数据本身就是聚集索引，也就是常说 IOT，索引组织表。非叶子节点按照主键顺序存放，叶子节点存放主键以及对应的行记录。所以对 INNODB 表进行全表顺序扫描会非常快。

非聚集索引：也叫 Secondary Index。指的是非叶子节点按照索引的键值顺序存放，叶子节点存放索引键值以及对应的主键键值。MySQL 里除了 INNODB 表主键外，其他的都是二级索引。MYISAM，memory 等引擎的表索引都是非聚集索引。简单点说，就是索引与行数据分开存储。一张表可以有多个二级索引。

假设表中有如下数据：

select * from t1;
+-------+----------+--------+------+--------------+
| id    | username | gender | age  | phone_number |
+-------+----------+--------+------+--------------+
| 10001 | 小花     | 女     |   18 | 18501877098  |
| 10005 | 小李     | 女     |   21 | 15827654555  |
| 10006 | 小白     | 男     |   38 | 19929933000  |
| 10009 | 小何     | 男     |   35 | 19012378676  |
| 10002 | 小王     | 男     |   20 | 17760500293  |
| 10003 | 小赵     | 女     |   29 | 13581386000  |
| 10004 | 小青     | 女     |   25 | 13456712000  |
| 10007 | 小米     | 男     |   23 | 19800092354  |
| 10008 | 小徐     | 女     |   22 | 18953209331  |
+-------+----------+--------+------+--------------+

MYISAM 存储引擎介绍

主键字段索引树：

非聚集索引树：

INNODB存储引擎

主键字段索引树：

非聚集索引树：

1、B+ Tree索引

大多数MySQL存储引擎默认都是B+ Tree，因为不需要进行全表扫描，只需要对树进行搜索即可，所以查询的速度会快很多。InnoDB 的 B+Tree 索引分为主索引和辅助索引。主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找。

2、哈希索引

哈希索引能以 O(1) 时间进行查找，但是失去了有序性：

• 无法用于排序与分组；
• 只支持精确查找，无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

3、全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。

4、空间索引

MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查。

常见的索引

1、独立的列

索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引。

select * from t_data_json where v_commission_amount+1 >30 limit 10

2、多列索引

在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。

3、索引列的顺序

让选择性最强的索引列放在前面。索引的选择性是指：不重复的索引值和记录总数的比值。最大值为 1，此时每个记录都有唯一的索引与其对应。选择性越高，每个记录的区分度越高，查询效率也越高。这就是为什么一些枚举值的字段不建议建索引。

4、前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列，合理使用前缀索引，只索引开始的部分字符。选择合适的前缀长度，既可以节省空间，也可以不用增加更多的查询成本。区分度越高性能越高，意味着重复的值就越少。

索引的优点

• 大大减少了服务器需要扫描的数据行数。
• 帮助服务器避免进行排序和分组，以及避免创建临时表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作。临时表主要是在排序和分组过程中创建，不需要排序和分组，也就不需要创建临时表）。
• 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）。

参考B+ Tree演示地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引设计（前缀索引）：https://opensource.actionsky.com/20210120-mysql/

索引设计（MySQL的索引结构）：https://opensource.actionsky.com/20201111-mysql/