目 录
（1）为什么 MySQL 选择B+树作为索引数据结构，而不是B树？
一、概述
- 索引是一种能够提高检索效率的有序的数据结构；
- 索引是解决 SQL 慢查询的一种方式；
- 不同的存储引擎有不同的索引类型；
- 分类：
- 数据结构分类：
- B+树 索引：采用 B+树的数据结构，MySQL 的 InnoDB 存储引擎采用该索引；
- Hash 索引：采用哈希表的数据结果，MySQL 仅 MEMORY 存储引擎支持。
- 物理存储分类：
- 聚集索引：索引和表中数据在一起，存储时按照索引顺序存储，一张表只能有一个聚集索引；
- 非聚集索引：索引和表中数据分离，索引独立于表空间，一张表可以有多个非聚集索引。
- 字段特性分类：
- 主键索引；
- 唯一索引；
- 普通索引；
- 全文索引：字段类型都是文本内容才可以使用，仅 InnoDB 和 MyISAM 存储引擎支持。
- 字段个数分类：
- 单列索引（单一索引）；
- 联合索引（复合索引、组合索引）。
- 优点：
- 提高查询性能：通过创建索引，大大降低了数据库查询的数据量；
- 加速排序；
- 减少 I/O 开销。
- 缺点：
- 占据额外的存储空间；
- 增、删、改操作性能损耗：每次对表进行修改操作，都需要更新索引；
- 资源消耗大：索引需要占用内存和 CPU 资源，特别是在大规模并发访问情况下。
- 建议使用索引的场景：
- 频繁执行查询操作的字段；
- 表数据量较大；
- 需要排序或分组的字段；
- 外键关联的字段。
- 不建议使用索引的场景：
- 频繁执行更新操作的表；
- 表数据量较小；
- 唯一性很差的字段。
二、索引
1.主键索引
主键字段会自动添加索引，被称为主键索引。
2.唯一索引
unique 约束的字段会自动添加索引，被称为唯一索引。
3.查看索引
show index from 表名;
4.添加索引
（1）建表时添加
create table 表名(
字段 类型,
……,
index 索引名(字段名)
);
drop table if exists pet;
create table pet(
id int primary key auto_increment,
no bigint unique,
name varchar(10),
age char(2),
sex char(2),
index pet_index(name)
);
show index from pet;
（2）建表后添加
- alter table 表名 add index 索引名(字段);
- create index 索引名 on 表名(字段名);
drop table if exists pet;
create table pet(
id int primary key auto_increment,
no bigint unique,
name varchar(10),
age char(2),
sex char(2),
);
-- 第一种方式
alter table pet add index pet_index_name(name);
-- 第二种方式
create index pet_index_age on pet(age);
show index from pet;
5.删除索引
alter table 表名 drop index 索引名;
alter table pet drop index pet_index_age;
alter table pet drop index pet_index_name;
show index from pet;
三、树
开始前，推荐一个数据结构可视化平台【Data Structure Visualization】。
1.二叉树
| id | name |
|---|---|
| 50 | 后羿 |
| 43 | 鲁班七号 |
| 28 | 伽罗 |
| 56 | 艾琳 |
| 54 | 李元芳 |
| 66 | 孙尚香 |
| 78 | 狄仁杰 |
| 76 | 虞姬 |
假设存储有一张表如上，若不为 id 字段添加索引，则默认进行全表扫描。若要查询 id = 76 的英雄姓名，至少要进行 8 次 I/O 开销。
为了提高效率，可以为 id 字段添加索引，假设使用了二叉树的数据结构，则只需要 5 次便可查找到 76。
但是，如果遇到一种极端情况如下图，所有 id 都是有序排列的，其查找效率等同于链表查询，时间复杂度是 O(n)。所以，MySQL 没有选择二叉树作为索引数据结构。
2.红黑树
通过自旋平衡规则进行旋转，子节点会自动分叉为 2 个分支，从而降低树的高度。数据有序插入时比二叉树数据检索性能更好。
- 红黑树有以下特点：左根右，根叶黑，不红红，黑路同。
- 左根右：左子树小于根节点，右子树大于根节点；
- 根叶黑：根节点是黑色，所有叶子节点也是黑色；
- 不红红：红色节点的子节点必须是黑色；
- 黑路同：从任意节点到其叶子节点的路径上，黑色节点的数量相同。
- 若查找 id = 76 英雄的姓名，则需要进行 4 次 I/O 开销。效率较普通二叉树高，但当数据量庞大时，树的高度会很高，查询效率也较低。所以，MySQL 也没有采用红黑树作为索引数据结构。
3.B树
- B树是自平衡树，又称为平衡多路查找树；
- 每个节点下的子节点数量大于 2；
- 每个节点 可以存储多个数据；
- 3 阶 B树，一个节点下最多可以有 3 个子节点，每个节点最多有 2 个数据；
- 4 阶 B树，一个节点下最多可以有 4 个子节点，每个节点最多有 3 个数据；
- 每个节点不仅存储了索引值，还存储了索引值对应的数据行；
- 但是 B树 不适合区间查找。
4.B+树
- B+树 将数据都存储在了叶子节点，且叶子节点之间使用链表连接；
- B+树 非叶子节点上只有索引值，所以非叶子节点可以存储更多的索引值，从而提高检索效率；
- MySQL 采用 16 阶B+树作为索引数据结构。
（1）为什么 MySQL 选择B+树作为索引数据结构，而不是B树？
答：
1.非叶子节点可以存储更多的键值，阶数可以更大，减少 I/O 开销，提高检索效率；
2.所有数据都是有效存储在叶子节点上的，分组查询效率更高；
3.数据页之间、数据记录之间采用链表连接，升序、降序操作更方便。
（2） 表中没有主键索引，还会创建B+树吗？
答：会的。若一张表没有主键索引，默认会使用一个隐藏的内置聚集索引。该聚集索引基于表的物理存储顺序构建，通常使用B+树实现。
四、Hash 索引
- 支持 Hash 索引的存储引擎：
- InnoDB：不支持手动创建，系统自动维护一个自适应的 Hash 索引。即使手动指定某字段采用 Hash 索引，最终查看索引时，索引类型还是B+树；
- MEMORY。
- Hash 索引底层是 Hash 表。一个数组，数组中每个元素是链表。和 Java 中的 HashMap 一样，Hash 表中每个元素都是 key-value 结构，key 存储索引值，value 存储行指针；
- 优点：只能用于等值比较，效率很高；
- 缺点：不支持排序，不支持范围查找；
- 关于 Hash 表的更多内容可以查看【Java基础关键_021_集合（五）】。
五、聚集索引和非聚集索引
- 按照数据的物理存储方式不同，可以将索引分为聚集索引和非聚集索引；
- 存储引擎是 InnoDB 的，主键上的索引属于聚集索引；存储引擎是 MyISAM 的，任意字段上的索引都是非聚集索引；
- InnoDB 的物理存储方式，在硬盘上生成以下文件：
- [ 表名 ].ibd（InnoDB data 表索引 + 数据）；
- [ 表名 ].frm（存储表结构信息）。
- MyISAM 的物理存储方式，在硬盘上生成以下文件：
- [ 表名 ].MYD（表数据）；
- [ 表名 ].MYI（表索引）；
- [ 表名 ].frm（表结构）。
- MySQL 8.0 开始，不再生成 frm 文件，引入了数据字典，用数据字典统一存储表结构信息；
- 聚集索引优点是：将数据存储在索引树的叶子节点上，可以减少一次查询，因为查询索引树的同时可以获取数据；缺点是：对数据进行修改或删除时需要更新索引树，会增加系统开销。
六、二级索引
- 二级索引属于非聚集索引，也称为辅助索引；
- 所有非主键索引都是二级索引；
- 叶子节点上存储的是一行记录的主键值，而不是这一行数据；
- 使用【select * 】会产生“回表”，即回到原数据表。所以尽量避免使用【select * 】语句，以此提升执行效率。
七、覆盖索引
- 覆盖索引指某个查询语句可以通过索引覆盖完成，不需要“回表”查询真实数据；
- 覆盖指在执行查询语句时，查询需要的所有列都可以从索引中提取到，不需要再去查询实际数据行获取查询所需数据；
- 创建覆盖索引需要考虑查询字段的选择，若查询需要的字段较多，可能需要创建包含多列的覆盖索引。
八、索引下推
- 一般情况下，索引下推是 MySQL 优化器自动处理的；
- 索引下推是 MySQL 中的一种优化方法，可以将查询中的过滤条件下推到索引层级中处理，从而减少回表次数，优化查询效率；
- 在使用索引下推时，MySQL 会在索引的叶节点层级执行查询的过滤条件，过滤掉无用的索引记录，仅返回符合条件的记录的主键，如此可以避免查询时回表读取表格的数据行。
九、单列索引和复合索引
- 单列索引是对数据库表中某一列或属性创建索引，对该列进行快速查找和排序操作；
- 复合索引是对数据库表中多个列创建索引；
- 最左前缀原则：复合索引中，索引最左边的列会被优先使用；
- 复合索引较单列索引的优势：
- 减少索引的数量；
- 提高查询性能；
- 覆盖查询：如果复合索引包含了所有查询需要的列，则数据库可以直接使用索引中的数据；
- 提高排序和分组性能。