一没有索引时MySQL 怎么找到一条数据假设你有一张表CREATE TABLE tb_user ( id INT PRIMARY KEY, name VARCHAR(50), age INT );表里有 100 万行数据物理上这些数据按插入顺序存放在磁盘文件里乱序的。当你执行SELECT * FROM tb_user WHERE age 25;MySQL 只能从第一行开始逐行读取到内存检查age是否等于 25。这就是全表扫描。弊端100 万行数据哪怕只有 1 条符合也要读 100 万次每次读取都可能触发一次磁盘 IO数据不在内存缓存中时磁盘 IO 是毫秒级的100 万次就是几十秒甚至几分钟因为全表扫描的性能不可接受所以必须设计一种不用逐行看就能直接跳到目标数据的机制。这就是索引。二索引的雏形——如果数据是有序的如果age这一列的数据在磁盘上是排好序的那查找age 25就可以用二分查找直接跳到中间位置发现age 5025 比 50 小去左半区中间找发现age 2025 比 20 大去右半区找找到age 25100 万条数据最多只需要查 20 次log₂(1000000) ≈ 20。但问题是表数据本身不可能按每一列都排好序。数据只能有一种物理存储顺序。所以索引的设计思路是单独维护一份排好序的数据结构里面只存你要查的字段值和对应行的位置不存整行数据。三为什么不用哈希表你可能想到用哈希表把age的值哈希一下O(1) 直接定位不是更快吗-- 哈希索引age25 → 哈希计算 → 直接拿到磁盘地址MySQL 确实支持哈希索引Memory 引擎默认用InnoDB 也有自适应哈希但它有一个致命弊端哈希表只支持等值查询不支持范围查询和排序。-- 等值查询哈希可以 WHERE age 25 -- 范围查询哈希完全无能为力 WHERE age 20 AND age 30 ORDER BY age因为哈希函数把值打散了相邻的值哈希后可能天各一方没有任何顺序关系。要做范围查询只能全表扫描。因为哈希表不支持范围查询所以索引不能只用哈希表。四为什么不用二叉搜索树既然需要有序那用二叉搜索树BST行不行每个节点存一个age值左小右大。可以但有一个工程问题二叉树的深度太大。100 万条数据二叉搜索树深度约为 20。这意味着查一次最多要访问 20 个节点。弊端在于磁盘 IOMySQL 的数据是存在磁盘上的一个节点通常就是一个磁盘页16KB。但在二叉树里一个节点只存一个值 两个指针远远没填满 16KB。查 20 个节点 20 次磁盘 IO每次磁盘 IO 约 10ms20 次就是 200ms而且如果数据分布不均二叉树可能退化成链表深度变成 100 万直接爆炸。AVL 树和红黑树通过自旋保证了平衡深度稳定为 log₂N但每个节点仍然只存一个值深度还是太大磁盘 IO 次数降不下来。因为二叉树深度大导致磁盘 IO 太多所以必须让树的每一层能存更多数据减少树的高度。五B 树——让每个节点存多个值B 树B-Tree的设计是一个节点不再只存一个值而是存多个值并且有多于两个的子节点。比如一个节点存 1000 个值就有 1001 个子节点。100 万条数据B 树的高度只需要 2-3 层第 1 层1000 个值第 2 层1000 × 1000 100 万个值查一次最多 3 次磁盘 IO性能大幅提升。B 树的结构每个节点是一个磁盘页16KB正好对应一次 IO节点内有序节点间有序既支持等值查询也支持范围查询因为有序但 B 树还有优化空间B 树中数据行本身或指向数据的指针是分散存储在每个节点里的不管是叶子节点还是非叶子节点都既存索引值又存数据。这带来两个弊端非叶子节点存了数据占用空间大一个 16KB 页能存的索引值变少树的高度被迫增加范围查询效率不高——查age 20 AND age 30找到 20 后需要在不同层级的节点间来回跳转磁盘随机 IO 多因为 B 树的数据分散在各节点导致非叶子节点不够紧凑、范围查询不够高效所以 MySQL 最终选择了 B 树。六B 树——MySQL 索引的最终结构B 树在 B 树基础上做了两个关键改进改进 1数据只存在叶子节点非叶子节点只存索引值和指针不存实际数据或数据地址。这样非叶子节点极其紧凑一个 16KB 页能存上千个索引值树的高度可以压到 3-4 层就能管理上亿条数据。改进 2叶子节点用链表连接所有叶子节点按顺序用双向链表连接起来。这两个改进解决了什么问题问题B 树B 树等值查询可以可以范围查询需要在不同层级节点间跳转找到起始叶子后顺着链表顺序读取连续 IO极快全表扫描需要遍历整棵树直接顺序遍历叶子链表即可非叶子节点空间存数据存不了多少索引只存索引极度紧凑B 树的查询过程SELECT * FROM tb_user WHERE age 25;从根节点常驻内存开始判断 25 应该在哪个子节点加载对应的非叶子节点1 次磁盘 IO继续判断加载对应的叶子节点1 次磁盘 IO在叶子节点内找到age 25拿到对应的数据地址如果是非主键索引再用主键去主键索引查一次回表范围查询SELECT * FROM tb_user WHERE age 20 AND age 30;先按上面的流程找到age 20所在的叶子节点然后顺着叶子节点的链表往后读直到超过 30整个过程是顺序 IO性能极高七聚簇索引 vs 非聚簇索引MySQL 的 InnoDB 引擎里B 树索引分两种这是理解索引的最后一个关键。聚簇索引Clustered Index——主键索引叶子节点存的不是地址而是整行数据本身。-- 主键索引的 B 树 非叶子节点[10 | 50 | 100] → 指针 叶子节点[id1, name张三, age20, ...] → [id2, name李四, age25, ...] → ...设计原因表数据在物理上只能有一种排序方式。InnoDB 选择用主键作为这个排序依据把整张表的数据按主键顺序组织成一棵 B 树。没有主键怎么办优先用你定义的主键没有主键用第一个非空唯一索引还没有隐式生成一个 6 字节的row_id所以 InnoDB 的表数据本身就是按主键索引组织的主键索引查到的叶子节点就是完整数据行不需要回表。非聚簇索引Secondary Index——普通索引如果你给age列建一个索引CREATE INDEX idx_age ON tb_user(age);这棵 B 树的叶子节点不存整行数据而是存[age20, id1] → [age25, id2] → [age25, id5] → ...为什么叶子只存主键不存整行数据因为一行数据可能有几 KB如果每个二级索引的叶子都存整行数据索引体积膨胀几十倍浪费大量磁盘空间一个 16KB 页存不了几条记录树变高查询变慢维护成本极高改一行数据要更新所有索引所以二级索引只存索引列 主键。当你用二级索引查询SELECT * FROM tb_user WHERE age 25;在idx_age索引树找到age 25的叶子节点拿到主键id再用这个id去主键索引树查整行数据这个过程叫回表。回表的弊端需要查两棵 B 树两次索引树查找如果返回的数据量很大回表次数多性能下降优化——覆盖索引SELECT id, age FROM tb_user WHERE age 25;你查的列只有id和age而idx_age的叶子里正好有这两个值不需要回表。这就是前面讲的覆盖索引。八索引的代价——为什么不是每列都建索引索引不是免费的午餐它有三个明显代价1. 占用额外空间每建一个索引就要额外存一棵 B 树。100 万条数据的表3 个索引 ≈ 4 倍存储空间。2. 写操作变慢插入、删除、更新时MySQL 不仅要改表数据还要维护所有索引树插入要在每棵索引树的正确位置插入节点可能触发节点分裂删除要删除索引节点可能触发节点合并更新如果更新了索引列要删除旧索引值、插入新索引值索引越多写操作越慢。3. 优化器选错索引的风险索引多的时候MySQL 优化器可能算错成本选择一个不合适的索引反而比全表扫描还慢。所以索引设计原则是只为频繁查询、频繁作为条件的列建索引写多读少的表要慎重。总结逻辑链阶段问题/弊端解决方案无索引全表扫描磁盘 IO 爆炸需要快速定位的数据结构哈希表不支持范围查询和排序放弃哈希用有序树结构二叉树深度大磁盘 IO 次数多让每个节点存多个值 → B 树B 树数据分散非叶子节点不紧凑范围查询随机 IO 多数据只放叶子叶子链表连接 → B 树表数据存储只能有一种物理顺序用主键组织数据 → 聚簇索引其他列索引不能每棵索引都存整行数据叶子只存主键 → 二级索引 回表索引维护写操作要更新多棵树权衡读写比例谨慎建索引
