为什么MySQL索引要用B+tree

前言

当你在遇到了一条慢  SQL  需要进行优化时，你第一时间能想到的优化手段是什么？

大部分人第一反应可能都是添加索引，在大多数情况下面，索引能够将一条  SQL  语句的查询效率提高几个数量级。

索引的本质：用于快速查找记录的一种数据结构。

索引的常用数据结构：

1. 二叉树
2. 红黑树
3. Hash 表
4. B-tree  （B树，并不叫什么B减树😁）
5. B+tree
   数据结构图形化网址：Data Structure Visualization

索引查询

大家知道  select * from t where col = 88  这么一条  SQL  语句如果不走索引进行查找的话，正常地查就是全表扫描：从表的第一行记录开始逐行找，把每一行的  col  字段的值和 88 进行对比，这明显效率是很低的。

而如果走索引的话，查询的流程就完全不一样了（假设现在用一棵平衡二叉树数据结构存储我们的索引列）

此时该二叉树的存储结构（Key - Value）：Key 就是索引字段的数据，Value 就是索引所在行的磁盘文件地址。

当最后找到了 88 的时候，就可以把它的 Value 对应的磁盘文件地址拿出来，然后就直接去磁盘上去找这一行的数据，这时候的速度就会比全表扫描要快很多。

但实际上 MySQL  底层并没有用二叉树来存储索引数据，是用的 B+tree（B+树）。

为什么不采用二叉树

假设此时用普通二叉树记录  id  索引列，我们在每插入一行记录的同时还要维护二叉树索引字段。

此时当我要找  id = 7  的那条数据时，它的查找过程如下：

此时找  id = 7  这一行记录时找了 7 次，和我们全表扫描也没什么很大区别。显而易见，二叉树对于这种依次递增的数据列其实是不适合作为索引的数据结构。

为什么不采用 Hash 表

Hash 表：一个快速搜索的数据结构，搜索的时间复杂度 O(1)
Hash 函数：将一个任意类型的 key，可以转换成一个 int 类型的下标

假设此时用 Hash 表记录  id  索引列，我们在每插入一行记录的同时还要维护 Hash 表索引字段。

这时候开始查找  id = 7  的树节点仅找了 1 次，效率非常高了。

但  MySQL  的索引依然不采用能够精准定位的Hash 表。因为它不适用于范围查询。

结构

哈希表结构，键值通过哈希函数映射到哈希桶。

原理

直接计算哈希值定位数据，无需遍历层级。
Hash算法通过以下步骤将任意长度的输入映射为固定长度的输出（哈希值）：

1. 输入处理：将输入数据（如字符串、文件）视为二进制流。
2. 分块处理：将输入分成固定长度的块（例如MD5分块为512位）。
3. 初始化：设置初始哈希值（如MD5初始化为特定的十六进制数）。
4. 迭代计算：对每个分块进行循环操作，结合当前哈希值与分块数据，通过位运算（如异或、循环移位、逻辑运算）生成新的哈希值。
5. 最终输出：所有分块处理完成后，输出固定长度的哈希值（如MD5为128位，SHA-256为256位）。

特点

• 等值查询极快：直接定位数据，无需遍历树结构。
• 无序性：键值通过哈希函数计算后，存储位置与原始顺序无关。
• 等值查询(=、IN、<=>)高效：通过哈希值直接定位数据，时间复杂度为 O(1)。
• 不支持范围、排序、模糊查询：

优点

• 等值查询极快：时间复杂度 O(1)，适合主键或唯一键查询。
• 无树结构维护成本：无需平衡树结构，写入简单（无分裂操作）。

缺点

• 不支持范围查询：哈希值无序，无法高效执行 >、<、BETWEEN 等操作。
• 哈希碰撞风险：键值重复或哈希冲突时，退化为链表遍历，性能骤降。
• 必须回表验证：即使定位到哈希桶，仍需回表对比实际数据。
• 联合索引限制：仅支持全列精确匹配，无法利用最左前缀原则。
• 内存依赖性强：哈希表通常需全内存加载，不适用大容量磁盘存储。
• 无法完全避免表扫描：哈希碰撞是导致表扫描的根本原因。

风险

• 哈希桶倾斜：键值分布不均时，部分哈希桶过长，查询性能不稳定。
• 扩容成本高：动态扩容需重新哈希，导致短暂性能下降。

适用场景

• 内存数据库（如 Redis Hash）。
• 等值查询频繁的场景（如缓存系统）。

为什么不采用红黑树

红黑树是一种特化的 AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡；
若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。

假设此时用红黑树记录  id  索引列，我们在每插入一行记录的同时还要维护红黑树索引字段。

插入过程中会发现它与普通二叉树不同的是当一棵树的左右子树高度差 > 1 时，它会进行自旋操作，保持树的平衡。

这时候开始查找  id = 7  的树节点只找了 3 次，比所谓的普通二叉树还是要更快的。

但  MySQL  的索引依然不采用能够精确定位和范围查询都优秀的红黑树。
因为当  MySQL  数据量很大的时候，索引的体积也会很大，可能内存放不下，所以需要从磁盘上进行相关读写，如果树的层级太高，则读写磁盘的次数（I/O交互）就会越多，性能就会越差。

B-tree

红黑树目前的唯一不足点就是树的高度不可控，所以现在我们的切入点就是树的高度。
目前一个节点是只分配了一个存储 1 个元素，如果要控制高度，我们就可以把一个节点分配的空间更大一点，让它横向存储多个元素，这个时候高度就可控了。这么个改造过程，就变成了  B-tree 。”

B-tree 是绝对平衡的多路搜索树，每个节点包含多个关键字和子节点指针，设计用于高效管理大量数据的读写操作

尤其适合磁盘存储、文件系统、部分数据库索引，例如：MongoDB

关键字(数据索引)

关键字的作用： 关键字在 B 树的内部节点中充当路由(Routing) 或 分隔符(Separators)。它们本身可能不是最终的数据记录，而是用于指引搜索路径。

• 键值（Key）：通常指的是用于索引和查找的字段值，例如数据库表的主键（Primary Key）或索引字段的值。
• 多个键值：指的是一个 B 树节点（磁盘块）中，可以存储不止一个关键字，而是多个有序排列的关键字。

B 树中关键字的工作原理

B 树的核心设计在于，它利用节点内的多个关键字将搜索空间高效地划分成多个子空间。
假设一个 B 树的内部节点包含 $k$ 个关键字 $K_1,K_2,\dots ,K_k$，并且有 $k+1$ 个子节点指针 $P_0,P_1,\dots ,P_k$。

1. 关键字的有序排列
   • 节点内的所有关键字都是有序递增排列的：$K_1<K_2<\cdots <K_k$。
2. 关键字与指针的关联（路由工作）
   • 每个关键字 $K_i$ 将左右两侧的搜索空间分开，它的工作是确定一个目标关键字 $X$ 应该进入哪个子节点（子树）：

3. “绝对平衡”与“多路搜索”的体现
   • 多路搜索（Multi-way Search）：正是因为每个节点包含多个键值，并且能根据这些键值做出 $k+1$ 个选择，所以 B 树被称为多路搜索树，而不是像二叉树那样只有 2 个选择。
   • 绝对平衡（Absolutely Balanced）：意味着所有叶子节点（包含数据或数据指针的节点）都位于同一层。这保证了从根节点到任何数据项的查找路径长度（即树高 $h$）是固定的，因此查找操作的性能非常稳定和高效。

B 树（B-tree）的最小阶 $m$ 是 $\mathbf{3}$。

这里的阶 $m$ 指的是一个节点可以拥有的最大子节点数量。

最小阶=3

B 树的基本特性要求它必须是一棵多路搜索树（Multi-way Search Tree）并且是平衡的。
要满足 B 树的性质，阶 $m$ 必须满足以下两个核心条件：

1. 节点能分裂和合并： 这是保持树平衡的关键。
2. 非根内部节点必须有两个及以上的子节点： 否则它就退化成二叉树或更简单的结构。

1. $m=2$（最大子节点数 <=2）

• 最小度 $t$ (最小子节点数) 要求：$t=\lceil m/2\rceil =\lceil 2/2\rceil =1$。
• 非根内部节点关键字数要求：$t-1=1-1=0$。
• 问题： 如果非根内部节点可以只有 1 个子节点（度 $d=1$）和 0 个关键字，那么它就不再是多路搜索树，而是退化成一个单链表，这将失去 B 树的效率和平衡性，查找时间会变成 $O(N)$ 而非 $O(\log N)$。
• 结论： 阶 $m$ 不能等于 2。

2. $m=3$（最大子节点数 <=3）

• 最小度 (最小子节点数) 要求：$t=\lceil m/2\rceil =\lceil 3/2\rceil =2$
• 非根内部节点关键字数要求：$t-1=2-1=1$
  这种 $m=3$ 的 B 树是完全符合 B 树定义的，它就是著名的 2-3 树（2-3 tree，一种特殊的 B 树）。
  因此，为了保证 B 树具有多路搜索的特性和平衡结构，其最小的阶（最大子节点数）必须是 $\mathbf{3}$。

相关名词

参数关系

算法的执行时间主要由读/写磁盘的次数决定，一次I/O操作应尽量读写可能多信息，节点规模一般以一个数据页为单位。一个节点包含的关键字及其子节点取决于数据页的大小。

根节点

• 度个数$d_{root}$满足：$2\le d_{root}\le m$
• 关键字数$k_{root\mathrm{\_}min}$满足：$k_{root\mathrm{\_}min}=1$

非根内部节点

• 关键字个数 $k$ 满足：(最小度称为 $t$)$\frac{m}{2}-1\le k\le m-1$
• 度个数 $d$ 满足： (最小度称为 $t$)$\frac{m}{2}\le d\le m$
• 所有的叶子节点都位于同一层。
• 节点存储数据：非叶子节点和叶子节点均存储数据（部分实现可能不同）。

优点

• 直接访问数据：所有节点（包括非叶子节点）存储键和对应的数据指针，可能在中间层级直接找到数据，减少查询深度。
• 平衡性：通过节点分裂和合并保持树的高度平衡，适合随机读写混合场景。
• 支持范围查询：键值有序，但范围查询效率低于 B+树。

缺点

• 范围查询效率低：叶子节点无链表连接，范围查询需跨层级遍历。
• 树高度较高：非叶子节点存储数据，导致分支因子（Fan-out）降低，树高度增加（如下图树高=4层）。
  
• 写入维护成本高：频繁的分裂和合并操作，影响写入性能。
• 空间利用率低：非叶子节点存储冗余数据，占用更多磁盘空间。

风险

• 数据分布不均：键值分布不均匀时，可能导致部分子树过深，查询效率下降。
• 节点分裂锁竞争：高并发写入时，节点分裂可能引发锁争用，导致性能波动。

适用场景

• 文件系统（如 NTFS、ReiserFS）
• 数据库索引（较少使用，逐渐被 B+Tree 取代）

名字取义（题外话，放松一下）

以下摘自维基百科
鲁道夫·拜尔（Rudolf Bayer）和 艾华·M·麦克雷（Ed M. McCreight）于1972年在波音研究实验室（Boeing Research Labs）工作时发明了  B-tree ，但是他们没有解释 B 代表什么意义（如果有的话）。

道格拉斯·科默尔（Douglas Comer）解释说：两位作者从来都没解释过  B-tree  的原始意义。我们可能觉得 balanced, broad 或 bushy 可能适合。其他人建议字母 B 代表 Boeing。源自于他的赞助，不过，看起来把  B-tree  当作 Bayer 树更合适些。

高德纳（Donald Knuth）在他1980年5月发表的题为 "CS144C classroom lecture about disk storage and B-trees" 的论文中推测了  B-tree  的名字取义，提出 B 可能意味 Boeing 或者 Bayer 的名字。

查找

B 树查找本质上是二叉树(Binary Search Tree)查找思想的多路泛化。

1. 二叉树节点只有 $1$ 个关键字和 $2$ 个分支，查找时只做左或右的二路决策。
2. 而 B 树节点拥有 $k$ 个关键字和 $(k+1)$ 个分支，查找时通过关键字比较，从多个分支中精确选择一条路径，进行多路决策。
   B 树查找的核心是分两级进行：
3. 节点查找（磁盘 I/O）：
   • 将目标节点从磁盘读取到内存中。
4. 关键字查找（内存操作）：
   • 在内存中的节点内，使用二分查找（折半查找）定位关键字。
   • 若找到则结束；若未找到，根据关键字大小判断并选择正确的子节点指针，回到第 1 步继续查找。

操作流程

现在需要查找元素：88
第一次：磁盘IO

第二次：磁盘IO

第三次：磁盘IO
然后这有一次内存比对，分别跟 70 与 88 比对，最后找到 88。

B 树的关键优势在于：

1. 分层计算：B 树将耗时巨大的磁盘 I/O（节点间跳转）与快速的内存比对（节点内查找）清晰分离。
2. 降低树高：由于 B 树一个节点能存储大量关键字（由阶决定），相同数据量下，它生成的节点总数远少于二叉树。
3. 核心优势：B 树通过大幅减少节点数量，从而极大地降低了必需的磁盘 I/O 次数，这正是其优于二叉树的性能优势所在。

插入

当  B-tree  要进行插入关键字时，都是直接找到叶子节点进行操作。

1. 根据要插入的关键字查找到待插入的叶子节点；
2. 因为一个节点的子节点的最大个数（阶）为 $m$，所以需要判断当前节点关键字的个数是否小于 $(m-1)$。
   • 是：直接插入
   • 否：发生节点分裂，按中间关键字分裂成左右两部分，中间关键字分裂到父节点当做索引存储。

以3阶树举例

叶子节点

插入元素：72

1. 查找待插入的叶子节点
   
2. 节点分裂
   关键字72插入到[70,88]节点后，后元素数量超过了2个，准备进行分裂；
   以中间关键字分裂，中间关键字分裂到父节点当做索引存储。

Tip: 当中间关键字有两个时，通常将左关键字进行上移分裂。

删除

删除操作比查找和插入复杂，原因在于：

1. 关键字位置不确定：待删除的关键字可能位于内部节点（作为索引）或叶子节点（作为数据）。
2. 维护平衡：删除后可能导致节点中的关键字数量低于最小限制，必须通过复杂的旋转（借键） 或合并操作来重新平衡 B 树，以维持其高性能特性。

以5阶树举例

根节点

内部节点

删除非叶子节点的元素后合并+旋转

删除目标：12

1. 查找元素 12 位置
   
2. 移除 12 后，违背  B-tree  对节点内关键字的要求
   对于非叶子节点元素的删除，我们需要用后继元素覆盖要被删除的元素，然后在后继元素所在的叶子中删除该后继元素。
   

叶子节点

直接删除

删除目标：50

1. 查找元素 50 位置
   
2. 在 [36, 50, 63] 节点移除 50 后，依然符合  B-tree  对节点内关键字的要求：$\frac{m}{2}-1\le k\le m-1$「$2\le 2\le 4$ 」
   
3. 删除完成

旋转

eg1：删除目标：11「兄弟节点有元素可借」

1. 查找元素 11 位置
   
2. 在 [10, 11] 节点移除 11 后，违背  B-tree  对节点内关键字的要求：$\frac{m}{2}-1\le k\le m-1$「$2\le 1\le 4$」
3. 需向兄弟节点(左节点优先借，不足则借右节点) 借关键字14进行移动，但不可能让10和14放一起，因为  14 > 12  ，这时候就要进行旋转「将父节点的元素 12 移到该节点，然后 12 就让位给14」
   
4. 删除完毕
   

合并+旋转

eg2：接着删除 10「兄弟节点无元素可借」

1. 在 [10, 12] 节点移除 10 后，违背  B-tree  对节点内关键字的要求
2. 需要向兄弟节点借元素，但兄弟节点无富余，将父节点的元素 8 移到该节点，这时候 3、6、8、12 都小于14，就先把它们放一起
   
3. 父节点只剩个14，违背了 B-tree 对节点内关键字的要求，将父节点的元素 20 移到该节点，这时候根节点都直接没了，直接合并 14、20、26、72 关键字
   
4. 删除完成
   

B+tree

结构

B-tree 的变种，叶子节点包含所有数据并形成有序链表。

特点

• 非叶子节点：仅作为索引，存储关键字和子节点指针。
• 叶子节点：存储所有关键字、数据、相邻的叶节点的指针，并通过指针形成双向链表。
• 叶子节点有序：数据按关键字排序，支持快速范围查询和排序。
• 平衡规则：分裂时仅复制键到父节点，维护成本低于 B树。
• 更高的扇出(Fan-out)：非叶子节点不存储数据，可容纳更多键，降低树的高度。

优点

• 范围查询高效：叶子节点通过指针形成双向链表，支持快速顺序访问。
• 覆盖索引优化：仅需访问叶子节点即可返回数据，减少回表查询。

缺点

• 等值查询略慢于 Hash：需从根节点遍历到叶子节点，时间复杂度为 $O(\log n)$。
• 空间占用：非叶子节点存储冗余键，占用额外空间。
  1. 当一个关键字作为数据键存储在叶子节点时，它必须是完整的。
  2. 同时，为了引导搜索路径，这个关键字（或它的一个副本）会被提升到内部节点中，充当分隔符。
  3. 一旦通过内部节点找到了范围的起点（第一个叶子节点），后续的查询（例如查找 $100$ 到 $200$ 之间的所有记录）只需要在叶子节点链表上顺序遍历，完全不需要再回到内部节点进行 I/O 操作。

风险

• 树高度增加：数据量极大时，树高度可能增长（需定期优化索引或分库分表）。
• 热点写入竞争：顺序插入可能导致叶子节点频繁分裂（如自增主键场景）。

适用场景

• 现代数据库索引（如 MySQL InnoDB、PostgreSQL）。
• 文件系统（如 Ext4、XFS）。

查找

B+tree  最大的优势就在查找上，主要是范围查询更加明显。

1. B-tree 节点中的每个关键字都有数据，而 B+tree 中间节点没有数据，只有索引；这就意味着相同大小的数据页可以放更多的节点元素，也就是在相同的数据量下，I/O 操作更少
2. 在范围查询上，B-tree 需要先找到指定范围内的下限，再找到上限，有了这两个过程后再取出它们之间的元素。B+tree 因为叶子节点通过双向链表进行连接，找到指定范围内的下限后，直接通过链表顺序遍历就行，这样就方便很多了。

在查询单个关键字上，和  B-tree  差不多：先把通过磁盘 I/O 找到节点，再把节点加载到内存中进行内部关键字比对，然后通过大小关系再决定接下来走哪个分支。
但是差别就在于  B+tree  的高度更加可控一些。 MySQL  默认给一个数据页数据分配的大小是 16KB，也就是 16 × 1024 = 16384 字节
官网说明：MySQL :: MySQL 5.7 Reference Manual :: 14.6.2.2 The Physical Structure of an InnoDB Index
证明：直接在数据库中通过  SQL  语句  show GLOBAL STATUS LIKE 'INNODB_page_size' 进行验证

+----------------+-----+
|Variable_name   |Value|
+----------------+-----+
|Innodb_page_size|16384|
+----------------+-----+

当我们的叶子节点全部撑满之后，可以来算一算它树的高度。

我们拿阿里的《Java 开发手册》嵩山版中对表主键的要求进行举例

bigint 64位 占 8Byte，索引旁边放指向下一节点的磁盘文件地址那块是6Byte，是  MySQL  底层写死了的。

通过计算：16384 Byte / (8+6) Byte ≈ 1170，也就是说一个节点设置 16KB 大小的话可以放 1170个索引。

叶子节点一个关键字占用1KB时，那一个节点就可以放16个元素，当整棵树叶子节点全部都被撑满时，通过计算  1170 × 1170 × 16 = 21902400
最后结果为2千多万，树的高度才为3，也就是我们要的高度可控。这也就是为什么  MySQL  的表有上千万数据的情况下，查询效率依然快的原因。

插入

节点内元素数量大于$(m-1)$ 时，按中间关键字分裂成左右两部分，中间关键字分裂到父节点当做索引存储，因叶子节点包含所有索引，所以本身它还会分裂至右边部分。

以5阶树举例

内部节点

1. 插入关键字：13
   
2. 关键字13插入到 [9, 10, 11, 12, 13] 节点后元素数量超过了4个，准备进行分裂；
   以中间关键字(11)分裂，中间关键字分裂到父节点当做索引存储，本身它也还会分裂右边部分。
   
3. 关键字11 被挪到父节点去之后，节点内元素数量超过了4个，准备进行分裂；
   以中间关键字(7)分裂，中间关键字分裂到父节点当做（冗余）索引存储。
   
4. 插入完成
   

叶子节点

1. 第一次在空树中插入 1
   
2. 再依次插入 2,3,4
   
3. 插入 5
   当插入关键字 5 时，此时节点内元素数量大于 (5-1) ，即超过了4个，这时候就要进行分裂；
   以中间关键字分裂，中间关键字分裂到父节点当做索引存储，由于叶子节点包含所有索引数据，所以本身它还会分裂至右边部分。
   

删除

删除对应节点关键字后，也需要看看节点内剩余关键字是否符合：$\frac{m}{2}-1\le k\le m-1$

• 符合：直接删除
• 不符合：与 B-tree 一样需向兄弟节点借元素，主要利用叶子节点链表和父节点进行
  1. 节点间转移（旋转）：利用叶子节点链表，直接与兄弟节点进行关键字借用，完成后更新父节点分隔符。
  2. 节点合并：若兄弟节点无法借出关键字，则将当前节点与兄弟节点合并，并从父节点中删除相应的分隔关键字。

根节点

根节点是唯一一个可以不必满足最小度 $t$ 约束的非叶子节点。
1. 树高度降低

• 条件： 合并操作一直递归，导致根节点关键字被全部删除（关键字数 $=0$），并且它只剩下一个唯一的子节点 $C$。
• 调整： 将子节点 $C$ 提升为新的根节点。
• 结果： B+ 树的高度减少 1。
  目标删除关键字：8
  

1. 删除关键字8后，不满足关键字要求：「$2\le 1\le 4$」
2. 这时兄弟节点均无富余，就直接与和兄弟节点合并 「合并关键字 [5, 6, 10]」，再删除父节点中的关键字「删除父节点中的关键字 10」
   
3. 这时关键字5的节点，不满足关键字要求：「$2\le 1\le 4$」
   
4. 这时兄弟节点均无富余，就直接与和兄弟节点合并 「合并关键字 [13, 15]」，此时根节点剩下一个唯一的子节点 [5, 13, 15]，合并根节点[11]，将子节点 [5, 11, 13, 15] 提升为新的根节点。
   
5. 完成删除
   
   2. 正常结束

• 条件： 根节点在丢失关键字后，关键字数量仍 $\ge 1$。
• 结果： 调整结束。
  目标删除关键字：3
  

1. 删除关键字3后，不满足关键字要求：「$2\le 1\le 4$」
2. 这时兄弟节点均无富余，就直接与和兄弟节点合并 「合并关键字 [1, 2, 4]」，再删除父节点中的关键字「删除父节点中的关键字 3」

叶子节点

删除操作总是发生在叶子节点。当删除一个记录后，如果叶子节点发生亏损（关键字数 $<t-1$）：

1. 借用（旋转）

• 条件： 相邻的兄弟节点 $S$ 有富余（关键字数 $>t-1$）。
• 调整： 将兄弟节点 $S$ 中靠近 $N$ 的一个记录移动到亏损节点 $N$ 中，同时更新父节点中作为 $N$ 和 $S$ 分隔符的关键字。
• 结果： 两个叶子节点都恢复合法，树结构高度不变。
  目标删除关键字：14

1. 删除关键字14后，不满足关键字要求：$\frac{m}{2}-1\le k\le m-1$「$2\le 1\le 4$」
2. 直接从兄弟节点(左节点优先借，不足则借右节点) 借关键字进行移动，然后再更新父节点的索引
   
3. 删除完成
   

2. 合并

• 条件： 兄弟节点 $S$ 没有富余（关键字数 $=t-1$）。
• 调整： 将亏损节点 $N$ 中的所有记录合并到 $S$ 中，然后删除 $N$。随后，必须删除 $N$ 在父节点中对应的指针和分隔关键字。
• 结果： 父节点会丢失一个关键字和一个子节点，这可能导致父节点也发生亏损，需要向上递归调整。
  接着删除元素：16

1. 删除 16 关键字后，它所在的节点只剩 17 一个关键字了，又要准备借关键字；
2. 这时兄弟节点均无富余，就直接与和兄弟节点合并 「合并关键字 [13, 15, 17]」，再删除父节点中的关键字「删除父节点中的关键字 16」
   
3. 删除完成
   

总结

1. 单个节点存储越多的元素，自然在整个过程中的磁盘I/O交互就越少；
2. 相对 B-tree 来说，所有的查询最终都会找到叶子节点，这也是 B+tree 性能稳定的一个体现；
3. 所有叶子节点通过双向链表相连，范围查询非常方便，这也是 B+tree 最明显的优势。

B+tree  vs  B-tree

特性	B 树 (B-tree)	B+ 树 (B+tree)
数据存储位置	所有节点（包括内部节点和叶子节点）都可以存储实际数据（数据记录或指向数据的指针）。	实际的数据记录（或指向数据的指针）只存储在叶子节点。 包括：关键字、指向数据行的指针（如磁盘地址或数据行的指针）
内部节点作用	既充当索引，又存储部分数据。	只充当索引（关键字）和路由（指针）。不存储实际数据。
关键字冗余	关键字不冗余。内部节点的关键字不重复出现在叶子节点。	内部节点用作索引的关键字冗余。所有关键字都会出现在叶子节点中。
范围查询效率	效率较低。进行范围查找时，需要对树的每一层都进行遍历，效率不稳定。	效率极高（核心优势）。所有叶子节点构成双向链表，只需定位到范围起点，然后沿链表顺序遍历即可。
查询效率	每次查询，数据可能存储在任何节点，查询性能不稳定（最好情况 1 次 I/O，最差情况 $h$ 次 I/O）。	数据只在叶子节点，任何查找都需要从根到叶子，查询性能稳定（总是 $h$ 次 I/O，其中 $h$ 是树的高度）。
磁盘 I/O	内部节点存储数据，导致节点能容纳的关键字和指针数量较少，树的高度可能更高。	内部节点只存储关键字和指针，扇出（Fanout）能力强，节点能容纳更多索引，树的高度更低，减少磁盘 I/O。
进行范围查找时需要获取所有节点，相比之下  B+tree  效率更高。
上图不够完善，更完善的B+tree 底层实际具体的数据结构如下图(每个节点都被称作一个数据页)

数据页

InnoDB 如何存储数据

虽然数据库记录按行存储，但 InnoDB 的 I/O 最小单位是 数据页（默认 16KB）。这意味着：
数据库 I/O 并非以行为单位，而是以页为单位，一次最少读写 16KB 内容到内存或磁盘，以提高效率。

数据页「默认16KB」

页目录 (Page Directory)

1. 物理与逻辑：数据页采用链表结构实现逻辑连续，无需物理连续存储。
2. 记录组织：页内记录按主键顺序组成单向链表，便于增删。
3. 检索优化：为提高检索效率，数据页设有页目录，作为记录的索引，实现快速定位，避免全链表扫描。

页目录与记录的关系图

查找机制

查找示例

1. 第一次二分 (槽间定位):
   • 目标： 查找 $0$ 到 $4$ 号槽的中间位。
   • 定位： 槽 $(0+4)/2=\mathbf{2}$ 号。
   • 判断： 2 号槽最大记录为 $8$。由于 $11>8$，搜索范围缩小到 $3\sim 4$ 号槽。
2. 第二次二分 (精确定位):
   • 目标： 查找 $3$ 到 $4$ 号槽的中间位。
   • 定位： 槽 $(2+4)/2=\mathbf{3}$ 号（取整，或根据具体算法）。
   • 判断： 3 号槽最大记录为 $12$。由于 $11<12$，确定目标记录在 $\mathbf{3}$ 号槽内。
3. 槽内遍历 (顺序查找):
   • 起点： 从 3 号槽指向的记录（主键 $9$）开始。
   • 查找： 顺序遍历该槽内的记录，向下搜索 $\mathbf{2}$ 次，找到主键为 $11$ 的记录。
     核心流程： 两次二分 (槽间) $\to$ 一次顺序遍历 (槽内)。

MySQL 的数据物理存储

MySQL 的数据物理存储方式，尤其是在有索引和无索引时，主要取决于所使用的存储引擎。最常见的两个引擎是 InnoDB 和 MyISAM，它们在这方面有根本的区别。

核心概念：聚簇索引 vs. 非聚簇索引

理解数据物理存储的关键在于理解这两种存储引擎如何组织数据和主键索引。

InnoDB 引擎（主流选择）

InnoDB 采用聚簇索引结构，这是理解其存储的关键。

无索引时（本质上仍有索引）

在 InnoDB 中，一张表必须且只能有一个聚簇索引。

• 如果表定义了主键 (Primary Key)：该主键就是聚簇索引。数据行会根据主键的顺序在磁盘上进行物理存储。
• 如果没有定义主键：
  1. MySQL 会寻找一个非空唯一索引 (Unique NOT NULL) 作为隐式的主键。
  2. 如果以上都没有，MySQL 会自动生成一个 6 字节的隐式行 ID 作为聚簇索引。
• 物理存储：无论如何，数据行总是按照聚簇索引的键值在物理上进行排序和存储。

有索引时

主键索引 (Primary Key Index / 聚簇索引)

• 结构：一个 B+ 树。
• 叶子节点：存储了整行数据记录。即数据和索引键值是存储在一起的。
• 查找过程：通过主键查找时，只需进行一次 B+ 树搜索，即可直接找到并读取完整的数据行。

辅助索引 (Secondary Index / 非聚簇索引)

• 结构：也是一个 B+ 树。
• 叶子节点：存储辅助索引的键值以及对应记录的（主键值）。
• 查找过程（回表）：
  1. 通过辅助索引 B+ 树进行搜索，找到对应的主键值。
  2. 拿着这个主键值，再到主键索引（聚簇索引）B+ 树中进行第二次搜索，才能找到完整的行数据。这个过程称为回表查询。

MyISAM 引擎（较少使用）

MyISAM 采用非聚簇索引结构，数据和索引是完全分离的。

无索引时

• 数据物理存储：数据行是按照插入的顺序，顺序地存放在数据文件（.MYD）中。
• 查询：进行全表扫描（Full Table Scan），顺序读取 .MYD 文件中的所有数据行。

有索引时

主键索引 (Primary Key Index / 非聚簇索引)

• 结构：一个 B+ 树。
• 叶子节点：存储主键的键值以及对应数据记录在 .MYD 文件中的物理地址（指针）。
• 数据文件：数据行本身依然是按插入顺序存放的。

辅助索引 (Secondary Index / 非聚簇索引)

• 结构：一个 B+ 树。
• 叶子节点：存储辅助索引的键值以及对应数据记录在 .MYD 文件中的物理地址（指针）。
• 查找过程：无论通过主键还是辅助索引查找，都是：
  1. 通过 B+ 树搜索，找到对应数据行的物理地址。
  2. 利用该地址，从 .MYD 文件中直接读取数据行。无需像 InnoDB 那样进行回表操作。

叶子节点的双向链表是逻辑上连续的

MySQL InnoDB 存储引擎中，B+ 树叶子节点之间连接的双向链表是逻辑上连续的，但在物理上通常是不连续的。

逻辑上的双向链表

• 含义： 叶子节点中的每一条记录（数据行）都包含一个指针（next_record），指向该数据页内主键值大于它的下一条记录。当一个数据页的最后一条记录指向下一个数据页中的最小记录时，就构成了整个叶子层面的双向链表。
• 作用： 确保了在进行范围查询和全索引扫描时，能够沿着主键的顺序逻辑地遍历所有数据，这是 B+ 树高效范围查询的基础。

物理上的不连续性

• 存储单位： InnoDB 的最小存储单位是页（通常 16KB）。叶子节点就是存储在这些数据页中的。
• 页的分布：
  • 随着数据的插入、删除和更新，数据页可能在磁盘上分配到不连续的物理位置（磁盘块或扇区）。
  • 虽然 B+ 树的叶子节点在逻辑上按主键排序，但它们在磁盘上的物理位置是分散的。
• 影响： 当遍历叶子链表从一个数据页跳转到另一个数据页时，可能需要进行一次随机磁盘 I/O 来加载下一个页。

小结

• 逻辑上的双向链表： 保证了数据的顺序访问性。
• 物理上的不连续存储： 页在磁盘上是随机存放的，但这种设计是为了更灵活地管理磁盘空间和应对数据的动态变化。

总结

B+ 树的查询

InnoDB 的索引策略总结

InnoDB 里的 B+ 树中的每个节点都是一个数据页，结构示意图如下：

通过上图，我们看出  B+ 树的特点：

• 只有叶子节点（最底层的节点）才存放了数据，非叶子节点（其他上层节）仅用来存放目录项作为索引。
• 非叶子节点分为不同层次，通过分层来降低每一层的搜索量；
• 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询；

聚簇/非聚簇索引

主键索引（聚簇索引）

• 定义：数据与索引存储在同一棵 B+ 树中，InnoDB引擎叶子节点直接存放完整的数据行(MyISAM引擎是存放数据地址)。
• 特点：
  • 主键必须唯一且非空 （若无主键，InnoDB 自动创建隐藏的 row-id）。
  • 由于数据在物理上只会保存一份，所以聚簇索引只能有一个
  • 数据物理存储顺序与主键索引的逻辑顺序一致。
  • 查询主键时，一次 I/O 获取数据「根节点和中间节点已缓存时」，范围查询（如 WHERE id BETWEEN 1 AND 100）高效。

二级索引（非聚簇索引）

• 定义：索引与数据分开存储，InnoDB引擎叶子节点 索引列的值 + 主键值（即 index_column + primary_key） (MyISAM引擎是存放数据地址)。
• 特点：
  • 需要两次 I/O 获取数据「根节点和中间节点已缓存时」，先查索引找到主键，再通过主键查数据，即“回表”。
    (MyISAM引擎 通过索引查询到数据地址直接获取数据，无需回表)
  • 可以覆盖非主键字段的查询需求，但需通过主键回表获取完整数据。
  • 可通过覆盖索引（索引本身包含所需字段）避免回表。
    二级索引的 B+ 树如下图，数据部分为主键值：
    

叶子节点内容

InnoDB 与 MyISAM 的对比

实际场景举例

• 理想情况：聚簇索引的根节点和中间节点已缓存在内存中，查找主键时直接定位到叶子节点（数据页），仅需 1 次磁盘 I/O。
• 实际场景：若树高为 3 且中间节点未缓存，则需要 3 次 I/O，但数据库通过 缓存机制（如缓冲池）显著减少实际磁盘访问次数。

1. InnoDB 聚簇索引查询

SELECT * FROM user WHERE id = 5;  -- 一次 I/O，直接通过主键索引找到数据。

2. InnoDB 非聚簇索引查询

SELECT * FROM user WHERE name = '张三';  
-- 两次 I/O：1. 通过 `name` 索引找到主键 `id=5`；2. 通过主键查数据。

3. MyISAM 索引查询

SELECT * FROM user WHERE age = 25;  
-- 一次 I/O：通过 `age` 索引直接找到行号，定位到数据文件。

设计原则

• 聚簇索引选择频繁查询的字段（如订单号、用户 ID）。
• 避免在 InnoDB 中频繁更新主键，否则会导致数据页分裂。
• 通过覆盖索引（索引包含所需字段）减少回表次数，提升性能。

总结

1. I/O 基本单位：InnoDB 以 数据页（默认 16KB）为最小 I/O 单位。
2. 页间组织：数据页间通过双向链表实现逻辑连续，物理可不连续。
3. 页内优化：页内记录按主键顺序由单向链表连接；通过页目录（槽/分组）和二分查找实现页内记录的高效检索。
4. 页间索引（B+ 树）：采用 B+ 树作为索引，每个节点对应一个数据页，用于高效定位数据页。
5. 索引分类：
   • 聚簇索引：B+ 树叶子节点存储实际数据，每表只有一个。
   • 二级索引：B+ 树叶子节点存储主键值，每表可有多个。
6. 二级索引查找优化：
   • 索引覆盖：所需数据全部在二级索引中找到，避免回表。
   • 回表：二级索引查到主键后，需通过聚簇索引二次查找获取完整数据行。