数据库

索引设计与 B+ 树原理

深入理解 InnoDB B+ 树索引结构、聚簇索引与二级索引差异、哈希索引适用场景，以及最左前缀原则、覆盖索引、ICP 等高级索引优化技术。

Leeting Yan 8 分钟阅读 3674 字

索引是数据库性能优化的基石，而 InnoDB 使用 B+ 树作为核心索引结构。本文从底层原理出发，解析 B+ 树的结构设计、聚簇索引与二级索引的差异、哈希索引的应用场景，以及实际开发中的高级索引优化策略。

1. 为什么不选二叉搜索树？

1.1 磁盘 IO 的代价

数据库索引需要持久化存储在磁盘上。内存访问时间约 100ns，磁盘随机 IO 约 10ms，相差 10 万倍。因此，索引结构的设计目标只有一个：最小化磁盘 IO 次数。

1.2 平衡二叉树的缺陷

二叉搜索树（10 亿数据 ≈ 30 层）：
查找路径: Root ──► 分支 ──► ... ──► Leaf（30 次磁盘 IO）

B+ 树（扇出 1000）：
查找路径: Root ──► 内部节点 ──► Leaf（仅 3 次磁盘 IO）

二叉树每个节点只存一条记录，且树高随数据量线性增长。B+ 树通过多路分支将树高压缩到 3~4 层，大幅减少 IO。

2. B+ 树结构详解

2.1 结构特征

B+ 树相比 B 树的核心特征：

特征B 树B+ 树（InnoDB 使用）
数据存放叶子节点和内部节点都存数据所有数据只在叶子节点
叶子节点关系无连接双向链表连接（范围查询友好）
内部节点作用存储数据 + 导航纯导航键值，可缓存更多索引
查询效率最好 O(1)（命中根节点）稳定 O(log n)（必须到叶子）
范围查询中序遍历，复杂顺序扫描叶子链表，高效

2.2 InnoDB 的 B+ 树页结构

InnoDB 的每个页 16KB，B+ 树的每个节点就是一页：

┌─────────────────────────────────────────────────────────────┐
│                      ROOT PAGE (16KB)                       │
├─────────────────────────────────────────────────────────────┤
│  PAGE HEADER (38B)    │ 校验/当前记录数/页类型/左右兄弟指针  │
├─────────────────────────────────────────────────────────────┤
│  PAGE DIRECTORY (Slot)│ 目录槽（每个槽对应一个记录组）        │
├─────────────────────────────────────────────────────────────┤
│  USER RECORDS         │ 索引记录（key + pointer）            │
│  ┌─────────────────────────────────────────────────────┐   │
│  │ key1 │ page_ptr1 │ key2 │ page_ptr2 │ ...        │   │
│  └─────────────────────────────────────────────────────┘   │
├─────────────────────────────────────────────────────────────┤
│  FREE SPACE           │ 空闲空间                           │
├─────────────────────────────────────────────────────────────┤
│  PAGE TRAILER (8B)    │ 校验和                             │
└─────────────────────────────────────────────────────────────┘

2.3 树高计算

假设：
- 页大小 = 16KB
- 主键 BIGINT (8B) + 指针 (6B) = 14B / 索引项
- 扇出 = 16384 / 14 ≈ 1170

树高 = 2（3层）：可容纳 1170 × 1170 × 记录数 ≈ 2000 万数据
树高 = 3（4层）：可容纳 1170 × 1170 × 1170 ≈ 16 亿数据

Root 和 Internal 节点常驻 Buffer Pool → 几乎所有查询只需 1 次 IO！

3. 聚簇索引（Clustered Index）

3.1 定义

聚簇索引即主键索引，叶子节点存储完整行数据。InnoDB 表必然有聚簇索引：

┌─────────────────────────────────────────────────────────────┐
│                     聚簇索引 B+ Tree                        │
│                                                             │
│  内部节点：主键值 + 子页指针                                  │
│                                                             │
│       [10]──────[30]──────[50]                              │
│       /  \      /  \      /  \                              │
│   <10  10-30 30-50  >50                                     │
│      \    |      |     /                                    │
│       \   |      |    /                                     │
│ 叶子节点链表（按主键顺序物理存储）：                           │
│  ┌───┐──►┌───┐──►┌───┐──►┌───┐                             │
│  │ 1 │   │ 5 │   │12 │   │23 │  ← (主键值 + 完整行数据)      │
│  └───┘   └───┘   └───┘   └───┘                             │
└─────────────────────────────────────────────────────────────┘

3.2 聚簇索引选择规则

InnoDB 按以下优先级选择聚簇索引键：

  1. 显式主键（Primary Key）
  2. 第一个非空唯一索引（NOT NULL UNIQUE）
  3. 自动生成 6 字节隐藏主键（ROW_ID）
-- 推荐：显式指定自增主键
CREATE TABLE users (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,  -- 显式主键，最佳选择
    name VARCHAR(100),
    email VARCHAR(100) UNIQUE
);

3.3 自增主键 vs 业务主键

主键类型优点缺点适用场景
自增 ID顺序插入，页分裂少业务无意义绝大多数场景
UUID全局唯一，可离线生成随机插入，页分裂严重分布式系统
业务键有业务含义可能变更、过长需权衡

UUID 优化：使用 UUID v7（时间戳前缀）替代 UUID v4，恢复顺序性。

4. 二级索引（Secondary Index）

4.1 结构：叶子存主键值

二级索引 (email_idx):
                              
叶子节点存储：(email值) + (对应主键值)
┌────────────────────────────────┐
│ abc@mail.com  │ 主键=5          │
│ def@mail.com  │ 主键=1          │
│ xyz@mail.com  │ 主键=12         │
└────────────────────────────────┘
                             │
                             ▼ 回表（ Bookmark Lookup ）
                    聚簇索引查找主键=1的行数据
                    
SELECT * FROM users WHERE email = 'def@mail.com'
         │
         ├──► 二级索引找到 email='def@mail.com' → 主键=1
         └──► 回表：用主键=1到聚簇索引取完整行数据

4.2 回表（Bookmark Lookup）与回表代价

-- 发生回表：SELECT * 需要完整行数据
SELECT * FROM users WHERE email = 'xxx';

-- 避免回表：二级索引包含所有需要列
SELECT id, email FROM users WHERE email = 'xxx';

大量回表会产生随机 IO，性能可能劣于全表扫描。此时 EXPLAIN 会显示 Using index condition; Using where。

5. 索引优化策略

5.1 最左前缀原则

联合索引 (a, b, c) 的有效查询：

-- ✅ 完全使用索引
WHERE a = 1 AND b = 2 AND c = 3
WHERE a = 1 AND b = 2
WHERE a = 1
WHERE a = 1 ORDER BY b, c

-- ⚠️ 部分使用（仅 a）
WHERE a = 1 AND c = 3

-- ❌ 不走索引（缺少最左列 a）
WHERE b = 2 AND c = 3
WHERE c = 3

B+ 树按联合索引的列顺序组织，跳过最左列等于跳着查找，无法利用树结构。

5.2 覆盖索引

-- 联合索引 (name, age)
CREATE INDEX idx_name_age ON users(name, age);

-- ✅ 覆盖索引：无需回表
SELECT name, age FROM users WHERE name = 'Alice';

-- ✅ 覆盖索引：id 是主键，二级索引叶子自带
SELECT id, name, age FROM users WHERE name = 'Alice';

-- ❌ 需要回表：email 不在索引中
SELECT name, age, email FROM users WHERE name = 'Alice';

EXPLAIN 显示 Using index 表示使用了覆盖索引。

5.3 索引条件下推（Index Condition Pushdown, ICP）

MySQL 5.6 引入的优化，将 WHERE 条件尽量"下推"到存储引擎层过滤：

-- 索引 idx_zipcode (zipcode, lastname)
SELECT * FROM people 
WHERE zipcode = '95054' 
  AND lastname LIKE '%etrunia%' 
  AND address LIKE '%Main Street%';

没有 ICP：

  • 索引找到所有 zipcode=‘95054’ 的记录 → 回表 → Server 层过滤 lastname/address

有 ICP：

  • 索引找到 zipcode=‘95054’ 后，在引擎层就用 lastname LIKE 过滤
  • 减少回表次数
EXPLAIN SELECT ...;
-- Extra: Using index condition  ← 启用了 ICP

5.4 索引设计 checklist

原则说明示例
加在 WHERE/ON高选择性列优先状态字段不加索引（选择性低）
最左前缀联合索引按查询频率排列(user_id, created_at)
避免冗余已有 (a,b)，不需要单独 (a)除非 a 需要作为唯一约束
长字段前缀VARCHAR(255) 用前缀索引KEY idx_email (email(10))
覆盖原则SELECT 列尽量在索引内避免回表
控制数量单表索引不超过 5~7 个写入时会维护所有索引
删除未使用监控查询日志performance_schema.table_io_waits_summary_by_index_usage

6. 哈希索引

6.1 InnoDB 自适应哈希索引

SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';
SHOW ENGINE INNODB STATUS; -- 'Hash searches/s, non-hash searches/s'

AHI（Adaptive Hash Index）不是显式创建的索引，而是 InnoDB 自动为频繁等值查询的 B+ 树页构建的内存哈希结构：

B+ 树查 email='alice@mail.com':
Root → Internal → Leaf  (3 IO，O(log n))

AHI 哈希查:
hash('alice@mail.com') → Page Pointer  (直接命中，O(1))

AHI 适合：

  • 高并发的单点等值查询
  • 读多写少的场景

AHI 可能的问题：

  • 高并发写入时 AHI partition 的 latch 竞争
  • MySQL 5.7+ 支持多分区：innodb_adaptive_hash_index_parts = 8

6.2 显式哈希索引：MySQL Memory 引擎

CREATE TABLE cache_table (
    id INT,
    data VARCHAR(1000),
    KEY USING HASH (id)  -- Memory 引擎支持显式哈希索引
) ENGINE=MEMORY;

Memory 引擎的哈希索引：

  • 精确匹配 O(1)
  • 不支持范围查询、排序、LIKE

7. 索引失效的常见场景

CREATE INDEX idx_name ON users(name);

-- ❌ 失效：对索引列使用函数
WHERE UPPER(name) = 'ALICE'

-- ❌ 失效：隐式类型转换
WHERE id = '100'   -- id 是 INT，与字符串比较触发转换

-- ❌ 失效：LIKE 开头通配符
WHERE name LIKE '%lice'

-- ❌ 失效：NOT、<>、!=（选择性差时可能全表）
WHERE status != 'deleted'

-- ❌ 失效：OR 条件中部分无索引
WHERE name = 'Alice' OR email = 'alice@mail.com'  -- email 无索引

-- ✅ 解决：函数索引（MySQL 8.0+）
CREATE INDEX idx_upper_name ON users((UPPER(name)));

8. 实践：用工具分析索引

8.1 EXPLAIN 解读

EXPLAIN SELECT * FROM users WHERE email = 'xxx';
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+
| 1  | SIMPLE      | users | NULL       | ref  | email_idx     | email_idx | 303 | const | 1    | 100.0    | NULL  |
+----+-------------+-------+------------+------+---------------+------+---------+-------+------+----------+-------+

关键字段：

  • type: system > const > eq_ref > ref > range > index > ALL（越左越好）
  • key: 实际使用的索引
  • rows: 预估扫描行数
  • Extra: Using index（覆盖）、Using where（WHERE过滤）、Using filesort（需排序）

8.2 慢查询日志 + pt-query-digest

# 启用慢查询日志
slow_query_log = 1
long_query_time = 1
log_queries_not_using_indexes = 1

# 分析
pt-query-digest /var/lib/mysql/slow.log > report.txt

9. 总结

索引设计的核心原则：

1. 理解 B+ 树特性
   ├── 多路平衡 → 低树高 → 少 IO
   ├── 叶子链表 → 范围查询友好
   └── 内部节点纯键 → 高扇出

2. 聚簇索引是核心
   ├── 数据物理有序存储
   └── 二级索引都指向它

3. 优化策略矩阵
   ├── 最左前缀 → 联合索引设计
   ├── 覆盖索引 → 减少回表
   ├── ICP → 减少无效回表
   ├── 前缀索引 → 节省空间
   └── 避免索引失效场景

索引不是越多越好。每个索引都是一份有序数据结构，写入时要维护。在"查询加速"与"写入开销"之间找到平衡，是高性能数据库设计的艺术。

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「数据库」更多文章

  1. 备份恢复与高可用方案
  2. 数据库性能监控与诊断
  3. NewSQL 选型对比