最近接受了深圳开源中国(也就创作和运营马云中国gitee网络的公司)科技公司面试官的电话面试,面试过程中面试官要求我谈一谈Mysql
的数据结构。笔者当时只记得Mysql
数据库的InnoDB存储引擎底层用到了B+树,对于什么是B+树以及InnoDB数据页结构的了解也不多,所以当时面试回答得很肤浅。很明显结果凉凉了,所以决定写篇文章系统地总结这个问题给自己加深印象,下次面试官再问这一块的问题,保证绝对不再翻车!
我们大部分接触过Mysql
数据库的程序员都知道Mysql
数据库的底层数据结构为B+树,在介绍B+树的时候有必要认识B树,因为B+树是B树的一个变种。
为了便于说明,我们先定义一条数据记录为一个二元组[key,data],key为记录的键值,key唯一;data为数据记录除key外的数据
B树:每个节点都存储key和data,所有节点组成这棵树,并且叶子节点指针为null。
图 1 B树存储结构示意图
B+树:只有叶子节点存储data,叶子节点包含了这棵树的所有键值,叶子节点不存储指针。
图 2 B+树存储结构示意图
后来,在B+树上增加了顺序访问指针,也就是每个叶子节点增加一个指向相邻叶子节点的指针,这样一棵树成了数据库系统实现索引的首选数据结构。原因有很多,最主要的是这棵树矮胖,一般来说,索引很大,往往以索引文件的形式存储的磁盘上,索引查找时产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小,I/O次数越少。那为什么是B+树而不是B树呢,因为它内节点不存储data,这样一个节点就可以存储更多的key。
在MySQL
中,最常用的两个存储引擎是MyISAM
和InnoDB
,它们对索引的实现方式是不同的。
MyISAM
: data 存的是数据地址。索引是索引,数据是数据。索引放在XX.MYI
文件中,数据放在XX.MYD
文件中,所以也叫非聚簇索引
图 3 MyISAM 引擎存储结构示意图
InnoDB
: data存的是数据本身。索引也是数据。数据和索引存在一个XX.IDB文件中,所以也叫聚簇索引。
图 4 InnoDB引擎结构示意图
MyISAM
与InnoDB
两种存储引擎的区别MyISAM
是非事务安全的,而InnoDB
是事务安全的MyISAM
锁的粒度是表级的,而InnoDB
支持行级锁MyISAM
支持全文类型索引,而InnoDB
不支持全文索引MyISAM
相对简单,效率上要优于InnoDB
,小型应用可以考虑使用MyISAM
MyISAM
表保存成文件形式,跨平台使用更加方便MyISAM
管理非事务表,提供高速存储和检索以及全文搜索能力,如果在应用中执行大量select
操作可选择MyISAM
存储引擎InnoDB
用于事务处理,具有ACID事务支持等特性,如果在应用中执行大量insert
和update
操作,可选择InnoDB
存储引擎。在InnoDB
中,数据会存储到磁盘上,在真正处理数据时需要先将数据加载到内存,表中读取某些记录时,InnoDB
存储引擎不需要一条一条的把记录从磁盘上读出来,InnoDB
采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB
中页的大小一般为 16 KB
,也就是说,当需要从磁盘中读数据时每一次最少将从磁盘中读取16KB
的内容到内存中,每一次最少也会把内存中的16KB
内容写到磁盘中。
InnoDB
数据页结构 InnoDB
管理存储空间的基本单位,一个页的大小默认是16KB
。在Mysql
数据库终端可以使用如下sql
语句查询页的大小:SHOW GLOBAL STATUS like 'Innodb_page_size'
页结构:
图 5 InnoDB存储引擎数据页结构
名称 | 中文名 | 占用空间 | 简单描述 |
---|---|---|---|
File Header | 文件头部 | 38字节 | 页的一些通用信息 |
Page Header | 页面头部 | 56字节 | 数据页专有的一些信息 |
Infimum+Supremum | 最小记录和最大记录 | 26字节 | 2个虚拟的行记录 |
User Records | 用户记录 | 不确定 | 实际存储的行记录内容 |
Free Space | 空闲空间 | 不确定 | 页中尚未使用的空间 |
Page Directory | 页面目录 | 不确定 | 页中的某些位置的相对位置 |
File Trailer | 文件尾部 | 8字节 | 校验页是否完整 |
表 1 InnoDB存储引擎数据页结构字段说明
一行记录可以以不同的格式存在InnoDB
中,行格式分别是Compact、Redundant、Dynamic和Compressed行格式
我们可以在创建或修改表的语句中指定行格式:
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
ALTER TABLE 表名 ROW_FORMAT=行格式名称
图 6 行格式示意图
这部分信息是服务器为了描述这条记录而不得不额外添加的一些信息,这些额外信息分为3类,分别是:
变长字段长度列表
Mysql
支持一些变长的数据类型,比如VARCHAR(M)
、VARBINARY(M)
、TEXT
类型,BLOB
类型,这些数据类型修饰列称为变长字段,变长字段中存储多少字节的数据不是固定的,所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。在Compact
行格式中,把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位,从而形成一个变长字段长度列表。
CHAR是一种固定长度的类型,VARCHAR则是一种可变长度的类型。
VARCHAR(M)
,M代表最大能存多少个字符。(MySQL5.0.3
以前是字节,之后就是字符)
Null值列表
Compact
行格式会把可以为NULL
的列统一管理起来,存一个标记为在NULL
值列表中,如果表中没有允许存储 NULL
的列,则 NULL
值列表也不存在了
记录头信息
除了变长字段长度列表、NULL
值列表之外,还有一个用于描述记录的记录头信息,它有5个固定的字节组成。5个字节也就是40个二进制,不同的位代表不同的意思,如图:
表 2 记录头信息字段说明
记录的真实数据
记录的真实数据除了我们定义的列数据之外,还有3个隐藏列
表 3 三个隐藏列说明
实际上这几个列的真正名称其实是:DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR。 一个表没有手动定义主键,则会选取一个Unique键作为主键,如果连Unique键都没有定义的话,则会为表默认添加一个名为row_id的隐藏列作为主键。所以row_id是在没有自定义主键以及Unique键的情况下才会存在的。
VARCHAR(M)
类型的列最多可以占用65535个字节。其中的M代表该类型最多存储的字符数量,如果我们使用ascii
字符集的话,一个字符就代表一个字节,我们看看VARCHAR(65535)
是否可用
首先在Mysql
数据库终端控制台执行如下sql
脚本:
CREATE TABLE varchar_size_demo(
c VARCHAR(65535)
) CHARSET=ascii ROW_FORMAT=Compact;
执行后会发现控制台报以下错误:
Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns to TEXT or BLOBs
报错信息表达的意思是:MySQL
对一条记录占用的最大存储空间是有限制的,除BLOB或者TEXT类型的列之外,其他所有的列(不包括隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字节。这个65535个字节除了列本身的数据之外,还包括一些其他的数据,比如说我们为了存储一个VARCHAR(M)
类型的列,其实需要占用3部分存储空间:
如果该VARCHAR
类型的列没有NOT NULL
属性,那最多只能存储65532个字节的数据,因为变长字段的长度占用2个字节,NULL
值标识需要占用1个字节。
没有NOT NULL
属性:
CREATE TABLE varchar_size_demo(
c VARCHAR(65532)
) CHARSET=ascii ROW_FORMAT=Compact;
执行结果:
Query OK, 0 rows affected (0.02 sec)
有Not Null
属性:
CREATE TABLE varchar_size_demo(
c VARCHAR(65533) not null
) CHARSET=ascii ROW_FORMAT=Compact;
执行结果:
Query OK, 0 rows affected (0.02 sec)
说明VARCHAR
类型的列有NOT NULL
属性时最多可存储65533个字节的数据
记录中的数据太多产生的溢出
一个页的大小一般是16KB
,也就是16384字节,而一个VARCHAR(M)
类型的列就最多可以存储65533个字节,这样就可能出现一个页存放不了一条记录。
在Compact
和Reduntant
行格式中,对于占用存储空间非常大的列,在记录的真实数据处只会存储该列的一部分数据,把剩余的数据分散存储在几个其他的页中,然后记录的真实数据处用20个字节存储指向这些页的地址(当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数),从而可以找到剩余数据所在的页。
这两种行格式类似于COMPACT
行格式,只不过在处理行溢出数据时有点儿分歧,它们不会在记录的真实数据处存储一部分数据,而是把所有的数据都存储到其他页面中,只在记录的真实数据处存储其他页面的地址。另外,Compressed
行格式会采用压缩算法对页面进行压缩
MySQL
索引的建立对于MySQL
的高效运行是很重要的,索引可以大大提高MySQL
的检索速度。
打个比方,如果合理的设计且使用索引的MySQL
是一辆兰博基尼的话,那么没有设计和使用索引的MySQL
就是一个人力三轮车。拿汉语字典的目录页(索引)打比方,我们可以按拼音、笔画、偏旁部首等排序的目录(索引)快速查找到需要的字。
索引分单列索引和组合索引。单列索引,即一个索引只包含单个列,一个表可以有多个单列索引,但这不是组合索引。组合索引,即一个索引包含多个列。
创建索引时,你需要确保该索引是应用在 SQL
查询语句的条件(一般作为 WHERE
子句的条件)。
实际上,索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录。
上面都在说使用索引的好处,但过多的使用索引将会造成滥用。因此索引也会有它的缺点:虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE和DELETE
。因为更新表时,MySQL
不仅要保存数据,还要保存一下索引文件。同时,建立索引时的索引文件会占用磁盘空间。
聚簇索引的特点:
1) 按主键值的大小进行记录和页的排序
2)B+树的叶子节点存储的是完整的用户记录,就是指这个记录中存储了所有列的值(包括隐藏列)
具有这两种特性的B+树称为聚簇索引,所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL
语句中显式的使用INDEX
语句去创建
InnoDB
存储引擎会自动的为我们创建聚簇索引。在InnoDB
存储引擎中,聚簇索引就是数据的存储方式(所有的用户记录都存储在了叶子节点),也就是所谓的索引即数据,数据即索引
聚簇索引只能在搜索条件是主键值时才能发挥作用,因为B+树中的数据都是按照主键进行排序的。当我们想以别的列作为搜索条件时我们可以多建几棵B+树,不同的B+树中的数据采用不同的排序规则
二级索引与聚簇索引有几处不同:
1)按指定的索引列的值来进行排序
2)叶子节点存储的不是完整的用户记录,而只是索引列+主键
3)目录项记录中不是主键+页号,变成了索引列+页号
在对二级索引进行查找数据时,需要根据主键值去聚簇索引中再查找一遍完整的用户记录,这个过程叫做回表
以多个列的大小为排序规则建立的B+树称为联合索引,本质上也是一个二级索引
目录项记录的唯一性
我们需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的:
InnoDB
存储引擎会自动为主键(如果没有它会自动帮我们添加)建立聚簇索引,聚簇索引的叶子节点包含完整的用户记录。红包福利
今天是2020农历庚子年的除夕,明天就是2021农历辛丑年新年第一天,在这里祝我的粉丝读者们:新春快乐,阖家团圆!2021年财运亨通,牛转乾坤,心想事成,欢欢喜喜过大年!
作为本公众号的运营者,可以向自己的读者粉丝们坦言:由于本人原创内容不够吸引众多的粉丝满足可以接广告的要求 ,因此本公众号尚未实现盈利。与同行业的很多大佬坐拥上万粉丝量每个月的广告收入可达到好几万不可同日而语。但是为了感谢粉丝们对笔者的厚爱,也希望我的粉丝们能把我的公众号推广给身边更多的朋友关注,我会发一个总额100元的支付宝红包,数量50个。希望2021年待自己的公众号实现盈利后明年的除夕夜我也能发一个上千元的红包来回馈我的粉丝读者。请粉丝读者们今晚18:00后在支付宝口令红包里输入口令:“程序员阿福春节福利”领取红包,手快有,手慢无。
6 参考文章
[1]数据结构---B树与B+树的区别以及在MySQL数据库中的应用(https://blog.csdn.net/zhuyanlin09/article/details/94642626)
[2] InnoDB行格式、数据页结构以及索引底层原理分析(https://www.yuque.com/books/share/9f4576fb-9aa9-4965-abf3-b3a36433faa6/og063h)
7 推荐阅读
[1] Linux系统云服务器上安装Mysql5.7数据库,解决不能远程访问的bug
原创不易,阅后请随手点个赞和再看。新读者欢迎加个关注,谢谢!