B+树简介

B + 树：多路搜索树的优化变体与数据库索引核心

B + 树是 B - 树的改进版本，作为一种多路平衡搜索树，它在 B - 树的基础上强化了对范围查询的支持和存储效率，成为数据库索引（如 MySQL InnoDB、PostgreSQL）和文件系统的核心数据结构。其设计充分适配磁盘 IO 特性，通过有序的叶子节点链表和集中存储的数据，实现高效的单点查询和范围查询。

B + 树的核心特点

m 阶 B + 树（m 为阶数，即节点最多的子节点数）具有以下关键特性：

节点结构：
- 每个非叶节点（索引节点）最多有m个子节点，存储m个关键字（用于索引子节点范围）。
- 非根节点的关键字数量k满足：⌈m/2⌉ ≤ k ≤ m（⌈m/2⌉为向上取整，保证节点不过于稀疏）。
数据存储：
- 所有实际数据（记录）仅存储在叶子节点，非叶节点仅作为索引（不存数据）。
- 叶子节点按关键字大小有序排列，且相邻叶子节点通过双向链表连接（形成有序链表），便于范围查询。
平衡性：
- 所有叶子节点位于同一层，保证查询效率稳定（最坏情况与平均情况性能一致）。

示例：3 阶 B + 树结构

          [10, 20]       // 非叶节点（索引节点）：2个关键字，3个子节点
         /    |    \
[5,10] <-> [15,20] <-> [25,30]  // 叶子节点（数据节点）：双向链表连接，存储所有记录

非叶节点[10,20]的关键字用于划分范围：左子节点存储≤10 的记录，中间存储 10~20 的记录，右子节点存储≥20 的记录。
叶子节点[5,10]、[15,20]、[25,30]通过指针串联，支持从 5 到 30 的连续范围查询。

B + 树的插入操作

B + 树的插入仅在叶子节点进行，插入后需保持节点有序和平衡性，核心处理 “节点溢出”（关键字数量超过m）的情况。

插入步骤（分三种情况）

情况 1：Leaf Page（叶子节点）和 Index Page（索引节点）均未满

直接将记录插入叶子节点的对应位置（保持有序），插入后关键字数量≤m。

情况 2：Leaf Page 满，Index Page 未满

拆分 Leaf Page：将满的叶子节点从中间关键字（第⌈m/2⌉个）拆分为两个节点：
- 左节点包含前⌊m/2⌋个关键字（⌊m/2⌋为向下取整）；
- 右节点包含剩余⌈m/2⌉个关键字。
上移中间关键字：将中间关键字插入其父 Index Page（索引节点），此时 Index Page 关键字数量仍≤m，插入完成。

情况 3：Leaf Page 满，Index Page 也满

先按情况 2 拆分 Leaf Page，上移中间关键字到 Index Page，导致 Index Page 溢出（关键字数量 = m+1）。
拆分 Index Page：将满的索引节点从中间关键字拆分为两个节点，中间关键字上移至更上层索引节点。
若上层索引节点仍溢出，重复拆分过程，直至根节点（根节点拆分后树高 + 1）。

优化：旋转操作减少拆分

若 Leaf Page 满但兄弟节点未满，优先将记录 “旋转” 到兄弟节点（而非直接拆分），减少磁盘 IO（拆分需写入新节点，旋转仅调整指针）。

B + 树的删除操作

B + 树的删除同样在叶子节点进行，需保证删除后节点关键字数量不低于⌈m/2⌉（填充因子≥50%），核心处理 “节点下溢”（关键字数量不足）的情况。

删除步骤（分三种情况）

情况 1：叶子节点和索引节点均不低于填充因子

直接删除叶子节点中的记录，若删除的是索引节点中的关键字（仅作为索引），用其右子节点的最小关键字替代（保持索引范围正确）。

情况 2：叶子节点下溢（<⌈m/2⌉），索引节点未下溢

尝试借调：若相邻兄弟节点关键字充足，从兄弟节点 “借” 一个关键字（同时调整父索引节点的分隔关键字）。
借调失败则合并：将当前叶子节点与兄弟节点合并（合并后关键字数量≤m），并删除父索引节点中对应的分隔关键字。

情况 3：叶子节点下溢，索引节点也下溢

按情况 2 合并叶子节点和兄弟节点，导致父索引节点关键字数量不足（下溢）。
合并索引节点：将下溢的索引节点与兄弟节点合并，删除上层索引节点的对应关键字。
若上层索引节点仍下溢，重复合并过程，直至根节点（根节点合并后树高可能 - 1）。

B + 树与 B - 树的核心区别

特性	B - 树	B + 树
数据存储位置	非叶节点和叶子节点均存储数据	仅叶子节点存储数据，非叶节点仅作索引
叶子节点连接	无关联	相邻叶子节点通过双向链表连接
查找结束位置	找到关键字所在节点即结束	必须遍历到叶子节点（数据唯一存储处）
关键字出现次数	每个关键字仅出现一次	索引节点的关键字在叶子节点中重复出现
非叶节点关键字数	有`k`个子节点则有`k-1`个关键字	有`k`个子节点则有`k`个关键字（对应子节点范围）
范围查询支持	需回溯父节点，效率低	通过叶子节点链表直接遍历，效率高

B + 树的优势与应用场景

核心优势

高效范围查询：叶子节点有序且链表连接，支持WHERE id BETWEEN a AND b等范围查询，无需回溯。
查询效率稳定：所有查询均需遍历到叶子节点，最坏时间复杂度与平均一致（O(logₘn)）。
适配磁盘 IO：非叶节点仅存索引，单个节点可存储更多关键字，树高更低（减少 IO 次数）；叶子节点集中存储数据，便于批量读取。

典型应用

数据库索引：MySQL InnoDB 的聚簇索引、PostgreSQL 的 B + 树索引均基于 B + 树，支持高效的单点查询和范围查询。
文件系统：用于目录索引，快速定位文件路径。

总结

B + 树通过 “数据集中存储于叶子节点” 和 “叶子节点链表化” 的设计，解决了 B - 树范围查询效率低的问题，同时保持了多路平衡树的低 IO 特性。其插入 / 删除时的拆分与合并逻辑保证了结构平衡，使查询性能稳定高效，成为大规模数据存储（尤其是数据库）的首选索引结构