MySQL 索引用的什么结构？

约 1112 字大约 4 分钟

MySQL 字节

2025-03-20

⭐ 题目日期：

字节 - 2024/12/25

📝 题解：

MySQL 的索引主要采用 B+ 树（B+ Tree） 结构，尤其是在 InnoDB 存储引擎中。以下是详细说明及其设计原理和优势：

1. MySQL 索引的核心结构：B+ 树

(1) B+ 树的特点

多路平衡搜索树：每个节点可包含多个键值（分支因子大），降低树的高度。
数据存储在叶子节点：非叶子节点仅作为索引（存储键值和子节点指针）。
叶子节点形成有序链表：相邻叶子节点通过指针连接，支持高效的范围查询。

(2) B+ 树的结构示例

           [非叶子节点]               
           | 10 | 20 | 30 |        
           /     |     \            
     [叶子节点]  [叶子节点]  [叶子节点]  
     5→10 →15   20→25→30   35→40→...  
     ↑          ↑          ↑         
    链表指针    链表指针    链表指针

2. 为什么选择 B+ 树？

(1) 对比其他数据结构

结构	缺点	B+ 树的优势
二叉搜索树	树高增长快（O(log n) 但实际更高），I/O 次数多	多路平衡，树高更低，减少磁盘访问次数
哈希表	不支持范围查询，内存消耗大	天然支持范围查询和排序操作
B 树	数据可能分散在非叶子节点，范围查询效率低	数据集中存储在叶子节点，范围查询直接遍历链表

(2) 核心优势

减少磁盘 I/O：
B+ 树的节点大小通常设置为磁盘页（如 16KB），单次 I/O 可加载大量键值，降低树的高度。
适合范围查询：
叶子节点的链表结构允许快速遍历区间数据（如 WHERE id BETWEEN 100 AND 200）。
稳定的查询性能：
所有查询均需遍历到叶子节点，时间复杂度稳定为 O(log n)。

3. InnoDB 的索引实现

(1) 聚簇索引（Clustered Index）

数据与索引绑定：主键索引的叶子节点直接存储行数据（即数据文件按主键顺序组织）。
一个表只有一个聚簇索引：若未定义主键，InnoDB 会自动生成隐藏的 ROW_ID 作为聚簇索引。

(2) 二级索引（Secondary Index）

叶子节点存储主键值：查询时需先查二级索引找到主键，再通过聚簇索引获取完整数据（称为回表）。

示例：
对 name 字段建索引，结构如下：

[非叶子节点] → [叶子节点（name: Alice → 主键 id=100）] → 回表查询聚簇索引获取行数据

(3) 联合索引（Composite Index）

最左前缀原则：索引按字段顺序组织（如 (a, b, c)），查询需从最左字段开始匹配。
索引覆盖：若查询字段均在索引中，无需回表（如 SELECT a FROM table WHERE a=1 AND b=2）。

4. 其他索引类型

(1) 哈希索引

Memory 引擎默认：基于哈希表，仅支持等值查询（=、IN），时间复杂度 O(1)。
InnoDB 自适应哈希索引（AHI）：
自动为高频访问的索引页创建哈希索引，加速查询。

(2) 全文索引（FULLTEXT）

基于倒排索引：用于文本搜索（如 MATCH(content) AGAINST('keyword')）。
支持分词和相关性排序：适用于 LIKE 无法高效处理的场景。

(3) 空间索引（R-Tree）

用于地理数据：支持 GIS 数据类型（如 POINT、POLYGON）。
基于 R 树实现：高效处理多维空间范围查询。

5. 索引的代价与优化

(1) 写入代价

插入/删除/更新：需维护 B+ 树结构，可能触发节点分裂或合并。
建议：避免过度索引，优先为高频查询字段建索引。

(2) 存储代价

索引占用磁盘空间：二级索引存储主键值，联合索引存储多个字段。
建议：使用前缀索引（如 INDEX(email(10))）减少空间占用（但可能影响查询精度）。

(3) 优化场景

覆盖索引：避免回表，提升查询性能。
索引下推（ICP）：在存储引擎层提前过滤数据（MySQL 5.6+）。

总结

默认索引结构：B+ 树（高扇出、低高度、适合磁盘 I/O 和范围查询）。
核心场景：
- 聚簇索引：主键查询、范围扫描。
- 二级索引：加速非主键字段查询（需注意回表）。
- 哈希索引：Memory 引擎的等值查询。
设计原则：根据查询模式选择索引，平衡读写性能与存储成本。