引言本篇文章是MySQL索引篇的终章通过前两篇文章MySQL索引初始篇、MySQL索引应用篇我们对索引有了深入的理解但是MySQL索引机制还是存在一些不理解的问题例如建立索引后MySQL会发生上面使用索引查询时是如何进行检索数据的而且在前面两篇文章中也留下了很多疑惑所以我们就在MySQL索引原理篇中去学习索引原理及其底层实现MySQL索引为什么使用BTree结构在MySQL索引机制中大家都知道MySQL索引机制默认使用BTree作为底层数据结构但是为什么使用BTree不使用其他树结构呢例如为什么不使用AVL树、B树、红黑树、二叉树呢那么我们下面就来聊一下索引为什么不支持数字、链表、队列等数据结构呢是因为这些元素都是按顺序并排促成农户的如果选择这些数据结构来实现索引的话那么走索引就没有意义了走索引了还是进行全表扫描没有给查询效率提高还会带来额外的内存开销毫无意义普通SQL的全表扫描过程想要真正理解MySQL为什么选用BTree作为索引机制的底层数据结构就得先理解一条普通SQL是如何进行全表扫描的理解全表扫描的过程即没有使用索引的时候这条普通SQL是如何执行的这样才能体会到有索引和没有索引的区别我们这里就讲解一下MySQL全表扫描的实际过程以下面这张用户表为例子------------------------------------------------------- | id | address | name | sex | age | ------------------------------------------------------- | 1 | 北京 | aa | 男 | 18 | ------------------------------------------------------- | 2 | 上海 | bb | 女 | 20 | ------------------------------------------------------- | 3 | 天津 | ff | 男 | 22 | ------------------------------------------------------- | 4 | 浙江 | dd | 女 | 24 | ------------------------------------------------------- | 5 | 广东 | ee | 男 | 23 | ------------------------------------------------------- 首先写一条不存在任何索引的普通SQL语句select * from user_table where name aa;因为这个用户表没有创建索引所以就没有使用到索引机制所以这里会走全表扫描通过全表扫描的形式来检索数据但是不管走的是全表扫描还是索引机制去检索数据数据都是存储在磁盘上的所以首先都会触发磁盘IO所以先说一下磁盘寻道的过程参考自竹子爱熊猫如果磁盘不是SSD类型那么磁盘大致是上面这个样子里面有一个盘面和磁针当发生磁盘IO时会根据给出的磁盘地址在盘面上寻道这个过程就跟VCD、DVD光碟一样盘面会开始转圈在盘面上有一个磁道当在盘面上转到对应的地址时磁道和磁针就会互相吸引然后以一上一下的方式读取0、1二进制数据最终从磁盘中将目标地址的数据读取出来走全表扫描的时候必然会触发磁盘IO但是磁盘寻道需要一个地址这个地址最开始就是本地表数据文件中的起始地址就是从表中第一行数据开始读读取到数据之后就会载入内存MySQL-Server就会根据所写的查询SQL的查询条件对读取到的数据进行判断如果不符合条件就会继续进行磁盘IO去读取其他数据如果表数据量比较大这里就不会按顺序IO的形式走全表检索而是触发随机的磁盘IO那么如果我们要查询上表的第五条数据那么是一定就会进行五次磁盘IO吗肯定不是的因为OS、MySQL中有一个优化措施叫局部性读取原理局部性读取原理比如目前有三块内存页x、y、z是相连的CPU此时在操作内存页x转的数据那么按照计算机的特性一般同一个数据都会被放入到物理相连的内存地址上存储即当前在操作x页的数据那么对于y、z这两页内存的数据很有可能在接下来的时间内被操作因此对于y、z这两页数据则会提前将其载入告诉缓冲区L1/L2/L3这个过程就叫利用局部性原理“预读”数据但是一次到底预读多大的数据放入到高速缓冲区中呢这个是由缓存行大小决定的例如在英特尔的MESI协议中缓存行的默认大小为64bytes也就是说在英特尔的CPU中一次性会将当前操作数据附近的64bytes数据(2页数据)提前载入进高速缓冲区上面讲的内容是操作系统高速缓冲区的知识如果没学OS的可以先去学一学在CPU中利用局部性原理提前将数据从内存放入L1/L2/L3三级缓冲区中主要是为了减少CPU寄存器与内存之间的性能差异由于CPU寄存器和内存之间的性能差异太大所以逐个读数据的形式会导致CPU工作期间的大量时间会处于等待数据状态所以利用局部性原理将数据“预读”到高速区。而对于MySQL而言亦是同理存储数据的磁盘和内存之间的性能差异也是巨大的因为MySQL也会利用局部性原理提前“预读”数据。这是什么意思呢其实就是指MySQL一次磁盘IO不仅仅只会读取一条表数据而是会读取多条数据那到底读多少条数据呢在InnoDB引擎中一次默认会读取16KB数据到内存。全表扫描过程由于MySQL中会使用局部性原理的思想所以对于给出的用户表数据而言可能只需要发生一次磁盘IO就能将前五条数据全部读到内存然后会在内存中对本次读取的数据逐条判断看一下每条数据的姓名字段是否为ee如果发现不符合SQL条件的行数据则会将当前这条数据放弃同时在本次SQL执行过程中会排除掉这条数据不会对其进行二次读取。如果发现当前的数据符合SQL条件要求则会将当前数据写入到结果集中然后继续判断其他数据。当本次磁盘IO读取到的所有数据全部筛选完成后紧接着会看一下表中是否还有其他数据如果还有则继续触发磁盘IO检索数据如果没有则将内存中的结果集返回。有人或许会疑惑为什么这里已经读到了符合条件的数据还需要继续发生磁盘IO呢因为表中的字段没有建立唯一索引或唯一约束因此MySQL不确定是否还有其他同名的数据所以需要将整个表全部扫描一遍才能得到最终结论。好的到这里就将MySQL全表扫描的过程讲明白了紧着来看看全表扫描有什么问题呢其实按目前的情况来看似乎不会有太大的问题因此表中数据不多一次磁盘IO几乎就能读完。但思考一下如果当表的数据量变为百万级别、千万级别呢假设表中一条数据大小为512Byte一次磁盘IO也只能读32条假设表中有320w条数据一次全表就有可能会触发10W次磁盘IO每次都需要在硬件上让那个盘面转啊转其过程的开销可想而知.....因此建立索引的原因就在于此处为了避免查询时走全表扫描因此全表扫描的开销会随着数据量增长而越来越大。索引为什么不选择二叉树研究这个问题就和数据结构与算法有一点关系了不过没学过也没事国外有一个大佬自己搭建了一个数据结构的动画演示网站里面有很多数据结构类型的动画展示图Data Structure Visualization前面我们已经知道了全表扫描走的是线性查询 如果数据越多开销就越大此时先来看看二叉搜索树二叉树也叫二叉搜索树Binary Search Tree二叉搜索树是遵循二分搜索实现的一种数据结构那么接下来我们就看看为什么这种数据结构不适合作为索引机制的底层数据结构这个图可以自己从上面说的哪个网站上自己画这就是一颗二叉搜索树我们构建了6个节点那么根据我们上面给的用户表案例假设我们要查询第五条数据ee以二叉搜索树作为索引机制的底层数据结构那么很显然需要走5次磁盘IO才能检索到对应的数据从这个动态的图中就可以看出确实就是要进行五次查询的因为树结构在磁盘中存储的位置不连续因此无法利用局部性原理读取后续的节点所以最终需要发送五次磁盘IO才能读取到数据二叉树不适合作为索引结构的原因如果索引的字段值是按顺序增长的二叉树会转变为链表结构由于结构转变成了链表结构因此检索的过程和全表扫描完全一样由于树结构在磁盘中各节点的数据并不连续因此无法利用局部性原理索引为什么不选择红黑树Red-Black Tree红黑树相比于二叉树红黑树进行了优化红黑树是一种自适应的平衡树会根据插入的节点数量和节点信息自动调整树结构来维持平衡从树的高度上看相比于上面二叉树同样是六个节点但是红黑树只有四层二叉树有六层那么很显然就检索数据的时候进行磁盘IO的次数减少了然后我们再看看检索过程同样去查询第五条数据ee红黑树只需要查询3次就查询到指定的数据了似乎比二叉树优化了很多但是为什么MySQL不选择红黑树呢红黑树不适合作为索引结构的原因虽然相比于二叉树来说树的高度/深度减少了查询次数少了但是这只是在数据量少的情况下体现了优势如果数据量大了树的高度依然会很大所以红黑树也不是最优解而且红黑树每一个节点只能存储一个数据节点之间也不是连续的所以一样不能使用局部性原理如果让单个节点存储的数据变多可以存储多个数据是不是又进一步优化呢B树就是这么进行优化的索引所以为什么不选择B-TreeB-Tree就是在红黑树的基础上进行了优化使得一个节点可以存储多个数据在上述网站中Max.Degree3就是表示每个节点最多可以存储多少个数据等于3就表示最多只能存储两个数据第三个数据就要往下进行拆分可以通过网站来进行操作一下同样给B-Tree也构建6个节点很显然单个节点可以存储多个数据而且树的高度也减少了只有2层了然后再看看B-Tree的查找过程只需要两次就查询到指定数据了而且一个节点可以存储多个数据那么还可以使用局部性原理让一次磁盘IO可以读取多个数据意思就是每查询一个节点都需要进行一次磁盘IO如果只能存储一个数据那么这次磁盘IO就只能检索到一个数据如果可以存储多个数据那么这些数据就是连续的而且一次磁盘IO就可以查询到多个数据select * from user_table where id between 2 and 5;例如上面这条SQL,需要查询表中id在2~5的所有数据,那就代表着需要查询4条数据,根据上面设置了更大的单个节点存储数据个数的容量,所有的数据都存在了一个节点中,所以只需要进行一次磁盘IO就可以查询到指定数据,但是在实际业务中数据量没有这么小,所以不可能所有的数据都会存储在一个节点中,所以又会触发多次磁盘IO进行检索数据,所以B-Tree也不合适作为索引的结构B-Tree不适合作为索引结构的原因即使相比于前面的二叉树和红黑树也有优化,但是当大数据量的时候一样需要进行多次磁盘IO来进行检索数据,所以也不是最优的结构,因为实际业务中的数据量都是很大的索引为什么要选择BTreeB-Tree的缺点就是不太适合进行范围查询,但是范围查询在关系型数据库中很常见,所以还需要进行优化,那么就来看看BTree相比于B-Tree,BTree的一个变化是有了叶节点和叶子节点,后面会详细讲这两个节点的作用,而且BTree在最下面一排节点之间,都存在一个单向指针,指向下一个节点的位置那么通过这个单向指针,在我们进行范围查询的时候,只需要找到第一个节点,然后直接根据个节点之间的单向指针,获取到对应范围之内的所有节点即可,所以只需要进行一次磁盘IO就能查询到范围查询中所以数据的位置那么下面我们看看叶节点和叶子节点在MySQL索引中的作用首先我们要指定叶节点和叶子节点是什么红圈范围内的是叶节点在MySQL中是不会存储数据的仅存储指向叶子节点的指针这样做的好处是能够让一个叶节点中存储更多的元素从而确保树的高度不会由于数据增长而变得很高最下面那一排节点就是叶子节点这些节点内部会存储实际的数据例如聚簇索引中就直接存储对应的行数据非聚簇索引中则存储指向主键/聚簇索引的字段值。同时每个叶子节点之间都有一个单向指针指向下一个节点从而使得最下面的一排叶子节点之间又形成了一个单向链表结构方便范围取值BTree结构为什么会存在叶节点在BTree中使用了叶节点同时冗余了一份节点信息这是为什么呢很明显从上面这个图中会发现BTree结构中2、3、4、5节点都出现了两次只有第一个和最后一个节点只出现了一次那么为什么要冗余节点呢首先我们要知道不能把所有的索引数据、表数据都存储在一个节点中虽然这样使得树的高度只有1看起来好像只需要一次磁盘IO就可以检索到自己需要的数据但事实并非如此因为一次磁盘IO读取的数据量是有限的不是想读取多少数据量就读取多少的一次磁盘IO只能读取一个节点中的一部分数据如果将整个节点的数据读取完一样需要进行多次磁盘IO本质上跟走一次全表查询没有什么区别那么为什么要冗余节点呢因为BTree中每个节点存放数据个数的大小是有效的如果我们把实际数据存储到叶节点中会导致单个树节点存储的索引键很少。但是如果树的叶节点不存储实际表中的行数据就代表单个节点可以存更多的索引键单个节点可以存更多的索引键就代表树的高度会变小树的高度越小就相当于查询时发送的磁盘IO的次数越少磁盘IO的次数越少那么检索数据的速度就越快所以这就是为什么BTree要使用叶节点冗余索引键但是索引中除了索引键还需要存储实际的行数据所以在下面一排的叶子节点中就会存储对应的索引键与行数据/聚簇索引字段值所以BTree的叶节点只是一个过渡的作用就是为了提高所以效率实际的行数据是保存在最下面的叶子节点中叶节点中仅有一个指针指向而已千万数据量级别的BTree会有多高假设MySQL中有一张千万级别数据量的表如果基于自增id的主键字段建立BTree索引那么此时树有多高呢想要知道这颗树有多高就必须建立在实际的依据上来计算索引字段值的大小MySQL中BTree单个节点的大小MySQL中单个指针的大小如何计算索引字段值的大小根据这个字段所使用的数据类型来决定。假设此时自增id在创建表的时候使用的数据类型是int类型int类型在计算机中占4bytes那么此时基于id字段建立主键索引时BTree每个节点的索引键大小就是4bytes如何获取到MySQL中BTree单个节点的大小对于索引单个节点的容量是多少在MySQL中默认使用引擎的一页大小作为单节点的容量假设此时表的存储引擎是InnoDB既可以通过下面这条命令进行查询show global status like Innodb_page_szie; ------------------------- | Variable_name | Value | ------------------------- | Innodb_page_size | 16384 | ------------------------- 从上述查询结果看InnoDB引擎的一页大小为16384bytes也就是16kb此时就代表BTree的每个节点容量是16kbMySQL中的指针是多大一般来说操作系统的指针为了方便寻址一般都与当前的操作系统的位数对应例如32位的操作系统指针就是32bit/4bytes,64位的操作系统指针一般是64bit/8bytes但是由于64bit的指针寻址范围太大目前计算机根本用不上这么大的寻址范围因此在MySQL-InnoDB引擎的源码中单个指针被缩小到6bytes千万级别的所有树高计算单个索引节点容量16kb主键字段值4b指针大小6b一个完整的索引信息是由主键字段指针组成的也就是4610B那此时先计算一下单个节点中可存储多少个索引信息16kb / 10b 1638个那此时来计算一下对于一颗高度为2的BTree根节点可存储1638个叶子节点指针也就代表着BTree的第二层有1638个叶子节点因为叶子节点要存储实际的行数据假设表中每行数据为1KB这也就是代表着一个叶子节点中可存储16条行数据那么一颗高度为2的B树可存储的索引信息为1638 * 16 26208条数据。再来算算树高为3的B树可以存多少呢因为最下面一排才是叶子节点此时树高为3也就代表着中间一排是叶节点只存储指针并不存储数据而每个节点可容纳1638个索引键指针信息因此计算过程是1638 * 1638 * 16 42928704条。是不是很令你惊讶树高为3的BTree竟然可以存储四千多万条数据也就代表着千万级别的表走索引查询的情况下大致只需要发生三次磁盘IO即可获取数据。当然上述的这个数据是基于主键为int类型、表的一行数据为1KB来计算的实际情况中会不一样因为主键有可能是bigint类型或其他类型而一行数据也可能不仅仅只有1KB。因此对于一张实际的千万级别表它的主键索引实际树高有多少你结合主键的数据类型以及一行数据的大小也可以计算出来它同时不会太高。 对实际的千万表索引树高感兴趣的我提供一个计算公式索引键大小索引字段类型所占的空间、一行表数据大小所有表字段的类型隐藏字段20Bytes所占大小总和得到这两个值之后再套入前面的例子中既可得知。看到这里对于索引凭啥那么快为啥能够提升查询性能相信大家也有了答案毕竟索引树高才是个位数发生的磁盘IO次数也那么少检索数据的速度不快才来了个鬼不过BTree中的每个索引页中还会存储页头页号、指针、伪记录等、页目录、页尾等信息大概一共占用128Bytes左右因此想要真正的计算出来接近实际情况的索引树高还需要把这点考虑在内MySQL索引底层的真正结构MySQL的索引底层的结构并不是直接就是BTree的原型因为BTree的叶子节点之间是单向指针组成的链表结构不适合用于倒排序查询因为只有单向指针只能先正序获取数据后再倒排一次所以MySQL对BTree进行了进一步的优化才得到MySQL最终的索引结构其实就是把单向链表变成了双向链表前缀索引为什么可以提升索引性能因为前缀索引是利用一个字段的前N个字符来创建索引的相比于使用完整字段值作为索引键前缀索引的索引键占用的空间更少那么一个索引键越小一个BTree节点中就可以存放更多个索引键那么树的高度就越小那么磁盘IO次数就更少检索数据时的效率就高建立索引时的不为人知的内幕回顾一下我们一般都会通过一下几种方式来创建索引# 通过CREATE语句创建 CREATE INDEX indexName ON tableName (columnName(length) [ASC|DESC]); # 通过ALTER语句创建 ALTER TABLE tableName ADD INDEX indexName(columnName(length) [ASC|DESC]); # 建表时通过DML语句创建 CREATE TABLE tableName( columnName1 INT(8) NOT NULL, columnName2 ...., ....., INDEX [indexName] (columnName(length)) ); 在使用SQL语句创建索引的时候MySQL会先判断一下当前表的存储引擎因为索引机制本身是由存储引擎提供实现的不同的存储引擎实现的索引是不同的因此创建索引之前要先判断存储引擎是哪一个然后根据不同的存储引擎去创建索引那么接下来我们重点聊一下常用的MyISAM、InnoDB常用存储引擎的数据存储我们分别使用MyISAM和InnoDB这两个存储引擎来创建两张表观察一下它们创建索引时的区别# 创建一张使用MyISAM引擎的表zz_myisam_index CREATE TABLE zz_myisam_index ( z_m_id int(8) NOT NULL, z_m_name varchar(255) NULL DEFAULT ) ENGINE MyISAM CHARACTER SET utf8 COLLATE utf8_general_ci ROW_FORMAT Compact; # 创建一张使用InnoDB引擎的表zz_innodb_index CREATE TABLE zz_innodb_index ( z_i_id int(8) NOT NULL, z_i_name varchar(255) NULL DEFAULT ) ENGINE InnoDB CHARACTER SET utf8 COLLATE utf8_general_ci ROW_FORMAT Compact; 上述过程中创建了两张表zz_myisam_index、zz_innnodb_index分别使用了不同的存储引擎在MySQL中所有的数据都会放入到磁盘中存储我们可以先找一下这两张表的本地位置默认的文件位置应该是在C:\ProgramData\MySQL\MySQL Server 8.0\data这个目录下这个目录下保存了所有已创建的数据库磁盘文件例如不同的后缀名就代表使用了不同的存储引擎那么接下来我们就讲解一下不同存储引擎的区别使用MyISAM存储引擎的表zz_myisam_index这张表就是使用MyISAM存储引擎的表它在本地磁盘中有三个文件zz_myisam_index.frm该文件中存储表的结构信息zz_myisam_index.MYD该文件中存储表的行数据zz_myisam_index.MYI该文件中存储表的索引数据MyISAM存储引擎的表数据和索引数据是存储在两个不同的磁盘文件中的这也就意味着MyISAM存储引擎不支持聚簇索引因为聚簇索引要求表数据和索引数据都存储在同一个空间中MyISAM存储引擎的.MYI索引文件中存储的是表数据所在的地址指针使用InnoDB引擎的表zz_innodb_index这张表是使用InnoDB引擎的表在磁盘中仅有两个文件zz_innodb_index.frm该文件中存储表的结构信息zz_innodb_index.ibd该文件中存储表的行数据和索引数据因为InnoDB引擎中表数据和索引数据都一起放在.ibd文件中也就代表着索引数据和表数据是处于同一块空间存储的这符合聚簇索引的定义因此InnoDB支持聚簇索引同时也正由于这个原因所以如果使用InnoDB引擎的表未主动创建聚簇索引它会自动选择表中的主键字段作为聚簇索引的字段。但如果表中未声明主键字段那则会选择一个非空唯一索引来作为聚簇索引。但如果表中依旧没有非空的唯一索引InnoDB则会隐式定义一个主键来作为聚簇索引这个列在上层是不可见的是一个按序自增的值手动创建索引后会发送的事情当手动创建索引之后MySQL还会去看一下当前表使用了哪一个存储引擎然后就去判断表中是否存在数据如果表中没有数据就直接构建一些索引信息例如索引字段是谁、索引键占多少个字节、创建的是什么类型的索引、索引的名字、索引归属那张表、索引的数据结构等然后直接写入对应的磁盘文件中例如MyISAM的表就会写入到.MYI文件中InnoDB存储引擎则写入到.ibd文件中上述过程是表数据为空的情况下创建索引会做的工作但是如果表中有数据就会多很多步骤下面讲解一下当表中有数据时首先MySQL-Server会先看一下目前要创建什么类型的索引然后基于要创建索引的类型对索引字段的值进行对应的操作例如唯一索引判断索引字段的每个值是否存在重复值如果有则抛出错误码和提示信息主键索引判断主键字段的每个值是否重复、是否有值、有就抛出错误码和提示信息全文索引判断索引字段的数据类型是否为文本类型对索引字段的值进行分词处理前缀索引对索引字段的值进行截取工作选用指定范围的值作为索引键联合索引对于组成联合索引的多个列进行值拼接组成多列索引键.......还有很多根据不同索引类型进行了相应的处理之后紧接着就会去判断当前索引的数据结构是什么是BTree、Hash还是其他的结构然后根据索引对于的数据结构再对索引字段的值进行再次处理例如BTree对索引字段的值进行排序按照顺序组成BTree结构Hash对索引字段的值进行哈希处理处理相应的哈希冲突方便后续查找...........还有很多已经把索引的数据结构和索引字段对应的值处理好了那么接下来就会将内存中处理好的字段数据写入到本地相应的磁盘文件中但如果此时为InnoDB存储引擎那在写入前还会做最后一个判断就是判断当前索引是否为主键/聚簇索引如果当前创建索引的字段是主键字段则在写入时进行重构.ibd文件中的数据将索引键和行数据调整到一块区域中存储如果这里创建的索引不是主键/聚簇索引或者是MyISAM存储引擎即当前创建的索引是非聚簇索引那么就会为每个索引键(索引字段值)寻找相应的行数据找到之后和索引键关联起来不过InnoDB、MyISAM存储引擎两者之间的非聚簇索引也有些许差异InnoDB因为有聚簇索引存在所以非聚簇索引在与行数据建立关联时存放的是主键/聚簇索引的字段值MyISAM由于表数据在单独的.MYD文件中因此可以直接以指针的形式关联起来即InnoDB存储引擎中的非聚簇索引都是主键/聚簇索引的附庸每个索引信息中是以索引键聚簇字段值这种形式关联的MyISAM存储引擎的非聚簇索引关联的是行数据的指针而InnoDB存储引擎关联的是聚簇索引的索引键所以InnoDB存储引擎的非聚簇所以在查询时需要进行回表要再查询一次聚簇索引才能得到数据而MyISAM每个非聚簇索引都能直接获取到行数据的地址可以直接根据指针获取数据所以MyISAM检索数据的效率比InnoDB快不少索引键和行数据也关联好了就开始根据存储引擎的不同将内存中的索引信息分别写入到不同的磁盘文件中写入操作完成之后BTree的根节点会放到内存中进行维护以便于后续索引查询时再次从磁盘中读取根节点信息感兴趣可以看看聚簇索引和非聚簇索引的结构区别在上图中给出了一张用户表然后基于ID字段建立主键/聚簇索引基于name字段建立普通/非聚簇索引最终索引结构如图中所示。在InnoDB聚簇索引的示意图中由于不方便画出每行数据就用row_data代替行数据。在InnoDB非聚簇索引中每个索引信息中存储聚簇索引的ID值。MyISAM非聚簇索引中每个索引信息中则直接存储行数据的指针。当然这里也是画出的伪结构因为不可能按照MySQL单节点16KB的尺寸1:1还原毕竟画不下这么大实际MySQL对于上述这些数据一个节点就全放下了。索引键的大小会随着值长度变化吗这个问题很有趣比如现在基于一个int类型的字段建立了一个索引但目前的字段值是1按理来说这个值只占1bits对不对那在索引键中或数据库中占多少呢答案是4Bytes/32bits这是因为一个int类型在操作系统中就会占用32bit空间不会根据实际值而减少占用空间。但大家也都知道数据库中还有不少文本类型例如varchar类型它是固定的长度吗并不是它是一个变长类型而非一个定长类型也就是一个varchar字段值占用的空间会随着实际所存储的数据而变化。所以对于一个索引键的大小是否会发生变化这要取决于你是基于什么字段类型建立的索引如果是定长类型就不会变化但如果是变长类型就会随之发生改变。索引内部查询与维护的过程在执行查询SQL的时候选中了索引那么索引内部的检索过程是什么样的呢写类型的SQL更改表数据后MySQL又会如何维护索引的内部结构呢聚簇索引查找数据的过程在MySQL执行篇中说过当查询SQL来到MySQL后会经过一系列处理最终来到优化器通过优化器来为SQL语句选择出一个合适的索引如果你对业务系统足够熟悉也可以自己手动选择索引任君选择那么当SQL命中索引时索引内部是如何查找对应的行数据的工作线程在执行查询SQL时首先会看一下当前索引的结构如果是Hash索引就很简单直接对索引字段的值进行哈希计算然后直接根据哈希值从索引中找到相应的索引信息最后获取数据即可但是如果索引结构是默认的BTree结构内部又会发送什么呢如果当前SQL使用的是主键/聚簇索引例如select * from zz_user where id 12;首先会根据条件字段去内存中找到聚簇索引的根节点然后根据节点中记录的地址去找次级的叶节点最后再根据叶节点中的指针地址找到最下面的叶子节点从而获取其中的行数据如BTree结构的索引似乎查找过程也并不复杂对不对但有一个细节点需要注意BTree的单个节点可存储多个数据也就是当磁盘IO发生后MySQL一次读取的数据中有多个索引信息此时MySQL如果查找单个节点中的索引信息呢会全部判断一次嘛其实并不会全部判断一次因为BTree是一种有序的数据结构小的会放左边大的会放右边单个节点中的索引信息同样遵循这个原理。既然单个节点中的数据也是有序的所以MySQL同样会采用二分查找法去检索数据。对于单个节点中的索引信息先从索引中间开始查询然后判断一下当前SQL中ID12这个条件是大于还是小于最中间的索引键小于则去节点左边取中间的索引键继续判断大于则去右边.....以此类推直至定位到单节点中对应索引键为止。OK如果是范围取值比如取ID2的所有数据则会先定位到ID2的索引键然后通过叶子节点之后的指针直接将2之后的数据全部取出。聚簇索引中定位到了索引键即代表着取到了数据毕竟索引和行数据是一起存储的。非聚簇索引查找数据的过程相较于聚簇索引而言非聚簇索引前面的步骤都是相同的仅是最后一步有些许不同罢了非聚簇索引经过一系列查询步骤后最终会取到一个聚簇索引的字段值然后再做一次回表查询也就是再去聚簇索引中查一次才能取到数据。如果是MyISAM引擎则直接根据索引树中记录的指针地址直接触发磁盘IO再次读取数据即可。写SQL执行时索引的维护过程前面分析了查询SQL执行时索引查找数据的过程那么出现增删改SQL索引又是怎么维护的呢同样也是要分数据结构的如果是Hash结构的索引直接进行增删改对应的索引键即可但是如果是BTree结构的索引因为要求内部节点是有序的所以需要维护有序性即增删改操作都会对BTree结构造成影响插入数据时索引的变化BTree索引是有序的对于这点在前面已经反复提到了但如果索引字段是数值类型例如int、bigint、long等本身就能区分大小顺序此时可以直接做排序工作。但如果是基于字符串或其他类型的字段建立索引呢又该如何排序呀其实对于这个问题也并不难回答大家还记得在建库建表时干的一件事情嘛在创建库表时咱们通常都会指定一个排序规则而这个规则就是MySQL对非数值类型字段的排序规则比如字符串类型的字段MySQL就会基于该规则对值先做计算处理然后得到一个数值用于排序。当然具体排序处理的过程暂且不去纠结重点只需搞清楚一点数据库中任何字段都能排序即可。OK~那此时像数据库中插入一条数据时还是以之前的用户表为例比如sql 体验AI代码助手 代码解读 复制代码INSERT INTO zz_user VALUES(6,上海市黄浦区xx街道666号,棕熊,男,30);同样假设用户表上有两个索引一是基于自增ID建立的主键索引第二个则是基于姓名字段建立的普通索引。当表中插入这条数据后索引又会发生什么变化呢咱们分开聊聊。主键/聚簇索引的变化因为主键索引字段也就是ID字段是顺序递增的因此只需要在本地索引文件的BTree结构中按照树结构找到最后的位置将当前插入的ID:6作为索引键以当前插入的行数据作为索引值然后插入到最后的节点中即可。如下按序递增的索引维护就是这么简单普通/非聚簇索引的变化因为姓名字段本身的数据类型是字符串与数值型字段天生的有序不同字符串类型是无序的因此首先需要根据已经配置好的排序规则先对插入的name棕熊这个值进行计算然后根据计算出的值决定当前数据在BTree中的索引位置计算好之后再执行插入工作过程如下相较于主键字段的顺序ID插入字符串类型的name值会复杂一些因为从这里可以明显看到插入的“棕熊”数据经过计算后它并不排最后面而是排中间所以要将这个值插入到对应的位置此时树的节点就会发生裂变后续的所有叶子节点都需要往后移动这个开销是较大的。同时在插入索引信息时会以“棕熊”作为索引键以ID6作为索引值然后一同插入也就是要与行数据建立关联MyISAM引擎则是行数据的地址指针。删除数据时索引的变化DELETE FROM zz_user WHERE ID 5;例如上述这条删除语句当执行后则会先根据ID在索引树中查找索引信息然后先删除非聚簇索引上的索引信息紧接着再去聚簇索引上删除主键索引信息和行数据。过程大致是相同的就不再制作动图演示其过程了重点要记住的是先删非聚簇索引信息再删聚簇索引的信息因为聚簇索引上存放着行数据如果先把聚簇索引删了就无法找到非聚簇索引上的信息了。修改数据时索引的变化UPDATE zz_user SET name 狗熊 WHERE ID 6;对于上述这条修改语句索引维护的过程相信大家自己也能推测出来毕竟修改的本质就是先删再插入首先在聚簇索引上查到ID6这条数据获取原本的name字段值“棕熊”然后以该值去非聚簇索引上找到对应的索引信息然后先将聚簇索引中的数据行改掉接着删除次级非聚簇索引的信息最后再插入一个“狗熊”的次级索引信息。会先更新数据行再修改次级索引的值但次级索引的修改是先删后改而聚簇索引不会删数据因为聚簇索引上保存着行数据是直接对行数据进行修改先读到内存中改完覆盖原本的数据。修改聚簇索引数据行的过程首先会在聚簇索引上根据ID6找到对应的行数据然后将行数据中的name字段更新为“狗熊”。至此对于写SQL执行后索引的维护过程就做了简单分析实际上也并不难。PS实际索引更新数据时具体的过程也会复杂一些会牵扯到锁机制也包括会判断修改的新值与原值的大小如果大小相同则直接在原空间做修改直接插入覆盖如果不同才会先删再改。主键为何推荐使用自增整数ID在《索引应用篇-主键的陷阱》中我曾推荐大家使用自增的整数ID作为主键而并不是使用随机的UUID这类字符串等类型这是为何呢因为观察前面name索引字段的插入过程能够很明显的观察到一个现象字符串是无序的当使用字符串作为主键字段时在插入数据的时候会频繁破坏原有的树结构造成树分裂以及后续节点的挪动一两个条数据插入倒还没关系但是每一条插入的数据都有可能导致树的结构调整一次这个过程的开销可想而知.....但是自增的整数ID就不会有这个问题因为插入的ID本身就是按序递增的因此插入的每一条新数据都会直接放到BTree最后的节点中存储。同时除开上述原因外还有一个原因就是UUID比整数自增ID长UUID至少占位32字节但int类型只占4字节存储一个UUID的空间可以存8个自增整数ID。也就代表着单个节点中能存储的自增ID会比UUID多很多单个节点存储的索引键越多.....后面这一排就不讲了前面复述过两次了大家应该也懂哈总结聚簇索引和非聚簇索引的根本区别聚簇索引中表数据和索引数据是按照相同顺序存储的非聚簇索引则不是。聚簇索引在一张表中是唯一的只能有一个非聚簇索引则可以存在多个。聚簇索引在逻辑物理上都是连续的非聚簇索引则仅是逻辑上的连续。聚簇索引中找到了索引键就找到了行数据但非聚簇索引还需要做一次回表查询。InnoDB-非聚簇索引与MyISAM-非聚簇索引的区别InnoDB中的非聚簇索引是以聚簇索引的索引键与具体的行数据建立关联关系的。MyISAM中的非聚簇索引是以行数据的地址指针与具体的行数据建立关联关系的。
六，MySQL索引原理篇：深入数据库底层原理揭开索引机制的神秘面纱
引言本篇文章是MySQL索引篇的终章通过前两篇文章MySQL索引初始篇、MySQL索引应用篇我们对索引有了深入的理解但是MySQL索引机制还是存在一些不理解的问题例如建立索引后MySQL会发生上面使用索引查询时是如何进行检索数据的而且在前面两篇文章中也留下了很多疑惑所以我们就在MySQL索引原理篇中去学习索引原理及其底层实现MySQL索引为什么使用BTree结构在MySQL索引机制中大家都知道MySQL索引机制默认使用BTree作为底层数据结构但是为什么使用BTree不使用其他树结构呢例如为什么不使用AVL树、B树、红黑树、二叉树呢那么我们下面就来聊一下索引为什么不支持数字、链表、队列等数据结构呢是因为这些元素都是按顺序并排促成农户的如果选择这些数据结构来实现索引的话那么走索引就没有意义了走索引了还是进行全表扫描没有给查询效率提高还会带来额外的内存开销毫无意义普通SQL的全表扫描过程想要真正理解MySQL为什么选用BTree作为索引机制的底层数据结构就得先理解一条普通SQL是如何进行全表扫描的理解全表扫描的过程即没有使用索引的时候这条普通SQL是如何执行的这样才能体会到有索引和没有索引的区别我们这里就讲解一下MySQL全表扫描的实际过程以下面这张用户表为例子------------------------------------------------------- | id | address | name | sex | age | ------------------------------------------------------- | 1 | 北京 | aa | 男 | 18 | ------------------------------------------------------- | 2 | 上海 | bb | 女 | 20 | ------------------------------------------------------- | 3 | 天津 | ff | 男 | 22 | ------------------------------------------------------- | 4 | 浙江 | dd | 女 | 24 | ------------------------------------------------------- | 5 | 广东 | ee | 男 | 23 | ------------------------------------------------------- 首先写一条不存在任何索引的普通SQL语句select * from user_table where name aa;因为这个用户表没有创建索引所以就没有使用到索引机制所以这里会走全表扫描通过全表扫描的形式来检索数据但是不管走的是全表扫描还是索引机制去检索数据数据都是存储在磁盘上的所以首先都会触发磁盘IO所以先说一下磁盘寻道的过程参考自竹子爱熊猫如果磁盘不是SSD类型那么磁盘大致是上面这个样子里面有一个盘面和磁针当发生磁盘IO时会根据给出的磁盘地址在盘面上寻道这个过程就跟VCD、DVD光碟一样盘面会开始转圈在盘面上有一个磁道当在盘面上转到对应的地址时磁道和磁针就会互相吸引然后以一上一下的方式读取0、1二进制数据最终从磁盘中将目标地址的数据读取出来走全表扫描的时候必然会触发磁盘IO但是磁盘寻道需要一个地址这个地址最开始就是本地表数据文件中的起始地址就是从表中第一行数据开始读读取到数据之后就会载入内存MySQL-Server就会根据所写的查询SQL的查询条件对读取到的数据进行判断如果不符合条件就会继续进行磁盘IO去读取其他数据如果表数据量比较大这里就不会按顺序IO的形式走全表检索而是触发随机的磁盘IO那么如果我们要查询上表的第五条数据那么是一定就会进行五次磁盘IO吗肯定不是的因为OS、MySQL中有一个优化措施叫局部性读取原理局部性读取原理比如目前有三块内存页x、y、z是相连的CPU此时在操作内存页x转的数据那么按照计算机的特性一般同一个数据都会被放入到物理相连的内存地址上存储即当前在操作x页的数据那么对于y、z这两页内存的数据很有可能在接下来的时间内被操作因此对于y、z这两页数据则会提前将其载入告诉缓冲区L1/L2/L3这个过程就叫利用局部性原理“预读”数据但是一次到底预读多大的数据放入到高速缓冲区中呢这个是由缓存行大小决定的例如在英特尔的MESI协议中缓存行的默认大小为64bytes也就是说在英特尔的CPU中一次性会将当前操作数据附近的64bytes数据(2页数据)提前载入进高速缓冲区上面讲的内容是操作系统高速缓冲区的知识如果没学OS的可以先去学一学在CPU中利用局部性原理提前将数据从内存放入L1/L2/L3三级缓冲区中主要是为了减少CPU寄存器与内存之间的性能差异由于CPU寄存器和内存之间的性能差异太大所以逐个读数据的形式会导致CPU工作期间的大量时间会处于等待数据状态所以利用局部性原理将数据“预读”到高速区。而对于MySQL而言亦是同理存储数据的磁盘和内存之间的性能差异也是巨大的因为MySQL也会利用局部性原理提前“预读”数据。这是什么意思呢其实就是指MySQL一次磁盘IO不仅仅只会读取一条表数据而是会读取多条数据那到底读多少条数据呢在InnoDB引擎中一次默认会读取16KB数据到内存。全表扫描过程由于MySQL中会使用局部性原理的思想所以对于给出的用户表数据而言可能只需要发生一次磁盘IO就能将前五条数据全部读到内存然后会在内存中对本次读取的数据逐条判断看一下每条数据的姓名字段是否为ee如果发现不符合SQL条件的行数据则会将当前这条数据放弃同时在本次SQL执行过程中会排除掉这条数据不会对其进行二次读取。如果发现当前的数据符合SQL条件要求则会将当前数据写入到结果集中然后继续判断其他数据。当本次磁盘IO读取到的所有数据全部筛选完成后紧接着会看一下表中是否还有其他数据如果还有则继续触发磁盘IO检索数据如果没有则将内存中的结果集返回。有人或许会疑惑为什么这里已经读到了符合条件的数据还需要继续发生磁盘IO呢因为表中的字段没有建立唯一索引或唯一约束因此MySQL不确定是否还有其他同名的数据所以需要将整个表全部扫描一遍才能得到最终结论。好的到这里就将MySQL全表扫描的过程讲明白了紧着来看看全表扫描有什么问题呢其实按目前的情况来看似乎不会有太大的问题因此表中数据不多一次磁盘IO几乎就能读完。但思考一下如果当表的数据量变为百万级别、千万级别呢假设表中一条数据大小为512Byte一次磁盘IO也只能读32条假设表中有320w条数据一次全表就有可能会触发10W次磁盘IO每次都需要在硬件上让那个盘面转啊转其过程的开销可想而知.....因此建立索引的原因就在于此处为了避免查询时走全表扫描因此全表扫描的开销会随着数据量增长而越来越大。索引为什么不选择二叉树研究这个问题就和数据结构与算法有一点关系了不过没学过也没事国外有一个大佬自己搭建了一个数据结构的动画演示网站里面有很多数据结构类型的动画展示图Data Structure Visualization前面我们已经知道了全表扫描走的是线性查询 如果数据越多开销就越大此时先来看看二叉搜索树二叉树也叫二叉搜索树Binary Search Tree二叉搜索树是遵循二分搜索实现的一种数据结构那么接下来我们就看看为什么这种数据结构不适合作为索引机制的底层数据结构这个图可以自己从上面说的哪个网站上自己画这就是一颗二叉搜索树我们构建了6个节点那么根据我们上面给的用户表案例假设我们要查询第五条数据ee以二叉搜索树作为索引机制的底层数据结构那么很显然需要走5次磁盘IO才能检索到对应的数据从这个动态的图中就可以看出确实就是要进行五次查询的因为树结构在磁盘中存储的位置不连续因此无法利用局部性原理读取后续的节点所以最终需要发送五次磁盘IO才能读取到数据二叉树不适合作为索引结构的原因如果索引的字段值是按顺序增长的二叉树会转变为链表结构由于结构转变成了链表结构因此检索的过程和全表扫描完全一样由于树结构在磁盘中各节点的数据并不连续因此无法利用局部性原理索引为什么不选择红黑树Red-Black Tree红黑树相比于二叉树红黑树进行了优化红黑树是一种自适应的平衡树会根据插入的节点数量和节点信息自动调整树结构来维持平衡从树的高度上看相比于上面二叉树同样是六个节点但是红黑树只有四层二叉树有六层那么很显然就检索数据的时候进行磁盘IO的次数减少了然后我们再看看检索过程同样去查询第五条数据ee红黑树只需要查询3次就查询到指定的数据了似乎比二叉树优化了很多但是为什么MySQL不选择红黑树呢红黑树不适合作为索引结构的原因虽然相比于二叉树来说树的高度/深度减少了查询次数少了但是这只是在数据量少的情况下体现了优势如果数据量大了树的高度依然会很大所以红黑树也不是最优解而且红黑树每一个节点只能存储一个数据节点之间也不是连续的所以一样不能使用局部性原理如果让单个节点存储的数据变多可以存储多个数据是不是又进一步优化呢B树就是这么进行优化的索引所以为什么不选择B-TreeB-Tree就是在红黑树的基础上进行了优化使得一个节点可以存储多个数据在上述网站中Max.Degree3就是表示每个节点最多可以存储多少个数据等于3就表示最多只能存储两个数据第三个数据就要往下进行拆分可以通过网站来进行操作一下同样给B-Tree也构建6个节点很显然单个节点可以存储多个数据而且树的高度也减少了只有2层了然后再看看B-Tree的查找过程只需要两次就查询到指定数据了而且一个节点可以存储多个数据那么还可以使用局部性原理让一次磁盘IO可以读取多个数据意思就是每查询一个节点都需要进行一次磁盘IO如果只能存储一个数据那么这次磁盘IO就只能检索到一个数据如果可以存储多个数据那么这些数据就是连续的而且一次磁盘IO就可以查询到多个数据select * from user_table where id between 2 and 5;例如上面这条SQL,需要查询表中id在2~5的所有数据,那就代表着需要查询4条数据,根据上面设置了更大的单个节点存储数据个数的容量,所有的数据都存在了一个节点中,所以只需要进行一次磁盘IO就可以查询到指定数据,但是在实际业务中数据量没有这么小,所以不可能所有的数据都会存储在一个节点中,所以又会触发多次磁盘IO进行检索数据,所以B-Tree也不合适作为索引的结构B-Tree不适合作为索引结构的原因即使相比于前面的二叉树和红黑树也有优化,但是当大数据量的时候一样需要进行多次磁盘IO来进行检索数据,所以也不是最优的结构,因为实际业务中的数据量都是很大的索引为什么要选择BTreeB-Tree的缺点就是不太适合进行范围查询,但是范围查询在关系型数据库中很常见,所以还需要进行优化,那么就来看看BTree相比于B-Tree,BTree的一个变化是有了叶节点和叶子节点,后面会详细讲这两个节点的作用,而且BTree在最下面一排节点之间,都存在一个单向指针,指向下一个节点的位置那么通过这个单向指针,在我们进行范围查询的时候,只需要找到第一个节点,然后直接根据个节点之间的单向指针,获取到对应范围之内的所有节点即可,所以只需要进行一次磁盘IO就能查询到范围查询中所以数据的位置那么下面我们看看叶节点和叶子节点在MySQL索引中的作用首先我们要指定叶节点和叶子节点是什么红圈范围内的是叶节点在MySQL中是不会存储数据的仅存储指向叶子节点的指针这样做的好处是能够让一个叶节点中存储更多的元素从而确保树的高度不会由于数据增长而变得很高最下面那一排节点就是叶子节点这些节点内部会存储实际的数据例如聚簇索引中就直接存储对应的行数据非聚簇索引中则存储指向主键/聚簇索引的字段值。同时每个叶子节点之间都有一个单向指针指向下一个节点从而使得最下面的一排叶子节点之间又形成了一个单向链表结构方便范围取值BTree结构为什么会存在叶节点在BTree中使用了叶节点同时冗余了一份节点信息这是为什么呢很明显从上面这个图中会发现BTree结构中2、3、4、5节点都出现了两次只有第一个和最后一个节点只出现了一次那么为什么要冗余节点呢首先我们要知道不能把所有的索引数据、表数据都存储在一个节点中虽然这样使得树的高度只有1看起来好像只需要一次磁盘IO就可以检索到自己需要的数据但事实并非如此因为一次磁盘IO读取的数据量是有限的不是想读取多少数据量就读取多少的一次磁盘IO只能读取一个节点中的一部分数据如果将整个节点的数据读取完一样需要进行多次磁盘IO本质上跟走一次全表查询没有什么区别那么为什么要冗余节点呢因为BTree中每个节点存放数据个数的大小是有效的如果我们把实际数据存储到叶节点中会导致单个树节点存储的索引键很少。但是如果树的叶节点不存储实际表中的行数据就代表单个节点可以存更多的索引键单个节点可以存更多的索引键就代表树的高度会变小树的高度越小就相当于查询时发送的磁盘IO的次数越少磁盘IO的次数越少那么检索数据的速度就越快所以这就是为什么BTree要使用叶节点冗余索引键但是索引中除了索引键还需要存储实际的行数据所以在下面一排的叶子节点中就会存储对应的索引键与行数据/聚簇索引字段值所以BTree的叶节点只是一个过渡的作用就是为了提高所以效率实际的行数据是保存在最下面的叶子节点中叶节点中仅有一个指针指向而已千万数据量级别的BTree会有多高假设MySQL中有一张千万级别数据量的表如果基于自增id的主键字段建立BTree索引那么此时树有多高呢想要知道这颗树有多高就必须建立在实际的依据上来计算索引字段值的大小MySQL中BTree单个节点的大小MySQL中单个指针的大小如何计算索引字段值的大小根据这个字段所使用的数据类型来决定。假设此时自增id在创建表的时候使用的数据类型是int类型int类型在计算机中占4bytes那么此时基于id字段建立主键索引时BTree每个节点的索引键大小就是4bytes如何获取到MySQL中BTree单个节点的大小对于索引单个节点的容量是多少在MySQL中默认使用引擎的一页大小作为单节点的容量假设此时表的存储引擎是InnoDB既可以通过下面这条命令进行查询show global status like Innodb_page_szie; ------------------------- | Variable_name | Value | ------------------------- | Innodb_page_size | 16384 | ------------------------- 从上述查询结果看InnoDB引擎的一页大小为16384bytes也就是16kb此时就代表BTree的每个节点容量是16kbMySQL中的指针是多大一般来说操作系统的指针为了方便寻址一般都与当前的操作系统的位数对应例如32位的操作系统指针就是32bit/4bytes,64位的操作系统指针一般是64bit/8bytes但是由于64bit的指针寻址范围太大目前计算机根本用不上这么大的寻址范围因此在MySQL-InnoDB引擎的源码中单个指针被缩小到6bytes千万级别的所有树高计算单个索引节点容量16kb主键字段值4b指针大小6b一个完整的索引信息是由主键字段指针组成的也就是4610B那此时先计算一下单个节点中可存储多少个索引信息16kb / 10b 1638个那此时来计算一下对于一颗高度为2的BTree根节点可存储1638个叶子节点指针也就代表着BTree的第二层有1638个叶子节点因为叶子节点要存储实际的行数据假设表中每行数据为1KB这也就是代表着一个叶子节点中可存储16条行数据那么一颗高度为2的B树可存储的索引信息为1638 * 16 26208条数据。再来算算树高为3的B树可以存多少呢因为最下面一排才是叶子节点此时树高为3也就代表着中间一排是叶节点只存储指针并不存储数据而每个节点可容纳1638个索引键指针信息因此计算过程是1638 * 1638 * 16 42928704条。是不是很令你惊讶树高为3的BTree竟然可以存储四千多万条数据也就代表着千万级别的表走索引查询的情况下大致只需要发生三次磁盘IO即可获取数据。当然上述的这个数据是基于主键为int类型、表的一行数据为1KB来计算的实际情况中会不一样因为主键有可能是bigint类型或其他类型而一行数据也可能不仅仅只有1KB。因此对于一张实际的千万级别表它的主键索引实际树高有多少你结合主键的数据类型以及一行数据的大小也可以计算出来它同时不会太高。 对实际的千万表索引树高感兴趣的我提供一个计算公式索引键大小索引字段类型所占的空间、一行表数据大小所有表字段的类型隐藏字段20Bytes所占大小总和得到这两个值之后再套入前面的例子中既可得知。看到这里对于索引凭啥那么快为啥能够提升查询性能相信大家也有了答案毕竟索引树高才是个位数发生的磁盘IO次数也那么少检索数据的速度不快才来了个鬼不过BTree中的每个索引页中还会存储页头页号、指针、伪记录等、页目录、页尾等信息大概一共占用128Bytes左右因此想要真正的计算出来接近实际情况的索引树高还需要把这点考虑在内MySQL索引底层的真正结构MySQL的索引底层的结构并不是直接就是BTree的原型因为BTree的叶子节点之间是单向指针组成的链表结构不适合用于倒排序查询因为只有单向指针只能先正序获取数据后再倒排一次所以MySQL对BTree进行了进一步的优化才得到MySQL最终的索引结构其实就是把单向链表变成了双向链表前缀索引为什么可以提升索引性能因为前缀索引是利用一个字段的前N个字符来创建索引的相比于使用完整字段值作为索引键前缀索引的索引键占用的空间更少那么一个索引键越小一个BTree节点中就可以存放更多个索引键那么树的高度就越小那么磁盘IO次数就更少检索数据时的效率就高建立索引时的不为人知的内幕回顾一下我们一般都会通过一下几种方式来创建索引# 通过CREATE语句创建 CREATE INDEX indexName ON tableName (columnName(length) [ASC|DESC]); # 通过ALTER语句创建 ALTER TABLE tableName ADD INDEX indexName(columnName(length) [ASC|DESC]); # 建表时通过DML语句创建 CREATE TABLE tableName( columnName1 INT(8) NOT NULL, columnName2 ...., ....., INDEX [indexName] (columnName(length)) ); 在使用SQL语句创建索引的时候MySQL会先判断一下当前表的存储引擎因为索引机制本身是由存储引擎提供实现的不同的存储引擎实现的索引是不同的因此创建索引之前要先判断存储引擎是哪一个然后根据不同的存储引擎去创建索引那么接下来我们重点聊一下常用的MyISAM、InnoDB常用存储引擎的数据存储我们分别使用MyISAM和InnoDB这两个存储引擎来创建两张表观察一下它们创建索引时的区别# 创建一张使用MyISAM引擎的表zz_myisam_index CREATE TABLE zz_myisam_index ( z_m_id int(8) NOT NULL, z_m_name varchar(255) NULL DEFAULT ) ENGINE MyISAM CHARACTER SET utf8 COLLATE utf8_general_ci ROW_FORMAT Compact; # 创建一张使用InnoDB引擎的表zz_innodb_index CREATE TABLE zz_innodb_index ( z_i_id int(8) NOT NULL, z_i_name varchar(255) NULL DEFAULT ) ENGINE InnoDB CHARACTER SET utf8 COLLATE utf8_general_ci ROW_FORMAT Compact; 上述过程中创建了两张表zz_myisam_index、zz_innnodb_index分别使用了不同的存储引擎在MySQL中所有的数据都会放入到磁盘中存储我们可以先找一下这两张表的本地位置默认的文件位置应该是在C:\ProgramData\MySQL\MySQL Server 8.0\data这个目录下这个目录下保存了所有已创建的数据库磁盘文件例如不同的后缀名就代表使用了不同的存储引擎那么接下来我们就讲解一下不同存储引擎的区别使用MyISAM存储引擎的表zz_myisam_index这张表就是使用MyISAM存储引擎的表它在本地磁盘中有三个文件zz_myisam_index.frm该文件中存储表的结构信息zz_myisam_index.MYD该文件中存储表的行数据zz_myisam_index.MYI该文件中存储表的索引数据MyISAM存储引擎的表数据和索引数据是存储在两个不同的磁盘文件中的这也就意味着MyISAM存储引擎不支持聚簇索引因为聚簇索引要求表数据和索引数据都存储在同一个空间中MyISAM存储引擎的.MYI索引文件中存储的是表数据所在的地址指针使用InnoDB引擎的表zz_innodb_index这张表是使用InnoDB引擎的表在磁盘中仅有两个文件zz_innodb_index.frm该文件中存储表的结构信息zz_innodb_index.ibd该文件中存储表的行数据和索引数据因为InnoDB引擎中表数据和索引数据都一起放在.ibd文件中也就代表着索引数据和表数据是处于同一块空间存储的这符合聚簇索引的定义因此InnoDB支持聚簇索引同时也正由于这个原因所以如果使用InnoDB引擎的表未主动创建聚簇索引它会自动选择表中的主键字段作为聚簇索引的字段。但如果表中未声明主键字段那则会选择一个非空唯一索引来作为聚簇索引。但如果表中依旧没有非空的唯一索引InnoDB则会隐式定义一个主键来作为聚簇索引这个列在上层是不可见的是一个按序自增的值手动创建索引后会发送的事情当手动创建索引之后MySQL还会去看一下当前表使用了哪一个存储引擎然后就去判断表中是否存在数据如果表中没有数据就直接构建一些索引信息例如索引字段是谁、索引键占多少个字节、创建的是什么类型的索引、索引的名字、索引归属那张表、索引的数据结构等然后直接写入对应的磁盘文件中例如MyISAM的表就会写入到.MYI文件中InnoDB存储引擎则写入到.ibd文件中上述过程是表数据为空的情况下创建索引会做的工作但是如果表中有数据就会多很多步骤下面讲解一下当表中有数据时首先MySQL-Server会先看一下目前要创建什么类型的索引然后基于要创建索引的类型对索引字段的值进行对应的操作例如唯一索引判断索引字段的每个值是否存在重复值如果有则抛出错误码和提示信息主键索引判断主键字段的每个值是否重复、是否有值、有就抛出错误码和提示信息全文索引判断索引字段的数据类型是否为文本类型对索引字段的值进行分词处理前缀索引对索引字段的值进行截取工作选用指定范围的值作为索引键联合索引对于组成联合索引的多个列进行值拼接组成多列索引键.......还有很多根据不同索引类型进行了相应的处理之后紧接着就会去判断当前索引的数据结构是什么是BTree、Hash还是其他的结构然后根据索引对于的数据结构再对索引字段的值进行再次处理例如BTree对索引字段的值进行排序按照顺序组成BTree结构Hash对索引字段的值进行哈希处理处理相应的哈希冲突方便后续查找...........还有很多已经把索引的数据结构和索引字段对应的值处理好了那么接下来就会将内存中处理好的字段数据写入到本地相应的磁盘文件中但如果此时为InnoDB存储引擎那在写入前还会做最后一个判断就是判断当前索引是否为主键/聚簇索引如果当前创建索引的字段是主键字段则在写入时进行重构.ibd文件中的数据将索引键和行数据调整到一块区域中存储如果这里创建的索引不是主键/聚簇索引或者是MyISAM存储引擎即当前创建的索引是非聚簇索引那么就会为每个索引键(索引字段值)寻找相应的行数据找到之后和索引键关联起来不过InnoDB、MyISAM存储引擎两者之间的非聚簇索引也有些许差异InnoDB因为有聚簇索引存在所以非聚簇索引在与行数据建立关联时存放的是主键/聚簇索引的字段值MyISAM由于表数据在单独的.MYD文件中因此可以直接以指针的形式关联起来即InnoDB存储引擎中的非聚簇索引都是主键/聚簇索引的附庸每个索引信息中是以索引键聚簇字段值这种形式关联的MyISAM存储引擎的非聚簇索引关联的是行数据的指针而InnoDB存储引擎关联的是聚簇索引的索引键所以InnoDB存储引擎的非聚簇所以在查询时需要进行回表要再查询一次聚簇索引才能得到数据而MyISAM每个非聚簇索引都能直接获取到行数据的地址可以直接根据指针获取数据所以MyISAM检索数据的效率比InnoDB快不少索引键和行数据也关联好了就开始根据存储引擎的不同将内存中的索引信息分别写入到不同的磁盘文件中写入操作完成之后BTree的根节点会放到内存中进行维护以便于后续索引查询时再次从磁盘中读取根节点信息感兴趣可以看看聚簇索引和非聚簇索引的结构区别在上图中给出了一张用户表然后基于ID字段建立主键/聚簇索引基于name字段建立普通/非聚簇索引最终索引结构如图中所示。在InnoDB聚簇索引的示意图中由于不方便画出每行数据就用row_data代替行数据。在InnoDB非聚簇索引中每个索引信息中存储聚簇索引的ID值。MyISAM非聚簇索引中每个索引信息中则直接存储行数据的指针。当然这里也是画出的伪结构因为不可能按照MySQL单节点16KB的尺寸1:1还原毕竟画不下这么大实际MySQL对于上述这些数据一个节点就全放下了。索引键的大小会随着值长度变化吗这个问题很有趣比如现在基于一个int类型的字段建立了一个索引但目前的字段值是1按理来说这个值只占1bits对不对那在索引键中或数据库中占多少呢答案是4Bytes/32bits这是因为一个int类型在操作系统中就会占用32bit空间不会根据实际值而减少占用空间。但大家也都知道数据库中还有不少文本类型例如varchar类型它是固定的长度吗并不是它是一个变长类型而非一个定长类型也就是一个varchar字段值占用的空间会随着实际所存储的数据而变化。所以对于一个索引键的大小是否会发生变化这要取决于你是基于什么字段类型建立的索引如果是定长类型就不会变化但如果是变长类型就会随之发生改变。索引内部查询与维护的过程在执行查询SQL的时候选中了索引那么索引内部的检索过程是什么样的呢写类型的SQL更改表数据后MySQL又会如何维护索引的内部结构呢聚簇索引查找数据的过程在MySQL执行篇中说过当查询SQL来到MySQL后会经过一系列处理最终来到优化器通过优化器来为SQL语句选择出一个合适的索引如果你对业务系统足够熟悉也可以自己手动选择索引任君选择那么当SQL命中索引时索引内部是如何查找对应的行数据的工作线程在执行查询SQL时首先会看一下当前索引的结构如果是Hash索引就很简单直接对索引字段的值进行哈希计算然后直接根据哈希值从索引中找到相应的索引信息最后获取数据即可但是如果索引结构是默认的BTree结构内部又会发送什么呢如果当前SQL使用的是主键/聚簇索引例如select * from zz_user where id 12;首先会根据条件字段去内存中找到聚簇索引的根节点然后根据节点中记录的地址去找次级的叶节点最后再根据叶节点中的指针地址找到最下面的叶子节点从而获取其中的行数据如BTree结构的索引似乎查找过程也并不复杂对不对但有一个细节点需要注意BTree的单个节点可存储多个数据也就是当磁盘IO发生后MySQL一次读取的数据中有多个索引信息此时MySQL如果查找单个节点中的索引信息呢会全部判断一次嘛其实并不会全部判断一次因为BTree是一种有序的数据结构小的会放左边大的会放右边单个节点中的索引信息同样遵循这个原理。既然单个节点中的数据也是有序的所以MySQL同样会采用二分查找法去检索数据。对于单个节点中的索引信息先从索引中间开始查询然后判断一下当前SQL中ID12这个条件是大于还是小于最中间的索引键小于则去节点左边取中间的索引键继续判断大于则去右边.....以此类推直至定位到单节点中对应索引键为止。OK如果是范围取值比如取ID2的所有数据则会先定位到ID2的索引键然后通过叶子节点之后的指针直接将2之后的数据全部取出。聚簇索引中定位到了索引键即代表着取到了数据毕竟索引和行数据是一起存储的。非聚簇索引查找数据的过程相较于聚簇索引而言非聚簇索引前面的步骤都是相同的仅是最后一步有些许不同罢了非聚簇索引经过一系列查询步骤后最终会取到一个聚簇索引的字段值然后再做一次回表查询也就是再去聚簇索引中查一次才能取到数据。如果是MyISAM引擎则直接根据索引树中记录的指针地址直接触发磁盘IO再次读取数据即可。写SQL执行时索引的维护过程前面分析了查询SQL执行时索引查找数据的过程那么出现增删改SQL索引又是怎么维护的呢同样也是要分数据结构的如果是Hash结构的索引直接进行增删改对应的索引键即可但是如果是BTree结构的索引因为要求内部节点是有序的所以需要维护有序性即增删改操作都会对BTree结构造成影响插入数据时索引的变化BTree索引是有序的对于这点在前面已经反复提到了但如果索引字段是数值类型例如int、bigint、long等本身就能区分大小顺序此时可以直接做排序工作。但如果是基于字符串或其他类型的字段建立索引呢又该如何排序呀其实对于这个问题也并不难回答大家还记得在建库建表时干的一件事情嘛在创建库表时咱们通常都会指定一个排序规则而这个规则就是MySQL对非数值类型字段的排序规则比如字符串类型的字段MySQL就会基于该规则对值先做计算处理然后得到一个数值用于排序。当然具体排序处理的过程暂且不去纠结重点只需搞清楚一点数据库中任何字段都能排序即可。OK~那此时像数据库中插入一条数据时还是以之前的用户表为例比如sql 体验AI代码助手 代码解读 复制代码INSERT INTO zz_user VALUES(6,上海市黄浦区xx街道666号,棕熊,男,30);同样假设用户表上有两个索引一是基于自增ID建立的主键索引第二个则是基于姓名字段建立的普通索引。当表中插入这条数据后索引又会发生什么变化呢咱们分开聊聊。主键/聚簇索引的变化因为主键索引字段也就是ID字段是顺序递增的因此只需要在本地索引文件的BTree结构中按照树结构找到最后的位置将当前插入的ID:6作为索引键以当前插入的行数据作为索引值然后插入到最后的节点中即可。如下按序递增的索引维护就是这么简单普通/非聚簇索引的变化因为姓名字段本身的数据类型是字符串与数值型字段天生的有序不同字符串类型是无序的因此首先需要根据已经配置好的排序规则先对插入的name棕熊这个值进行计算然后根据计算出的值决定当前数据在BTree中的索引位置计算好之后再执行插入工作过程如下相较于主键字段的顺序ID插入字符串类型的name值会复杂一些因为从这里可以明显看到插入的“棕熊”数据经过计算后它并不排最后面而是排中间所以要将这个值插入到对应的位置此时树的节点就会发生裂变后续的所有叶子节点都需要往后移动这个开销是较大的。同时在插入索引信息时会以“棕熊”作为索引键以ID6作为索引值然后一同插入也就是要与行数据建立关联MyISAM引擎则是行数据的地址指针。删除数据时索引的变化DELETE FROM zz_user WHERE ID 5;例如上述这条删除语句当执行后则会先根据ID在索引树中查找索引信息然后先删除非聚簇索引上的索引信息紧接着再去聚簇索引上删除主键索引信息和行数据。过程大致是相同的就不再制作动图演示其过程了重点要记住的是先删非聚簇索引信息再删聚簇索引的信息因为聚簇索引上存放着行数据如果先把聚簇索引删了就无法找到非聚簇索引上的信息了。修改数据时索引的变化UPDATE zz_user SET name 狗熊 WHERE ID 6;对于上述这条修改语句索引维护的过程相信大家自己也能推测出来毕竟修改的本质就是先删再插入首先在聚簇索引上查到ID6这条数据获取原本的name字段值“棕熊”然后以该值去非聚簇索引上找到对应的索引信息然后先将聚簇索引中的数据行改掉接着删除次级非聚簇索引的信息最后再插入一个“狗熊”的次级索引信息。会先更新数据行再修改次级索引的值但次级索引的修改是先删后改而聚簇索引不会删数据因为聚簇索引上保存着行数据是直接对行数据进行修改先读到内存中改完覆盖原本的数据。修改聚簇索引数据行的过程首先会在聚簇索引上根据ID6找到对应的行数据然后将行数据中的name字段更新为“狗熊”。至此对于写SQL执行后索引的维护过程就做了简单分析实际上也并不难。PS实际索引更新数据时具体的过程也会复杂一些会牵扯到锁机制也包括会判断修改的新值与原值的大小如果大小相同则直接在原空间做修改直接插入覆盖如果不同才会先删再改。主键为何推荐使用自增整数ID在《索引应用篇-主键的陷阱》中我曾推荐大家使用自增的整数ID作为主键而并不是使用随机的UUID这类字符串等类型这是为何呢因为观察前面name索引字段的插入过程能够很明显的观察到一个现象字符串是无序的当使用字符串作为主键字段时在插入数据的时候会频繁破坏原有的树结构造成树分裂以及后续节点的挪动一两个条数据插入倒还没关系但是每一条插入的数据都有可能导致树的结构调整一次这个过程的开销可想而知.....但是自增的整数ID就不会有这个问题因为插入的ID本身就是按序递增的因此插入的每一条新数据都会直接放到BTree最后的节点中存储。同时除开上述原因外还有一个原因就是UUID比整数自增ID长UUID至少占位32字节但int类型只占4字节存储一个UUID的空间可以存8个自增整数ID。也就代表着单个节点中能存储的自增ID会比UUID多很多单个节点存储的索引键越多.....后面这一排就不讲了前面复述过两次了大家应该也懂哈总结聚簇索引和非聚簇索引的根本区别聚簇索引中表数据和索引数据是按照相同顺序存储的非聚簇索引则不是。聚簇索引在一张表中是唯一的只能有一个非聚簇索引则可以存在多个。聚簇索引在逻辑物理上都是连续的非聚簇索引则仅是逻辑上的连续。聚簇索引中找到了索引键就找到了行数据但非聚簇索引还需要做一次回表查询。InnoDB-非聚簇索引与MyISAM-非聚簇索引的区别InnoDB中的非聚簇索引是以聚簇索引的索引键与具体的行数据建立关联关系的。MyISAM中的非聚簇索引是以行数据的地址指针与具体的行数据建立关联关系的。
