(MySQL)索引

注：此博文为本人学习过程中的笔记

1.简介

1.1.概念 

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

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

1.2.为什么要使用索引 

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

2.索引应该选择哪种数据结构

2.1.HASH 

时间复杂度是O(1)，查询速度非常快，但是MySQL并没有选择HASH作为索引的默认数据结构，主要原因是HASH不支持范围查找

2.2.二叉搜索树 

二叉树搜索树的中序遍历是一个有序数组，但有几个问题导致它不适合用作索引的数据结构

1.最坏情况下二叉搜索树会形成一个单边树，时间复杂度为O(N)

2.节点个数过多无法保证树高

AVL和红黑树，虽然是平衡或者近似平衡，但是毕竟是二叉结构

在检索数据时，每次访问某个节点的子节点时都会发生一次磁盘IO，而在整个数据库系统中，IO是性能的瓶颈，减少IO次数可以有效的提升性能

2.3.N叉树 

为了解决树高的问题，可以使用N叉树，通过观察，相同的数据量的情况下，N叉树的树高可以得到有效的控制，也就意味着在相同数据量的情况下可以减少IO的次数，从而提升效率。但是MySQL认为N叉树作为索引的数据结构还不够好

2.4.B+树 

2.4.1.简介 

B+树是一种经常用于数据库和文件系统等场合的平衡查找树，是MySQL索引采用的数据结构 

2.4.2.B+树的特点 

能够保持数据稳定有序，插入与修改有较稳定的时间复杂度

非叶子节点仅具有索引作用，不存储数据，所有叶子节点保存真实数据

所有叶子节点构成一个有序链表，可以按照key排序的次序一次遍历全部数据

2.4.3.B+树与B树的对比

叶子节点中的数据是连续的，且相互链接，便于区间查找和搜索

非叶子节点的值都包含在叶子节点中

对于B+树而言，在相同树高的情况下，查找任一元素的时间复杂度都一样，性能均衡 

3.MySQL中的页 

3.1.为什么要使用页 

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

局部性原理：

是指程序在执行时呈现出局部性规律，在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，局部性通常有两种形式：时间局部性和空间局部性

时间局部性：如果一个信息项正在被访问，那么在近期它很可能会被再次fangwen

空间局部性：将来要用到的信息大概率与正在使用的信息在空间地址上是临近的

每一个页中即使没有数据也会使用16kb的存储空间，同时与索引的B+树中的节点对应，可以通过系统变量innodb_page_size查看

在MySQL中有多种不同类型的页，最常用的就是用来存储数据和索引的“索引页”，也叫做“数据页”，但不论哪种类型的页都会包含页头和页尾，页的主体信息使用“数据行”进行填充

3.2.页文件头和页文件尾

页头和页尾包含了很多信息，我们只需要知道在页头中包含了上一页页号和下一页页号，通过这两个属性可以把页与页之间连接起来，形成一个双向链表

3.3.页主体 

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

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

3.4.页目录

当按主键或索引查找某条数据时，最直接简单的方式就是从头行Infimun开始，沿着链表顺序逐个比对查找，但一个页有16kb，通常会存在数百行数据，每次都要遍历数百行，无法满足高效查询，为了提高查询效率， innodb采用二分查找来解决查询效率问题；

具体实现方式是，在每一个页中加入一个叫做页目录page directory的结构，将页内包括头行，尾行在内的所有行进行分组，约定头行单独为一组，其他每个组最多8行数据，（尾行存在最后一组）同时把每个组最后一行在页中的地址，按主键从小到大的顺序记录在页目录中，页目录中的每一个位置称为一个槽，每个槽都对应了一个分组，一旦分组中的数据超过分组的上限8个时，就会分裂出一个新的分组；

后续在查询某行时，就可以通过二分查找，先找到对应的槽，然后在槽内最多8个数据行中进行遍历即可，从而大幅提高了查询效率，这时一个页中的核心结构就完成了

4.B+树在索引中的应用 

根据索引的不同会生成不同的树，有普通索引树和主键索引树等，非叶子节点保存索引数据，叶子节点保存真实数据 

4.1.计算三层树高的B+树可以存放多少条记录 

假设一条用户数据大小为1kb，在忽略数据页中数据页自身属性空间占用的情况下，一页可以存16条数据

索引页一条数据的大小为，主键用bigint类型占8byte，下一页地址占6byte，一共是14byte，一个索引页可以保存16*1024/14 = 1170条索引记录 

如果只有三层树高的情况，综合只保存索引的根节点和二级节点的索引页以及保存真实数据的数据行，那么一共可以保存1170*1170*16 = 21902400条记录，也就是说在两千多万条数据的表中，可以通过三次IO就完成数据的检索

5.索引分类

5.1.主键索引

当在一个表上定义一个主键primary key时，innodb使用它作为聚集索引

推荐为每个表定义一个主键。如果没有定义主键以及表中没有逻辑上唯一且非空的列可以使用主键，那MySQL会自己添加一个看不见的自增列，列名为row_id，来产生索引的作用 

5.2.普通索引 

最基本的索引类型，没有唯一性的限制

可能为多列创建组合索引，称为复合索引或组全索引

5.3.唯一索引 

当在一个表中定义一个唯一键unique时，自动创建唯一索引。

与普通索引类似，但区别在于唯一索引的列不允许有重复值

5.4.全文索引

基于文本列(char,varchar或text列)上创建，以加快对这些列中包含的数据查询和dml操作

用于全文搜索，仅MyISAM和innodb引擎支持

注意MySQL并不擅长存储文本，因此当需要存储文本时会选择其他数据库 

6.使用索引

6.1.自动创建 

当我们为一张表加主键约束(primary key)，外键约束(foreign key)，唯一键约束(unique)时，MySQL会为对应的列自动创建一个索引

如果表不指定任何约束时，MySQL会自动为每一列生成一个索引并用row_id进行标识

6.2.手动创建

6.2.1.主键索引

-- 方式一，创建表时创建主键
create table t_test_pk(id bigint primary key auto_increment,name varchar(20)
);-- 方式二，创建表时单独指定主键列
create table t_test_pk1(id bigint auto_increment,name varchar(20),primary key(id)
);-- 方式三，修改表中的列为主键索引
create table t_test_pk2(id bigint,name varchar(20)
);alter table t_test add primary key(id);
alter table t_test_pk2 modify id bigint auto_increment;

6.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);

6.2.3.普通索引

-- 方式一，创建表时指定索引列
create table t_test_index(id bigint primary key auto_increment,name varchar(20) unique,sno varchar(10),index(sno)
);-- 方式二，修改表中的列为普通索引
create table t_test_index1(id bigint primary key auto_increment,name varchar(20),sno varchar(10)
);
alter table t_test_index1 add index(sno);-- 方式三，单独创建索引并指定索引名
create table t_test_index2(id bigint primary key auto_increment,name varchar(20),sno varchar(10)
)；
create index index_name on t_test_index2(sno);

6.3.创建复合索引 

创建语法与创建普通索引相同，只不过指定多个列，列与列之间用逗号隔开

-- 方式一，创建表时指定索引列
create table t_test_index4(id bigint primary key auto_increment,name varchar(20),sno varchar(10),class_id bigint,index(sno, class_id)
);-- 方式二，修改表中的列为复合索引
create table t_test_index5(id bigint primary key auto_increment,name varchar(20),sno varchar(10),class_id bigint
);
alter table t_test_index5 add index(sno, class_id);-- 方式三，单独创建索引并指定索引名
create table t_test_index6(id bigint primary key auto_increment,name varchar(20),sno varchar(10),class_id bigint
);
create index index_name on t_test_index6(sno, class_id);

6.4.查看索引 

-- 方式一
show keys from t_test_index6;-- 方式二
show index from t_test_index6;-- 方式三，简要信息
desc t_test_index6;

6.5.删除索引 

6.5.1.主键索引 

-- 语法
alter table 表明 drop primary key;-- 示例，删除t_test_index6表中的主键
alter table t_test_index6 drop primary key;-- 如果提示由于自增列产生错误，先删除自增属性再删除主键
alter table t_test_index6 modify id bigint;
alter table t_test_index6 drop primary key;

6.5.2.其他索引

-- 语法
alter table 表名 drop index 索引名;-- 示例，删除t_test_index6表中名为index_name的索引
alter table t_test_index6 drop index index_name;

6.6.创建索引的注意事项 

索引应该创建再高频查询的列上

索引需要占用额外的存储空间

对表进行插入，更新，删除操作时，同时也会修改索引，可能会影响性能

创建过多或不合理的索引会导致性能下降，需要谨慎选择和规划索引

7.查看SQL语句是否使用索引

我们可以使用explain(查看执行计划) 

其中type表示访问类型，有以下几种分类，性能由差到好

1.ALL：扫描全表

2.index：扫描全部索引树 

3.range：扫描部分索引，索引范围扫描，对索引的扫描开始于某一点，返回匹配值域的行，常见于between,<,>等的查询

4.ref：使用非唯一索引或唯一索引的前缀进行的查找，不是主键或不是唯一索引

5.eq_ref：唯一性索引扫描，对于每个索引键，表中只有一个记录与之匹配，常见于主键索引或唯一索引扫描

6.const,system：单表中最多有一个匹配行，查询起来非常迅速，例如根据主键或唯一索引查询，system是const类型的特例，当查询的表只有一行的情况下，使用system

7.null：不用访问表或者索引，直接就能得到结果

8.索引覆盖和回表查询 

回表查询是指通过索引树中的值，去对应的数据树获得相应的信息

索引覆盖是指通过查询索引树直接查询到需要的需要的数据，不需要回表查询了