为什么MySQL索引使用B+树数据结构？

B+树的基本概念

B+树是一种自平衡的多路搜索树，是B树的变体。它具有以下特点：

所有数据记录都存储在叶子节点上
非叶子节点只存储键值和指针，不存储实际数据
叶子节点之间通过指针连接，形成一个有序链表
查询效率稳定，时间复杂度为O(log n)

--- title: B+树结构示意图 --- graph TD A["根节点 键值+指针"] --> B["内部节点 键值+指针"] A --> C["内部节点 键值+指针"] B --> D["叶子节点 键值+数据指针"] B --> E["叶子节点 键值+数据指针"] C --> F["叶子节点 键值+数据指针"] C --> G["叶子节点 键值+数据指针"] D -.-> E E -.-> F F -.-> G style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px style F fill:#f9f,stroke:#333,stroke-width:2px style G fill:#f9f,stroke:#333,stroke-width:2px

与其他数据结构的比较

二叉搜索树

特性	二叉搜索树	B+树
结构	每个节点最多两个子节点	每个节点可以有多个子节点
高度	可能很高，导致IO次数多	高度较低，IO次数少
查询效率	O(log n)，但可能退化	稳定的O(log n)
范围查询	需要中序遍历	叶子节点链表，高效

B树

特性	B树	B+树
数据存储	所有节点都存储数据	只有叶子节点存储数据
查询稳定性	不稳定，可能在非叶子节点找到	稳定，必须到叶子节点
范围查询	效率较低	叶子节点链表，高效
节点利用率	相对较低	相对较高

哈希索引

特性	哈希索引	B+树索引
查询效率	O(1)	O(log n)
范围查询	不支持	高效支持
排序	不支持	天然支持
前缀匹配	不支持	支持
空间占用	相对较小	相对较大

B+树的优势特性

1. 磁盘IO优化

多路平衡：B+树是多路平衡树，每个节点可以拥有多个子节点，使得树的高度大大降低
减少IO次数：树的高度越低，查询时磁盘IO次数越少，查询效率越高
块存储优化：B+树的节点大小通常设计为与磁盘块大小相匹配，一个节点可以一次性读入内存

--- title: B+树与二叉树高度对比 --- graph LR subgraph B+树 A1["根节点"] --> B1["内部节点"] B1 --> C1["叶子节点"] B1 --> C2["叶子节点"] B1 --> C3["叶子节点"] end subgraph 二叉搜索树 A2["根节点"] --> B2["左子节点"] A2 --> B3["右子节点"] B2 --> C4["左叶子"] B2 --> C5["右叶子"] B3 --> C6["左叶子"] B3 --> C7["右叶子"] end style C1 fill:#f9f,stroke:#333,stroke-width:2px style C2 fill:#f9f,stroke:#333,stroke-width:2px style C3 fill:#f9f,stroke:#333,stroke-width:2px style C4 fill:#f9f,stroke:#333,stroke-width:2px style C5 fill:#f9f,stroke:#333,stroke-width:2px style C6 fill:#f9f,stroke:#333,stroke-width:2px style C7 fill:#f9f,stroke:#333,stroke-width:2px

2. 范围查询高效

有序链表结构：B+树的叶子节点通过指针连接成一个有序链表
顺序访问：对于范围查询，只需定位到起始节点，然后沿链表顺序访问即可
避免回溯：不需要像B树那样在不同层级之间来回移动

--- title: B+树范围查询示意图 --- graph LR A["根节点"] --> B["内部节点"] B --> C["叶子节点 10-20"] B --> D["叶子节点 21-30"] B --> E["叶子节点 31-40"] C -.-> D D -.-> E subgraph 范围查询15-35 direction LR F["定位到15"] --> G["顺序访问到35"] end C -.-> F E -.-> G style C fill:#f9f,stroke:#333,stroke-width:2px style D fill:#f9f,stroke:#333,stroke-width:2px style E fill:#f9f,stroke:#333,stroke-width:2px

3. 查询性能稳定

固定查询路径：任何查询都必须从根节点到叶子节点，查询路径长度相同
稳定的时间复杂度：所有查询的时间复杂度都是O(log n)，不会出现波动
可预测的性能：数据库优化器可以准确预测查询成本

4. 节点利用率高

数据集中存储：所有数据都存储在叶子节点，非叶子节点只存储键值和指针
空间利用率高：非叶子节点可以存储更多的键值，进一步降低树的高度
缓存友好：非叶子节点可以更多地被缓存，提高查询效率

MySQL索引使用B+树的具体原因

1. 磁盘与内存的权衡

磁盘IO是瓶颈：数据库数据通常存储在磁盘上，磁盘IO速度远慢于内存访问
减少IO次数：B+树的多路特性使得树的高度很低，大大减少了磁盘IO次数
预读机制：B+树的节点大小与磁盘块匹配，可以利用操作系统的预读机制

2. 数据库查询特点

点查询和范围查询：数据库查询不仅包括单条记录查询，还包括大量范围查询
排序需求：很多查询需要结果排序，B+树的有序性天然支持排序
前缀匹配：LIKE 'prefix%'这样的查询需要有序结构支持

3. 事务和并发控制

锁粒度：B+树结构使得数据库可以实现更细粒度的锁
并发控制：B+树的结构有利于实现多版本并发控制(MVCC)
事务隔离：B+树的稳定性有助于实现不同级别的事务隔离

4. 存储引擎设计

InnoDB的选择：MySQL最常用的存储引擎InnoDB选择B+树作为索引结构
聚簇索引：InnoDB的聚簇索引使用B+树，将数据行和索引存储在一起
二级索引：InnoDB的二级索引也是B+树，存储主键值而非行指针

--- title: InnoDB存储引擎中的B+树索引结构 --- graph TD subgraph 聚簇索引 A1["根节点 主键值+指针"] --> B1["内部节点 主键值+指针"] B1 --> C1["叶子节点 主键值+完整行数据"] B1 --> C2["叶子节点 主键值+完整行数据"] C1 -.-> C2 end subgraph 二级索引 A2["根节点 索引键值+指针"] --> B2["内部节点 索引键值+指针"] B2 --> C3["叶子节点 索引键值+主键值"] B2 --> C4["叶子节点 索引键值+主键值"] C3 -.-> C4 end C3 -.-> |"通过主键回表"| C1 C4 -.-> |"通过主键回表"| C2 style C1 fill:#f9f,stroke:#333,stroke-width:2px style C2 fill:#f9f,stroke:#333,stroke-width:2px style C3 fill:#f9f,stroke:#333,stroke-width:2px style C4 fill:#f9f,stroke:#333,stroke-width:2px

B+树在MySQL中的实际应用

1. 聚簇索引

表数据组织方式：InnoDB表数据文件本身就是按B+树组织的一个索引结构
叶子节点存储：聚簇索引的叶子节点包含完整的行数据
主键依赖：如果没有定义主键，MySQL会选择第一个唯一索引作为聚簇索引

2. 二级索引

辅助索引：除聚簇索引外的其他索引都是二级索引
存储主键值：二级索引的叶子节点存储的是索引键值和对应的主键值
回表操作：通过二级索引查询时，需要通过主键值再到聚簇索引中查找完整数据

3. 联合索引

多列索引：B+树支持在多个列上创建索引
最左前缀原则：联合索引按照定义时的列顺序进行排序，支持最左前缀匹配
覆盖索引：如果查询的字段都包含在索引中，可以避免回表操作

4. 全文索引

特殊结构：MySQL的全文索引虽然使用B+树，但内部结构更为复杂
分词处理：全文索引会对文本进行分词处理，然后为每个词建立B+树索引
相关性排序：支持基于相关性的排序和查询

总结

MySQL索引使用B+树数据结构的原因可以总结为以下几点：

磁盘IO优化：B+树的多路平衡特性使得树的高度很低，大大减少了磁盘IO次数
范围查询高效：叶子节点的链表结构使得范围查询非常高效
查询性能稳定：所有查询都必须从根到叶子，时间复杂度稳定在O(log n)
节点利用率高：非叶子节点只存储键值和指针，空间利用率高
数据库查询特点匹配：B+树的特点很好地匹配了数据库查询的特点，包括点查询、范围查询和排序需求
事务和并发控制支持：B+树结构有利于实现事务和并发控制机制

B+树作为MySQL索引的数据结构，是在磁盘IO、内存使用、查询性能等多方面因素综合考量的最优选择，这也是为什么MySQL以及其他主流数据库系统都采用B+树作为索引数据结构的原因。

account_tree

思维导图

Interview AiBoxInterview AiBox — 面试搭档

不只是准备，更是实时陪练

Interview AiBox 在面试过程中提供实时屏幕提示、AI 模拟面试和智能复盘，让你每一次回答都更有信心。

免费下载 Interview AiBoxdownload 查看价格方案sell

AI 助读

一键发送到常用 AI

MySQL索引使用B+树数据结构主要基于以下几个原因：1) B+树的多路平衡特性降低了树的高度，减少了磁盘IO次数；2) 叶子节点的链表结构使范围查询高效；3) 查询路径固定，性能稳定在O(log n)；4) 非叶子节点只存储键值和指针，空间利用率高；5) 特点与数据库查询需求高度匹配，支持点查询、范围查询和排序；6) 有利于事务和并发控制的实现。这些优势使B+树成为在磁盘IO、内存使用和查询性能等方面综合考量的最优选择。

智能总结

深度解读

考点定位

思路启发