引言

​ 内容为慕课网的《高并发 高性能 高可用 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 在实际的过程有还是做了改良，实践和实际之间总是有某种差别。