MySQL 索引与 B+Tree 原理
为什么 MySQL 选择 B+Tree 而不是 B-Tree 或红黑树？最左前缀原则的根本原因是什么？从数据结构讲起。
一、索引的本质——排序的数据结构
- 1.1 索引 = 预排序 + 快速查找
- 1.2 没有索引时——全表扫描
- 1.3 有索引时——二分查找的变种
二、为什么是 B+Tree
- 2.1 哈希表——等值查询快，范围查询不行
- 2.2 二叉搜索树——高度太高，磁盘 IO 多
- 2.3 B-Tree——非叶子节点也存数据，范围查询仍需中序遍历
- 2.4 B+Tree——数据只存叶子节点，叶子节点双向链表连接
三、B+Tree 的结构
- 3.1 页（Page）——InnoDB 的最小存储单元，默认 16KB
- 3.2 非叶子节点——只存键值 + 子节点指针
- 3.3 叶子节点——存完整数据，双向链表串联
- 3.4 为什么 B+Tree 的高度很低——高扇出
四、聚簇索引与二级索引
- 4.1 聚簇索引——叶子节点存完整行数据（主键索引）
- 4.2 二级索引——叶子节点存主键值
- 4.3 回表——二级索引找到主键，再回聚簇索引查完整数据
- 4.4 覆盖索引——避免回表
五、最左前缀原则
- 5.1 联合索引的 B+Tree 结构——按字段顺序排序
- 5.2 为什么
(a, b, c)索引，WHERE b = ?用不了 - 5.3 索引下推（ICP）——5.6 的优化
六、索引失效的场景
- 6.1
LIKE '%xxx'——前缀模糊匹配 - 6.2 函数/计算——
WHERE DATE(create_time) = '2024-01-01' - 6.3 类型隐式转换——
WHERE phone = 13800138000 - 6.4 OR 条件——非索引列参与 OR
七、总结
- B+Tree 是为磁盘 IO 优化的数据结构
- 索引设计的本质是”排序字段的选择”
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 谜思录！
相关推荐
2018-06-02
SQL 执行全链路
SELECT * FROM user WHERE id = 1 —— 这简单一行，在 MySQL 内部经历了什么？ 一、MySQL 整体架构 1.1 Server 层——连接器、查询缓存、分析器、优化器、执行器 1.2 存储引擎层——InnoDB / MyISAM / Memory 1.3 架构图——各组件的位置 二、连接器 2.1 TCP 握手 + 身份认证 2.2 权限读取——连接建立时读取，之后不变 2.3 连接管理——wait_timeout 空闲连接超时 2.4 长连接 vs 短连接——长连接 OOM 问题 三、查询缓存（MySQL 8.0 已移除）...
2019-03-16
MySQL 事务隔离与 MVCC
可重复读级别下，为什么读不到别的事务已提交的数据？MVCC（多版本并发控制）是 InnoDB 的答案。 一、事务的 ACID 1.1 Atomicity——redo log（重做日志） 1.2 Consistency——由其他三个保证 1.3 Isolation——MVCC + 锁 1.4 Durability——redo log 二、四种隔离级别 2.1 READ UNCOMMITTED——脏读 2.2 READ COMMITTED——不可重复读 2.3 REPEATABLE READ（InnoDB 默认）——幻读（部分解决） 2.4 SERIALIZABLE——串行化 三、M...
2019-06-15
MySQL 锁机制详解
死锁是怎么发生的？SELECT ... FOR UPDATE 到底锁了什么？本文系统梳理 MySQL 的锁体系。 一、锁的分类总览 1.1 按粒度——全局锁、表级锁、行级锁 1.2 按模式——共享锁（S）、排他锁（X）、意向锁（IS/IX） 1.3 按算法——记录锁、间隙锁、临键锁 二、全局锁 2.1 FLUSH TABLES WITH READ LOCK——全库只读 2.2 使用场景——全库备份（mysqldump --master-data） 2.3 风险——业务停摆 三、表级锁 3.1 表锁——LOCK TABLES ... READ/WRITE 3.2 元数据锁...
2017-06-03
Netty 线程模型详解
Netty 的高性能离不开其精巧的线程模型。从 Boss 线程接收连接到 Worker 线程处理 IO，主从 Reactor 模型如何落地？ 一、Netty 线程模型概述 1.1 BossGroup 和 WorkerGroup 的职责划分 1.2 EventLoop——Netty 的线程抽象 1.3 一个 EventLoop 绑定一个线程——thread-safe 的保证 二、EventLoopGroup 的创建 2.1 NioEventLoopGroup——Boss / Worker 的创建 2.2 线程数设置——new NioEventLoopGroup(1) vs ...
2018-12-01
慢 SQL 优化实践
订单列表接口线上响应 3 秒，用户投诉不断。本文还原从发现到优化的全过程。 一、问题发现 1.1 监控告警——接口 RT P99 超 3 秒 1.2 慢查询日志——long_query_time = 1s 1.3 定位到具体 SQL 二、分析阶段 2.1 EXPLAIN 执行计划——type=ALL，全表扫描 2.2 表数据量——订单表 500 万行 2.3 当前的索引情况 三、优化 1：添加索引 3.1 创建 idx_user_status_time(user_id, status, create_time) 3.2 EXPLAIN 对比——type=ref...
2016-09-17
Kafka 高性能原理
Kafka 为什么这么快？PageCache、sendfile、顺序写盘——这些底层技术的巧妙组合成就了 Kafka 的超高吞吐。 一、Kafka 的 IO 模型 1.1 基于磁盘的消息持久化——不是内存队列 1.2 为什么用磁盘还能这么快——六字秘诀”顺序写 + 零拷贝” 1.3 传统 IO 的 4 次拷贝 + 4 次上下文切换 二、零拷贝（Zero Copy） 2.1 sendfile() 系统调用——DMA 直接传输 2.2 2 次拷贝 + 2 次上下文切换 2.3 mmap() 内存映射——另一种零拷贝 2.4 Kafka 中的 FileChannel.transferTo...