MySQL底层数据结构与算法浅析
1、概述
MySQL中，当我们发现某个sql的执行时间很长时，最先想到的就是给表加索引，加了索引之后，查询性能就会有显著的提升。
为了知其所以然，那么只有去了解MySQL的底层储存结构和索引的查询算法，只有这样才能写出性能更好的sql和知道如何去优化一个慢SQL。
下文会简单的介绍MySQL的底层数据结构与算法。
2、数据结构与算法演进
任何一个好的产品，都是不断的优化才能到今天这么成熟和好用。MySQL也是一样，它也考虑过存储结构的优化过程。
后文都以磁盘中存储了8条表数据，并且磁盘位置索引以index代指、磁盘存放的表数据以value代指为例：
(index, value)
(1, '{id: 1, name: xm}') // 磁盘索引1的位置，存储了一条表数据{id: 1, name: xm}
(2, '{id: 2, name: df}')
(3, '{id: 3, name: tr}')
(4, '{id: 4, name: ui}')
(5, '{id: 5, name: ue}')
(6, '{id: 6, name: gh}')
(7, '{id: 7, name: re}')
(8, '{id: 8, name: uu}')
数据说明
如果我要读取id为3的数据，按照顺序全量遍历的流程：
1、先把磁盘索引index为1的磁盘数据加载到内存，然后发现id不等于3
2、然后把磁盘索引index为2的磁盘数据加载到内存，然后发现id不等于3
3、最后把磁盘索引index为3的磁盘数据加载到内存，才发现这个id等于3，然后返回
以上总共进行了3次磁盘IO。(一次磁盘IO比内存IO耗时多很多)
2.1、二叉树
为了方便检索，大家很容易想到的就是先排好序之后，然后进行二分查找，这样效率相比于全量遍历每次就减少一半的范围，即查询复杂度就降为了O(logN)。
2.1.1、存储结构示例
当我们表id以1、3、2、4、8、6、7、5的顺序存入，就会变成下面这样：
插入id=1：作为根节点，磁盘索引1，name=xm
插入id=3：比1大，放在1的右子树，磁盘索引3，name=tr
插入id=2：比1大，比3小，放在3的左子树，磁盘索引2，name=df
插入id=4：比1、3都大，放在3的右子树，磁盘索引4，name=ui
插入id=8：比1、3、4都大，放在4的右子树，磁盘索引8，name=uu
插入id=6：比1、3、4大，比8小，放在8的左子树，磁盘索引6，name=gh
插入id=7：比1、3、4、6大，比8小，放在6的右子树，磁盘索引7，name=re
插入id=5：比1、3、4大，比6、8小，放在6的左子树，磁盘索引5，name=ueindex=1(id:1, name:xm)\index=3(id:3, name:tr)/ \index=2(id:2, name:df) index=4(id:4, name:ui)\index=8(id:8, name:uu)/index=6(id:6, name:gh)/ \index=5(id:5, name:ue) index=7(id:7, name:re)
如果要检索id为8的数据，那么仅需要检索4次即可。如果是从头开始遍历那么就会查找8次，这样分析下来，使用二叉树比使用全量顺序遍历节省了很多时间。
但是这只是常规的情况，如果插入是这样顺序插入：
插入id=1：作为根节点，磁盘索引1，name=xm
插入id=2：比1大，放在1的右子树，磁盘索引2，name=df
插入id=3：比1、2都大，放在2的右子树，磁盘索引3，name=tr
插入id=4：比1、2、3都大，放在3的右子树，磁盘索引4，name=ui
插入id=5：比前面所有节点都大，放在4的右子树，磁盘索引5，name=ue
插入id=6：比前面所有节点都大，放在5的右子树，磁盘索引6，name=gh
插入id=7：比前面所有节点都大，放在6的右子树，磁盘索引7，name=re
插入id=8：比前面所有节点都大，放在7的右子树，磁盘索引8，name=uuindex=1(id:1, name:xm)\index=2(id:2, name:df)\index=3(id:3, name:tr)\index=4(id:4, name:ui)\index=5(id:5, name:ue)\index=6(id:6, name:gh)\index=7(id:7, name:re)\index=8(id:8, name:uu)
这样的话，会导致查询id为8的记录时，依旧要查询8次，也就跟全量遍历没区别了。可以试想一下，单表如果使用自增ID的话，那么查询一次的耗时将每次都是最长路径。因此MySQL没有选择此数据结构。
2.2、红黑树(二叉平衡树)
普通的二叉树会有单边子树无限增长导致成为单链表的缺陷，红黑树就是为了解决这个问题的，它检测到左右子树的层级相差时会左右自动平衡。
2.2.1、存储结构示例
以上面的1~8顺序插入为例：
│ 步骤1: 插入id=1
│ index=1(id:1, name:xm) [BLACK]
│ - 插入第一个节点，直接作为根节点，根节点必须是黑色
│
│ 步骤2: 插入id=2
│ index=1(id:1, name:xm) [BLACK]
│ \
│ index=2(id:2, name:df) [RED]
│ - 2 > 1，插入到1的右子树，新节点初始为红色
│
│ 步骤3: 插入id=3
│ index=1(id:1, name:xm) [BLACK]
│ \
│ index=2(id:2, name:df) [RED]
│ \
│ index=3(id:3, name:tr) [RED]
│ - 违反性质：连续两个红色节点(2和3)
│ - 修复操作：左旋转1节点，重新着色
│
│ 修复后：
│ index=2(id:2, name:df) [BLACK]
│ / \
│ index=1(id:1, name:xm) index=3(id:3, name:tr)
│ [RED] [RED]
│
│ 步骤4-8: 继续插入id=4,5,6,7,8
│ 经过多次旋转和重新着色操作后，最终达到平衡状态：
│
│ index=4(id:4, name:ui) [BLACK]
│ / \
│ index=2(id:2, name:df) index=6(id:6, name:gh)
│ [BLACK] [BLACK]
│ / \ / \
│ index=1 index=3 index=5 index=7
│ (id:1,xm) (id:3,tr) (id:5,ue) (id:7,re)
│ [RED] [RED] [RED] [RED]
│ \
│ index=8(id:8,uu)
│ [BLACK]
│
│ 关键修复操作类型：
│ 1. 左旋转：当右子树过高时，将右子节点提升为新的根节点
│ 2. 右旋转：当左子树过高时，将左子节点提升为新的根节点
│ 3. 重新着色：调整节点颜色以满足红黑树性质
│ 4. 复合操作：结合旋转和重新着色来维护平衡 index=4(id:4, name:ui) [BLACK]/ \index=2(id:2, name:df) index=6(id:6, name:gh)[BLACK] [BLACK] / \ / \
index=1 index=3 index=5 index=7
(id:1,xm) (id:3,tr) (id:5,ue) (id:7,re)
[RED] [RED] [RED] [RED]\index=8(id:8,uu)[BLACK]
这样每次在插入时平衡后，就能稳定查询复杂度在O(logN)。
但是这里列举的只是8条数据，如果实际存储了上百万条数据，树的层级就会非常高了，依旧捉襟见肘，因此MySQL依旧没有使用这个存储结构。
2.3、B树
既然节点越多，二叉树的高度就越高。那么有没有一种办法可以让树的高度降下来呢？
B树就是解决这个问题的：
- 内存IO肯定比磁盘IO快几个数量级，那么在一个树的节点中放更多的磁盘索引就可以把节点个数缩减下来
- B树就是这么干的， 一个节点中存储不止一个（id， 磁盘索引index）数据，这样数据的高度就降下来了
- 到底一个节点存了多少个（id, 磁盘索引）呢？这就跟计算机的数据页概念有关，计算机把数据从磁盘加载到内存，是按数据页为单位批量加载的
- 一个页16KB数据，如果按照一个普通二叉树节点14B（bigint 8 + 磁盘地址 6）来算大约可以存储1170个普通节点!
2.3.1、存储结构示例
仅按照一个节点存储3个：
│ 根节点 │
│ [index=2(id:2,df) | index=4(id:4,ui) | index=6(id:6,gh)] │
│ / | | \ │
│ [index=1] [index=3] [index=5] [index=7|index=8] │
│ (id:1,xm) (id:3,tr) (id:5,ue) (id:7,re|id:8,uu)
可以看到，在一个节点存三个索引的情况下，仅需要2层就存下了8个数据。 当查询id为8 的数据时，仅需要花费磁盘IO2次。
但是这依旧不是MySQL如今的存储数据结构：
- B树的节点中存储了磁盘索引+id数据，好像只需要在非叶子节点存储id数据，叶子节点存储磁盘索引就可以了，这样可以让一个B树节点存储更多的内容。
- sql语句中还有范围查找，这个B树结构貌似也不能很好的支持。
2.4、B+树（B树升级版）
MySQL如今就是采用的这个数据结构
1、为了让B树一个节点存储的更多，直接将非叶子节点仅存储索引id，然后叶子节点存储索引id+磁盘索引index
2、为了支持范围查找，直接让叶子节点支持前后的磁盘索引指针，这样就能方便的向前或向后查找。
2.4.1、存储结构示例
仅按照一个节点存储3个：
│ 内部节点
│ [id=3 | id=6]
│ / | \
│ 叶子节点1 叶子节点2 叶子节点3
│ [id=1|id=2] [id=3|id=4|id=5] [id=6|id=7|id=8]
│ (index=1,name:xm| (index=3,name:tr| (index=6,name:gh|
│ index=2,name:df) index=4,name:ui| index=7,name:re|
│ index=5,name:ue) index=8,name:uu)
│
│ 叶子节点链式指针连接：
│ ┌─────────────┐ next ┌─────────────┐ next ┌─────────────┐
│ │ 叶子节点1 │ ────────→ │ 叶子节点2 │ ────────→ │ 叶子节点3 │
│ │ [id=1|id=2] │ ←──────── │[id=3|id=4|id=5]│ ←──────── │[id=6|id=7|id=8]│
│ └─────────────┘ prev └─────────────┘ prev └─────────────┘
│
特别说明
1、叶子节点中，除了了放索引id之外，不一定放的就是表数据本身（index=xx,name:xx），这个跟存储引擎有关。
2、如果是InnoDB存储引擎（聚簇索引）: 叶子节点中索引和表数据是直接放在一起的，也就是本示例。
3、如果是MyISAM存储引擎（非聚簇索引）：叶子节点中仅放索引 和 磁盘索引index（磁盘地址）。
4、按照常用的InnoDB存储引擎来算，一个表数据1KB占用，那么树的高度为3时，可以存储上千万级别数据（1170 x 1170 x 16）
5、另外值得一提的是，一般来说MySQL会把根节点常驻内存(InnoDB的Buffer Pool)，高版本的MySQL会把非叶子节点常驻内存，实际查询会比想象的更快。
│ 1. **InnoDB Buffer Pool 缓存机制**：
│
│ ┌─────────────────┐
│ │ Buffer Pool │ ← MySQL内存缓存区域
│ │ (默认128MB) │
│ └─────────────────┘
│ │
│ ├─ 索引页缓存 (Index Pages)
│ ├─ 数据页缓存 (Data Pages)
│ └─ 日志缓存等其他
│
│ 2. **B+树节点缓存优先级**：
│
│ 优先级从高到低：
│ ┌────────────────────────────────────────────────────────────┐
│ │ 1. 根节点 (Root Node) - 几乎100%常驻内存 │
│ │ 2. 第一层非叶子节点 - 高频访问，优先缓存 │
│ │ 3. 第二层非叶子节点 - 根据访问频率缓存 │
│ │ 4. 叶子节点 (Leaf Nodes) - 根据LRU算法缓存 │
│ └────────────────────────────────────────────────────────────┘
│
│ 3. **实际查询性能分析**：
│
│ 假设一个4层B+树索引：
│ ┌─────────────────┐
│ │ 根节点 │ ← 内存中 (0次磁盘I/O)
│ │ [缓存100%] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 第1层非叶子节点 │ ← 内存中 (0次磁盘I/O)
│ │ [缓存90%+] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 第2层非叶子节点 │ ← 可能在内存 (0-1次磁盘I/O)
│ │ [缓存60%+] │
│ └─────────────────┘
│ │
│ ┌─────────────────┐
│ │ 叶子节点 │ ← 可能需要磁盘读取 (0-1次磁盘I/O)
│ │ [缓存视情况] │
│ └─────────────────┘
│
│ 4. **MySQL版本演进的优化**：
│
│ MySQL 5.1及以前：
│ - 主要缓存热点数据页
│ - 根节点通常在内存，但不保证
│
│ MySQL 5.5-5.7：
│ - InnoDB成为默认引擎
│ - 改进Buffer Pool算法
│ - 更智能的索引页预加载
│
│ MySQL 8.0+：
│ - 自适应哈希索引 (Adaptive Hash Index)
│ - 更大默认Buffer Pool
│ - 智能预读算法
│ - 压缩页缓存
│
│ 5. **实际性能提升效果**：
│
│ 理论磁盘I/O次数：4次 (4层树)
│ 实际磁盘I/O次数：1-2次 (缓存优化后)
│ 性能提升：50-75%
│
│ 查询时间对比：
│ - 无缓存：4次磁盘I/O ≈ 40ms (假设10ms/次)
│ - 有缓存：1次磁盘I/O ≈ 10ms
│
│ 6. **相关配置参数**：
│
│ innodb_buffer_pool_size - Buffer Pool大小
│ innodb_old_blocks_pct - LRU算法参数
│ innodb_read_ahead_threshold - 预读阈值
│ innodb_adaptive_hash_index - 自适应哈希索引
│
│ 7. **验证方法**：
│
│ SHOW ENGINE INNODB STATUS; -- 查看Buffer Pool命中率
│ SELECT * FROM INFORMATION_SCHEMA.INNODB_BUFFER_PAGE; -- 查看缓存页面
3、拓展
3.1、MySQL表实际存储文件
1、如果是InnoDB存储引擎（聚簇索引），仅会存储在表名.frm（存储表结构）、表名.idb（存储索引 + 表数据）中。
2、如果是MyISA存储引擎（非聚簇索引），会存储在表名.frm（存储表结构）、表名.MYD（存储表数据）、表名.MYI（存储表索引）中。
由上可知，存储引擎是以表为载体的。（一个库里面可以存在不同存储引擎的表）
特别说明
1、InnoDB的主键索引才是聚簇索引，因为非主键索引查询全量记录时，都需要回表到主键索引二次查询，因此非主键索引也就不算聚簇索引了。
3.2、MySQL表隐藏列
从上面了解到，表数据存储，肯定是要设定一个索引的。如果在建表是如果不设置主键和索引会发现什么？
1、首先MySQL自己会逐列去检索是否每行是唯一的，如果是，则直接内部定为主键索引并维护。
2、如果找不到唯一的列，MySQL就会自己加个隐藏列，也就是列编号来维护主键索引。
由上可知，在建表时，建议制定主键列，避免MySQL额外维护主键的开销。当然，推荐使用整型自增的列作为主键更好（整型比字符串占用的空间更小 且方便比对 且方便范围查询 且更易于让索引维护有序性）。
3.3、Hash索引的优与劣
1、优点：仅需要进行一次Hash算法就可以定位到hash槽，比遍历B树的层级快。
2、缺点：1> 有Hash碰撞的情况，那是hash槽对应的链表是单链表，复杂度不稳定。 2> hash很难支持范围查找。
由上可知，在表存储场景下，弊大于利。
3.4、二级索引存储内容
InnoDB存储引擎：
1、子节点仅会存储主键索引（一般就是ID）。 – 因此二级索引需要拿到全量表字段数据时需要回表查询
2、这样做的原因：1> 维护主键与二级索引直接的一致性。 2> 节省磁盘空间。
MyISA存储引擎：
1、主键与二级索引的子节点都是存储的磁盘索引（磁盘地址）。
上面2个之所以有差异，是因为它们本身的设计就不一样。InnoDB的全数据都是存在主键叶子节点的，因此只能回表。 但是MyISA的主键索引是直接存磁盘索引（磁盘地址）的，因此其二级索引页指向磁盘索引。
3.5、二级索引之联合索引的结构
1、联合索引和主键索引的差别：
- 主键索引的字段仅有一个（一般是id）
- 联合索引的字段不止一个（例如：age, name2个及以上字段同时作为索引）
2、联合索引的比较规则：跟字符串比较类似，先比较age，如果age一样，再比较name。
3、结构示例：
│ 内部节点
│ [(age=22,name=tr) | (age=28,name=gh)]
│ / | \
│ 叶子节点1 叶子节点2 叶子节点3
│ [(age=18,name=xm)| [(age=22,name=tr)| [(age=28,name=gh)|
│ (age=20,name=df)] (age=22,name=ui)| (age=30,name=re)|
│ (age=25,name=ue)] (age=32,name=uu)]
│ ↓ ↓ ↓
│ [id=1|id=2] [id=3|id=4|id=5] [id=6|id=7|id=8]
由上可知，“最左前缀匹配”索引优化的由来。