国产积木索引表_三高Mysql - Inndb存储引擎和索引介绍

三高Mysql-Inndb存储引擎及索引介绍介绍

内容是慕课网《MySQL高并发、高性能、高可用实践》视频的学习笔记以及个人整理和拓展后的笔记。 本节的内容是对存储结构的高级理解，同时也介绍了为什么使用B+索引。 作为最终的数据结构，其实在具体实现上并没有完全遵循B+格式，而是内部做了很多“手脚”。 这也是所谓理论与实践的区别。

如果内容较难，可以按照《Mysql如何运行》个人读书笔记专栏补课。 我也在一边学习一边更新。

地址如下：。

索引组织表

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

它不是“组织表”，而是按“索引”组织的表。 索引就是数据。 数据就是索引。 默认情况下，表将按主键顺序存储并根据一定的规则排序。 默认的索引组织形式称为聚类。 指数。

什么是索引？

索引可以简单的理解为一个目录，类似于我们书中的目录页，它可以帮助我们快速定位到具体的内容。 它是一种对数据库的一个或多个列进行预排序的数据结构。 请注意，这是一个旨在加速数组的数据结构。 搜索速度。

但索引也存在问题，即目录本身也需要占用存储空间，并随着数据的扩展而扩展。 同时，如果索引使用不当，也会出现问题。 比如，如果我们的目录索引内容都一模一样，出现“索引失败”问题，此时索引效果就会大打折扣，还不如直接搜索数据。

主键定义和主键索引

在Mysql的Inndb存储引擎中，使用的主键索引也称为聚集索引：

存储引擎表中的每个表都必须有一个主键，表中有一个非空的唯一索引就是主键。 如果有多个非空唯一索引且未定义主键，则选择第一个定义的索引。 如果不满足所有条件，则会在数据行中自动创建一个6字节的指针隐藏列作为主键，并且这个主键的内键是自增的，允许记录按顺序存储。

下面使用视频中的案例讨论的下表的主键是什么？

从上面的截图中可以看到，字段 a 没有定义唯一索引。 虽然它非空，但它不是唯一的，因此它不是主键。 虽然b是第一个定义的，但它不是非空的，因此不能用作索引。 而d和c虽然都是唯一索引和非空列，但是根据多个非空索引，检索第一个定义索引为主键的规则，最终主键为字段d。

B+树索引

B+树的索引结构是B+树的基本结构。 以下是传统B+树的结构：

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

最底层指的是b+树，但并不完全一样。 节点分别称为数据页和索引页，但实际上索引页和数据页除了数据类型不同之外，基本相同。 即索引就是数据，数据就是索引，索引它分为聚集索引和辅助索引。 聚集索引最大的特点就是存储键就是主键ID，主键ID是按照一定的规则生成的或者在创建表的时候指定的，但是必须有一个主键索引，也就是一张表有必须是主键。 辅助索引使用主键作为索引字段的值，数值存储索引主键。

同级数据页使用双向链表，索引页也使用双向链表。 这与B+树的数据结构不同。 传统的B+树只在最低叶子节点有链表设计。

聚集索引

聚集索引是指根据表的主键构建B+树。 叶子节点直接存储行数据而不是指针，但实际上叶子节点本身也是数据页但只存储指针。

下面的案例图只是从最粗略的角度观察MySQL的数据页设计。 实际内容比这张图复杂得多：

聚集索引的特点

为什么要从大到小排序呢？

其实主要的目的就是利用二分查找的方法来快速定位查找数据页，提高查找的效率。 需要注意的是，由于MySQL早期版本的索引设计只能按升序排列，因此大多数聚集索引都是升序索引，在8.0版本中对此进行了优化。

辅助索引

辅助索引的存在形式：

设计与主键索引相同，但键存储的是索引字段的值，该值就是主键值。

辅助索引根据创建的索引构建几棵B+树，联合索引除外。

辅助索引相当于一棵新的B+树。

主键索引：

主键索引也称为聚集索引。 由于底层采用B+树设计结构，Mysql必须有主键，并使用主键作为索引。

主键索引是指以键为主键、值为数据的索引形式。

一旦表创建完成，系统中就会默认存在一棵以主键为索引的B+树。

什么是退货单？

当查询辅助索引时，由于查询结果是主键的值，因此需要按照二值法根据主键的值在聚集索引中再次查找。 这时相当于再次检查聚集索引。 本质上，它被检查了两次。 这是一棵B+树，所以回调到表中。

下图是一个表返回操作：

假设我们需要查找值为5的数据，首先我们会通过二分遍历“槽”找到二级索引中的具体数据行。 这个数据行不仅保存了索引值还保存了主键的值，因此我们需要将主键的值返回到聚集索引中才能找到实际存储的行记录。

但如果搜索条件和搜索列都是索引值，则实际上会使用“覆盖索引”搜索方式，不需要进行返表操作。

索引算法

对于刚接触B+树的同学来说，看到这些数据结构可能会感到困惑。 同时，他们也不清楚为什么要设计这么复杂的东西。 因此课程中通过介绍各种数据结构来介绍为什么最终选择B+树结构。 ，我们简单对比一下各种常见的数据结构，来理解为什么最终选择B+树。

对于一些常见的算法，可以阅读以下网站：Data()。

哈希表

〜//.html

哈希表的数据结构非常简单。 它只包含简单的键值对。 哈希函数用于计算索引列的哈希值存储。 哈希表最典型的索引应用类型就是哈希索引。 通过索引列 总计列计算哈希函数进行存储。

哈希表的缺点：

哈希表最大的问题是键冲突，因为如果出现键冲突，那么索引就会退化为顺序全表遍历，或者拉出一个链表来存储冲突的哈希键进行遍历，而哈希索引是最合适的。 等价查询实际上并不经常使用。 更常使用范围或模糊搜索。 这时候哈希表的数据结构就很难发挥作用了。

线性结构

线性结构指的是经典的数组，包括链表、数组和栈结构。 比如数组的查询效率是O​​(n)，搜索性能是O(1)，这似乎更适合设计数据库。

特征：

时间复杂度 O(n)。

需要从第一个开始进行遍历线性搜索，搜索效率为O(1)。

数组的特点是查找快，更新慢，而链表的特点是更新快，查找稍慢。

缺点不适合作为数据库：

对于任何线性结构来说，查找、更新、删除的速度似乎都非常好，但是顺序数组的插入速度却让人无法接受，尤其是在数组中间插入时，需要复制数组并移动它落后，而且链的搜索速度是不可接受的，也不利于磁盘存储。 如果数据量很大，开销巨大，显然不适合。

二分查找：二分查找是线性数组结构中非常常用的方法。 有序数组在等效查询和范围查询场景下的性能都非常好。

二分查找演示图：~//.html

时间复杂度（O(logn)），每次搜索都是前一次搜索的一半。

使用数组的中点作为比较对象。

根据中点数据大小，选择一半数据作为新的数组搜索。

一次可以查到的数据量是一半。

缺点：二分查找虽然将查询提升了一个数量级，但是仍然没有避免插入的问题。

二叉树

既然线性结构有局限性，那么逻辑结构是否可行呢？ 那么我们可以想想如果使用二叉树的话该如何处理。

时间复杂度为O(logN)。

搜索效率的快慢取决于树的高度。

遍历方法分为前序遍历、中序遍历和后序遍历。

如果所有节点都添加到一侧，则可能会退化为线性搜索。

缺点不适合作为数据库：

插入和删除需要一定的性能，并且为了节点的稳定性，需要使用左转或右转操作来维持二叉树的平衡，因此随后扩展了平衡二叉树和红黑树。

平衡二叉树和红黑树

平衡二叉树在二叉树中引入了左手和右手操作来保持平衡。 平衡二叉树的定义是：左右子树的高度差不能超过1，左右两侧相对平衡，因此称为平衡二叉树。 还有红黑树

AVL树通过左手和右手操作来浮动或下沉节点。

AVL 树保证不会退化为线性搜索。

缺点不适合作为数据库：

1.虽然可以保证查询的性能不会下降，但是树的左手和右手操作非常消耗性能。 存储数据时，会出现漫长的等待。 同时，你仍然会发现这样的存储效率很低。 ，而且磁盘利用率很低。

2、另外，从数据结构图中发现有一个非常明显的缺点，那就是一个节点只能有两个子节点。 如果插入大量节点，树的高度就会不断膨胀。 即使操作可以平衡，对于插入操作来说仍然是非常消耗性能的。

B树

数据结构演示图：~//BTree.html

由于二叉树只有两个节点，我们调整结构，增加每一层的节点内容，将树控制在2-4层。 可以同时包含多个子节点，可以大大提高存储效率。 同时，这种紧凑的结构也有利于磁盘的顺序扫描。

线性数据结构和树结构的组合。

通过多个数据节点显着降低树的高度。

无需旋转即可保持树木平衡

缺点：

但遗憾的是，B树有一个非常致命的缺陷，那就是不适合范围搜索。 如果我们想要跨多个范围查询，我们需要从根节点开始多次遍历整棵树。 我们知道，普通范围查询是很常见的，这样的性能开销对于数据库来说显然是不切实际的。

B+树

数据结构演示图：~//.html

B+树是B树的优化和变种。 其实可以发现它是兼容线性结构和逻辑结构的。 最后，基于B树，所有数据都存在于叶子节点中，索引节点放在非叶子节点中。 终于有这样的界面了。

特征：

B+树是从B树发展而来的一种数据结构

B+树中的所有数据都位于叶节点中。

B+树的所有数据最终形成一个线性表。

存储引擎结构

最后我们回到存储引擎所理解的存储引擎的基本结构。

如果想详细了解这部分的结构，建议阅读《Mysql如何运行》这本书，里面非常详细的介绍了Mysql的整个内部结构，对于理解存储结构很有帮助。

下面是存储引擎的数据存储的简单结构图。 更详细的结构视频中就不展开了。 另外，如果要详细解释的话，一篇文章是远远不够的，所以这里只能是一个大概的了解：

表空间：数据表在磁盘上的存储空间。 默认情况下，所有表的数据都存在于共享表空间中。 当然，也可以将每个表的数据放在一个独占的表空间中，以达到权限使用的目的。

：段分为叶节点段和非叶节点段。 叶节点段称为B+树段节点，非叶节点为索引页。

区域：区域通常由 64 个页面组成。 每个部分对应多个区域。 一个段的大小为1M。 一般由连续的段数据页组成，但一般一次申请3-4个。 （需要考虑内存容量）

数据页：页是数据的最小单位。 默认为 16kb。 数据页是B+树的一个节点。 最重要的是，数据页的设计考虑到了SSD和机械硬盘的设计。 机械硬盘的最小读写单位是512KB。 ，SSD的最小读写单元是4b，所以16KB是它们的倍数，可以节省空间。

数据行：数据行分为两种类型，包括inf和sup数据行。 无论一个表是否有数据行，至少都会有这两个数据行。 同时，每行会默认隐藏三个字段。 Trx Id 是多用途的。 对事务的控制。

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

答：如果数据页太大，那么如果每次读取数据页时只查找几行数据，就会浪费大量的计算机资源，因为数据库系统需要避免IO。 如果数据页太小，由于磁盘最小的读取单位有限制，性能可能会因多次读取而迅速下降。 如果数据页太大，如果只需要少量数据，就会浪费IO性能。

因此，MySQL在设计数据页大小时，考虑了固态盘和机械盘读取单位之间的折衷。

数据行

为了防止读者误解，以下所有介绍都是针对存储引擎和.7版本的。

数据行格式

提示：这里我们提前做好预防措施。 事实上，技术上的改进都是细节上的改进。 了解了之后，你会发现其实都是一样的东西。 但关键是魔鬼隐藏在细节中，所以你需要小心区别对待。

数据行的内容比较特殊。 由于历史原因，它有所演变。 为了方便理解，我们需要记住mysql数据行有两种格式。 它们分别由 和 两种格式组成。 为了方便理解，我们把这两个人称为AB，MySQL中有四种数据行格式，但是因为其中两种是旧的格式，在新版本中不再使用，所以在面试中可能会被问到，所以有必要了解它们。 :

：包含和。

：包含（5.0和8.0之后的默认表行格式）和（压缩格式）

如果需要知道当前mysql版本的默认行格式，可以使用SHOW LIKE“ormat”命令来查看。

让我们按照从最旧到最新的顺序看一下行格式的演变。

A叔叔的格式：

：该格式的英文名称被翻译为“冗余”格式。 它是 .0 之前的默认行格式。 需要注意的是，以下示例图片中的分隔符实际上并不存在。 在实际存储过程中，它们都是按照特定的编码进行编码的。 用于紧凑存储。

这就会带来一个问题，比如我们如何找到col1或者coln？ 所以，前端字段偏移列表的作用就是帮助MySQL快速定位到要查找的具体列，但是我们也需要注意，字段偏移列表是按倒序处理的。 让我们通过一个例子来直接解释这些字段。 偏移列表的作用：

再次强调，字段偏移列表并不固定记录变长列长度，而是存储两个相邻列之间的偏移长度。 假设当前有三列数据，顺序存储长度分别为1、2、3。 根据字段偏移列表的规则为1、3（3-1=2）、6（6-3=3）。 这些值字段偏移列表以相反的顺序存储。 同时真实的数据是用十六进制表示的，所以最终的结果是：06 03 01（注意中间加了空格是为了方便阅读，其实是紧凑的排列）

有些部分比较容易理解，比如表示字段偏移列表的单位和记录列数，还有一个非常重要的元素：下一个数据行的地址信息等。

rowId在之前的笔记中已经提到过。 如果创建表时没有指定主键，那么mysql就会使用这个rowId作为隐藏主键。 使用TxID进行事务控制，然后使用roll进行undo log回滚，实现MVCC。 机制，最后col1、col2、col3这三列就是真实数据。

如果你还好奇为什么字段偏移列表要逆序存储，其实仔细观察上面的行格式结构就可以看出端倪。 以滚动点为边界，左边是头信息和字段偏移列表，右边是真实数据。 官方的说法是，记录分为两部分：记录头信息和真实数据。 使用反向存储可以使长度和真实数据列“对称”。 指针向左移动一个指针向右移动，效率更高。

B叔叔的格式：

格式：这种格式更加精致。 可以看到上面的字段偏移量列表并不是很直观。 每次都需要进行减法来计算柱的真实长度。 因此采用变长字段列表对其进行改进，直接存储变长字段列表。 列的长度倒序存储，在此基础上增加NULL值列表来维护每一列是否为NULL，并用位表来标记每一列是否为NULL，0为NULL，1为非NULL，且同样以倒序存储。

记录头中的信息差异不是特别大，所以这里忽略，重点是“可变长度字段列表”和“NULL值列表”的变化。 技术进步总是很小但非常有效。

优点是太大的页面会被压缩存储，但压缩存储的问题是读取时需要解包读取，会消耗更多的性能。

最后，我们可以从下图中看到基本行格式的具体特点。 该表来自.7的官方文档，地址：

行格式 紧凑存储功能 增强的可变长度列存储 大索引键前缀支持 支持的表空间类型 所需的文件格式 系统、每个表文件、常规或 NoNo 系统、每个表文件、常规或系统、每个表文件、常规 -每张桌子，

可变列和不可变列

我们都知道Mysql支持很多数据类型，比如char、int、blob、text等，这里我们重点关注变长列和定长列的数据类型。 变长列是指指定长度与实际长度不一致的列。 比如里面的var这个词代表（变量），所以称为变量。 列，定长列是具有固定长度字符，char的列。 我们发现无论是在学校学习还是各种网上百科全书，char通常被认为是定长的，而不是定长的。

是不是真的？ 然而，随着时代的发展，char其实已经发生了变化。 这里，可以看到.7的文档说明：

参考：

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

原文：as-中固定大于或等于768字节，可以脱页。 对于 ，如果集合的字节数小于 3，则 CHAR(255) 可以为 768 个字节，就像 一样。

a的最大长度是多少

在.1之前，最大值为255，这可能是许多数据库管理工具默认为（255）的原因之一。

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

请注意，我们谈论的是字节而不是字符。 由于字符串实际上是通过字节进行特殊编码转译的，所以一些变长编码的存储长度是实时变化的。 例如，编码最多占用4个字节。 ，上述数据65535/4约等于16383个字符。

那么编码的最大列长度是16383？ 真的吗？ 其实这个值也是有参考价值的。 虽然理论上应该存储这么多数据，但实际上长度肯定小于16383。至于原因，你可以实际尝试创建一个表，你会发现创建失败或者字段修改失败。

这和mysql底层数据结构有关，因为变长字段需要记录长度，而mysql需要一些额外的记录空间来存储，以便记录信息。

注意：该函数不记录字符数，而是记录实际占用的长度。 由于中文需要存储3个字符，因此实际存储的长度为63000/3=21000。

提示：如果修改错误消息如下：1118 - 行大小太大。 所使用的表类型（而非 BLOB）的行大小为 65535。请检查 . 你必须有一些文本或BLOB

写在最后

从Mysql的B+树结构以及其他可能的数据库数据结构设计中，我们可以发现B+树对多种数据结构的兼容和平衡，并且Mysql在实践的过程中做出了改进。 理论和实践之间总是存在某种差异。 不同之处。