IT评测·应用市场-qidao123.com

标题: 6. MySQL 索引的数据结构(具体说明) [打印本页]
作者: 自由的羽毛    时间: 2025-3-9 09:24
标题: 6. MySQL 索引的数据结构(具体说明)
6. MySQL 索引的数据结构(具体说明)

@
目次

这篇文章是我蹲在《尚硅谷》-康师傅博主家的 WiFi 上(不是)，连夜 Ctrl+C / V 俩的镇站神文。
这篇转载只是为了，跟大家分享好内容，没有任何商业用途。如果你喜欢这篇文章，请一定要去原作者 B站《尚硅谷-MySQL从菜鸟到大牛》看看，说不定还能发现更多宝藏内容呢！
1. 为什么利用索引

索引是存储引擎用于快速找到数据记载的一种数据结构，就好比一本教科书的目次部分，通过目次中找到对应文章的页码，便可快速定位到需要的文章。MySQL中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记载，直到找到与条件符合的记载。

如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查询数据，这样操纵非常斲丧时间。如果数据顺序摆放，那么也需要从1到6行按顺序读取，这样就相当于进行了6次IO操纵，仍旧非常耗时。如果我们不借助任何索引结构资助我们快速定位数据的话，我们查找 Col 2 = 89 这条记载，就要逐行去查找、去比力。从Col 2 = 34 开始，进行比力，发现不是，继续下一行。我们当前的表只有不到10行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多次硬盘I/0才能找到。现在要查找 Col 2 = 89 这条记载。CPU必须先去磁盘查找这条记载，找到之后加载到内存，再对数据进行处理。这个过程最耗时间就是磁盘I/O（涉及到磁盘的旋转时间（速率较快），磁头的寻道时间(速率慢、费时)）
假如给数据利用 二叉树 这样的数据结构进行存储，如下图所示

对字段 Col 2 添加了索引，就相当于在硬盘上为 Col 2 维护了一个索引的数据结构，即这个 二叉搜刮树。二叉搜刮树的每个结点存储的是 (K, V) 结构，key 是 Col 2，value 是该 key 所在行的文件指针（地址）。好比：该二叉搜刮树的根节点就是：(34, 0x07)。现在对 Col 2 添加了索引，这时再去查找 Col 2 = 89 这条记载的时候会先去查找该二叉搜刮树（二叉树的遍历查找）。读 34 到内存，89 > 34; 继续右侧数据，读 89 到内存，89==89；找到数据返回。找到之后就根据当前结点的 value 快速定位到要查找的记载对应的地址。我们可以发现，只需要 查找两次 就可以定位到记载的地址，查询速率就提高了。
这就是我们为什么要建索引，目的就是为了 减少磁盘I/O的次数，加快查询速率。
2. 索引及其优缺点

2.1 索引概述

MySQL官方对索引的定义为：索引（Index）是资助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满意特定查找算法。 这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的底子上实现 高级查找算法 。
索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的 最大索引数和 最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。
优点：
（1）类似大学图书馆建书目索引，提高数据检索的服从，降低 数据库的IO资本 ，这也是创建索引最主 要的缘故原由。
（2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
（3）在实现数据的 参考完整性方面，可以 加快表和表之间的毗连 。换句话说，对于有依赖关系的子表和父表联合查询时， 可以提高查询速率。
（4）在利用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的斲丧。
缺点：
增加索引也有很多不利的方面，主要表现在如下几个方面：
（1）创建索引和维护索引要 耗费时间 ，并 且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占 磁盘空间 ，除了数据表占数据空间之 外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就大概比数据文 件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速率，同时却会 降低更新表的速率 。当对表 中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速率。 因此，选择利用索引时，需要综合考虑索引的优点和缺点。
因此，选择利用索引时，需要综合考虑索引的优点和缺点。
提示：
索引可以提高查询的速率，但是会影响插入记载的速率。这种情况下，最好的办法是先删除表中的索引，然后插入数据，插入完成后再创建索引。
3. InnoDB中索引的推演

3.1 索引之前的查找

先来看一个精确匹配的例子：
  1. SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
复制代码
假设现在表中的记载比力少，所有的记载都可以被存放到一个页中，在查找记载的时候可以根据搜刮条件的不同分为两种情况：
2. 在很多页中查找
在很多页中查找记载的活动可以分为两个步调：
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记载所在的页，所以只能 从第一个页沿着双向链表 一直往下找，在每一个页中根据我们上面的查找方式去查 找指定的记载。由于要遍历所有的数据页，所以这种方式显然是 超级耗时 的。如果一个表有一亿条记载呢？此时 索引 应运而生。
3.2 计划索引

建一个表
  1. mysql> CREATE TABLE index_demo(
  2. -> c1 INT,
  3. -> c2 INT,
  4. -> c3 CHAR(1),
  5. -> PRIMARY KEY(c1)
  6. -> ) ROW_FORMAT = Compact;
复制代码
这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键， 这个表利用 Compact 行格式来现实存储记载的。这里我们简化了index_demo表的行格式示意图：

我们只在示意图里展示记载的这几个部分：
将记载格式示意图的其他信息项临时去掉并把它竖起来的效果就是这样：

把一些记载放到页里的示意图就是：

1. 一个简单的索引计划方案
我们在根据某个搜刮条件查找一些记载时为什么要遍历所有的数据页呢？由于各个页中的记载并没有规律，我们并不知道我们的搜刮条件匹配哪些页中的记载，所以不得不依次遍历所有的数据页。所以如果我们 想快速的定位到需要查找的记载在哪些数据页 中该咋办？我们可以为快速定位记载所在的数据页而建立一个目次 ，建这个目次必须完成下边这些事：
那么这些记载以及按照主键值的大小串联成一个单向链表了，如图所示：

从图中可以看出来， index_demo 表中的3条记载都被插入到了编号为10的数据页中了。此时我们再来插入一条记载
  1. INSERT INTO index_demo VALUES(4, 4, 'a');
复制代码
由于 页10 最多只能放3条记载，所以我们不得不再分配一个新页：

注意：新分配的 数据页编号大概并不是一连的。它们只是通过维护者上一个页和下一个页的编号而建立了 链表 关系。另外，页10中用户记载最大的主键值是5，而页28中有一条记载的主键值是4，由于5>4，所以这就不符合下一个数据页中用户记载的主键值必须大于上一个页中用户记载的主键值的要求，所以在插入主键值为4的记载的时候需要伴随着一次 记载移动，也就是把主键值为5的记载移动到页28中，然后再把主键值为4的记载插入到页10中，这个过程的示意图如下：

这个过程表明了在对页中的记载进行增删改查操纵的过程中，我们必须通过一些诸如 记载移动 的操纵来始终保证这个状态一直成立：下一个数据页中用户记载的主键值必须大于上一个页中用户记载的主键值。这个过程称为 页分裂。
由于数据页的 编号大概是不一连 的，所以在向 index_demo 表中插入很多条记载后，大概是这样的效果：

我们需要给它们做个 目次，每个页对应一个目次项，每个目次项包罗下边两个部分：
1）页的用户记载中最小的主键值，我们用 key 来表示。
2）页号，我们用 page_on 表示。

以 页28 为例，它对应 目次项2 ，这个目次项中包含着该页的页号 28 以及该页中用户记载的最小主 键值 5 。我们只需要把几个目次项在物理存储器上一连存储（好比：数组），就可以实现根据主键 值快速查找某条记载的功能了。好比：查找主键值为 20 的记载，具体查找过程分两步：
至此，针对数据页做的浅易目次就搞定了。这个目次有一个别名，称为 索引 。
2. InnoDB中的索引方案
① 迭代1次：目次项纪录的页
InnoDB怎么区分一条记载是普通的 用户记载 还是 目次项记载 呢？利用记载头信息里的 record_type 属性，它的各自取值代表的意思如下：
我们把前边利用到的目次项放到数据页中的样子就是这样：

从图中可以看出来，我们新分配了一个编号为30的页来专门存储目次项记载。这里再次强调 目次项记载 和普通的 用户记载 的不同点：
相同点：两者用的是一样的数据页，都会为主键值天生 Page Directory （页目次），从而在按照主键值进行查找时可以利用 二分法 来加快查询速率。
现在以查找主键为 20 的记载为例，根据某个主键值去查找记载的步调就可以大致拆分成下边两步：
② 迭代2次：多个目次项纪录的页

)
从图中可以看出，我们插入了一条主键值为320的用户记载之后需要两个新的数据页：
现在由于存储目次项记载的页不止一个，所以如果我们想根据主键值查找一条用户记载大致需要3个步调，以查找主键值为 20 的记载为例：
③ 迭代3次：目次项记载页的目次页
如果我们表中的数据非常多则会产生很多存储目次项记载的页，那我们怎么根据主键值快速定位一个存储目次项记载的页呢？那就为这些存储目次项记载的页再天生一个更高级的目次，就像是一个多级目次一样，大目次里嵌套小目次，小目次里才是现实的数据，所以现在各个页的示意图就是这样子：

如图，我们天生了一个存储更高级目次项的 页33 ，这个页中的两条记载分别代表页30和页32，如果用 户记载的主键值在 [1, 320) 之间，则到页30中查找更具体的目次项记载，如果主键值 不小于320 的 话，就到页32中查找更具体的目次项记载。
我们可以用下边这个图来形貌它：

这个数据结构，它的名称是 B+树 。
④ B+Tree
一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记载的那层为第 0 层， 之后依次往上加。之前我们做了一个非常极端的假设：存放用户记载的页 最多存放3条记载 ，存放目次项 记载的页 最多存放4条记载 。其实真实环境中一个页存放的记载数量是非常大的，假设所有存放用户记载 的叶子节点代表的数据页可以存放 100条用户记载 ，所有存放目次项记载的内节点代表的数据页可以存 放 1000条目次项记载 ，那么：
你的表里能存放 100000000000 条记载吗？所以一般情况下，我们用到的 B+树都不会超过4层 ，那我们通过主键值去查找某条记载最多只需要做4个页面内的查找（查找3个目次项页和一个用户记载页），又由于在每个页面内有所谓的 Page Directory （页目次），所以在页面内也可以通过 二分法 实现快速 定位记载。
3.3 常见索引概念

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集 索引称为二级索引或者辅助索引。
1. 聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（所有的用户记载都存储在了叶子结点），也就是所谓的 索引即数据，数据即索引。
术语"聚簇"表示当前数据行和相邻的键值聚簇的存储在一起
特点：
我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记载都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的利用INDEX 语句去创建， InnDB 存储引擎会 自动 的为我们创建聚簇索引。
优点：
缺点：
2. 二级索引（辅助索引、非聚簇索引）

如果我们想以别的列作为搜刮条件该怎么办？肯定不能是从头到尾沿着链表依次遍历记载一遍。
答案：我们可以多建几颗B+树，不同的B+树中的数据采用不同的排列规则。比方说我们用c2列的大小作为数据页、页中记载的排序规则，再建一课B+树，效果如下图所示：

这个 B+ 数与上边介绍的聚簇索引有如下几处不同：

概念：回表
我们根据这个以c2列大小排序的B+树只能确定我们要查找记载的主键值，所以如果我们想根 据c2列的值查找到完整的用户记载的话，仍旧需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就 是根据c2列的值查询一条完整的用户记载需要利用到 2 棵B+树！
标题：为什么我们还需要一次 回表 操纵呢？直接把完整的用户记载放到叶子节点不OK吗？
答复：
如果把完整的用户记载放到叶子结点是可以不用回表。但是太占地方了，相当于每建立一课B+树都需要把所有的用户记载再都拷贝一遍，这就有点太浪费存储空间了。
由于这种按照非主键列建立的B+树需要一次回表操纵才可以定位到完整的用户记载，所以这种B+树也被称为二级索引，或者辅助索引。由于利用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树为c2列简历的索引。
非聚簇索引的存在不影响数据在聚簇索引中的构造，所以一张表可以有多个非聚簇索引。

小结：聚簇索引与非聚簇索引的原理不同，在利用上也有一些区别：
3. 联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按 照 c2和c3列 的大小进行排序，这个包含两层含义：
为c2和c3建立的索引的示意图如下：

如图所示，我们需要注意以下几点：
注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。它的意 思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
3.4  InnoDB的B+树索引的注意事项

1. 根页面位置万年不动
现实上B+树的形成过程是这样的：
这个过程特殊注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建议一个索引，那么它的根节点的页号便会被记载到某个地方。然后凡是 InnoDB 存储引擎需要用到这个索引的时候，都会从哪个固定的地方取出根节点的页号，从而来访问这个索引。
2. 内节点中目次项记载的唯一性
我们知道B+树索引的内节点中目次项记载的内容是 索引列 + 页号 的搭配，但是这个搭配对于二级索引来说有点不严谨。还拿 index_demo 表为例，假设这个表中的数据是这样的：

如果二级索引中目次项记载的内容只是 索引列 + 页号 的搭配的话，那么为 c2 列简历索引后的B+树应该长这样：

如果我们想新插入一行记载，其中 c1 、c2 、c3 的值分别是: 9、1、c, 那么在修改这个为 c2 列建立的二级索引对应的 B+ 树时便碰到了个大标题：由于 页3 中存储的目次项记载是由 c2列 + 页号 的值构成的，页3 中的两条目次项记载对应的 c2 列的值都是1，而我们 新插入的这条记载 的 c2 列的值也是 1，那我们这条新插入的记载到底应该放在 页4 中，还是应该放在 页5 中？答案：对不起，懵了
为了让新插入记载找到自己在那个页面，我们需要保证在B+树的同一层页节点的目次项记载除页号这个字段以外是唯一的。所以对于二级索引的内节点的目次项记载的内容现实上是由三个部分构成的：
也就是我们把主键值也添加到二级索引内节点中的目次项记载，这样就能保住 B+ 树每一层节点中各条目次项记载除页号这个字段外是唯一的，所以我们为c2建立二级索引后的示意图现实上应该是这样子的：

这样我们再插入记载(9, 1, 'c') 时，由于 页3 中存储的目次项记载是由 c2列 + 主键 + 页号 的值构成的，可以先把新纪录的 c2 列的值和 页3 中各目次项记载的 c2 列的值作比力，如果 c2 列的值相同的话，可以接着比力主键值，由于B+树同一层中不同目次项记载的 c2列 + 主键的值肯定是不一样的，所以最后肯定能定位唯一的一条目次项记载，在本例中最后确定新纪录应该被插入到 页5 中。
3. 一个页面最少存储 2 条记载
B树索引利用存储引擎如表所示：
索引 / 存储引擎MyISAMInnoDBMemoryB-Tree索引支持支持支持即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb和MyISAM默认的索 引是Btree索引；而Memory默认的索引是Hash索引。
MyISAM引擎利用 B+Tree 作为索引结构，叶子节点的data域存放的是 数据记载的地址 。
4. MyISAM索引的原理




4.2 MyISAM 与 InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：
小结：


5. 索引的代价

索引是个好东西，可不能乱建，它在空间和时间上都会有斲丧：
一个表上索引建的越多，就会占用越多的存储空间，在增删改记载的时候性能就越差。为了能建立又好又少的索引，我们得学学这些索引在哪些条件下起作用的。
6. 最后：

“在这个最后的篇章中，我要表达我对每一位读者的感激之情。你们的关注和回复是我创作的动力源泉，我从你们身上罗致了无尽的灵感与勇气。我会将你们的鼓励留在心底，继续在其他的领域奋斗。感谢你们，我们总会在某个时刻再次相遇。”


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4