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树

    • 结构如图所示:image-20210727103400151

    • 从图可以看出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 树一样需要对每一层进行遍历,这有利于数据库做全表扫描。
      
    • 结构如图:
      img
      image-20210727104140208

B+树主键目录(重点,为什么主键查找快)

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

image-20210727104753238

索引页

  • 那假设有1000万条记录、5000万条记录呢?是不是就算是二分法查找,其效率也依旧是很低的,所以为了解决这种问题 MySQL又设计出了一种新的存储结构—索引页

  • 索引页是什么?自己理解就是MySQL在套娃,在数据页外再套一层。例如要查找id为8的这条数据,先通过最小id定位在索引页1里,然后再根据索引页中的主键目录找到数据页2,然后再在具体的数据页找到这条id为8的记录。过程如下图:
    image-20210727105750822

image-20210727105826770

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

image-20210727110235332

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

B+树,也是二叉搜索树的一种,但是他的数据仅仅存储在叶子节点(在这里就是数据页),像这种索引页+数据页组成的组成的B+树就是聚簇索引

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

非主键索引

image-20210812203118515

  • 对于非主键索引,MySQL也会帮忙维护一张B+树。你有多少索引,就会维护多少B+树。(为什么总说不能乱建索引,因为索引也会占用空间,实际上这就是根本原因)
  • 现在对name+age建立索引,那其数据页中是这样的:image-20210727112500413
  • 在插入数据的时候,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+树本来就是排好序的(左<中<右),在我们使用范围查询的时候可以使用到,范围查询不会使索引失效的,但这样的问题可能是会导致别人
可以很容易猜出数据的量级和变化趋势,因为是自增的嘛,还有一个原因是因为页分裂,后续学习补充。

Q.E.D.


一个热爱生活的95后精神小伙