清晨的一缕阳光
返回

B+ 树索引原理

引言

在数据库性能优化中，索引是最核心也是最有效的手段之一。MySQL 的 InnoDB 存储引擎使用 B+ 树作为默认的索引数据结构。理解 B+ 树的原理，对于编写高效 SQL、设计合理索引至关重要。

本文将深入讲解：

核心概念

什么是 B+ 树

B+ 树是一种多路平衡查找树，是 B 树的变体。它的核心特点是：

  1. 所有数据都存储在叶子节点，非叶子节点只存储索引键
  2. 叶子节点之间通过指针连接，形成有序链表
  3. 树的高度平衡，保证查询效率稳定

为什么选择 B+ 树

MySQL 选择 B+ 树而非其他数据结构，主要基于以下考虑：

数据结构优点缺点适用场景
哈希表等值查询 O(1)不支持范围查询，哈希冲突精确匹配
二叉搜索树结构简单容易退化成链表，高度不平衡内存数据
红黑树自平衡，查询稳定树太高，磁盘 IO 次数多内存索引
B 树多路平衡，支持范围查询数据分散存储，范围查询需中序遍历文件系统
B+ 树数据集中存储，范围查询高效，磁盘 IO 少插入删除需维护平衡数据库索引

B+ 树的数据结构

物理结构详解

B+ 树由三种节点组成：

graph TD
    Root[根节点<br/>非叶子节点] --> Node1[非叶子节点 1]
    Root --> Node2[非叶子节点 2]
    Root --> Node3[非叶子节点 3]
    
    Node1 --> Leaf1[叶子节点 1]
    Node1 --> Leaf2[叶子节点 2]
    Node2 --> Leaf3[叶子节点 3]
    Node2 --> Leaf4[叶子节点 4]
    Node3 --> Leaf5[叶子节点 5]
    Node3 --> Leaf6[叶子节点 6]
    
    Leaf1 -.-> Leaf2
    Leaf2 -.-> Leaf3
    Leaf3 -.-> Leaf4
    Leaf4 -.-> Leaf5
    Leaf5 -.-> Leaf6
    
    style Root fill:#e1f5ff
    style Node1 fill:#e1f5ff
    style Node2 fill:#e1f5ff
    style Node3 fill:#e1f5ff
    style Leaf1 fill:#fff4e1
    style Leaf2 fill:#fff4e1
    style Leaf3 fill:#fff4e1
    style Leaf4 fill:#fff4e1
    style Leaf5 fill:#fff4e1
    style Leaf6 fill:#fff4e1

节点特点：

  1. 根节点（Root）

    • 树的入口点
    • 可以是叶子节点（树只有 1 层）或非叶子节点

  2. 非叶子节点（Internal Node）

    • 只存储索引键和指针，不存储实际数据
    • 每个节点包含 N 个键和 N+1 个指针
    • 作用：导航，快速定位到目标叶子节点

  3. 叶子节点（Leaf Node）

    • 存储所有实际数据（行记录）
    • 包含指向下一个叶子节点的指针（双向链表）
    • 所有叶子节点在同一层

页（Page）结构

InnoDB 中，B+ 树的节点以页为单位存储：

计算示例：

假设：
- 页大小：16KB = 16384 字节
- 主键：BIGINT = 8 字节
- 指针：6 字节
- 每索引项：8 + 6 = 14 字节

非叶子节点每页可存储索引项数：
16384 / 14 ≈ 1170 个

三层 B+ 树可存储数据量：
1170 × 1170 × 16 ≈ 2190 万行

这意味着，一个高度为 3 的 B+ 树就可以存储约 2000 万行数据，查询任意一行最多只需要 3 次磁盘 IO！

聚簇索引与二级索引

聚簇索引（Clustered Index）

聚簇索引是 InnoDB 的核心特性，它的特点是：

聚簇索引的选择规则：

  1. 如果定义了主键（PRIMARY KEY），则使用主键作为聚簇索引
  2. 如果没有主键，但有**唯一索引（UNIQUE）**且所有列非空，则选择第一个符合条件的唯一索引
  3. 如果以上都没有，InnoDB 会自动生成一个隐藏的 ROW_ID 作为聚簇索引
-- 示例：创建带主键的表
CREATE TABLE users (
    id BIGINT PRIMARY KEY,  -- 主键作为聚簇索引
    name VARCHAR(50),
    email VARCHAR(100),
    age INT
) ENGINE=InnoDB;

聚簇索引的 B+ 树结构：

graph TD
    subgraph 聚簇索引
        Root[根节点<br/>主键值] --> Leaf1[叶子节点<br/>主键 + 完整行数据]
        Root --> Leaf2[叶子节点<br/>主键 + 完整行数据]
        Leaf1 -.-> Leaf2
    end
    
    style Root fill:#e1f5ff
    style Leaf1 fill:#fff4e1
    style Leaf2 fill:#fff4e1

二级索引（Secondary Index）

二级索引（也称为非聚簇索引）的特点是：

-- 创建二级索引
CREATE INDEX idx_email ON users(email);
CREATE INDEX idx_age ON users(age);

二级索引的 B+ 树结构：

graph TD
    subgraph 二级索引 idx_email
        Root2[根节点<br/>email 值] --> Leaf3[叶子节点<br/>email + 主键 id]
        Root2 --> Leaf4[叶子节点<br/>email + 主键 id]
        Leaf3 -.-> Leaf4
    end
    
    style Root2 fill:#e1f5ff
    style Leaf3 fill:#fff4e1
    style Leaf4 fill:#fff4e1

查询过程对比

场景 1：使用聚簇索引查询

SELECT * FROM users WHERE id = 100;

查询过程：

  1. 从根节点开始，定位到 id=100 的叶子节点
  2. 直接从叶子节点获取完整行数据
  3. 只需 1 次查询

场景 2：使用二级索引查询

SELECT * FROM users WHERE email = 'test@example.com';

查询过程：

  1. 在 idx_email 二级索引中定位到对应叶子节点
  2. 获取主键 id 值
  3. 回表：到聚簇索引中查询完整行数据
  4. 需要 2 次查询（二级索引 + 聚簇索引）

场景 3：覆盖索引（无需回表）

SELECT id, email FROM users WHERE email = 'test@example.com';

查询过程：

  1. 在 idx_email 二级索引中定位
  2. 直接从二级索引获取 id 和 email（都在索引中）
  3. 无需回表，只需 1 次查询

索引查询优化

最左前缀原则

对于联合索引，查询必须遵循最左前缀原则：

-- 创建联合索引
CREATE INDEX idx_name_age_email ON users(name, age, email);

有效查询：

WHERE name = '张三'                    -- ✅ 使用第 1 列
WHERE name = '张三' AND age = 25       -- ✅ 使用前 2 列
WHERE name = '张三' AND age = 25 AND email = 'x'  -- ✅ 使用全部 3 列

无效查询（索引失效）：

WHERE age = 25                         -- ❌ 跳过第 1 列
WHERE email = 'x'                      -- ❌ 跳过前 2 列
WHERE name = '张三' AND email = 'x'    -- ⚠️ 只使用第 1 列，email 用不到

范围查询的影响

范围查询会停止使用后续索引列：

-- 索引：(name, age, email)
WHERE name = '张三' AND age > 20 AND email = 'x'
-- 结果：name 用索引，age 用索引范围扫描，email 无法使用索引

索引覆盖优化

覆盖索引是指查询所需的所有列都在索引中，无需回表：

-- 索引：idx_email_age(email, age)

-- ✅ 覆盖索引查询
SELECT email, age FROM users WHERE email = 'test@example.com';

-- ❌ 需要回表
SELECT * FROM users WHERE email = 'test@example.com';

优化建议：

注意事项

常见陷阱

  1. 索引不是越多越好

    • 每个索引都需要存储空间
    • INSERT/UPDATE/DELETE 时会降低性能（需维护索引）
    • 建议：只为高频查询字段创建索引

  2. 区分度低的字段不适合建索引

    -- ❌ 性别字段只有 2 个值，区分度低
CREATE INDEX idx_gender ON users(gender);

-- ✅ 手机号区分度高
CREATE INDEX idx_phone ON users(phone);

  3. 避免在索引列上使用函数

    -- ❌ 索引失效
WHERE YEAR(create_time) = 2024;

-- ✅ 索引有效
WHERE create_time >= '2024-01-01' AND create_time < '2025-01-01';

性能考虑

  1. B+ 树高度

    • 理想情况：2-3 层（千万级数据）
    • 过高会导致 IO 次数增加
    • 通过 SHOW TABLE STATUS 查看表统计信息

  2. 页分裂

    • 插入数据时可能导致页分裂（页满后拆分）
    • 自增主键可避免随机插入导致的页分裂
    • 定期 OPTIMIZE TABLE 可整理碎片

  3. 索引选择性

    • 选择性 = 不同值数量 / 总行数
    • 选择性越高，索引效果越好
    • 主键选择性 = 1（最优）

总结

核心要点

  1. B+ 树特点：数据存储在叶子节点，叶子节点形成有序链表，适合范围查询
  2. 聚簇索引：索引与数据在一起，一个表只能有一个
  3. 二级索引：叶子节点存储主键，查询需回表
  4. 覆盖索引：查询列都在索引中，无需回表，性能最优
  5. 最左前缀原则：联合索引查询必须从最左列开始

最佳实践

下一步

理解 B+ 树原理后，下一章我们将学习：

参考资料

分享这篇文章到:
分享到QQ 分享到微博 分享文章到Email
上一篇文章
Go Channel 底层原理
下一篇文章
Go GMP 调度模型详解