深入解析mysql中的索引（原理详解）

一、什么是索引

索引是帮助MySQL高效获取数据的排好序的数据结构

前置知识：树的高度越低查询效率越高

二、索引数据结构

数据结构模拟网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
（一）二叉树
问题：不能自平衡，极端情况出现倾斜，查询效率和链表类似

（二）红黑树
红黑树对数据进行平衡，解决了单边增长的问题；
问题：数据量大的不适合，数据量大的时候，树的高度不可控，从根节点到叶子节点，需要多次遍历查找，效率偏低。

（三）Hash
1、对索引的key进行一次hash计算就可以定位出数据存储的位置
2、很多时候Hash索引要比B+ 树索引更高效
3、仅能满足 “=”，“IN”，不支持范围查询
4、hash冲突问题

（四）B-Tree
1、叶节点具有相同的深度，叶节点的指针为空；
2、所有索引元素不重复；
3、节点中的数据索引从左到右递增排列；

（五）B+Tree(B-Tree变种)
1、非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
2、叶子节点包含所有索引字段
3、叶子节点用指针连接，提高区间访问的性能

三、InnoDB一棵B+树可以存放多少行数据？

这个问题的简单回答是：约2千万
在MySQL中我们的InnoDB页的大小默认是16k，当然也可以通过参数设置：

SHOW GLOBAL STATUS LIKE "Innodb_page_size"

数据表中的数据都是存储在页中的，所以一个页中能存储多少行数据呢？假设一行数据的大小是1k，那么一个页可以存放16行这样的数据。

如果数据库只按这样的方式存储，那么如何查找数据就成为一个问题
因为我们不知道要查找的数据存在哪个页中，也不可能把所有的页遍历一遍，那样太慢了。
所以人们想了一个办法，用B+树的方式组织这些数据。如图所示：

InnoDB中主键索引B+树是如何组织数据、查询数据的，我们总结一下：
1、InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。

2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据；

那么回到我们开始的问题，通常一棵B+树可以存放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数。

上文我们已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针？

其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。

那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170* 1170 *16=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。

在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

四、为什么MySQL的索引要使用B+树而不是其它树形结构?比如B树？

B树
叶子节点具有相同的深度，叶子节点的指针为空
所有索引元素不重复
节点中的数据索引从左到右递增排列

B+树索引
非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接，提高区间访问的性能

为什么data节点挪到叶子节点，一个节点可以存储更多的索引

16^n=2000万，n就是树的高度，存储同样的数据，B+树的高度远小于B树
因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出）

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

五、存储引擎索引实现

聚集索引的意思：叶子节点存放了索引和数据又叫聚簇索引。
非聚集索引又叫稀疏索引。主键索引就是一种聚簇索引！

（一）MyISAM索引文件和数据文件是分离的(非聚集)
MyISAM索引文件和数据文件是分离的(非聚集)，存储引擎是作用于表的;
索引文件存放索引，数据文件存放数据，索引和数据不放在一起存
查询：先查询B+树上的索引，再用查询到的位置查询数据文件

（一）InnoDB索引实现
表数据索引数据存放于.ibd文件中

1、表数据文件本身就是按B+Tree组织的一个索引结构文件
2、聚集索引-叶节点包含了完整的数据记录
（1）主键索引：

（2）辅助索引（二级索引）
主键索引的叶子节点存储了完整的数据行，而非主键索引的叶子节点存储的则是主键索引值，通过非主键索引查询数据时，会先查找到主键索引，然后再到主键索引上去查找对应的数据，这个过程叫做回表(下文中会再次提到)。

二级索引与聚簇索引有几处不同：

1. 按指定的索引列的值来进行排序
2. 叶子节点存储的不是完整的用户记录，而只是索引列+主键。
3. 目录项记录中不是主键+页号，变成了索引列+页号。
4. 在对二级索引进行查找数据时，需要根据主键值去聚簇索引中再查找一遍完整的用户记录，这个过程叫做回表

（3）联合索引：
以多个列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。

3、为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
(1)主键是InnoDB用来构建B+树的。如果没有主键，会使用唯一的列作为索引，如果还是没有，会建立隐藏列，作为索引列。
(2)如果不用整型的自增主键，用UUID作为主键会怎么样？
UUID是字符串类型，查询操作会有比较操作，整型比较操作快,整型主键比UUID省空间,UUID不是自增的
(3)HASH索引：值做hash运算，运算后的值和存储位置一一映射
为什么不用Hash？
Hash对范围查询支持不好。某一列数据是无序的，B+树在构建的时候可以让数据有序。

4、为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

六、B+树索引总结

1、每个索引都对应一棵B+树。用户记录都存储在B+树的叶子节点，所有目录记录都存储在非叶子节点。
2、InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。
3、可以为指定的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。
4、B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。
通过索引查找记录是从B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了页目录，所以在这些页面中的查找非常快。

七、Mysql索引会失效的几种情况总结

查看博客：Mysql索引会失效的几种情况总结

https://blog.csdn.net/weixin_36586564/article/details/79641748

【相关推荐：mysql视频教程】

以上就是深入解析mysql中的索引（原理详解）的详细内容，转载自php中文网