为什么使用 B+树

B+树结构特点

B+树示例（3阶）：

                    [10 | 20 | 30]
                   /    |    |    \
          /-------/     |    |     \-------\
         /              |    |              \
    [1,2,3,4,5]   [11,12,13]  [21,22,23]  [31,32,33]

特点：
1. 非叶子节点只存储索引（关键字）
2. 所有数据存储在叶子节点
3. 叶子节点之间通过指针连接（双向链表）
4. 每个节点可以存储多个关键字

为什么不用 B 树

B 树的问题：

• 非叶子节点存储数据，节点大小受限，树的高度增加
• 范围查询需要在中序遍历中跳转，效率低

为什么不用二叉树

示例：

二叉树：1000万数据
log₂(10,000,000) ≈ 24 次磁盘 I/O

B+树：1000万数据，阶数 m=1000
log_1000(10,000,000) ≈ 3 次磁盘 I/O

为什么不用 Hash

Hash 的问题：

• 不支持范围查询（WHERE age > 18）
• 不支持排序（ORDER BY）
• 不支持模糊查询（LIKE 'abc%'）

B+树的具体优势

1. 减少磁盘 I/O

// 假设：
// - 磁盘页大小：16KB
// - 每个索引项：8B（指针）+ 8B（主键）= 16B
// - 非叶子节点可存储：16KB / 16B = 1024 个索引项
// - 树高度：log_1024(10,000,000) ≈ 3

// 3 次磁盘 I/O 就能找到任何数据

2. 支持范围查询

-- B+树：顺序扫描叶子节点
SELECT * FROM users WHERE age BETWEEN 18 AND 25;

-- 只需要：
-- 1. 定位到 age=18 的叶子节点
-- 2. 沿着链表顺序访问到 age=25

3. 查询性能稳定

B 树：数据可能在任何层级
- 查询 1：根节点（1 次 I/O）
- 查询 2：叶子节点（3 次 I/O）

B+树：数据都在叶子节点
- 所有查询：3 次 I/O（性能稳定）

4. 支持全表扫描

-- B+树：直接遍历叶子节点链表
SELECT * FROM users;

-- 无需回退到根节点，顺序访问即可

InnoDB B+树实现细节

聚簇索引

-- 主键索引（聚簇索引）
CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    age INT
);

-- B+树叶子节点存储：
-- | 主键 id | name | age | ... |

非聚簇索引（辅助索引）

-- 辅助索引
CREATE INDEX idx_age ON users(age);

-- B+树叶子节点存储：
-- | age | 主键 id |

-- 查询过程（回表）：
-- 1. 在 idx_age 中找到 age=18 的记录，得到 id
-- 2. 在聚簇索引中根据 id 找到完整数据