当前位置：首页 > news >正文

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

news 来源：原创 2025/5/19 1:18:44

文章目录

前言
一、MySQL索引是什么？
二、索引的核心需求
三、MySQL为什么选择B+Tree做为数据结构
- 1.如果使用的是Hash 做为数据结构
- 2.如果使用二叉树做为数据结构
- 3.使用红黑树做为数据结构
- 4.使用B-Tree做为数据结构
- 5.B+Tree做为数据结构
4.B+Tree深度剖析
- 结构特性
- 与 B-Tree 的关键区别
5.InnoDB索引实现
- 聚集索引
- 非聚集索引
6.为什么建议 InnoDB 表必须建主键，并且推荐使用整型的自增主键？
总结

前言

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做为数据结构的原因。