三高 Mysql - Inndb 存储引擎和索引介绍
引言
内容为慕课网的《高并发 高性能 高可用 MySQL 实战》视频的学习笔记内容和个人整理扩展之后的笔记，这一节的内容是对于 InnoDb 的存储结构进阶了解，同时介绍为什么会使用 B+索引作为最终数据结构，但是实际上 InnoDb 在具体实现中也并没有完全遵循 B+的格式，而是在内部做了很多“手脚”，这也是所谓理论和实践之间的差异。
如果内容比较难，可以跟随《Mysql 是怎么样运行》个人读书笔记专栏补补课，个人也在学习和同步更新中。
地址如下：https://juejin.cn/column/7024363476663730207。
索引组织表
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+树的区别如下：
InnoDb 底层参考的是 b+ 树，但是其实不完全相同，节点被称之为数据页和索引页，但是实际上索引页数据页除了数据类型不同基本一致，也就是索引即数据，数据即索引，索引它分为聚簇索引和辅助索引，聚簇索引最大特点是存放键是主键 ID，而主键 ID 根据一定的规则生成或者在建表的时候指定，但是一定会有一个主键索引，也就说一个表一定存在主键。而辅助索引使用的是主键为索引字段的值，数值存放的是索引主键。
同层的数据页之间使用的是双向链表，索引页也是使用双向链表，这和 B+树的数据结构是不一样的，传统 B+ 树只在最底层的叶子节点为链表的设计。
聚簇索引
聚簇索引指的是根据表的主键构建一个 B+ 树。叶子节点直接存放行数据而不是放指针，但是实际上叶子节点本身也是数据页只不过存放的是指针而已。
下面的案例图仅仅为最粗糙的角度观察 mysql 的数据页设计，实际内容要远比这张图复杂很多：
聚簇索引的特点
非叶子节点存储的是索引，叶子节点则为数据，从左到右排序，在页分裂的时候，会把主键较大的值移动到对应的数据页。
索引页之间使用链表进行连接，而叶子节点实际的数据存储区域，统一使用链条表进行串联。所以可以发现除开最顶层，所有的层级页和页之间是由链表之间链接的。
每一个数据页包含 infimum 数据行代表当前数据页的第一个节点也就是最小值，supermum 代表最后一个节点也就是最大值，这两个“行记录”是 Mysql 设计者的一个小把戏，目的是方便数据的查找和不同数据页之间的串联，也就是说每一个数据页默认至少有两个“虚拟”数据行。
所有的数据页号会组成一个页目录，按照最大数据的数据页号进行排序，页目录里面从小到大存放了主键的 id 值，通过值找到对应的数据页内容，用于快速定位数据所在的数据页。
Innodb 默认为主键索引也就是聚簇索引。
为什么要使用从大到小的顺序进行排序？
其实主要是为了使用二分查找方法快速定位和查找数据页，提高查找的效率。注意由于早期 Mysql 版本中的索引设计只能按照升序的方式进行排列，导致聚簇索引多数为升序的索引，在 8.0 的版本中得到优化。
辅助索引
辅助索引的存在形式：
和主键索引的设计一样，但是 key 存放的是索引字段的值，值是主键值。
辅助索引根据建立的索引除联合索引的情况外均为有几个索引建立几颗 B+ 树。
辅助索引相当于一颗新的 B+ 树。
主键索引：
主键索引也叫聚簇索引，由于底层使用了 B+ 树的设计结构，所以 Mysql 必定有主键并且以主键作为索引的形式。
主键索引指的是键为主键，值为数据一种 索引形式。
一旦创建表则系统默认会存在一颗以主键索引的 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)，看起来是对于设计数据库比较合适。
特点：
时间复杂度
O(n)。需要从第一个开始做一次遍历线性查找，查找的效率是
O(1)。数组的特点是查找快，更新慢，而链表的特点是更新快，查找稍慢。
不适合作为数据库的缺点：
对于任意的线性结构来说的查找，更新，删除的速度似乎很不错，但是顺序数组的插入速度不能接受，尤其是在数组中间插入的时候，需要拷贝数组向后挪位置，而链条的查找速度不能接受并且不利于磁盘存储，如果数据量很大的情况下开销庞大，显然都是不适合的。
二分查找：二分查找对于线性数组结构来说是非常常用的方式，有序数组在等值查询和范围查询场景中的性能就都非常优秀。
二分查找演示图：https://www.cs.usfca.edu/~galles/visualization/Search.html
时间复杂度（O(logn)），每一次查找都是上一次的一半。
使用数组的中点作为比较对象。
根据中点数据大小，选择一半数据作为新数列查找。
每次可以查找的数据量为一半。
不足点：二分查找虽然在查询上提升一个量级，但是依然没有避免插入的问题。
二叉树
既然线性结构有限制，那么逻辑结构是否可行？所以我们可以思考如果用二叉树如何处理。
时间复杂度是 O(logN)。
搜索效率的速度取决于树的高度。
遍历方式，分为前序遍历，中序遍历，后序遍历。
如果所有的节点往一侧添加，可能退化为线性查找。
不适合作为数据库的缺点：
插入和删除需要耗费一定的性能，并且为了节点的稳定，需要使用左旋或者右旋的操作，维持二叉树的平衡，所以后续拓展出平衡二叉树和红黑树。
平衡二叉树和红黑树
平衡二叉树针对二叉树引入左旋和右旋的操作维持平衡，平衡二叉树的定义是：左右两个子树的高度差不能超过 1，左右两边相对平衡，因此称之为平衡二叉树。而红黑树 s
AVL 树，通过左旋和右旋的操作将节点进行上浮或者下沉。
AVL 树保证不会退化为线性查找。
不适合作为数据库的缺点：
1. 虽然可以保证查询的性能不会退化，但是对于树的左旋和右旋的操作十分耗费性能，在存储数据的时候会出现长时间等待的情况，同时还是会发现这样存储的效率是十分低的，同时磁盘的利用率十分低。
2. 另外从数据结构图发现还有一个十分明显的缺点，那就是一个节点只能有两个子节点，如果插入大量节点会导致树的高度不断膨胀，即使可以平衡操作，对于插入的操作而言还是十分耗费性能的。
B 树
数据结构演示图：https://www.cs.usfca.edu/~galles/visualization/BTree.html
既然二叉树只有两个节点，那么我们调整结构，让每一层的节点内容增多，并让树控制在 2-4 层。同时可以包含多个子节点，这样即可极大提高存储效率，同时这种紧凑的结构也方便磁盘的顺序扫描。
线性数据结构和树结构的结合。
通过多数据节点大大降低树的高度。
不需要旋转就可以保证树的平衡
缺点：
但是很可惜 B 树有一个十分致命的缺陷，那就是不适合作为范围查找，如果我们想跨越多个范围进行查询，那么需要从根节点遍历一整颗树多次，我们知道范围查询的常见是非常常见的，这样的性能开销对于数据库来说显然不实际。
B+树
数据结构演示图：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B+树是对于 B 树的一种优化和变种，其实可以发现就是在线性结构和逻辑结构的兼容，最终在 B 树的基础上，所有的数据存在叶子节点，而索引节点放在非叶子节点，最终这样的接口。
特点：
B+树是 B 树发展过来的一种数据结构
B+树所有数据都在叶子节点。
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。
原文：
InnoDbencodes fixed-length fields greater than or equal to 768 bytes in length as variable-length fields, which can be stored off-page. For example, aCHAR(255)column can exceed 768 bytes if the maximum byte length of the character set is greater than 3, as it is withutf8mb4.
一个 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 在实践的过程有还是做了改进，理论和实践之间总是有某种差异。
赐他一块白石，石头上写着新名 2020.09.23 加入
如果我们想要知道自己想要做什么，必须先找到自己的白色石头。欢迎关注个人公众号“懒时小窝”，不传播焦虑，只分享和思考有价值的内容。
评论