引言

索引是数据库中老生常谈的概念，B+ 树更是 MySQL 中最常见的索引实现，但是对于索引中具体细节并不一定清楚，因此本文介绍从二叉树到 B+ 树的演进，并介绍 B+ 树为维护有序而进行的页分裂与页合并操作。

由于个人能力有限，以下内容可能有误，欢迎批评指正。

概念

数据结构

在数据库的搭建与应用中，根据不同的使用场景来选择恰当的数据结构至关重要，这直接关乎数据库的性能与效率。以下是几种基础数据结构的详细对比分析：

• 哈希表
  • 原理：利用哈希函数（也称为散列函数）将键（key）转化为固定的地址，以此地址作为索引，精准定位哈希表中与之对应的 值（value）。
  • 优势：在平均情况下，执行查找、插入和删除元素的操作时，时间复杂度仅为O(1) ，这使得它在处理等值查询（即单点查询，简称为点查）时表现出色，例如在缓存系统中，能快速定位并获取所需数据。
  • 局限性：由于经过哈希函数处理后的键是无序排列的，所以哈希表并不适用于范围查询。
• 顺序数组
  • 特性：在内存中以连续的方式存储数据，这使得通过索引能够迅速定位到对应的元素，基于索引访问数据的时间复杂度低至O(1) 。
  • 查询优势：得益于数组元素的有序排列，可以运用二分查找算法。在确认索引的过程中，二分查找的时间复杂度为O(logN)，因此顺序数组既能高效地进行等值查询，也能很好地处理范围查询。
  • 插入删除劣势：但在进行插入和删除操作时，如果操作位置并非数组尾部，就需要移动部分元素，这一过程的时间复杂度高达O(N)，这也导致它更适合存储静态数据，即较少发生数据变动的数据。
• 有序链表
  • 插入删除优势：在进行插入和删除元素操作时，时间复杂度仅为O(1) ，这是因为只需对链表中的指针进行修改即可完成操作。
  • 访问劣势：由于在内存中存储不连续，在访问元素时，需要从链表头部开始遍历，所以访问元素的时间复杂度为O(N) 。

总而言之，不难发现以上几种基础数据结构各有长短。而在实际应用中，许多其他更为复杂的数据结构，本质上都可以看作是这些基础数据结构的组合或变形，它们在不同的场景下发挥着各自独特的作用 。

数据页

MySQL的默认存储引擎InnoDB属于磁盘数据库存储引擎，它会将数据与索引存储于磁盘之上，并借助缓存机制来提升性能表现。

磁盘数据库的关键特性是最终将数据持久化保存在磁盘里，不过从磁盘读取数据到内存的过程中，必然会涉及磁盘I/O操作。为提升数据读写效率，InnoDB把页设定为磁盘与内存交互的基本单位。

InnoDB通过innodb_page_size参数对页大小进行控制，该参数的默认值是16KB，而操作系统中的数据页大小通常为4KB，这就意味着InnoDB中的一页相当于操作系统中的四页。基于此，InnoDB在读入所请求的页面时，会采用磁盘预读策略，同步预读另外三页的数据。当程序试图读取的数据不在内存中时，便会触发缺页异常。这时，系统会向磁盘发送读盘信号，磁盘将数据加载到内存，待加载完成，异常返回，程序得以继续执行。

每个数据页能够保存多行数据。当数据页从磁盘加载至内存后，还需要在数据页中进一步定位所需的数据行。在数据页中，记录按照索引值从小到大的顺序串联成一个单向链表，所以在执行查询操作时，需要通过遍历这个链表来定位数据，时间复杂度为O(N) 。

如下图所示，如果链表无序，查询 4 时需要找 5 次，也就是全表扫描，而如果链表有序，需要找 4 次。

但尽管是内存操作，如果数据量增大后 O(N) 的时间复杂度也会慢，因此出现了 页目录。

页目录

页目录（slot，槽）的原理可以参考跳表。

跳表如下图所示，其中每隔 n 个元素抽出一个组成一级索引，每隔 2*n 个元素组成二级索引。

MySQL 数据页中通过页目录将数据行分组，并规定每个槽中的元素在 1~8 条， 槽中保存本组元素中的最大记录。

因此查询过程中首先定位在哪个槽（二分法），然后在槽中定位数据行（遍历），总的时间复杂度可以认为 O(logN)。

如下图所示，假设每个槽中最多保存 3 条数据，查询 4 时由于 3 < 4 < 5，因此从槽 1 的下一个元素开始遍历，发现槽 2 的第一个元素就是 4。

显然，数据页中使用页目录可以将查询的时间复杂度从 O(N) 下降到 O(logN)。

实际上，跳表是数据库中常用的数据结构，比如 Redis 中的 ZSet。

ZSet 是有序集合，类似于一个集合（Set），但每个元素都有一个相关联的分数（Score），这个分数可以用来对元素进行排序，比如用于排行榜。

ZSet 结构体是以下两个数据结构的组合：

• 哈希表，适合单点查询，具体是以常数复杂度获取元素权重；
• 跳表，适合范围查询，时间复杂度 O(logN)，实现多层的有序链表。

参考文章 Redis 为什么用跳表，而不用平衡树？，如下图所示是一个层级为 3 的跳表。

其中头节点有 L0~L2 三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来：

• L0 层级共有 5 个节点，分别是节点1、2、3、4、5；
• L1 层级共有 3 个节点，分别是节点 2、3、5；
• L2 层级只有 1 个节点，也就是节点 3 。

可以发现 Redis ZSet 中跳表的使用与 MySQL 中的页目录是相同的思想。页目录提高了页内数据的查询效率，为提高多页数据的查询效率，出现了 索引。

索引

从本质上来说，页内数据与多页数据均以链表形式存在，正因如此，它们都能够借助页目录来实现优化。

页目录里存储着最小数据的索引值，我们将这样的目录称作索引。很明显，数据页的作用是对数据行进行组织，而索引则是用于组织数据页。

在InnoDB存储引擎中，索引是基于B+树来实现的，也就是说，每一个索引实际上都是一棵B+树。InnoDB表属于索引组织表，这意味着表中的数据会按照主键的顺序进行存放。

在B+树的多层页结构中，上层节点会保存下层节点的主键最小值，并且在同一层的页之间，前一页的主键值一定小于后一页的主键值。基于这样的结构特性，我们就能够按照从上到下、从左到右的顺序进行查询，这也正是B+树结构对于数据排序的重要意义所在，它为高效的数据检索和排序操作提供了坚实的基础 。

如下所示，是一个简化版的 B+ 树示意图。同样查询 4 时通过索引定位到 3 < 4 < 5，因此定位到数据页 15，其中定位数据行 4。

因此索引是一种有序的数据结构，用于管理数据页，从而提高查询效率， 核心思想是减少 IO 次数。

但是 B+ 树的实现并不是凭空产生，也不是没有缺点，下面从最简单的树也就是二叉树开始，介绍 B+ 树特性的演进。

树

二叉树

二叉树作为一种基础且重要的数据结构，具备以下主要特征与概念：

• 根节点：整棵二叉树中，唯一没有父节点的特殊节点，它是整棵树的起始点，所有其他节点都由它衍生而出。
• 子节点：二叉树的每个节点，最多能拥有两个子节点，分别称作左子节点和右子节点，这是二叉树区别于其他树形结构的关键特性之一。
• 节点的度：用于衡量一个节点的分支情况，即该节点所拥有子节点的数量，度为0的节点即为末端节点，而度为2的节点拥有最完整的分支结构。
• 父子关系：除根节点外，二叉树的每个节点都存在唯一的父节点，这种关系构建起了树的层级结构，使得数据的组织和访问有序可循。
• 兄弟关系：处于同一父节点下的两个不同子节点，它们之间互为兄弟节点，兄弟节点在树的结构中处于同一层级，共同丰富了树的分支形态。
• 叶子节点：也被称为终端节点，这类节点没有子节点，位于二叉树的最底层，是树的末端分支。
• 节点的层次：通常将根节点定义为第一层，从根节点开始，每向下一层，节点的层次数就增加1，比如根节点的子节点为第二层，以此类推，这种层次划分有助于理解树的深度和节点分布。
• 树的高度：从根节点出发，到最深叶子节点的最长路径上所包含的节点数量，一般认为叶子节点的高度为0，树的高度反映了二叉树的整体规模和深度 。

• 树的遍历，按照一定的规则与顺序访问每个节点，包括深度优先遍历与广度优先遍历，其中深度优先遍历分为前序遍历、中序遍历、后序遍历，针对的是父节点的访问顺序。时间复杂度为 O(N)。

如下图所示是几种二叉树示意图，其中 2、3 都是特殊的二叉树。

其中：

• 2 对应满二叉树，定义是二叉树只有度为 0 的节点和度为 2 的节点，并且度为 0 的节点在同一层上；
• 3 对应完全二叉树，定义是子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

普通二叉树中的节点没有顺序，查询时需要遍历全部结点，时间复杂度为 O(N)，其中 N 是树中节点的数量。因此加入“有序”的特性，而有序的二叉树称为二叉搜索树。

二叉搜索树

二叉搜索树（Binary Search Tree），也称为二叉查找树、二叉排序树，是指一棵空树，或者是具有下列性质的二叉树：

• 若它的 左子树 不空，则左子树上 所有节点 的值均 小于 它的根节点的值；
• 若它的 右子树 不空，则右子树上 所有节点 的值均 大于 它的根节点的值；
• 它的左、右子树也分别为二叉搜索树（ 重复性）。

显然二叉搜索树的中序遍历是升序排列，如下所示是二叉搜索树的示意图。

二叉搜索树是一种极为经典且应用广泛的数据结构，它巧妙融合了链表和数组的优势。在插入与删除操作上，二叉搜索树如同链表一样高效快捷，而在查找操作方面，又具备数组那种快速定位的特性。这一系列操作的时间复杂度均为O(logN) ，其关键原因在于二叉搜索树能够运用二分查找法。众所周知，二分法的实施前提是数据有序，这也是二叉搜索树又被称作排序树的缘由。

得益于上述特性，二叉搜索树在众多领域有着广泛的应用。例如在文件系统和数据库系统中，常常会采用这种数据结构来实现高效率的排序与检索操作，帮助系统快速定位和管理数据，极大地提升了系统的运行效率。

如下图所示，参考文章《为什么MySQL采用B+树作为索引？》，将所有二分查找过程中用到的中间节点，通过指针依次连接起来，并选取最中间的节点作为根节点，如此便构建形成了二叉查找树。这种构建方式直观地展示了二叉查找树与二分查找法之间的紧密联系，也进一步揭示了其高效查找的内在机制 。

查询节点 3 的示意图如下所示，其中跳跃查询。

插入节点的示意图如下所示，其中新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。

但是如果二叉搜索树的左右子树不平衡，极端场景下会退化为链表，查询的时间复杂度退化为 O(N)，因此又加入了“平衡”的特性，而平衡的二叉搜索树称为平衡搜索树。

平衡搜索树

平衡搜索树（Balanced Search Tree），又称平衡二叉树，是一类特殊的二叉搜索树，具备如下关键性质：

• 二叉搜索树特性：在平衡搜索树的任意节点上，其左子树内所有节点的值均小于该节点自身的值，而右子树内所有节点的值均大于该节点的值。这一特性确保了树结构上数据的有序性，为高效搜索提供了基础。
• 平衡特性：树的左右子树高度差被限制在一个特定固定值以内（常见为 1）。通过维持这样的平衡，使得树的高度能够保持在尽可能小的状态，进而优化了搜索、插入和删除等操作的时间复杂度。

此固定值的设定差异，衍生出了不同类型的平衡搜索树。以AVL树和红黑树为例，它们对应的固定值分别为1和2 。以下为AVL树的示意图。

平衡搜索树的设计目的是将动态操作（如插入、删除和查找）的时间复杂度维持在 O(log N) ，具体是通过旋转和重新组织节点来维持平衡性质。

如下图所示，平衡二叉树插入新值时为保持平衡可能需要多次旋转，从而保证左右子树的高度相等。

平衡树的维护需要消耗一定的资源与时间，存在相应的开销。也正因如此，它通常被应用于内存结构对象。比如在Linux内核的进程管理体系中，就采用了红黑树来管理进程的状态信息，这些信息涵盖了进程的优先级、CPU使用情况等关键数据。借助红黑树的特性，系统能够快速地在不同进程之间进行切换，有效提升了系统的运行效率。

然而，当数据量持续增长，树中节点数量不断增多，树的高度也会随之攀升。在这种情况下，二叉搜索树的性能就会受到较大影响，不再适合用于大规模数据的处理。于是，多路搜索树应运而生。多路搜索树的一个显著特点是，单个节点可以拥有多个子节点，这使得树在存储大量数据时，能够有效降低自身高度，进而提升数据的查找效率。这种特性让多路搜索树特别适用于外部存储场景，也就是将索引以文件的形式存储在磁盘上，满足了磁盘存储大规模数据时对高效检索的需求 。

B树

B树中的“B”可理解为“Balance”，意味着它是一种多路搜索树，同时也是多路平衡查找树。B树具有以下主要特征：

• 根节点子节点数量：根节点至少包含两个子节点，这是B树结构起始的基础条件，为后续数据的分散存储和查找提供了基本的分支结构。
• 节点子节点上限与阶数：每个节点最多拥有M个子节点，且M>2 ，这里的M被称作B树的阶。在实际应用中，B树的出度（Degree，即一个节点的子节点数目）常常超过100，例如1200，并且树的高度通常不会超过3，这样的结构设计使得B树在存储大量数据时依然能够保持高效的查找性能。
• 非根与非叶子节点的子节点下限：除根节点和叶子节点外，其他每个节点至少有ceil(M/2)个孩子。这里的ceil表示取上限操作，比如1.2的上限值为2。这一特性保证了B树在生长过程中，内部节点能够保持一定的饱满度，避免出现过于稀疏的情况，从而维持树的平衡和查找效率。
• 节点数据存储：B树的每个节点，无论是叶子节点还是非叶子节点，都具备保存数据（键值对）的能力。其中，非叶子节点保存的数据页用户记录中主键的最小值与页号，通过这种方式确保下一个数据页中用户记录的主键值大于上一个页中用户记录的主键值，使得数据在B树结构中呈现有序排列，为高效的查找操作奠定基础。
• 节点数据与子节点数量关系及节点分裂：每个节点最多有M - 1个数据，同时最多有M个子节点。这是因为M - 1个数据可以划分出M个区域，分别对应M个子节点所指向的数据范围。一旦节点中的数据数量或子节点数量超过这一要求，为了维持B树的结构特性，节点就会进行分裂操作，将数据重新分配到新的节点中。
• 叶子节点层级：B树的所有叶子节点都处于同一层，这明确要求B树作为平衡搜索树，其左右子树的高度差必须等于0 ，保证了树结构的严格平衡，使得查找路径的长度相对稳定，进而提升查找效率。
• 根节点地址与磁盘IO次数：树的根节点的地址存储在内存的数据字典中，这使得在进行数据检索时，一次检索最多需要“树的高度 - 1”次磁盘IO。通过将根节点地址常驻内存，减少了磁盘IO的次数，提高了数据访问的速度。

如下为B树的示意图，其中M = 3 。在该图中，根节点（磁盘块1）使用2个关键字（17与35）划分出3个区域。p1指向的范围小于17，p2指向的范围为17 - 35，p3指向的范围大于35，完全符合搜索树的定义，直观地展示了B树的结构和数据组织方式 。

如果查询 29，查询流程为：

• 从根节点出发，17 < 29 < 35，因此通过 p2 指针访问子节点磁盘块 3；
• 由于 26 < 29 < 30，因此继续通过 p2 指针访问磁盘块 8；
• 由于磁盘块 8 是叶子节点，数据页内部二分查找，从 28 开始找到 29，因此 IO 次数为 3 - 1 = 2。

注意二叉搜索树通过旋转保持平衡，而多路搜索树通过分裂与合并节点保持平衡。

如下图所示是 B 树中依次插入 1、2、3、4、5、6、7 的示意图，其中插入时判断，小于中位数的元素放入左边节点，大于中位数的元素放入右边节点，中位数作为分隔值，参考文章 维基百科 - B 树。

B-树操作可视化网站 中可以查看依次插入 1、2、3、4、5、6、7 的动图。

测试显示如果依次插入 3、2、5、4、6、1、7，数据分布不同，原因是 B 树的数据分布与插入顺序有关。

依次删除 4、5。

需要注意 B 树的非叶子节点中保存完整的数据，带来的影响包括：

• 查询不稳定，原因是查询可能在非叶子节点就结束；
• 树的高度增加，原因是单个节点的数据较大，同样大小的数据页可以保存的节点数量减少。

因此针对 B 树优化后出现了 B+ 树。

B+树

相较于B树，B+树具有以下显著特征：

• 节点数据存储差异：B+树的非叶子节点仅保存键值，也就是索引信息，并不存储记录数据。这使得B+树的节点能够容纳更多的子节点，拥有更大的出度，进而在存储大量数据时，能有效降低树的高度，提升查询效率。
• 查询稳定性：B+树的所有查询操作最终都会到达叶子节点。这种特性保证了查询路径的一致性，无论查询的是何种数据，其查询过程和时间复杂度都相对稳定，不会因为数据在树中的位置不同而产生较大波动。
• 可能存在重复数据：由于B+树右子树中的值大于等于父节点的值，即使在非叶子节点中找到了与查询值相等的键，搜索操作也不会停止，而是会继续进入右子树进行查询。这就导致在B+树中可能会出现重复数据的情况，而B树在查询到相等值时即可停止搜索，不存在这一问题。
• 双向指针结构与范围查询优势：B+树每一层的非叶子节点以及所有的叶子节点之间均由双向指针连接。这一独特结构使得B+树在进行范围查询时表现出色。以B树和B+树的范围查询对比来说，B树的范围查询类似于对IN范围内的每个值进行单独查询，而B+树的范围查询则更像是BETWEEN AND操作，等价于>= AND <=，能够通过双向指针快速定位到范围内的所有数据，极大地提高了范围查询的效率。
• 非叶子节点索引存储特性：在InnoDB的B+树中，非叶子节点拥有多少个子节点，就对应有多少个索引，并且非叶子节点会保存子节点中所有索引的最小值。而普通的B+树中，非叶子节点的子节点个数为M阶，索引个数则为M - 1，这种差异体现了InnoDB B+树在索引组织和存储上的独特性，有助于更高效地进行数据定位和检索 。

InnoDB B+ 树的示意图如下所示。

B+树操作可视化网站 中查看普通 B+ 树依次插入 1、2、3、4、5、6、7 的动图，显然叶子节点中保存全部数据。

测试显示如果依次插入 3、2、5、4、6、1、7，数据分布也不同，原因是 B+ 树的数据分布也与插入顺序有关。

依次删除 4、5。

《MySQL 45 讲》中总结到，B+ 树为了维护索引的有序性，在插入新值的时候需要做必要的维护：

• 页分裂（写满的数据页中间写入）
• 页合并（数据页的利用率）

《MySQL 技术内幕 InnoDB 存储引擎》中详细介绍了 B+ 树的页分裂与页合并。

下面是看到的部分相关资料：

• InnoDB Page Merging and Page Splitting，介绍页分裂与页合并，并测试对比多种主键的页分裂与页合并次数，包括自增主键、uuid 等；
• Innodb页合并和页分裂，翻译了两篇文章，第一篇就是上一篇，第二篇测试非 delete 语句导致的表碎片，包括插入回滚、插入失败、页分裂；
• InnoDB数据页什么时候合并，其中使用数据页分析工具观察删除操作是否导致页合并，并查看索引的高度、索引的页数；
• InnoDB表聚集索引层高什么时候发生变化，其中使用多种数据页分析工具观察插入操作是否导致树分裂。

下面详细介绍 B+ 树，包括页分裂与页合并。

B+ 树

树

参考文章 InnoDB：B-tree index（1），B+ 树的数据结构见下图。

其中：

• 树高度的定义，叶子节点是 0，父节点高度是子节点高度 + 1；

• 树中有三种节点，包括根节点、非叶子节点（分支节点、中间节点）、叶子节点，每个节点都是页（page）；

• 每个 page 中有两个系统记录（具有固定页内偏移量），包括 Infimum record（下确界）/ supremum record（上确界），是一个 page 内 record list 的头/尾节点；

• 每个 record 由 key + value 组成，因此也可以将关系型数据库理解为 key-value 存储。非叶子节点与叶子节点中保存的数据不同：

  • 主键索引，key 对应主键，value 对应存储完整的用户记录，包括行的其他字段与隐藏列；

  • 二级索引，key 对应二级索引列，value 对应主键。

  • 非叶子节点，key 中保存子节点中的最小 key，value 中保存 point（page_no，页号）；

  • 叶子节点，key 中保存可以数据行的若干列，value 中保存其余列，不同类型索引中对应不同的数据：

• 同一高度的 page 连接成双向链表，称为 page list；

• 同一 page 的 record 连接成单向链表，称为 record list；

• 数据写入过程中为了维护树的稳定性，可能发生页分裂或页合并，因此 B+ 树适合读多写少的场景。

插入

在数据库索引的管理过程中，插入操作往往会引发页分裂现象，而页分裂的关键触发条件在于页的状态是否写满。这里，一个值得深入探讨的问题是：写满的定义是否等同于填充100% ？

事实上，InnoDB存储引擎中的innodb_fill_factor（填充因子）参数，专门用于调控page的填充率（“page - full” percentage）。该参数的默认值虽为100%，但实际上系统会预留1/16的空间，用于应对记录长度可能出现的扩展情况，这也就意味着实际的填充率大致为94%。

当数据页中剩余空间不足以容纳新数据时，页分裂便会发生。从直观理解的角度，我们可以将页分裂的触发条件简单归纳为填充率超过innodb_fill_factor所设定的值。

基于上述原理，适当增大innodb_fill_factor的值，能够有效提升空间利用率，降低页分裂发生的概率，进而减少数据碎片的产生。然而，这也存在一定的风险，当字段长度需要扩展时，反而会因空间不足而增大页分裂发生的可能性。此外，delete操作后若不释放空间，而是采用复用的实现方式，同样能够降低页分裂出现的概率。

需要特别注意的是，innodb_fill_factor是一个实例级别的参数，并非作用于单个表，这就要求在调整该参数时，需从整个实例的层面进行综合考量。

如下图所示，假设第10页已经达到写满状态，此时若要写入数据17，会发现没有足够的空间容纳。一种可能的简单处理方式是将17写入下一页，但如果下一页也处于写满状态，这种方法显然无法解决问题。

因此，在实际处理过程中，系统会将第10页从中间位置分裂成两个页，把原页中一半的数据拷贝至新页，随后对数据页之间的指针进行相应修改，以此完成页分裂的操作，并确保数据的连续性和完整性 。

索引插入操作完整的算法见下表，参考《MySQL 技术内幕 InnoDB 存储引擎》。

Leaf Page 满	Index Page 满	操作
No	NO	直接将记录插入到叶子节点
Yes	NO	1、拆分 Leaf Page 2、将中间节点放入到 Index Page 中 3、将小于中间节点的记录放左边 4、将大于等于中间节点的记录放右边
Yes	Yes	1、拆分 Leaf Page 2、将小于中间节点的记录放左边 3、将大于等于中间节点的记录放右边 4、拆分 Index Page 5、将小于中间节点的记录放左边 6、将大于等于中间节点的记录放右边 7、将中间节点放入上一层 Index Page

不同插入场景的示意图如下所示，参考 聊聊 MySQL 的优化思路，其中假设每个节点只能存储 4 个子节点。

第一种场景【leaf page 和 index page 都没有满】，插入节点 28。

第二种场景【leaf page 满 index page 没有满】，插入节点 70，发生一次页分裂。

第三种场景【leaf page 和 index page 都满】，插入节点 95，发生两次页分裂。

另外，B+ 树中为了减少页分裂，提供了类似平衡二叉树的旋转功能。当 left page 已满，但是左右兄弟节点没有满时，将记录移到当前所在页的兄弟节点。如下所示，插入 70 时，没有发生页分裂，而是发生左旋。

删除

索引的删除操作可能会导致页合并，所以问题是页合并的触发条件是什么？

实际上 MERGE_THRESHOLD（合并阈值）参数用于控制是否发生页合并，默认是页大小的 50%。

当数据页的填充率小于 MERGE_THRESHOLD 时，会尝试将其与兄弟节点合并。

需要注意的是支持给表与索引指定 MERGE_THRESHOLD。

# 创建索引时指定，之后不允许修改
ALTER TABLE t_sk ADD INDEX k1(c1) COMMENT 'MERGE_THRESHOLD=20';

# 可以在运行时修改
ALTER TABLE t_sk COMMENT 'MERGE_THRESHOLD=40';

如下图所示，当第 5 页与第 6 页第发生大量删除导致占用空间均不足一半时将发生页合并。

索引删除操作完整的算法见下表，参考《MySQL 技术内幕 InnoDB 存储引擎》。

叶子节点小于合并阈值	非叶子节点小于合并阈值	操作
No	NO	直接将记录从叶子节点删除，如果该节点还是 Index Page 的节点，用该节点的右节点代替
Yes	NO	合并叶子节点和它的兄弟节点，同时更新 Index Page
Yes	Yes	1、合并叶子节点和它的兄弟节点 2、更新 Index Page 3、合并 Index Page 和它的兄弟节点

不同删除场景的示意图如下所示，注意是从插入 95 开始，不是从插入 70 的左旋开始。

第一种场景【叶子节点和非叶子节点都大于合并阈值】，删除节点 70，操作 leaf page。

第一种场景【叶子节点和非叶子节点都大于合并阈值】，删除节点 25，操作 leaf page 和 index page。

第三种场景【叶子节点和非叶子节点都小于合并阈值】，删除节点 60，合并 leaf page 和 index page。

结论

索引的设计理念是典型的以空间换时间策略，作为一种有序的数据结构，它能够将原本可能无序写入的数据，在逻辑层面转化为有序状态，进而通过减少I/O操作次数，大幅提升查询效率。

在数据处理领域，常见的支持快速查找的数据结构主要有哈希表、顺序数组以及二叉搜索树，它们各自具备独特的性能特点：

• 哈希表：查询操作的时间复杂度能达到O(1) ，这使得它在处理等值查询时表现极为出色，能够迅速定位到目标数据。然而，由于哈希函数的特性，哈希表并不擅长处理范围查询，在面对这类需求时往往显得力不从心。
• 顺序数组：查询操作的时间复杂度为O(logN) ，这一特性让它在等值查询和范围查询中都能保持不错的效率。不过，顺序数组在进行中间位置写入操作时，需要对大量数据进行拷贝，这不仅耗费时间，还可能导致性能瓶颈。
• 二叉搜索树：同样具有O(logN)的时间复杂度，其核心特征是每个节点的左子树中所有节点的值都小于该节点，而右子树中所有节点的值都大于该节点。这种结构赋予了二叉搜索树独特的优势，它既像链表一样具备快速插入与删除操作的能力，又像数组一样拥有快速查找的特性。但它也存在明显的缺点，当树的结构不平衡时，二叉搜索树会退化为链表，导致查询效率大幅下降。

B+树作为B树的优化版本，在性能和结构上都有显著改进。先来了解B树的主要特性：

• 搜索树特性：B树兼具链表快速插入与删除的灵活性，以及数组快速查找的高效性。但维持数据的有序性需要额外的操作和开销，这是其在实际应用中需要面对的挑战。
• 平衡树特性：B树的左右子树高度差保持相等，这使得查询过程相对稳定，无论数据位于树的哪个位置，查询时间都能保持在一个相对稳定的范围内。然而，为了维持这种平衡状态，B树需要频繁进行旋转等操作，这增加了维护的复杂性。
• N叉树特性：B树的节点出度较高，这使得树的整体高度得以降低。在非叶子节点中，B树保存着数据页的用户记录中主键的最小值与页号，通过这种方式确保了下一个数据页中用户记录的主键值大于上一个页中用户记录的主键值，为高效的查询提供了数据组织基础。

B+树与B树相比，存在以下关键区别：

• 节点数据存储差异：B树的非叶子节点中既保存索引数据，也保存记录数据；而B+树的非叶子节点仅保存索引数据。这一差异使得B+树的节点能够容纳更多的子节点，拥有更高的出度，从而降低树的高度，减少I/O操作次数，提升查询效率。
• 节点连接方式不同：B树的节点之间没有指针相连，而B+树的节点之间，包括叶子节点与非叶子节点，都通过双向指针连接。这种结构使得B+树在进行范围查询时具有明显优势，能够快速定位到范围内的所有数据。

B+树在维护索引有序性的过程中，针对插入新值的情况，需要进行特定的维护操作：

• 页分裂机制：当数据页写满时，会触发页分裂操作。具体的触发条件是填充率大于innodb_fill_factor（填充因子）参数，该参数默认值为100%，但实际上系统会预留1/16的空间用于记录长度的扩展，所以实际相当于填充率达到94%时就可能触发页分裂。
• 页合并机制：当数据页填充率较低时，会发生页合并操作。其触发条件是填充率小于MERGE_THRESHOLD（合并阈值）参数，该参数默认值为页大小的50% ，当数据页的填充率低于这个阈值时，系统会考虑将相邻的数据页进行合并，以优化存储结构和提升性能。

B+ 树的维护操作包括分裂、合并、上移、下移。

显然，索引的优点是可以加快查询速度，缺点是占用内存或磁盘空间，同时减慢了插入与更新操作的速度。

总结下，MySQL InnoDB 中的索引基于 B+ 树实现，索引用于组织数据页，每个数据页之间有双向指针。数据页用于组织数据行，每行记录之间有单向链表。多层页之间上层节点保存下层节点的主键最小值，同层页之间前一页主键小于后一页，同一页内部前一行主键小于后一行，因此数据行全局有序，从而可以从上到下从左到右从前往后顺序查询。

B+树作为一种独特的数据结构，具有以下三个显著特点：

• 多叉树结构：B+树属于多叉树类型，这意味着其节点内部能够存储多个孩子节点。这种结构设计使得B+树在存储相同数量的数据时，相较于二叉树，树的高度更低，从而有效减少了数据查询时的查找路径长度，提高了查询效率。
• 数据有序性：B+树内部存储的数据是有序排列的，这一特性使其能够支持顺序遍历维护的数据。无论是进行范围查询还是查找特定数据，有序的数据排列都为高效的检索操作提供了有力支持，极大地提升了数据处理的速度和准确性。
• 节点数据存储特性：B+树根据节点类型的不同，内部保存的数据也有所差异。根节点和分支节点主要保存数据的索引信息，这些索引信息就像是数据的“目录”，能够快速引导查询到目标数据所在的大致范围；而叶子节点则保存着原始数据，这种存储方式既保证了数据的完整性，又通过索引与数据的分离，进一步优化了查询性能。

值得一提的是，上述第三个特性是许多其他常规数据结构所不具备的。正是由于B+树拥有这些特点，使其具备了平衡性、有序性和高效性能等显著优势。这使得B+树在各类数据处理场景中表现出色，尤其适用于支持范围查询，以及高效地进行数据插入、删除和查找操作，广泛应用于数据库索引、文件系统等领域 。

参考教程

• 《MySQL 是怎样运行的：从根儿上理解 MySQL》
• 《MySQL 技术内幕 InnoDB 存储引擎》
• 你管这破玩意叫B+树?
• 聊聊 MySQL 的优化思路
• 【从入门到入土】令人脱发的数据库底层设计
• 索引很难么？带你从头到尾捋一遍MySQL索引结构，不信你学不会！
• 从数据页的角度看 B+ 树
• 为什么 MySQL 采用 B+ 树作为索引？
• InnoDB：B-tree index（1）
• InnoDB：B-tree index（2）
• 为什么选择b+树作为存储引擎索引结构
• 存储引擎的演变过程
• Redis 为什么用跳表，而不用平衡树？
• 为什么MySQL数据库索引选择使用B+树？
• MySQL索引原理及慢查询优化
• 深入理解了MySQL，你才能说熟悉数据库
• B-树操作可视化网站
• B+树操作可视化网站