当前位置：首页 > ds >正文

磁盘存储链式的 B 树与 B+ 树

ds 2025/5/14 15:39:45

🧭 本节目标

理解 B 树与 B+ 树出现的背景和适用场景
学会区分它们在结构和访问方式上的核心区别
分析为何 B+ 树更适合用于磁盘存储
引导手动实现一个简单的 B 树（插入、查找）版本，打下基础

一、为什么红黑树不适合磁盘？

在内存中，红黑树表现优秀。但在磁盘或 SSD 上的大规模数据结构中，它就不那么合适了：

❌ 原因一：红黑树高度偏高

红黑树高度 ≈ 2 log₂(n)，虽然比链表强，但访问节点太多
每次查找都需要跳转多个节点，而每跳一次就可能触发一次磁盘 I/O，代价巨大

❌ 原因二：节点小，不适合块式存储

红黑树节点小（通常是一个 key + 两个指针）
无法利用磁盘或页缓存的块读取优势，不符合局部性原理

二、B 树的提出：为磁盘设计的树结构

🔑 B 树（Balanced Tree）最早由 Bayer 和 McCreight 于 1972 年提出。

✅ 它的目标：

让每个节点尽可能大（例如一个 4KB 页），减少磁盘访问次数
每个节点存储多个 key，从而大大降低树的高度

三、B 树结构定义（以 m 阶为例）

一个 m 阶 B 树满足以下条件：

每个节点最多有 m 个子节点，m ≥ 3
每个非叶子节点最少有 ⌈m/2⌉ 个子节点
每个节点中存储 k 个 key，满足：k = 子节点数 - 1
所有叶子节点在同一层（平衡性）
节点 key 保持升序排列

📐 举例：一棵 5 阶 B 树

        [17 35]/   |   \[5 8] [20 22] [40 60]

根有两个 key：17, 35
三个子节点分别存储小于 17，17~35，和大于 35 的 key
每个节点可能存储 2~4 个 key（因为 m=5）

四、B+ 树的改进：为范围查找和磁盘友好优化

🟩 B+ 树对 B 树的改进：

结构方面	B 树	B+ 树
叶子节点	含数据（部分）	全部数据只在叶子节点中
非叶子节点	存储 key 和数据指针	只存储 key，不存数据
有序遍历	需要中序递归	叶子节点链式连接，遍历更快
查询性能	较差（中途返回数据）	一致性强（固定深度，访问叶子）

📌 B+ 树的叶子节点链式结构：

[5 8] → [12 17] → [20 22] → [40 60]

这使得范围查找和分页查询变得非常高效（几乎是数据库的必备功能）

五、磁盘存储与页结构分析

在现代数据库系统或操作系统中，磁盘按页管理：

结构项	描述
页大小	通常是 4KB（4096 字节）
数据对齐	每个数据结构要对齐页
B+ 树节点设计	通常设计为一个节点=一个页

✅ 举例：每页可容纳 100 个 key

假设每个 key 为 16 字节，一个页可容纳约 256 个 key
树高 log₁₀₀(n)，即百万级数据仅需树高为 3~4 层，磁盘访问次数显著降低

六、应用场景：B 树 vs B+ 树

场景	推荐结构	原因
操作系统文件索引	B+ 树	范围查找+分页遍历更强
数据库索引结构（如 MySQL）	B+ 树	结构化磁盘页管理
小型内存数据结构	B 树或红黑树	不涉及磁盘，可用 B 树/红黑树

七、C++ 实现 B 树（简单示例）

以下是一个简化的 B 树实现（m=3）：

#include <iostream>
#include <vector>
#include <algorithm>const int DEGREE = 3;  // m 阶 B 树，最多 2*DEGREE - 1 个 keyclass BTreeNode {
public:
bool isLeaf;
std::vector<int> keys;
std::vector<BTreeNode*> children;BTreeNode(bool leaf) : isLeaf(leaf) {}void traverse() {for (size_t i = 0; i < keys.size(); ++i) {if (!isLeaf) children[i]->traverse();std::cout << keys[i] << " ";}if (!isLeaf) children[keys.size()]->traverse();
}BTreeNode* search(int key) {int i = 0;while (i < keys.size() && key > keys[i]) ++i;if (i < keys.size() && key == keys[i]) return this;if (isLeaf) return nullptr;return children[i]->search(key);
}
};class BTree {
BTreeNode* root;public:
BTree() : root(nullptr) {}void traverse() {if (root != nullptr) root->traverse();
}BTreeNode* search(int key) {return (root == nullptr) ? nullptr : root->search(key);
}// 插入逻辑略复杂，建议下一节手动实现
};

这里只写了查找和遍历，完整的插入+分裂逻辑我们将在下一节详细展开并实现

八、为什么数据库都用 B+ 树？

✅ 多数数据库索引（如 MySQL 的 InnoDB）使用 B+ 树

原因：

查询访问路径统一（所有数据都在叶子）
更适合范围查询、分页、排序
叶子节点可顺序扫描（链表形式）
非叶子节点只做路由，不带实际数据，结构更清晰
每个节点可以装满一个页，减少 I/O 次数

九、本节小结

重点点	内容
B 树特点	多路查找、节点包含多个 key、结构平衡
B+ 树优化	所有数据都在叶子节点、非叶子仅做索引、叶子链式连接
工程优势	高度低、减少磁盘 I/O、结构清晰、页对齐优化
应用	文件系统索引、数据库索引、范围查找、高效分页遍历