【MySQL】深入了解索引的底层逻辑结构

文章目录

主键排序
一. InnoDB的索引结构
- 1. 单个page
- 2. 多个page
二. 为什么选择B+树
三. 聚簇索引和非聚簇索引
结束语

主键排序

我们创建一个user表，并乱序插入数据

mysql> create table if not exists user(-> id int primary key,-> age int not null,-> name varchar(16) not null-> );mysql> insert into user (id,age,name )values(3,18,'杨过'),(4,16,'小龙女'),(2,26,'黄蓉'),(5,36,'郭靖'),(1,56,'欧阳锋');
Query OK, 5 rows affected (0.00 sec)
Records: 5  Duplicates: 0  Warnings: 0mysql> select * from user;
+----+-----+-----------+
| id | age | name      |
+----+-----+-----------+
|  1 |  56 | 欧阳锋    |
|  2 |  26 | 黄蓉      |
|  3 |  18 | 杨过      |
|  4 |  16 | 小龙女    |
|  5 |  36 | 郭靖      |
+----+-----+-----------+
5 rows in set (0.00 sec)

我们发现，虽然是乱序插入，但是显示出来却是排好序的。这是MySQL做的吗？让我们带着这个疑问开始本章的学习

一. InnoDB的索引结构

MySQL的基本单位是Page，Page存储着数据，而一个数据表文件因其数据量多少由一个或多个Page构成

1. 单个page

在这里插入图片描述
不同的Page，在MySQL中，都是16KB大小，使用page_prev和page_next互相链接，构成双向链表

上面构建的user表，因为有主键，所以MySQL会默认按照主键对数据进行排序，让Page内的数据是有序且彼此关联的

排序同时也可以提高查询速度
Page内部存放数据，实质是使用了链表，链表是增删快，查询慢，所以需要优化查询效率。
而有序，可以保证每次查询都是有效查询，当前值一定比前面的值大，比后面的值小。

2. 多个page

Page的作用是在查询数据时，直接将一整页的数据加载到内存中，以减少IO次数，从而提高性能。但Page内部采用了链表的结构，还是需要线性遍历的，效率太低

MySQL使用页目录进一步提高查询效率

页目录

我们在看一本书时，前几页是整本书的目录，如果我们想查看其中的某一章节，那么就可以根据目录中那一章节的页数，跳跃查找
但存储目录同样需要纸张，所以目录是一种以空间换时间的做法

单页情况

我们在单页Page中加入目录

在这里插入图片描述

通过引入目录，如果我们要查询id=4的数据，之前需要线性遍历4次，但现在可以先通过目录2[3]，直接进行定位新的起始位置，提高了效率。

所以，为什么MySQL要自动排序呢？
因为方便引入目录

多页情况

Page的大小为16KB，当数据量不断增大时，势必需要多个Page存储数据
在单表数据不断被插入的情况下，MySQL会在容量不足时，自动开辟新的Page来保存新的数据，使用指针的方式，将所有的Page组织起来

在这里插入图片描述

而当Page越来越多时，Page之间也是使用指针连接，整体是双向链表结构，Page之间仍是线性查询。
如何解决呢？其实是一样的，给这些Page也带上目录就好了

使用一个目录来指向某一页，而这个目录项存放的是指向的Page中存放的最小的数据的键值
和Page内目录不同的地方在于，这种目录管理的级别是Page，页内目录管理级别是行
其中，每个目录项的构成是：键值+指针（下图没画指针的地址）

在这里插入图片描述
存在一个目录页来管理页目录，目录页中的数据存放的就是指向的那个Page中最小的数据。有数据，就可以通过比较，找到该访问那个Page，进而通过指针，找到下一个Page

目录页的本质也是页，普通页中存放的是用户数据，目录页存放的是普通页的地址

即使数据量变大，页目录变大，我们依然可以再在上方添加管理页目录的页目录来加快检索效率
在这里插入图片描述

这种结构其实就是B+树
此时，随便查找一个id值，查找的Page数减少，意味着IO次数也减少了，那么效率也就提高了

总结一下

Page分为目录页和数据页，目录页只放各个下级Page的最小键值
查找的时候，自顶向下查找，只需要加载部分目录页到内存中，即可以完成算法的整个查找过程，大大减少了IO次数

二. 为什么选择B+树

链表or线性表
链表和线性表肯定是不行的，线性查找的效率太低了
二叉搜索树
二叉搜索树，如果插入的值一直比起始都大或者小，就会出现退化的问题，变成线性结构
AVL树&&红黑树
虽然AVL树是平衡树，红黑树是接近平衡，但是毕竟是二叉结构，相比较多阶B+，意味着树整体过高。都是自顶向下查找，层高越低，意味着查找次数越少，系统与硬盘的IO次数更少
Hash
官方的索引实现中，MySQL是支持Hash的，不过InnoDB和MyISAM并不支持Hase跟进其算法特征，决定了虽然有时候也很快O(1)，不过，在面对范围查找就明显不行，另外还有其他差别，有兴趣可以查一下

在这里插入图片描述
图中的BTREE是B+树