深入理解MySQL索引底层数据结构

---

---

前言

MySQL 索引的底层实现是数据库性能优化的核心，其核心数据结构是 B+Tree。

---

一、MySQL索引是什么？

索引是帮助MySQL高效获取数据的排好序的数据结构。就像是书的目录一样，排好序方便我们快速检索需要的内容。

二、索引的核心需求

• 快速定位数据：避免全表扫描，降低时间复杂度（从O(n)到O(log n)）
• 范围查询高效：支持 BETWEEN、>、< 等范围操作
• 磁盘IO优化：减少磁盘随机访问次数（B+Tree 的矮胖结构是关键）

三、MySQL为什么选择B+Tree做为数据结构

1.如果使用的是Hash 做为数据结构

• 优点：对索引的 key 进行一次 hash 计算就可以定位出数据存储的位置
• 缺点：如果数据量大，容易出现hash碰撞效率也不会很快，同时仅能满足 “ =” ，“ IN” 查询，不支持范围查询。
  

2.如果使用二叉树做为数据结构

• 优点：查找效率快，同时二叉树天然保持数据有序，支持范围查找。同时二叉树数据结构简单便于维护。
• 缺点：二叉树不能自己维护平衡，一旦出现下图的情况（链表）则效率会大大减弱。同时数据量过大二叉树的高度过高，查询效率依旧很慢。
  

3.使用红黑树做为数据结构

• 优点：红黑树在插入和删除操作时能够保持较好的平衡性，通过颜色标记和自旋保持自身平横。
• 缺点：数据量过大时，红黑树的高度会很高，影响查找效率，同时红黑树的实现相对复杂，需要维护节点的颜色和平衡规则，这在大量插入和删除操作时可能会导致频繁的树重构。红黑树的结构也不适合范围查询，因为其数据分散在各个节点中
  

4.使用B-Tree做为数据结构

• 优点：B-Tree通过多路搜索和平衡特性，能够快速定位数据，适合大量数据查询，插入和删除操作会自动调整树的结构，保持平衡，确保性能稳定。叶子节点在同一深度，查询效率快。
• 缺点：B-Tree索引需要额外的空间来存储索引结构，因为叶子节点包含了数据。
  

5.B+Tree做为数据结构

B+Tree是在B-Tree的结构上进行优化的，使其更适配于做为MySQL索引。B+Tree的所有非叶子节点不存储数据，可以设置更多的索引。叶子节点存储数据，同时叶子节点维护双向链表，更方便于快速查询。

4.B+Tree深度剖析

结构特性

• 叶子节点结构：
  存储 完整数据记录（InnoDB 聚集索引）
  通过双向链表连接，支持高效范围遍历

• 非叶子节点：
  仅存储 键值 + 子节点指针（非数据区）
  单节点可存储更多键值，降低树高度

与 B-Tree 的关键区别

5.InnoDB索引实现

聚集索引

聚集索引也叫主键索引，主键索引的叶子节点存储行的所有数据，查询速度极快，避免回报操作。

非聚集索引

非聚集索引也叫二级索引，叶子节点存储主键值，要想获取其他数据，则需要通过主键（聚集索引）再去查询一次，获取行所有数据。也就是所说的回表，可以使用联合索引，将要获取的字段值放在索引中，避免回表操作，提高查询效率。

6.为什么建议 InnoDB 表必须建主键，并且推荐使用整型的自增主键？

使用InnoDB引擎如果没有设置主键，则引擎会自动帮助我们维护一个主键（自增主键），这个主键我们看不到，都是引擎给维护处理的，方便我们查找数据，这个工作交给引擎的话会增加引擎的负担，影响查询效率。B+Tree的数据结构我们也学习过了，他会帮助我们进行数据的排序，如果使用的是UUID或字符串，还会再多一个转换和排序的处理。

---

总结

以上就是今天要讲的内容，本文介绍了MySQL使用索引的优势，同时讲了MySQL索引选择B+Tree做为数据结构的原因。