工程项目管理软件app嘉兴seo
文章目录
- 主键排序
- 一. 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+树
- B树
数据结构演示链接：数据结构可视化
B树
B+树
-
B树的节点，既有数据，又有Page指针，而B+树，只有叶子节点有数据，其他目录页只有键值和Page指针
-
B+树的叶子节点是相连的，而B树没有
之所以选择B+树，是因为目录页不存储数据，只存储指针，可以存储更多的key，可以使得树更矮，所以IO次数更少
叶子节点相连，也更便于进行范围查找
三. 聚簇索引和非聚簇索引
先介绍一下MyISAM的存储结构
MyISAM同样使用B+树，但不同的是叶节点的数据存放的是数据记录的地址。
如下图所示：CoI1为主键
MyISAM最大的特点，是将索引Page和数据Page分离，也就是叶子节点没有数据，只有对应数据的地址
相较于InnoDB索引，InnoDB是将索引和数据放在一起的
用MyISAM为存储引擎创建表会形成三个文件
.frm后缀表示表结构数据
.MYD后缀表示用户数据
.MYI后缀表示主键索引数据
其中，MyISAM这种用户数据与索引数据分离的索引方案，叫做非聚簇索引
用InnoDB为存储引擎创建表会形成两个文件
.from后缀表示表结构数据
.ibd后缀表示主键索引和用户数据
InnoDB这种用户数据与索引数据放在一起的索引方案，叫做聚簇索引
MySQL除了默认会建立主键索引以外，用户也可能按照需求用其他列信息建立索引，一般这种索引叫做普通（辅助）索引
对于MyISAM建立普通索引和主键索引没有什么差别，无非是主键不能重复，而非主键可以重复
下图是基于MyISAM的Col2建立的索引，和主键索引没有差别
MyISAM建立索引，会建立一个新的B+树，页目录和叶子结点所存储的指针改变，不会建立新的数据表
同样，InnoDB除了主键索引，用户也会创建普通索引，以上表的Col3建立普通索引，如下图
可以看到，InnoDB的非主键索引中叶子节点并没有数据，而只有对应记录的key值，存储的是主键索引的键值
所以通过普通索引，找到目标记录，需要两遍索引：
首先检索普通索引获得主键
然后用主键在主键索引中检索获得数据。
这个过程，叫作回表查询
结束语
感谢你的阅读
如果觉得本篇文章对你有所帮助的话，不妨点个赞支持一下博主，拜托啦，这对我真的很重要。
