引言

内容为慕课网的《高并发 高性能 高可用 MySQL 实战》视频的学习笔记内容和集体整顿扩大之后的笔记，这一节的内容是对于InnoDb的存储构造进阶理解，同时介绍为什么会应用B+索引作为最终数据结构，然而实际上InnoDb在具体实现中也并没有齐全遵循B+的格局，而是在外部做了很多“手脚”，这也是所谓实践和实际之间的差别。

如果内容比拟难，能够追随《Mysql是怎么样运行》集体读书笔记专栏补补课，集体也在学习和同步更新中。

地址如下：https://juejin.cn/column/7024...。

索引组织表

InnoDb 的所有表都是索引组织表，索引组织表有如下的定义：

不是一种“组织表”，而是由“索引”组织的表，索引即数据数据即索引，InnoDb中表默认都会主键程序寄存，同时依照肯定的规定排序，默认的索引组织模式被称为聚簇索引。

什么是索引？

索引能够简略了解为目录，相似于咱们书中的目录页，帮咱们疾速定位具体的内容，对于数据库某一列或者多列进行预排序的数据结构，留神这是一种数据结构目标是为了放慢数组的搜寻速度。

然而索引也有问题，那就是目录自身也须要占用存储空间并且随着数据的收缩而收缩，同时如果索引应用的不失当也会呈现问题，比方如果咱们的目录索引的内容全都是截然不同的会呈现“索引生效”问题，此时索引成果大打折扣，不如间接搜寻数据。

主键定义和主键索引

在Mysql的Inndb存储引擎中，应用的主键索引也被称为聚簇索引：

InnoDb 的存储引擎表中每张表必须有一个主键，表中有一个非空惟一索引即为主键。如果存在多个非空惟一索引并且没有定义主键，抉择第一个定义的索引，若所有条件不满足则InnoDb在数据行中主动创立一个6个字节的指针暗藏列作为主键，并且这个主键外部是自增的使得记录能够依照程序进行存储。

上面用视频中的案例举例探讨的上面这个表主键是什么？

从下面的截图能够看到，字段a没有定义惟一索引，尽管它是非空的然而并不是惟一的所以不是主键，b尽管是最先定义的，然而他不是非空所以也不能作为索引，而d和 c尽管都是惟一索引并且都是非空列，依据多个非空索引取第一个定义索引为主键的规定，最终主键为字段d。

B+树索引

B+树的索引构造是InnoDb的根底构造，上面是传统的B+树的构造：

• Btree 应用B+树作为索引的数据结构。
• B+树的高度为2-4层，查找数据非常快。
• B+树索引将非叶子节点所谓索引节点，叶子节点为数据节点，数据节点之间用链表串联实现优化范畴查问。

Inndo的B+树和传统B+树的区别如下：

1. InnoDb底层参考的是b+ 树，然而其实不完全相同，节点被称之为数据页和索引页，然而实际上索引页数据页除了数据类型不同基本一致，也就是索引即数据，数据即索引，索引它分为聚簇索引和辅助索引，聚簇索引最大特点是寄存键是主键ID，而主键ID依据肯定的规定生成或者在建表的时候指定，然而肯定会有一个主键索引，也就说一个表肯定存在主键。而辅助索引应用的是主键为索引字段的值，数值寄存的是索引主键。
2. 同层的数据页之间应用的是双向链表，索引页也是应用双向链表，这和B+树的数据结构是不一样的，传统B+ 树只在最底层的叶子节点为链表的设计。

聚簇索引

聚簇索引指的是依据表的主键构建一个B+ 树。叶子节点间接寄存行数据而不是放指针，然而实际上叶子节点自身也是数据页只不过寄存的是指针而已。

上面的案例图仅仅为最毛糙的角度观察mysql的数据页设计，理论内容要远比这张图简单很多：

聚簇索引的特点

• 非叶子节点存储的是索引，叶子节点则为数据，从左到右排序，在页决裂的时候，会把主键较大的值挪动到对应的数据页。
• 索引页之间应用链表进行连贯，而叶子节点理论的数据存储区域，对立应用链条表进行串联。所以能够发现除开最顶层，所有的层级页和页之间是由链表之间链接的。
• 每一个数据页蕴含infimum数据行代表以后数据页的第一个节点也就是最小值，supermum代表最初一个节点也就是最大值，这两个“行记录”是Mysql设计者的一个小把戏，目标是不便数据的查找和不同数据页之间的串联，也就是说每一个数据页默认至多有两个“虚构”数据行。
• 所有的数据页号会组成一个页目录，依照最大数据的数据页号进行排序，页目录外面从小到大寄存了主键的id值，通过值找到对应的数据页内容，用于疾速定位数据所在的数据页。
• Innodb 默认为主键索引也就是聚簇索引。

为什么要应用从大到小的程序进行排序？

其实次要是为了应用二分查找办法疾速定位和查找数据页，进步查找的效率。留神因为晚期Mysql版本中的索引设计只能依照升序的形式进行排列，导致聚簇索引少数为升序的索引，在8.0的版本中失去优化。

辅助索引

辅助索引的存在模式：

1. 和主键索引的设计一样，然而key寄存的是索引字段的值，值是主键值。
2. 辅助索引依据建设的索引除联结索引的状况外均为有几个索引建设几颗B+ 树。
3. 辅助索引相当于一颗新的B+ 树。

主键索引：

1. 主键索引也叫聚簇索引，因为底层应用了B+ 树的设计构造，所以Mysql必然有主键并且以主键作为索引的模式。
2. 主键索引指的是键为主键，值为数据一种 索引模式。
3. 一旦创立表则零碎默认会存在一颗以主键索引的B+ 树。

回表是什么？

当辅助索引进行查问的时候因为查问的后果为主键的值，所以须要依据主键的值再去聚簇索引依据二分法查找一遍，这时候等于须要再查一遍聚簇索引，实质上是查了两次B+ 树，所以叫回表。

上面的示意图是一次回表操作：

假如咱们须要搜寻值为5的数据，首先会在二级索引通过二分遍历“槽”的模式找到具体所在的数据行，这个数据行保留索引值之外还存储了主键的值，所以这里须要拿到主键的值回到聚簇索引中找到理论存储的行记录。

然而如果查找条件和查找列都为索引值实际上会应用“笼罩索引”的查找形式，不须要回表操作。

索引算法

对于刚刚接触B+树的同学看到这些数据结构可能会懵圈，同时也不分明为什么要设计这么个简单的玩意，所以在课程中引入了各种数据结构来介绍为什么最终抉择了B+树的构造，上面咱们来简略比照各种常见的数据结构来理解为什么最初抉择了B+ 树这种数据结构。

对于一些常见的算法能够浏览上面的网站理解：Data Structure Visualization (usfca.edu)。

哈希表

https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

哈希表的数据结构非常简略，只蕴含简略的键值对，用哈希函数给索引列计算一个哈希值存储，哈希表最典型的索引利用类型是哈希索引，通过对于索引列的总列计算一个哈希函数进行存储。

哈希表毛病：

哈希表最大的问题在于key抵触，因为如果存在key抵触，那么此时索引会进化为程序的全表遍历，或者说拉出一个链表存储抵触哈希key进行遍历，并且哈希索引最为实用的等值查问理论在应用过程中并不是非常频繁，更多的时候会应用范畴或者含糊搜寻，这时候哈希表的数据结构是很难发挥作用的。

• 哈希表不适用于范畴查找和含糊搜寻。
• 哈希抵触会进化为程序遍历查问。

线性构造

线性构造指的是经典数组，包含链表，数组和堆栈构造，比方数组的查问效率是O(n)，并且查找的性能是O(1)，看起来是对于设计数据库比拟适合。

特点：

1. 工夫复杂度O(n)。
2. 须要从第一个开始做一次遍历线性查找，查找的效率是O(1)。
3. 数组的特点是查找快，更新慢，而链表的特点是更新快，查找稍慢。

不适宜作为数据库的毛病：

对于任意的线性构造来说的查找，更新，删除的速度仿佛很不错，然而程序数组的插入速度不能承受，尤其是在数组两头插入的时候，须要拷贝数组向后挪地位，而链条的查找速度不能承受并且不利于磁盘存储，如果数据量很大的状况下开销宏大，显然都是不适宜的。

二分查找：二分查找对于线性数组构造来说是十分罕用的形式，有序数组在等值查问和范畴查问场景中的性能就都十分优良。

二分查找演示图：https://www.cs.usfca.edu/~galles/visualization/Search.html

1. 工夫复杂度（O(logn)），每一次查找都是上一次的一半。
2. 应用数组的中点作为比拟对象。
3. 依据中点数据大小，抉择一半数据作为新数列查找。
4. 每次能够查找的数据量为一半。

有余点：二分查找尽管在查问上晋升一个量级，然而仍然没有防止插入的问题。

二叉树

既然线性构造有限度，那么逻辑构造是否可行？所以咱们能够思考如果用二叉树如何解决。

1. 工夫复杂度是O(logN)。
2. 搜寻效率的速度取决于树的高度。
3. 遍历形式，分为前序遍历，中序遍历，后序遍历。
4. 如果所有的节点往一侧增加，可能进化为线性查找。

不适宜作为数据库的毛病：

插入和删除须要消耗肯定的性能，并且为了节点的稳固，须要应用左旋或者右旋的操作，维持二叉树的均衡，所以后续拓展出均衡二叉树和红黑树。

均衡二叉树和红黑树

均衡二叉树针对二叉树引入左旋和右旋的操作维持均衡，均衡二叉树的定义是：左右两个子树的高度差不能超过 1，左右两边绝对均衡，因而称之为均衡二叉树。而红黑树s

1. AVL 树，通过左旋和右旋的操作将节点进行上浮或者下沉。
2. AVL树保障不会进化为线性查找。

不适宜作为数据库的毛病：

1. 尽管能够保障查问的性能不会进化，然而对于树的左旋和右旋的操作非常消耗性能，在存储数据的时候会呈现长时间期待的状况，同时还是会发现这样存储的效率是非常低的，同时磁盘的利用率非常低。

2. 另外从数据结构图发现还有一个非常显著的毛病，那就是一个节点只能有两个子节点，如果插入大量节点会导致树的高度一直收缩，即便能够均衡操作，对于插入的操作而言还是非常消耗性能的。

B 树

数据结构演示图：https://www.cs.usfca.edu/~galles/visualization/BTree.html

既然二叉树只有两个节点，那么咱们调整结构，让每一层的节点内容增多，并让树管制在2-4层。同时能够蕴含多个子节点，这样即可极大进步存储效率，同时这种紧凑的构造也不便磁盘的程序扫描。

1. 线性数据结构和树结构的联合。
2. 通过多数据节点大大降低树的高度。
3. 不须要旋转就能够保障树的均衡

毛病：

然而很惋惜B树有一个非常致命的缺点，那就是不适宜作为范畴查找，如果咱们想逾越多个范畴进行查问，那么须要从根节点遍历一整颗树屡次，咱们晓得范畴查问的常见是十分常见的，这样的性能开销对于数据库来说显然不理论。

B+树

数据结构演示图：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B+树是对于B 树的一种优化和变种，其实能够发现就是在线性构造和逻辑构造的兼容，最终在B树的根底上，所有的数据存在叶子节点，而索引节点放在非叶子节点，最终这样的接口。

特点：

1. B+树是B树倒退过去的一种数据结构
2. B+树所有数据都在叶子节点。
3. B+树所有数据最终造成了一个线性表。

InnoDb 的存储引擎构造

最初咱们再回到InnoDb存储引擎理解InnoDb 的存储引擎根本构造。

如果想要具体的理解这部分的构造，倡议浏览《Mysql是怎么样运行》这本书外面对于整个Mysql内部结构做了十分具体的介绍，对于了解InnoDb的存储构造非常有帮忙。

上面为InnoDb存储引擎的数据存储繁难结构图，更加具体的构造在视频中并没有开展，另外如果开展讲述的话一篇文章也是远远不够的，所以这里只能是大抵理解：

表空间：数据表在磁盘上的存储空间，默认状况下所有表的数据存在共享表空间，当然为了权限的应用每一个表的数据也能够放在独占的表空间，

段：段分为叶子节点段和非叶子节点段，叶子节点段叫做B+树段节点，而非叶子节点就是索引页了。

区：区通常由64个页组成，每一个段外面对应很多区，一个区段大小是1M，个别由间断段数据页组成，然而个别一次申请为申请3-4个。（须要思考内存的承受能力）

数据页：页是InnoDb的最小数据单位，默认为16kb，一个数据页是B+树的节点，最要害的是数据页的设计思考到了SSD和机械硬盘的设计，一个机械硬盘最小的读写单位是512KB，一个SSD最小的读写单位是4b，所以16KB是他们的倍数，能够节俭空间。

数据行：数据行分为2种类型，包含inf和sup两个数据行，不论一个表是否有数据行，至多会有这两个数据行，同时每一行默认会暗藏三个字段，Trx Id多用于事务的管制。

为什么数据页不能太大，也不能太小？

答复：如果数据页太大，那么每次读取数据页如果只是查找几行数据，那么会节约大量的计算机资源，因为IO的对于数据库系统是须要尽量避免的，如果数据页太小因为磁盘最小的读取单元存在限度，也可能会因为屡次读取导致性能极速降落，而数据页太大如果须要的数据仅仅几条又非常节约IO的性能。

所以mysql在设计数据页大小的时候思考的固态磁盘和机械磁盘的读取单位的折中。

数据行

为了避免读者误会上面的所有的介绍都是针对InnoDb的存储引擎以及mysql5.7的版本中进行介绍。

数据行格局

提醒：这里先提前打一下预防针，其实技术的改良都是细节的改良，理解完之后会发现其实也就那么一回事，然而关键在于魔鬼藏在细节中，所以须要小心辨别看待。

数据行的内容比拟非凡，因为历史的起因他进行了演变，也为了不便了解，咱们须要记住mysql的数据行有两种格局，他们别离由Antelope 和 Barracuda 两种格局，为了不便了解咱们称这两个人为AB吧，在mysql的数据行格局一共有四种类型，然而因为其中REDUNDANT和COMPACT两种格局是新版本中早就不再应用较老的格局，然而在面试中可能被问到所以有必要进行了解：

Antelope：蕴含REDUNDANT和COMPACT.

Barracuda：蕴含DYNAMIC（5.0之后以及8.0默认的建表行格局）和COMPRESSED（压缩格局）

如果须要理解以后mysql版本的默认行格局，能够应用SHOW VARIABLES LIKE "InnoDb_default_row_format"的命令进行查看。

上面咱们依照从旧到新到程序来看一下行格局演变。

A大叔的格局：

REDUNDANT：REDUNDANT格局英文名称翻译过去叫做“冗余”格局，他是mysql5.0之前的默认行格局，须要留神到是上面的示例图分隔符理论是不存在的，在理论存储到过程中都是依照特定编码进行紧凑存储的。

这样就会带来一个问题，比方咱们要找到col1或者找到coln要怎么查？所以最前端的字段偏移列表的作用就是来帮忙mysql疾速定位到具体要查找到列的，然而咱们又须要留神字段偏移列表应用了逆序存储的形式进行解决，咱们间接通过一个例子进行解释字段偏移列表的作用：

再次强调字段偏移列表不是固定记录变长列长度的，而是寄存的是相邻两个列之间的偏移长度，假如以后有三列varchar数据，顺序存储长度别离为1，2，3，依照字段偏移列表的规定为1，3（3-1=2），6（6-3=3），这几个值字段偏移列表逆序存储同时，实在数据依照16进制示意，所以最终的后果为：06 03 01（留神两头空格为了方面浏览退出，理论是紧凑的排列060301）

header局部比拟好了解，比方示意字段偏移列表的单位以及记录列的数量，以及一个非常重要的元素：下一个数据行的地址信息等。

rowId在之前的笔记中提到过，如果在建表的时候没有指定主键，那么mysql就会应用这个rowId作为暗藏的主键，TxID用于事务管制，而后是roll pointer用于undo log回滚实现MVCC的机制，最初便是col1，col2，col3的列是实在的数据。

如果还是好奇为什么字段偏移列表要逆序存储，其实仔细观察下面的行格局构造能够看出端倪，以roll point为界线，右边是头信息和字段偏移列表，左边是实在数据。官网说法是把记录分为记录头信息和实在数据两局部，而应用逆序存储的形式能够让长度和实在数据列“对称”，指针向左移，一个指针向右挪动，效率高一些。

B大叔的格局：

COMPACT格局：这个格局比REDUNDANT粗劣很多，能够看到下面的字段偏移列表不是很直观，每次都须要进行一次减法能力算入列的实在长度，所以Compact应用了变长字段列表改良，变长字段列表间接存储列的长度并且以逆序的形式存储，并且在此基础上退出了NULL值列表来保护每一列是否为NULL，应用位表的形式标记每一列是否为NULL，0为NULL，1为非NULL，并且同样是逆序存储。

记录头的信息差别并不是特地大，所以这里间接疏忽了，重点关注“变长字段列表”和“NULL值列表”的改变，技术的提高总是渺小然而非常无效的。

COMPRESSED的长处是对于过大的页会进行压缩存储，然而压缩存储的问题是读取的时候须要解包读取，会更多消耗肯定的性能。

最初咱们能够从上面的图看到根本的行格局的具体个性，这个表来自于mysql5.7的官网文档，地址为：https://dev.mysql.com/doc/refman/5.7/en/InnoDb-row-format.html：

可变列和不可变列

咱们都晓得Mysql反对的数据类型是很多的比方varchar，char，int，blob，text等等。这里咱们重点关注变长列的和不变长列的数据类型，变长列指的是指定长度和理论长度不统一的列比方varchar，其中的var单词就是代表variableke（可变），所以称之为可变列，不变长列也就是字符长度固定的列char，咱们发现无论是学校学习还是各种网上百科，通常介绍会认为char是固定长度的，varchar是不固定长度的。

真的是这样吗？然而随着时代的倒退char其实也产生了变动这里，能够看mysql5.7的文档解释：

参考：https://dev.mysql.com/doc/refman/5.7/en/char.html

InnoDb将长度大于或等于 768 字节的固定长度字段编码为可变长度字段在页外存储。例如 CHAR(255)如果字符集的最大字节长度大于 3，则列可能超过 768 个字节，就像utf8mb4。

原文：InnoDb encodes fixed-length fields greater than or equal to 768 bytes in length as variable-length fields, which can be stored off-page. For example, a CHAR(255) column can exceed 768 bytes if the maximum byte length of the character set is greater than 3, as it is with utf8mb4.

一个varchar最大长度是多少

在mysql4.1之前，varchar的最大值为255，这大略也是很多数据库管理工具默认给varchar(255)的一个起因。

在5.0以上的 版本中varchar最多能够占用65535个字节，为什么是65535？是因为InnoDb最多给一个字段调配2个字节，也就是说一个varchar最多只有16位，2的16次方-1= 65535（受到二进制补位的影响）。

留神这里说的是字节而不是字符，因为字符串实际上是通过字节进行非凡编码翻译而来，所以对于一些变长编码的存储长度是实时变动的，比方utf8mb4的编码最多占4个字节，套入下面的数据65535/4约等于16383个字符。

所以针对utf8mb4编码的varchar列最大长度为16383？真的是这样么？实际上这个值也是一个参考，尽管实践上的确应该存储这么多数据，然而实际上是必定长度达不到16383的，至于理由其实能够理论建设一个表尝试，会发现创立失败或者批改字段失败。

这和mysql的底层数据结构有关系，因为变长字段须要记录长度，同时mysql为了记录信息须要用一些额定的记录空间进行存储。

备注：length函数不是记录字符的个数，而是理论占用的长度，因为中文须要3个字符长度存储，所以理论存储的长度为63000/3=21000

提醒：如果批改报错内容如下
1118 - 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的B+树结构和其余可能的数据库数据结构设计，能够发现B+树是多种数据结构兼容和均衡，而Mysql在实际的过程有还是做了改良，实践和实际之间总是有某种差别。