B+ 树索引
B+ 树是关系数据库最常用的索引结构——它是多路平衡查找树，所有数据都在叶子节点，内部节点只存"路标"，适合磁盘块存储和大规模范围查询
🤔 为什么数据库不用二叉搜索树做索引？
你已经在数据结构部分学过二叉搜索树（BST）——查找效率 O(log n)，在内存中表现很好。
但数据库的数据存在磁盘上。磁盘和内存有个根本性区别：磁盘读取一次数据的最小单位是一个”块”（Block，通常是 4KB~16KB），而不是一个字节。
如果你用二叉树做索引：
[50]
/ \
[25] [75]
/ \ / \
[10] [37][60] [90]
- 每个节点只存一个键（比如 50）
- 每个节点占用一个磁盘块（4KB）
- 读取一个块只拿到一个键，浪费了 99.9% 的空间
- 100 万行数据的二叉树大约有 20 层高——查一次可能要读 20 次磁盘，每次几毫秒，加起来上百毫秒
B+ 树的核心思路就是：让每个磁盘块”塞满”尽可能多的键，大幅降低树的高度。
📚 类比：图书馆的索引系统
假设你要在一座巨大的图书馆里找一本《数据库系统概论》。
二叉搜索树 = 每层书架只贴一个字：“A-Z”的书的入口处只有一个”中”字标签。你要一个一个书架地看——从”中”到”数据”到”数据”到”数据库”……走很多步。
B+ 树 = 入口处有个大指示牌：“计算机类 → 3 楼 东南区”。到 3 楼又有更细的指示牌：“数据库 → 3-B-04 书架”。顺着指示走三步就到了。
关键区别：二叉树的每个”路标”只指向两个方向（左/右），B+ 树的每个”路标”指向几十甚至几百个方向。
🌳 B+ 树的结构
B+ 树由两种节点组成：
内部节点（Internal Node）——只存”路标”
内部节点存的是键的”分界线”——告诉你要去哪个子节点找数据：
内部节点：[50, 100, 150]
↘
键 < 50 → 左边
50 ≤ 键 < 100 → 中间
100 ≤ 键 < 150 → 右边
150 ≤ 键 → 最右边
每个内部节点通常可以存几百个键——这就是为什么 B+ 树可以很”矮”。
叶子节点（Leaf Node）——存实际数据
叶子节点存的是真正的数据行或指向数据行的指针。所有叶子节点在同一层，通过指针连成一个链表：
叶子层：[10, 20, 30] → [40, 50, 60] → [70, 80, 90]
↑ 链表指针 ↑
这个链表结构使得范围查询非常高效——找到范围的起点后，顺着链表往后读就行。
完整的 B+ 树
内部节点层：
[50, 100]
/ | \
[20,35] [70,85] [120,150]
/ | / | / \
叶子节点层：
[10,15,20] [25,30,35] [50,60,70] [75,80,85] [100,110,120] [130,140,150]
──→ 链表连接 ────────────────────────────────────────────────────→
三步查找过程（以找 75 为例）：
- 从根节点 [50, 100] 开始 → 75 在 50 和 100 之间 → 走中间子节点
- 到达 [70, 85] → 75 在 70 和 85 之间 → 走左数第二个子节点
- 到达叶子节点 → 扫描找到 75
💡 整个查找只需 3 次 I/O——无论表里有 100 万行还是 1000 万行。这就是 B+ 树的威力。
📊 B+ 树的关键特性
| 特性 | 含义 | 为什么重要 |
|---|---|---|
| 多路（Multi-way） | 每个节点存几百个键 | 一个磁盘块塞满信息 |
| 平衡（Balanced） | 所有叶子在同一深度 | 查询时间稳定，不会退化 |
| 有序（Ordered） | 叶子节点按链表连接 | 范围查询（BETWEEN、>、<）效率高 |
| 扇出高（High Fanout） | 每个节点有几百个子节点 | 树高度低（~3-4 层） |
数值对比
| 数据量 | 二叉树高度 | B+ 树高度（扇出 500） |
|---|---|---|
| 1,000 | ~10 | ~2 |
| 1,000,000 | ~20 | ~3 |
| 1,000,000,000 | ~30 | ~4 |
1 亿条数据，B+ 树查一次只需要 4 次磁盘 I/O。 相比二叉树的 30 次，差距是数量级的。
🚀 B+ 树的插入和删除
插入——节点满了就”分裂”
INSERT INTO students VALUES (45, '赵六', 22, '计科1班');
- 找到 45 应该插入的叶子节点
- 如果节点还有空位 → 直接插入（保持有序）
- 如果节点满了 → 分裂（Split）：把节点一分为二，把中间键提升到父节点
- 如果父节点也满了 → 父节点继续分裂
- 直到根节点——如果根也满了，树的高度 +1
删除——节点太空了就”合并”
删除的反向过程：
- 找到并删除目标键
- 如果节点太”空”（低于填充阈值） → 尝试和兄弟节点合并（Merge）
- 合并后父节点少了一个子节点 → 调整父节点
- 如果父节点也太空了 → 继续向上合并
🧩 类比：图书馆书架的扩容
插入就像往书架上放新书。
- 书架有空位 → 直接插进去（保持按字母序）
- 书架满了 → 从中间分成两个书架，贴上新的范围标签（写到内部节点）
- 书架太多的时候 → 增加一个指示牌层（树增高）
B+ 树的自平衡
B+ 树的分裂和合并机制确保树始终平衡——无论你怎么插入、删除，所有叶子节点永远在同一深度。
这是 B+ 树和二叉搜索树的关键区别：二叉搜索树在最坏情况下会退化成链表（比如插入有序数据），但 B+ 树永远不会。
🏢 为什么 MySQL 的 InnoDB 用 B+ 树？
MySQL 是最流行的关系数据库之一，它的默认存储引擎 InnoDB 用 B+ 树作为索引结构。
-- 在 MySQL 中创建表时，主键自动用 B+ 树索引
CREATE TABLE students (
id INT PRIMARY KEY, -- 自动创建 B+ 树索引
name VARCHAR(50),
age INT
);
-- 手动创建的普通索引也是 B+ 树
CREATE INDEX idx_name ON students(name);
InnoDB 的 B+ 树有个特殊之处——它用的是聚簇索引（Clustered Index）：叶子节点直接存储整行数据，而不是指向数据的指针。
这意味着：
- 按主键查：一次 B+ 树查找就能拿到所有列的数据
- 按普通索引查：先在索引的 B+ 树里找到主键值，再回主键的 B+ 树里找完整数据（这叫”回表”）
-- 按主键查 → 直接拿数据（一次 B+ 树查找）
SELECT * FROM students WHERE id = 100;
-- 按普通索引查 → 先找主键，再回主键树查（两次 B+ 树查找）
SELECT * FROM students WHERE name = '张三';
📝 小结
| 概念 | 一句话 |
|---|---|
| B+ 树 | 多路平衡查找树——每个节点存几百个键，高度只有 3-4 层 |
| 内部节点 | 只存”路标”（键的分界线），不存数据 |
| 叶子节点 | 存实际数据，用链表连接支持范围查询 |
| 扇出 | 每个节点的子节点数——扇出越大，树越矮 |
| 分裂（Split） | 节点满时一分为二，保证平衡 |
| 聚簇索引 | MySQL InnoDB 的 B+ 树——叶子直接存整行数据 |
🎯 思考题：B+ 树为什么可以实现为”每个节点的大小 = 一个磁盘块的大小”？这给读取带来了什么好处？（提示：想想 I/O 次数和块读取的关系）
为什么先学这个？ B+ 树是数据库最通用的索引结构。但有些场景——比如等值查询——还有更快的选择：哈希索引。