B-树简介

B - 树（B 树）：多路平衡查找树的磁盘优化设计

B - 树（B 树）是一种多路平衡查找树，专为磁盘等外存设备设计，通过降低树的高度减少磁盘 IO 次数，广泛应用于数据库索引（如 MySQL 的 InnoDB 引擎）和文件系统。与二叉树相比，B 树允许每个节点包含多个关键字和子树，在相同数据量下具有更低的高度，显著提升大规模数据的查询效率。

B - 树的核心概念

关键术语

阶数（m）：B 树的阶数是指一个节点最多可拥有的子节点数量（即多路的 “路数”）。例如，m 阶 B 树的一个节点最多有 m 个子节点。
关键字：节点中存储的用于查找的数值（如数据库中的索引键），每个关键字对应一条记录或指向记录的指针。
度：一个节点实际拥有的子节点数量（≤ 阶数 m）。

m 阶 B 树的定义与特性

一个 m 阶 B 树需满足以下属性，以保证平衡性和高效查找：

节点结构：
- 每个非叶节点包含 k-1 个关键字和 k 个子节点（k 为该节点的度，2 ≤ k ≤ m）。
- 关键字按升序排列：key₁ < key₂ < ... < keyₖ₋₁，且第 i 个子节点中的所有关键字均满足 keyᵢ₋₁ < 子节点关键字 < keyᵢ（边界关键字除外）。
根节点特殊规则：
- 根节点至少有 2 个子节点（k ≥ 2），除非树中仅含根节点（空树或仅一个节点）。
非根节点规则：
- 每个非根节点的度 k 满足：⌈m/2⌉ ≤ k ≤ m（⌈m/2⌉ 表示向上取整，如 m=5 时，⌈5/2⌉=3）。
- 关键字数量 j 满足：⌈m/2⌉ - 1 ≤ j ≤ m - 1（如 m=5 时，关键字数量为 2~4）。
叶子节点：
- 所有叶子节点位于同一层（平衡特性），且不含子节点（或子节点为 null）。

示例：3 阶 B 树

3 阶 B 树（m=3）的特性：

每个非根节点的度 k 满足 2 ≤ k ≤ 3（⌈3/2⌉=2）。
关键字数量 j 满足 1 ≤ j ≤ 2（⌈3/2⌉ - 1 = 1，m-1=2）。

结构示例：

        [15, 30]       // 根节点：2个关键字，3个子节点（k=3）
       /   |   \
[5,10]  [20,25]  [35,40]  // 叶子节点：每个含2个关键字，无子节点

B - 树的优势：为何优于二叉树？

降低树高，减少磁盘 IO

二叉树（如 AVL 树）的高度为 O(log₂n)，而 m 阶 B 树的高度为 O(logₘn)。
例如，存储 100 万条数据时：
- 二叉树高度约 20（2²⁰ ≈ 100万）。
- 100 阶 B 树高度仅 3（100³ = 100万）。
磁盘 IO 次数与树高成正比，B 树能显著减少 IO 操作（机械硬盘的 IO 成本远高于内存操作）。

适配磁盘存储特性

磁盘以 “块” 为单位读写（如 4KB / 块），B 树的节点大小通常设计为与磁盘块一致，每个节点的关键字和子节点指针可一次性读入内存，减少 IO 次数。
二叉树的每个节点仅含 1 个关键字，读取效率低（相同数据量需更多 IO）。

B - 树的基本操作

1. 查找

过程：从根节点开始，根据关键字的大小选择子节点（如查找值 x 时，若 keyᵢ₋₁ < x < keyᵢ，则进入第 i 个子节点），递归直至叶子节点。
时间复杂度：O(logₘn)，取决于树高和每个节点的关键字查找（通常用二分法，O(logk)，k 为节点关键字数）。

2. 插入

核心：插入后需保持 B 树的平衡性，若节点关键字数量超过 m-1，则触发分裂：
1. 将节点从中间关键字（⌈m/2⌉ 位置）分为左、右两个子节点。
2. 中间关键字上升至父节点，若父节点也溢出，则继续分裂，直至根节点（根节点分裂会使树高 + 1）。
示例：3 阶 B 树插入关键字 22 导致节点 [20,25] 溢出（关键字数 = 3 > 2），分裂为 [20] 和 [25]，中间关键字 22 上升至父节点。

3. 删除

核心：删除后需保证节点关键字数量不低于⌈m/2⌉ - 1，若不足则需合并或借调：
1. 借调：从相邻兄弟节点借一个关键字（需调整父节点的分隔关键字）。
2. 合并：若借调失败，将当前节点与兄弟节点合并，并删除父节点中对应的分隔关键字（可能导致父节点下溢，需递归处理）。

B - 树的应用场景

数据库索引：如 MySQL 的 InnoDB 引擎使用 B + 树（B 树的变种）作为聚簇索引，加速数据查询。
文件系统：用于目录索引，快速定位文件位置。
大型索引服务：如搜索引擎的倒排索引，处理海量关键词查询。

B - 树与 B + 树的区别（扩展）

B + 树是 B 树的优化变种，更适合数据库场景：

B + 树的叶子节点串联成链表，支持范围查询（如 WHERE id BETWEEN 100 AND 200）。
B + 树的非叶子节点仅作索引，不存储实际数据，所有数据均在叶子节点，查询效率更稳定。

总结

B - 树通过 “多路平衡” 设计，在相同数据量下比二叉树具有更低的高度，大幅减少磁盘 IO 次数，是外存存储的核心数据结构。其 m 阶特性保证了节点的平衡性和高效的插入、删除、查找操作，为数据库和文件系统的高性能提供了基础