MySQL--索引（详解）

                                                   欢迎大家来到权权的博客~
                               欢迎大家对我的博客进行指导，有什么不对的地方，我会及时改进哦~ 

博客主页链接点这里–>：权权的博客主页链接

一、本节目标

了解什么是索引
了解除索引使用的数据结构
掌握B+树在索引中的应用
掌握索引分类和使用

二、简介

2.1索引是什么？

概念：MySQL的索引是⼀种数据结构，它可以帮助数据库高效地查询、更新数据表中的数据。索引通过⼀定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度。

MySQL 索引类似于书籍的目录，通过指向数据行的位置，可以快速定位和访问表中的数据，比如汉语字典的目录（索引）页，我们可以按笔画、偏旁部首、拼音等排序的目录（索引）快速查找到需要的字。
• 笔画索引

• 偏旁部⾸索引

• 拼⾳索引

2.2为什么要使用索引？

使用索引的目的只有⼀个，就是提升数据检索的效率，在应用程序的运行过程中，查
询操作的频率远远⾼于增删改的频率。

三、索引应该选择哪种数据结构？

3.1 HASH

众所周知，hash是最重要的数据结构木有之一，时间复杂度达到O（1）,可是，索引却不选择它，因为hash不支持范围查找。

3.2 二叉搜索树

⼆叉搜索树的中序遍历是⼀个有序数组，但有几个问题导致它不适合用作索引的数据结构。
二叉树的中序遍历是一个有序序列–>它支持范围查找，但是时间复杂度可能会退化成一个单边树O（N），节点个数过多时，无法保证树高。

由于数据库中的数据是在磁盘上保存的，每一次访问子节点都会发生一次磁盘IO，磁盘IO是制约数据库性能的主要因素。
磁盘IO：计算机系统与硬盘之间的数据输入和输出操作

3.3 B树

使用B树可以有效解决树高问题时间复杂度：0（logN）.

相同数据量的情况下，N叉树的树高可以得到有效的控制，也就意味着在相同数据量的情况
下可以减少IO的次数，从而提升效率。但是MySQL认为B树做为索引的数据结构不够好。

3.4 B+树

3.4.1 简介

B+树是⼀种经常用于数据库和⽂件系统等场合的平衡查找树，MySQL索引采用的数据结构，以3阶
B+树为例，如下图所示：

时间复杂度：O（logN）

3.4.2 B+树的特点

•能够保持数据稳定有序，插⼊与修改有较稳定的时间复杂度
• ⾮叶⼦节点仅具有索引作⽤，不存储数据，所有叶⼦节点保真实数据
• 所有叶⼦节点构成⼀个有序链表，可以按照key排序的次序依次遍历全部数据

3.4.3B+树和B树的对比

•叶子节点中的数据是连续的，且相互链接，便于区间查找和搜索。
• 非叶子节点的值都包含在叶子节点中
• 对于B+树而言，在相同树高的情况下，查找任⼀元素的时间复杂度都⼀样，性能均衡。

索引一般使用B+树

面试题：索引使用了什么数据结构?

四、MySQL的页

4.1 为什么使用页？

在 .ibd 文件中最重要的结构体就是Page(⻚)，页是内存与磁盘交互的最小单元，默认大小为16KB，每次内存与磁盘的交互⾄少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为在使用数据的过程中，根据局部性原理，将来要使用的数据大概率与当前访问的数据在空间上是临近的，所以⼀次从磁盘中读取⼀页的数据放⼊内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘I/O提高性能。

局部性原理：
是指程序在执⾏时呈现出局部性规律，在⼀段时间内，整个程序的执⾏仅限于程序中的某部分分。相应地，执行所访问的存储空间也局限于某个内存区域，局部性通常有两种形式：时间局部性和空间局部性。
时间局部性（Temporal Locality）：如果⼀个信息项正在被访问，那么在近期它很可能还会被再次访问。
空间局部性（Spatial Locality）：将来要用到的信息⼤概率与正在使用的信息在空间地址上是临近的。

• 每⼀个页中即使没有数据也会使⽤ 16KB 的存储空间，同时与索引的B+树中的节点对应。

查看页大小：show variables like 'innodb_page_size;'

在MySQL中有多种不同类型的页，存储数据的页叫数据页，存储索引的页叫索引页，但不论哪种类型的页都会包含页头(File Header)和页尾(File Trailer)，页的主体信息使用数据"行"进行填充，数据页的基本结构如下图所示：

数据页：
主要用途：用于存储表中的实际数据行。比如在一个存储员工信息的表中，员工的编号、姓名、年龄等具体数据都会存储在数据页中。
结构组成：包含文件头、页头、最小记录与最大记录、用户记录、空闲空间、页目录和文件尾等部分。这些部分协同工作，以有效地组织和管理数据存储，支持数据的快速查找、插入和删除操作。
索引页：
主要用途：存储索引数据结构，如 B + 树索引。索引页中的每个索引条目都指向一个数据页，从而实现快速的数据查找。例如，在一个根据员工姓名建立索引的表中，索引页中存储着按照姓名排序的索引信息以及对应的指向数据页的指针，通过索引页可以快速定位到包含目标姓名的员工数据所在的数据页 。
结构组成：同样包含页头、索引节点和指向下一层节点或数据页的指针等。索引页中的索引节点按照特定的顺序组织，通常是根据索引列的值进行排序，以便快速查找和比较。

4.2 页文件头和页文件尾

页文件头和叶文件尾包含的内容如图所示：

这里我们只关注，上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来，形成⼀个
双向链表。

4.3 页主体

页主体部分是保存真实数据的主要区域，每当创建⼀个新页，都会自动分配两个行，⼀个是页内最小行 Infimun ，另⼀个是页内最大行 Supremun ，这两个行并不存储任何真实信息，而是做为数据链表的头和尾，第⼀个数据行有⼀个记录下一行的地址偏移量的区域 next_record 将页内所有数据行组成了⼀个单向链表，此时新页的结构如下所示：

当向⼀个新页插⼊数据时，将 Infimun 连接第⼀个数据行，最后一行真实数据行连接Supremun ，这样数据行就构建成了⼀个单向链表，更多的行数据插⼊后，会按照主键从小到大的顺序进行连接，如下图所示：

4.4页目录

当按主键或索引查找某条数据时，最直接简单的方法就是从头行 infimun 开始，沿着链表顺序逐个比对查找，但⼀个页有16KB，通常会存在数百行数据，每次都要遍历数百行，无法满足高效查询，为了提高查询效率，InnoDB采用⼆分查找来解决查询效率问题；
• 具体实现⽅式是，在每⼀个页中加⼊⼀个叫做页目录 Page Directory 的结构，将页内包括头行、尾行在内的所有行进行分组，约定头行单独为⼀组，其他每个组最多8条数据，同时把每个组最后一行在页中的地址，按主键从小到大的顺序记录在页目录中在，页目录中的每⼀个位置称为⼀个槽，每个槽都对应了⼀个分组，⼀旦分组中的数据⾏超过分组的上限8个时，就会分裂出⼀个新的分组；
• 后续在查询某行时，就可以通过⼆分查找，先找到对应的槽，然后在槽内最多8个数据行中进行遍历即可，从而⼤幅提⾼了查询效率，这时⼀个页的核心结构就完成了；

• 例如要查找主键为6的行，先比对槽中记录的主键值，定位到最后⼀个槽2，再从最后⼀个槽中的第⼀条记录遍历，第⼆条记录就是我们要查询的目标行。

4.5 数据页头

数据页头记录了当前页保存的数据的相关信息

五、B+树在MySQL索引当中的应用

非叶子节点保存索引数据，叶子节点保存真实的数据，如下图所示：

以查找id为5的记录，完整的检索过程如下：

1. 首先判断B+树的根节点中的索引记录，此时 5 < 7 ，应访问左孩子节点，找到索引页2。
2. 在索引页2中判断id的大小，找到与5相等的记录，命中，加载对应的数据页3。
   以上的IO过程，加载索引页1 --> 加载索引页2 --> 加载数据页3.

提出问题： 计算三层树高的B+树可以存储多少条数据？

答：假设⼀条用户数据大小为1KB，在忽略数据页中数据页自身属性空间占用的情况下，一页可以存16条数据。
索引页当中存的是主键值和子节点的引用，也就是下一节点的偏移量（地址），假设主键为 bigint：8 byte，下一页地址为4byte,也就是一条索引记录占8+4=12byte,一个索引页可以存161024/12=1365，也就说理论上应该三层树高的B+树可以存：13651365*16=29811600条记录，在当前场景下，表中有29811600条的情况下，通过三次IO就可以完成数据的查询。

六、索引的分类

6.1 主键索引

当在一个表中定义一个主键 PRIMARY KEY时，会自动创建索引，索引的值是主键列的值，使用innodb作为聚集索引（聚簇索引）。推荐为每一个表定义一个主键，如果木有逻辑上唯一且非空的列或者列集可以使用主键，则添加一个自增列（auto_increment）.

6.2 普通索引

最基本的索引，木有唯一性的限制。可能为多列创造的组合索引，称为符合索引或者组全索引。

6.3 唯一索引

当在一个表当中定义唯一键Unique时,自动创建唯一索引，与普通索引类似，区别在于唯一索引的列不允许存在有重复的值

6.4 全文索引

基于文本列（char,varchar或者text列）上创建,以加快对这些列中包含的数据查询和DML操作，仅MyISAM和InnoDB引擎支持。

6.5 非聚集索引

• 聚集索引以外的索引称为非聚集索引或⼆级索引。
• ⼆级索引中的每条记录都包含该行的主键列，以及⼆级索引指定的列。
• InnoDB使用这个主键值来搜索聚集索引中的完整记录，这个过程称为回表查询。

例如：select * from 员工表 where 姓名='张三'；

6.6 索引覆盖

当⼀个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列，这时就可以直接返回数据，而不用回表查询，这样的现像叫做索引覆盖。

例如：select 部门 from 员工表 where 姓名='张三';

七、使用索引

7.1 自动创建索引

当我们为⼀张表加主键约束(Primary key)，外键约束(Foreign Key)，唯⼀约束(Unique)时，MySQL会为对应的的列自动创建⼀个索引.
• 如果表不指定任何约束时，MySQL会自动为每⼀列生成⼀个索引并用 ROW_ID 进行标识.

7.2 手动创建索引

7.2.1 创建主键索引

-- 创建表的时候指定主键
create table t_pk1 (
  id bigint PRIMARY KEY auto_increment,
  name varchar(20)
);
desc t_pk1;

-- 创建表时单独指定主键列
create table t_pk2 (
  id bigint auto_increment,
  name VARCHAR(20),
  PRIMARY KEY (id)
);

show index from t_pk2; --- 查看索引

-- 修改表中的列为主键索引
create table t_pk3 (
  id bigint,
  name varchar(20)
);
show index from t_pk3;

-- 修改表中的id列为主键索引
ALTER TABLE t_pk3 ADD PRIMARY key (id);
ALTER TABLE t_pk3 MODIFY id BIGINT auto_increment;

7.2.2 创建唯一索引

# ⽅式⼀，创建表时创建唯⼀键
create table t_test_uk (
 id bigint primary key auto_increment,
 name varchar(20) unique
);
# ⽅式⼆，创建表时单独指定唯⼀列
create table t_test_uk1 (
 id bigint primary key auto_increment,
 name varchar(20),
 unique (name)
);
# ⽅式三，修改表中的列为唯⼀索引
create table t_test_uk2 (
 id bigint primary key auto_increment,
 name varchar(20)
);
alter table t_test_uk2 add unique(name);

7.2.3 创建复合索引

-- 方式一，创建表时候指定索引
create table if not exists animals(
id BIGINT primary key auto_increment,
name varchar(25),
index(id,name)
)ENGINE=innodb;
-- 方式二，修改表中的列为复合索引
create table if not exists animals1(
id BIGINT primary key auto_increment,
name varchar(25)
)ENGINE=innodb;
alter table animals1 add index(id,name);
-- 方式三，单独创建索引并且指定索引名字
create table if not exists animals2(
id BIGINT primary key auto_increment,
name varchar(25)
)ENGINE=innodb;
create index index_animals2 on animals2(id,name);
show index from animals2;

7.2.4 创建普通索引

-- 创建表的时候创建普通索引
CREATE TABLE t_index1 (
  id bigint PRIMARY KEY auto_increment,
  name varchar(20) UNIQUE,
  sno varchar(20),
  index (sno)
);

-- 修改表中的列为普通索引
CREATE TABLE t_index2 (
  id bigint PRIMARY KEY auto_increment,
  name varchar(20) UNIQUE,
  sno varchar(20)
);

alter table t_index2 add index (sno);

-- 单独创建索引并指定索引名 
CREATE TABLE t_index3 (
  id bigint PRIMARY KEY auto_increment,
  name varchar(20),
  sno varchar(20)
);

-- 为name 列建立索引，不指定索引名时失败，必须要指定名字
create index on t_index3(name);

-- 索引名推荐使用 idx_表名_列名[_列名]...
create index idx_t_index3_sno on t_index3(sno);

alter TABLE t_index3 drop index idx_t_index3_sno;

7.3 查看索引

-- 方法一
select index from 表名;
-- 方法二
select keys from 表名;
select keys from 表名\G;
# ⽅式三，简要信息：desc 表名;
desc 表名

7.4 删除索引

-- 删除主键索引
alter table 表名 drop PRIMARY KEY;
-- 如果要删除的主键索引是自增列，那么要先把自增列改成非自增，这里假设id被设置成了自增列
ALTER TABLE 表名 MODIFY id bigint;
# 然后再删除主键索引
alter table 表名 drop primary key;
-- 删除其他索引 
alter table 表名 drop index 被设置了的索引列;

通过上面的学习，会产生一个疑问，那我们怎么知道它有没有走索引呢？

7.5 explain 关键字

作用：可以去查看自己写的SQL走没有走索引，可以查看执行计划,explain.

我们先给动物表创建一个索引。

然后我们查看这个动物表的执行计划：

我们可以看到它返回的是一个执行计划，并不是一个结果集。

1.不加条件查询所有，这个结果就是explain后面的执行计划。

欧耶！！！我学会了！！