深入理解Mysql索引底层数据结构与算法
2025-10-27 22:13:50 0 举报AI智能生成
深入理解Mysql索引底层数据结构与算法
作者其他创作
大纲/内容
索引是什么？
帮助mysql高效获取数据的排好序的数据结构
索引数据结构
链表
二叉树
红黑树（平衡二叉树）
B树
B+树
Hash表
也可作为mysql索引数据结构，几乎不用hash作为mysql索引
很多时候Hash索引要比B+树索引更高效
但是仅能满足=，in，不支持范围查询
存在hash冲突问题
数组
跳表
为什么mysql选择B+树作为索引数据结构
1.链表
查询是o(n)的时间复杂度，肯定不适合
空间利用率不高，既要存储自身数据还要存储下一个节点的指针
事务支持不够，容易造成数据不一致问题
内存中存储是不连续的，容易碎片化，浪费存储空间，影响数据访问效率
2.树
一定程度上解决了链表的不足之处
树种类
二叉树
特征
最多2个分支的分层结构
左子节点小于父节点，右子节点大于父节点
复杂度
理想情况（平衡二叉树）
增删查时间复杂度是O(Log n)
最糟糕情况
退化成链表，查询时间复杂度是o(n)
优缺点
平衡时查询效率高，但失衡会退化
红黑树
特征
每个节点非红即黑
根节点是黑色
叶子节点是黑色
红色节点的子节点是黑色
任意节点到叶子节点的黑色数量相同
复杂度
它是一个自平衡的二叉树，通过红黑规则和旋转操作维持平衡，保证增删查的时间复杂度始终为O(Log n)
优点那么多为什么没选择红黑树作为mysql的索引数据结构
磁盘I/O效率
红黑树的 “二叉结构” 导致层级太多，磁盘 I/O 次数翻倍
数据存储结构
每个节点只能存一个键值和两个指针，红黑树的 “固定小节点” 在数据库海量数据面前，空间利用率太低，还不够折腾的。需要很高的树，不可控
并发控制
多用户并发时候，需要用到锁机制才能解决数据一致性问题，太麻烦
B树
又名平衡多路查找树
目的减少磁盘I/O次数，提高了查询性能
特征
m阶b树
最多有m个子节点
每个非叶子节点至少有m/2个子节点
有叶子都出现在同一水平
data存储在叶子节点和非叶子节点
叶子节点之间没有指针相连
B+树
B树的变种
与b树的区别
data存储位置
b树存在于叶子节点和非叶子节点，b+树存在于叶子节点，可以存更多的索引
叶子节点之间关联
b树叶子节点不存指针，b+树叶子节点存相邻节点的指针，通过双向指针连成链表，方便范围查询
树的高度取决于非叶子节点能够存储的索引元素，存的越多，高度越低，所以b+树更优于b树
相同点
从左到右都是递增的，排好序的
千万级数据表如何用B+树索引快速查找？
InnoDB里面默认每个节点大小是16kb，每个索引键（int8字节+指针8字节），最终这个节点可以存储16*1024/16个索引，假设三层树，最终结果也有256 × 256 × 256 ≈ 1600万，三层就有那么多索引，磁盘I/O也才3次
往往跟节点作为常驻内存，磁盘I/O减少了一次，大大提升查询性能
存储引擎
MyIsam
文件结构
.frm
.MYI
存储索引数据
.MYD
存储数据记录
主键索引
非聚集索引
索引和数据分开存储的
非主键索引
非聚集索引
InnoDB
文件结构
.frm
.ibd
索引和数据记录
主键索引
只有一个聚集索引
索引和数据存在一起的
查询效率要比非聚集索引效率高，聚集索引叶子节点里面存储的是数据记录，而非聚集索引还要再去.MYD文件中查找具体的数据，相当于回表操作
二级索引
非聚集索引
叶子节点存放的是索引和主键值
为什么非主键索引叶子节点存储的是主键值？
数据一致性
当数据行被修改时（如某字段值变更），所有包含该数据的非主键索引都需要同步更新，否则会出现 “索引与数据不一致” 的情况。这会大幅增加更新操作的开销，减少复杂度
节省存储空间
为什么InnbDB表必须建主键，并且推荐使用整型自增主键？
问题1，必须建主键？
1.表数据文件是按照B+树组织的一个索引结构文件，如果有主键，就直接用主键来组织文件
2.如果没有主键，会从第一列从左往右找，选一个数据都不重复的列，作为主键。
3.如果找不到任何一列，则建一个隐藏列rowid来作为主键
4.mysql资源非常宝贵，反正最终要有一个主键，不如自己动手去建一个主键
问题2，推荐使用整型？
整型比较会快些，相对于字符串一个个字符比较
索引占用空间小，节约磁盘空间
问题3，推荐使用自增主键？
如果是非自增的，可能会发生分裂，树可能会自平衡
效率高
联合索引
多个字段组合的索引
最左前缀原理
收藏
0 条评论
下一页
