MySQL索引原理探索

`MySQL`索引原理探索

索引的本质其实就是各种各样的数据结构，在增删改查的各种操作有不通的时间复杂度和空间复杂度

索引的类型

Hash索引:
- 参考java中的hash结构，因为其结构，查找单条数据的效率特别高，时间复杂度仅为O(1)。但Mysql的Innodb引擎就是不支持hash索引
- Hash索引适合精确查找，但是范围查找不适合。
- 存储引擎都会为每一行计算一个hash码，hash码都是比较小的，并且不同键值行的hash码通常是不一样的，hash索引中存储的就是Hash码，hash 码彼此之间是没有规律的，且 Hash 操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。这就是为什么hash索引只能进行全职匹配的查询，因为只有这样，hash码才能够匹配到数据。
二叉树
- 特点：插入、增加、删除的时间复杂度为O(n);一个节点最多有俩个子节点；左节点小于本节点，右节点大于本节点，即右>中>左。
- 特殊结构-平衡二叉树：增删改查时间复杂度O(log n)。数据量越多，遍历次数越多，IO次数就越多，就越慢（磁盘的IO由树高决定）
B树
- 结构如图所示：
- 从图可以看出B数包含俩部分：key和data部分，当data的数据较多的时候，每个节点可用的key就比较少了，同样也会有二叉树树高从而增加了磁盘 IO 的次数，进而影响查询效率。

B+树

MySQL 中最常用的索引的数据结构是 B+ 树，他有以下特点：

1、在 B+ 树中，所有数据记录节点都是按照键值的大小存放在同一层的叶子节点上，而非
叶子结点只存储key的信息，这样可以大大减少每个节点的存储的key的数量，降低B+ 树的
高度。
2、B+ 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的
指针，双向链表。
3、B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更
少所以查询数据更快。
4、B+ 树查询速度更稳定：B+ 所有关键字数据地址都存在叶子节点上，所以每次查找的次数
都相同所以查询速度要比B树更稳定;
5、B+ 树天然具备排序功能：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区
间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
6、B+ 树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，而不需要
像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

结构如图：

B+树主键目录（重点，为什么主键查找快）

MySQL 在存储数据的时候是以数据页为最小单位的，且数据在数据页中的存储是连续的，数据页中的数据是按照
主键排序的（没有主键是由 MySQL自己维护的 ROW_ID 来排序的），数据页和数据页之间是通过双向链表来关
联的，数据与数据时间是通过单向链表来关联的。
在每个数据页中，他必然就有一个最小的主键，然后每个数据页的页号和最小的主键会组成一个主键目录（就像下
图中的左边部分），假设现在要查找主键为 2 的数据，通过二分查找法最后确定下主键为 2 的记录在数据页 1
中，此时就会定位到数据页 1 接着再去定位主键为 2 的记录

索引页

那假设有1000万条记录、5000万条记录呢？是不是就算是二分法查找，其效率也依旧是很低的，所以为了解决这种问题 MySQL 又设计出了一种新的存储结构—索引页
索引页是什么?自己理解就是MySQL在套娃，在数据页外再套一层。例如要查找id为8的这条数据，先通过最小id定位在索引页1里，然后再根据索引页中的主键目录找到数据页2，然后再在具体的数据页找到这条id为8的记录。过程如下图：

如果索引页太大呢？继续套娃

假设你要查找 37 这条记录，说实话我根本不知道这条记录在哪里。来模拟MySQL的查找过程，首先从最顶层的索引页开始查找，因为 id=37，因此定位到了索引页16，然后到索引页 16 中继续查找，此时同样能够定位到 id=37 在索引页 3 中，然后继续查找，最终能够定位到数据实在数据页 8 中，假设数据页 8 是这样子的

完整流程图：

B+树，也是二叉搜索树的一种，但是他的数据仅仅存储在叶子节点（在这里就是数据页），像这种索引页+数据页组成的组成的B+树就是聚簇索引(此处描述有误，应该这样理解，如果通过某个索引能找到所有列的数据，那么这个索引就是聚簇索引，一般为主键索引。无主键索引的mysql会有默认的，且只有一个聚簇索引。且聚簇索引的顺序就是数据的物理顺序)

聚簇索引的顺序就是数据的物理存储顺序，而对非聚簇索引的解释是:索引顺序与数据物理排列顺序无关。正式因为如此，所以一个表最多只能有一个聚簇索引。

聚簇索引是 MySQL 基于主键索引结构创建的

非主键索引

对于非主键索引，MySQL也会帮忙维护一张B+树。你有多少索引，就会维护多少B+树。（为什么总说不能乱建索引，因为索引也会占用空间，实际上这就是根本原因）
现在对name+age建立索引，那其数据页中是这样的：
在插入数据的时候，MySQL 首先会根据 name 进行排序，如果 name 一样，就根据联合索引中的 age 去排序，如果还一样，那么就会根据主键字段去排序。插入的原理就是这样子的。此时每个数据页中的记录存放的实际是索引字段和主键字段，而其他字段是不存的（为什么不存放？一样的数据到处存放很浪费空间的，也没必要，所以才会有下面的索引优化
SELECT name FROM student WHERE name='wx'
那么此时的查询是完美的，使用到了索引且不需要回表

回表

是这样子的，现在要根据 name 查找到该条记录，且查询的字段（即 select 后面的查询字段）也仅仅有 name（只要是在 name,age,id 这三个字段中都可以）这个时候是能够直接获取到最终的记录的
换句话说，因为联合索引中的记录也仅仅有 name，age，id，所以在查询的如果也仅仅查询这三个字段，那么在该B+树中就能够查询到想要的结果了。
那现在假设查询的 SQL 是这样子的（我们假设 student 中还有除了name，age，id 其他的字段 ）
SELECT * FROM student WHERE name='wx'
那这下子就完蛋了，因为你现在虽然根据 name 很快的定位到了该条记录，但是因为 name+age 不是聚簇索引，此时的 B+ 树的数据页中存放的仅仅是自己关联的索引和主键索引字段，并不会存其他的字段，所以这个时候其他的属性值是获取不到的，这时候该怎么办？
这种情况下，MySQL 就需要进行回表查询了。此时 MySQL 就会根据定位到的某条记录中的 id 再次进行聚簇索引查找，也就是说会根据 id 去维护 id 的那么 B+ 树中查找。因为聚簇索引中数据页记录的是一条记录的完整的记录，这个过程就叫回表。

根据非主键索引查询到的结果并没有查找的字段值，此时就需要再次根据主键从聚簇索引的根节点开始查找，这样再次查找到的记录才是完成的。

对于非主键索引（一般都是联合索引），在维护 B+ 树的时候，会根据联合索引的字段依次去判断，假设联合索引为：name + address + age，那么 MySQL 在维护该索引的 B+ 树的时候，首先会根据 name 进行排序，name 相同的话会根据第二个 address 排序，如果 address 也一样，那么就会根据 age 去排序，如果 age 也一样，那么就会根据主键字段值去排序，且对于非主键索引，MySQL 在维护 B+ 树的时候，仅仅是维护索引字段和主键字段。

后续补充

日常中推荐主键设置成自增长的，因为B+树本来就是排好序的（左<中<右），在我们使用范围查询的时候可以使用到，范围查询不会使索引失效的，但这样的问题可能是会导致别人
可以很容易猜出数据的量级和变化趋势，因为是自增的嘛，还有一个原因是因为页分裂，后续学习补充。

目录CONTENT

MySQL索引原理探索