mysql系列3—mysql索引图解

🕗 发布于 2024-12-10 03:41 mysql android 数据库

背景

索引类似字典的目录，用于提高查询速度。字典目录存放单词与页码的映射关系，在目录中根据单词找到页码，根据页码翻到指定页面，得到单词的详细信息。数据以行为单位存放于磁盘，每条行记录对应一个存储地址，索引可以存放数据和存储地址的映射关系，通过索引可快速得到记录的地址；没有索引，查询将退化为数据库遍历。
以上是对索引概念的泛泛理解，mysql索引体系的建立也以此为基础，并进行扩展优化。
本文介绍mysql索引为后续介绍mysql索引创建原则、索引失效场景以及explain命令的介绍建立基础。

1.数据结构选择

为提高查询效率，索引需要顺序存放；考虑需要进行读写，初步可选的数据结构有数组、链表、树；再考虑到数组需要动态扩容，而链表的查询效率相对数组和树较高，因此树相对更合适。

1.1 平衡二叉树

树中较为简单的结构为二叉树，查询和修改的时间复杂度为O(logN)到O(N)之间，极端不平衡时退化为链表，复杂度达到O(N)，而平衡的二叉树的时间复杂度固定在O(logN)。
不考虑磁盘IO的情况，如索引存放在内存中，那么平衡二叉树可以作为一个选择。
以下结合案例进行说明：
请添加图片描述
存在一个t_user表，有id,name,phone,address四个字段，其中id为主键。基于id字段建立索引，索引结构如上图所示，每个节点存放id值和行记录地址。
当执行select * from t_user where id = 33时:
[1] 获取树的根节点30, 33大于根节点30，走右子树;
[2] 获取右子树根节点35, 33小于35，走左子树;
[3] 获取左子树根节点37, 37=37，得到地址0xag01;
[4] 根据0xag01读取表记录并返回;
此过程共进行3次索引IO和1次表数据IO.
比起直接遍历表的7次IO效率要高，且随着数据量增加，索引的优势越来越明显。

缺点:
mysql的索引以文件的形式存在磁盘上，查询时需从磁盘加载到内存，涉及IO操作。为减少IO次数而提高效率，mysql规定磁盘与内存交换的最小单位是数据页，默认一页16K，即mysql的一次IO至少16K的数据。
上述平衡二叉树索引中，每个节点需要一次IO，每次IO仅读取12个字节(4字节整型键+8字节数据地址)，无异于卡车一次拉一条吉娃娃，太过浪费！可优化为一次拉多条吉娃娃，即树的每个节点存放多个索引键值对。
此时，可用B树替代平衡二叉树。

1.2 B树

B树也是一种自平衡树，时间复杂度为O(logN)，相对于平衡二叉树，每个节点可存放多个数据。
以下结合案例进行说明：
请添加图片描述
当执行select * from t_user where id = 33时:
[1] 经历一次IO，得到树的根节点，判断21<33<35, 走P2指向的节点；
[2] 经历一次IO，得到33，满足条件停止索引扫描，表记录的地址为0xag01;
[3] 根据0xag01读取表记录并返回;
共进行2次索引IO和1次表数据IO.
相对平衡二叉索引树减少了IO次数。案例为了演示方便，每个树节点仅存了2个索引键值对，mysql实际每个树节点可存上千个索引节点，查询效率对比更加明显。
缺点：对于范围查询不支持高效检索：
当执行"select * from t_user where id >=33 and id <=50"时:
需先检索出满足id>=33的最小节点，再依次遍历索引树，直到得到满足id<=50的最大节点；然后根据得到表记录地址获取表记录数据。因此，B树索引结构不支持范围查询的快速检索。

1.3 B+树

B+树是B树的一种变体，时间复杂度为O(logN). B+树的非叶子节点不包含数据，只包含索引键和子节点指针，而叶子节点则包含了索引键和数据记录的地址。通过叶子节点间的链表，可以高效地进行顺序访问操作。
以下结合案例进行说明:
请添加图片描述
当执行select * from t_user where id >=33 and id <=50时:
[1] 经历两次IO，从树的根节点，到达33节点，满足id>=33且id<=50, 记录地址为0xag01;
[2] 读取33节点的后驱节点，得到35节点，满足35<=50，记录地址为0xaf01;
[3] 读取35节点的后驱节点，得到50节点，满足50<=50，记录地址为0xag01;
[4] 读取50节点的后驱节点，不满足50<=50，停止检索;
[5] 根据得到的地址从磁盘读取数据并返回。
由33节点->35节点->50节点基于根节点的链表进行，无需从树的根节点遍历，效率相对B树得到了显著提高。
扩展：
案例使用的索引键是表的主键，索引值使用的数据地址，可以进行扩展：
[1] 索引键：主键索引、普通索引、组合索引；
[2] 索引值：数据本身，数据的磁盘地址;
在不同的存储引擎、不同的索引，实现可能不同。
从应用层的角度，存在三种索引类型：
[1] 主键索引(Primary Key)：每个表只能有一个主键索引，字段具有唯一性约束，不为空；
[2] 唯一索引(Unique Key)：字段具有唯一性约束，可以为空；
[3] 普通索引(Key)：字段没有唯一性约束，可以为空;
唯一索引和普通索引中包含多个列时形成组合索引。
从实现层的角度，Mysql在InnoDB和MyIsam存在三种类型的索引：
[1] 主键索引：根据主键列生成的数据结构, 在InnoDB中主键索引又叫做聚簇索引;
[2] 辅助索引：根据唯一索引或者普通索引列生成的数据结构；
[3] 组合索引：根据表的多列生成的数据结构；
以下对常用的INNODB和MyIsam存储引擎分章节展开进行介绍。

2.MyIsam

MyIsam的索引文件和数据文件分开存储，对于每个表都对应三个文件：“.frm"文件保存表的定义信息，”.MYD"文件保存数据信息，".MYI"文件保存索引信息。
如表结构定义为:

CREATE TABLE `t_test_myisam` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`name` VARCHAR(50) NOT NULL COLLATE 'utf8_general_ci',
PRIMARY KEY (`id`) USING BTREE
)
COLLATE='utf8_general_ci'
ENGINE=MyISAM
AUTO_INCREMENT=1
;

进入mysql目录查看t_test_myisam表相关的文件：

[root@124 test_db]# ls -al | grep t_test_myisam
-rw-r-----.  1 mysql mysql 8586 11月 24 15:31 t_test_myisam.frm
-rw-r-----.  1 mysql mysql    0 11月 24 15:31 t_test_myisam.MYD
-rw-r-----.  1 mysql mysql 1024 11月 24 15:31 t_test_myisam.MYI

MyIsam的索引值固定存的是数据的磁盘地址，因索引键的变化存在以下三种类型的索引结构。

2.1 主键索引

MyIsam的主键索引根据表的Primary Key生成，实现原理与章节1.3 B+树中案例完全相同。

2.2 辅助索引

MyIsam的主键索引根据表的Unique Key或普通Key生成，数据结构与主键索引一致。与主键索引的区别在于：
因辅助索引可能不唯一或者为空，精确查询需要扩展为范围搜索。
另外，唯一索引和非唯一索引在存储和查询性能上没有区别，仅唯一索引在插入和更新数据时会额外检查数据的唯一性，以确保不会引入重复的值。
以下结合案例进行说明（假设id不唯一):
请添加图片描述
当执行select * from t_user where id = 30时:
[1] 经历两次IO，从树的根节点，到达30节点，满足id=30, 记录地址为0xac01;
[2] 读取30(0xac01)节点的后驱节点，得到30(0xad01)节点，满足id=50，记录地址为0xad01;
[3] 读取30(0xad01)节点的后驱节点，得到33节点，不满足id=30，停止检索;
[4] 根据得到的地址从磁盘读取数据并返回。

2.3 组合索引

当数据库表中某几列经常被作为条件进行增删改查时，可以将这几列组合形成索引。根据最左匹配原则，定义组合索引时需要注意字段在索引中的顺序。
例如定义KEY(a, b, c)时，相当于同时定义了三个索引：KEY(a), KEY(a, b), KEY(a, b, c). 因为对组合索引检索时，依次按照索引列的顺序进行匹配，即最左匹配原则：数据整体先按照a的顺序排序，a顺序相同的项，按照b的顺序排序；b顺序相同的项，按照c的顺序排列。从而KEY(a, b, c)可以满足KEY(a, b), 而无法满足KEY(a, c).
以下结合案例进行说明:
t_abcd表中有4个字段，a,b,c分别为整型，d为字符串类型; a为主键，并给abc加上组合索引:

CREATE TABLE `t_abcd` (
`a` INT(11) NOT NULL,
`b` INT(11) NULL DEFAULT NULL,
`c` INT(11) NULL DEFAULT NULL,
`d` VARCHAR(50) NULL DEFAULT NULL COLLATE 'utf8_general_ci',
PRIMARY KEY (`a`) USING BTREE,
INDEX `idx_abc` (`a`, `b`, `c`) USING BTREE
)
COLLATE='utf8_general_ci'
ENGINE=MyISAM
;

a、b、c组合索引结构如下所示:
请添加图片描述
当执行select a,b,c,d from t_abcd where a=3 and b=12 and c=333时，根据最左匹配原则比较规则，沿着红色箭头读取到叶子节点的地址0xac01, 然后根据0xac01获取数据:
[1] 取根节点(a=3,b=22,c=777)，判断a=3=3, b=15>12,则走左侧；
[2] 读取节点(a=3,b=12,c=333), 判断a=3=3，b=12=12, c=333=333, 则走右侧;
[3] 读取节点(a=3,b=15,c=444), 判断a=3=3，b=15, 则走左侧;
[4] 读取节点(a=3,b=12,c=333), 判断a=3=3，b=12=12, c=333=333得到满足条件的叶子节点，提取数据地址为0xac01;
[5] 根据得到的地址从磁盘读取数据并返回。
最后，取出索引B+的根节点，横向观察:
请添加图片描述
可以看到：a，(a,b), (a,b,c)按照非递减顺序排列，而其他组合无线性规律。

3.InnoDB

InnoDB的索引文件和数据文件存储在同一个文件中，对于每个InnoDB表都对应两个个文件：“.frm"文件保存表的定义信息，”.ibd"文件保存数据信息和索引信息(mysql8中只有一个文件)。
如表结构定义为:

CREATE TABLE `t_test_innodb` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`name` VARCHAR(50) NOT NULL COLLATE 'utf8_general_ci',
`phone` VARCHAR(50) NULL DEFAULT NULL,
    `address` VARCHAR(1024) NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE,
INDEX `idx_name` (`name`) USING BTREE
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB
;

进入mysql目录查看t_test_innodb表相关的文件：

[root@124 test_db]# ls -al |grep t_test_innodb
-rw-r-----.  1 mysql mysql   8616 11月 24 17:05 t_test_innodb.frm
-rw-r-----.  1 mysql mysql 114688 11月 24 17:05 t_test_innodb.ibd

INNODB的索引值可以是数据本身或者主键ID，结合索引键的变化存在以下三种类型的索引结构。

3.1 主键索引

InnoDB的主键索引又叫聚簇索引，每个InnoDB表有且只有一个聚簇索引。
聚簇索引的索引值直接使用数据本身，而索引键根据以下规则生成：
[1] 表中定义了主键，使用主键生成主键索引;
[2] 表中定义了为空的唯一索引，使用该索引对应的列生成主键索引；
[3] 使用DB_ROW_ID构建主键索引.
其中DB_ROW_ID在"mysql系列3—mysql数据存储和缓存原理"中介绍过：INNODB存储数据时，为每行添加了一个隐藏的主键DB_ROW_ID.
其中DB_ROW_ID在"mysql系列3—mysql数据存储和缓存原理"中介绍过：INNODB存储数据时，为每行添加了一个隐藏的主键DB_ROW_ID.
以下结合案例进行说明。
t_test_innodb表的数据如下所示，其中ID为主键：
请添加图片描述
此时，根据主键ID构造聚簇索引树。当执行"select * from t_test_innodb where id = 33"查询语句时，沿着如下路径搜索：

当执行"select * from t_test_innodb where id >=33 and id <=50"时，沿着如下路径搜索：

3.2 辅助索引

InnoDB的其他索引类型都会对应生成一个辅助索引结构。辅助索引的键对应索引列，而值存放的是主键ID(而非数据或者数据地址)。以下结合案例进行说明。
t_test_innodb表的定义中对name字段添加了索引: INDEX idx_name (name) USING BTREE; idx_name索引将以name字段的值构建索引树。
当执行"select * from t_test_innodb where name =‘g’;"时，搜索路径如下所示:
请添加图片描述
现根据g在辅助索引树上找到匹配的叶子节点，提取该节点存放的主键ID，然后根据主键ID从主键索引树中提取对应的记录数据(回表查询)。

3.3 组合索引

与章节2.3中MyIsam的组合索引实现类似，区别在于，索引值存放的是主键ID而非数据库地址。
MyIsam的组合索引拿到地址后，去磁盘读取；而InnoDB的存储引擎拿到主键ID后，需要回表查询，即根据ID从主键索引中查询数据。

4. 覆盖索引

覆盖索引是一种合理利用索引的策略。当组合索引已包含了查询所需的列，而不用再根据主键ID或者数据地址回表查询时，可以减少IO次数，达到效率优化的目标，称为覆盖索引。
以下结合案例进行说明：
由于覆盖索引只需要检索索引树，因此MyISam和InnoDB在此案例下无区别，不妨以MyIsam为例。
当执行"select a,b,c from t_abcd where a=3 and b=12":
请添加图片描述
沿着红色箭头确定的路径达到根节点后，索引键为(a=3,b=12,c=333), 索引值为0xac01; 索引键已包含了查询所需的所有字段，无需再根据0xac01地址获取数据，减少了IO次数。因此，建立联合索引时可以考虑是否可通过覆盖索引进行优化。

原文地址：https://blog.csdn.net/Sheng_Q/article/details/144005610

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：树莓派发那科 Fanuc Linux跨平台CNC数控数据采集协议，TCP协议包
下一篇：WordPress Elementor Page Builde 任意文件读取漏洞复现（CVE-2024-9935）

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14