【数据库】索引--从原理到实践

这里是@那我掉的头发算什么 刷到我，你的博客算是养成了😁😁😁

简介

索引是什么？

MySQL的索引是⼀种数据结构，它可以帮助数据库⾼效地查询、更新数据表中的数据。索引通过⼀定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度。 MySQL 索引类似于书籍的⽬录，通过指向数据⾏的位置，可以快速定位和访问表中的数据，⽐如汉语字典的⽬录（索引）⻚，我们可以按笔画、偏旁部⾸、拼⾳等排序的⽬录（索引）快速查找到需要的字。

为什么要使用索引？

显⽽易⻅，使⽤索引的⽬的只有⼀个，就是提升数据检索的效率，在应⽤程序的运⾏过程中，查询操作的频率远远⾼于增删改的频率。

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

HASH

时间复杂度是 O(1) ，查询速度⾮常快，但是MySQL并没有选择HASH做为索引的默认数据结构，主要原因是HASH不⽀持范围查找。 比如，查找下标为一到十的数据，hash中并不是连续存储，无法实现。

⼆叉搜索树

⼆叉搜索树的中序遍历是⼀个有序数组，但有⼏个问题导致它不适合⽤作索引的数据结构

1. 最坏情况下时间复杂度为O(N）
2. 节点个数过多⽆法保证树⾼ AVL和红⿊树，虽然是平衡或者近似平衡，但是毕竟是⼆叉结构 在检索数据时，每次访问某个节点的⼦节点时都会发⽣⼀次磁盘IO，⽽在整个数据库系统中，IO是性能的瓶颈，减少IO次数可以有效的提升性能

在这里插入图片描述

N叉树

为了解决树⾼的问题，可以使⽤N叉树

在这里插入图片描述

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

B+树

简介

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

在这里插入图片描述

B+树的特点

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

B+树与B树的对比☆☆★

1.叶子节点之间有一个相互连接的引用，可以通过一个叶子节点找到他相邻的兄弟节点–》mysql在组织叶子节点时使用的是双向链表，注意上图的小箭头 2.非叶子节点的值都包含在叶子节点中–》mysql非叶子节点只保存了对叶子结点的引用，没有保存真实数据。 3.对于B+树而言，在相同树高的情况下，查找任意元素的时间复杂度都一样，性能均衡。

MYSQL中的页

为什么要使用页

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

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

每⼀个⻚中即使没有数据也会使⽤ 16KB 的存储空间，同时与索引的B+树中的节点对应，查看⻚的⼤⼩，可以通过系统变量 innodb_page_size查看：

在这里插入图片描述

在MySQL中有多种不同类型的⻚，最常⽤的就是⽤来存储数据和索引的"索引⻚"，也叫做"数据⻚"，但不论哪种类型的⻚都会包含⻚头(File Header)和⻚尾(File Trailer)，⻚的主体信息使⽤数据"⾏"进⾏填充，数据⻚的基本结构如下图所⽰：

在这里插入图片描述

页文件头和页文件尾

⻚⽂件头和⻚⽂件尾中包含的信息，如下图所⽰：

在这里插入图片描述

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

页主体

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

在这里插入图片描述

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

在这里插入图片描述

页目录

当按主键或索引查找某条数据时，最直接简单的⽅法就是从头⾏ infimun 开始，沿着链表顺序逐个⽐对查找，但⼀个⻚有16KB，通常会存在数百⾏数据，每次都要遍历数百⾏，⽆法满⾜⾼效查询，为了提⾼查询效率，InnoDB采⽤⼆分查找来解决查询效率问题；

具体实现⽅式是，在每⼀个⻚中加⼊⼀个叫做⻚⽬录 Page Directory 的结构，将⻚内包括头⾏、尾⾏在内的所有⾏进⾏分组，约定头⾏单独为⼀组，其他每个组最多8条数据，同时把每个组最后⼀⾏在⻚中的地址，按主键从⼩到⼤的顺序记录在⻚⽬录中在，⻚⽬录中的每⼀个位置称为⼀个槽，每个槽都对应了⼀个分组，⼀旦分组中的数据⾏超过分组的上限8个时，就会分裂出⼀个新的分组；

后续在查询某⾏时，就可以通过⼆分查找，先找到对应的槽，然后在槽内最多8个数据⾏中进⾏遍历即可，从⽽⼤幅提⾼了查询效率，这时⼀个⻚的核⼼结构就完成了；

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

在这里插入图片描述

数据页头

数据⻚头记录了当前⻚保存数据相关的信息，如下图所⽰：

在这里插入图片描述

B+在MySQL索引中的应用

在这里插入图片描述

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

1. ⾸先判断B+树的根节点中的索引记录，此时 5 < 7 ，应访问左孩⼦节点，找到索引⻚2
2. 在索引⻚2中判断id的⼤⼩，找到与5相等的记录，命中，加载对应的数据⻚

加载索引页1-》加载索引页2-》加载数据页3

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

假设⼀条⽤⼾数据⼤⼩为1KB，在忽略数据⻚中数据⻚⾃⾝属性空间占⽤的情况下，⼀⻚可以存16条数据

索引⻚⼀条数据的⼤⼩为，主键⽤BIGINT类型占8Byte，下⼀⻚地址6Byte，⼀共是14Byte，⼀个索引⻚可以保存 16*1024/14 = 1170 条索引记录

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

索引分类

主键索引

• 当在⼀个表上定义⼀个主键 PRIMARY KEY 时，自动创建一个索引，索引的值就是主键的值，InnoDB使⽤它作为聚集索引。 • 推荐为每个表定义⼀个主键。如果没有逻辑上唯⼀且⾮空的列或列集可以使⽤主键，则添加⼀个⾃增列。

普通索引

• 最基本的索引类型，没有唯⼀性的限制。 • 可能为多列创建组合索引，称为复合索引或组全索引

通常为查询频繁的列创建索引

唯⼀索引

• 当在⼀个表上定义⼀个唯⼀键 UNQUE 时，⾃动创建唯⼀索引。 • 与普通索引类似，但区别在于唯⼀索引的列不允许有重复值。

全文索引

• 基于⽂本列(CHAR、VARCHAR或TEXT列)上创建，以加快对这些列中包含的数据查询和DML操作 • ⽤于全⽂搜索，仅MyISAM和InnoDB引擎⽀持。

聚集索引

• 与主键索引是同义词 • 如果没有为表定义 PRIMARY KEY, InnoDB使⽤第⼀个 UNIQUE 和 NOT NULL 的列作为聚集索引。 如果表中没有 PRIMARY KEY 或合适的 UNIQUE 索引，InnoDB会为新插⼊的⾏⽣成⼀个⾏号并⽤6字节的 ROW_ID 字段记录， ROW_ID 单调递增，并使⽤ ROW_ID 做为索引。

非聚集索引

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

☆

在这里插入图片描述

索引覆盖

• 当⼀个select语句使⽤了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列，这时就可以直接返回数据，⽽不⽤回表查询，这样的现象称为索引覆盖

在这里插入图片描述

在这里插入图片描述

使⽤索引

自动创建

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

手动创建

主键索引

1.创建表时创建主键

在这里插入图片描述

在这里插入图片描述

2.修改表中的列为主键列

在这里插入图片描述

没有索引信息：

在这里插入图片描述

添加主键：

在这里插入图片描述

在这里插入图片描述

添加自增：

在这里插入图片描述

在这里插入图片描述

唯一索引

与主键索引一样，可以通过多种方法自动创建。

普通索引

在这里插入图片描述

key这一栏。pri是主键索引，uni是唯一索引，mul是普通索引

在这里插入图片描述

创建表之后修改索引

在这里插入图片描述

在这里插入图片描述

创建复合索引

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

在这里插入图片描述

在这里插入图片描述

推荐手动创建索引并指定索引名

在这里插入图片描述

在这里插入图片描述

删除索引

主键索引

语法：

alter table (name) drop primary key;

在这里插入图片描述

主键自增时无法删除索引。

在这里插入图片描述

在这里插入图片描述

其他索引

语法：

alter table 表名 drop index 索引名;

在这里插入图片描述

创建索引的注意事项

• 索引应该创建在⾼频查询的列上 • 索引需要占⽤额外的存储空间 • 对表进⾏插⼊、更新和删除操作时，同时也会修索引，可能会影响性能 • 创建过多或不合理的索引会导致性能下降，需要谨慎选择和规划索引

如何查看自己写的SQL走没走索引？

explain + 查询语句可以查看语句执行过程的相关信息。

还是使用test_26数据库下的student表 索引情况：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

索引覆盖与回表查询：

在这里插入图片描述

索引失效：

总结

这篇文章围绕 MySQL 索引展开了全面分享，从索引的定义、作用出发，对比了 HASH、二叉搜索树等数据结构的局限性，详细讲解了 B + 树成为 MySQL 索引核心数据结构的原因及特性。接着介绍了 InnoDB 的页机制，包括页的作用、结构组成以及页目录对查询效率的提升，还通过计算说明了三层 B + 树的存储容量优势。之后梳理了主键索引、普通索引、聚集索引等常见分类，演示了索引的创建、删除操作，同时提醒了创建索引的注意事项。最后分享了用explain工具判断 SQL 是否走索引的方法，以及索引覆盖、回表查询和索引失效等实战场景，希望能帮助大家从原理到实践，彻底搞懂 MySQL 索引并合理运用。