MySQL - 理解 InnoDB 的 B+ 树索引

这篇笔记想把两件事说清楚索引的结构到底长什么样、什么场景下真的能用上。这两点想通了“最左前缀”“回表”覆盖索引这些概念就不用死记靠推理就能得出结论。目录为什么需要索引索引如何演化成 B 树聚簇索引与二级索引索引不是免费的午餐B 树索引能用上的场景回表的代价与覆盖索引挑选和设计索引的经验一、为什么需要索引InnoDB 的每个数据页内部靠页目录 二分查找能很快定位到记录但页与页之间只是通过双向链表相连物理位置上并不连续。这就带来一个问题按主键查询页内可以二分查找但要先知道记录在哪一页——没有索引时只能从第一页开始顺着链表逐页查找。按其他列查询情况更差页内没有为非主键列建立目录只能从头到尾逐条记录比对。表的数据量小的时候还好一旦上到千万级这种从头扫到尾的方式基本无法接受。于是就需要一种能跳过大部分无关页面、直接定位到目标数据的机制——这就是索引。二、索引如何演化成 B 树理解索引结构关键的一步是先设想一个最朴素的方案给所有数据页建一个目录每条目录项记录该页最小的主键值 页号把这些目录项连续存放对目录本身做二分查找两步就能定位到记录。但这个方案有两个问题一个数据页最大只有 16KB表越来越大时目录项本身也会多到一页装不下——连续存放这个前提就不成立了。记录频繁增删时目录项也要跟着变动。中间删掉一条后面的目录项都要往前移动维护成本很高。InnoDB 的解决办法是直接复用存储用户记录的那套数据页结构来存储目录项本身。目录项被当作一种特殊记录处理记录头里的record_type 1用于标识同样能享受页目录 二分查找的机制。当一页装不下所有目录项时就分裂出新页上层再生成一层目录项的目录项——这样逐层往上叠加最终就形成了一棵倒置的树这就是B 树。下图是简化版结构假设每页只放 2~3 条记录实际场景中一页能放几百上千条B 树也就用不着长这么多层图中实线箭头是父子指针代表上层目录项指向下一层的具体页面虚线是双向链表代表同一层的页面前后相连。关键结论最底层第 0 层存放的是真正的用户记录称为叶子节点上面几层存放目录项记录称为内节点。有一点需要记住根节点自诞生起页号就不再变化。系统只需记住这个根页号就能顺着它找到任何数据。另外二级索引的内节点不能只保存索引列 页号否则索引列值相同时无法判断新记录该分到哪个子页——所以实际保存的是索引列 主键 页号三元组确保同一层的记录彼此可以区分。此外一个页最少要存 2 条记录否则树会退化成一条链表也就失去了索引的意义。按这个结构推算假设叶子节点能存 100 条记录内节点能存 1000 条目录项B 树 3 层就能容纳 1 亿条记录4 层能容纳千亿级——这就是索引查找只需几次 I/O的原因。三、聚簇索引与二级索引InnoDB 里每建一个索引就对应一棵独立的 B 树但按叶子节点存储内容的不同可以分成两类聚簇索引二级索引排序依据主键值索引列的值叶子节点内容完整的用户记录含所有列索引列 主键值建立方式InnoDB 自动创建无主键会隐式生成需显式CREATE INDEX数量每张表唯一一个可以建多个这里有一点容易被忽略但很重要在 InnoDB 里索引就是数据本身——聚簇索引的叶子节点直接就是数据的存储方式而不是额外的一份查找结构。二级索引的叶子节点只保存索引列 主键所以要拿到完整记录还需要拿着这个主键再查一次聚簇索引这个过程称为回表。之所以要付出回表这一次额外开销是因为如果每建一个索引都把完整记录再拷贝一份存储空间的开销会很大得不偿失。联合索引本质上仍是一棵二级索引 B 树只是排序规则变成先按第一列排序第一列相同时再按第二列排序依此类推。它和给几个列分别建索引完全是两回事——联合索引从头到尾只对应一棵树。题外话 · MyISAMMyISAM 走的是另一条路——数据文件和索引文件分开存储包括主键索引在内所有索引都只保存索引列 行号查询时同样要回表一次相当于 InnoDB 里所有索引都是二级索引的效果。四、索引不是免费的午餐建索引是有代价的主要体现在两方面空间上每建一个索引就要多生成一棵 B 树每个节点都是实打实的数据页占用存储空间。时间上每次增删改都要维护索引这棵树的排序关系可能触发页分裂、记录移位索引建得越多写入性能损耗越大。所以是否要为某列建索引还得结合下面这些能否用上索引的场景来判断。五、B 树索引能用上的场景以一个三列联合索引为例KEYidx_name_birthday_phone_number(name,birthday,phone_number)全值匹配WHERE 条件把索引里的列都用上了写在前面还是后面并不影响结果查询优化器会自动调整比较顺序。匹配左边的列最左前缀原则条件只包含索引最左边连续的几列比如只有name或者name birthday也能用上对应前缀部分的索引但如果中间跳过了一列只给name和phone_number中间的birthday缺失后面的列就用不上了。匹配列前缀字符串本身按前缀排好序所以name LIKE As%这类前缀匹配能用上索引但LIKE %As%或纯后缀匹配就不行可以考虑把字符串反转存储把后缀匹配转换成前缀匹配。匹配范围值范围查询只有最左边那一个参与范围比较的列能用上索引后面的列即使也在联合索引里也无济于事——因为范围过滤后的记录不再保证按后面那一列排好序。精确匹配 范围匹配组合前面的列都是等值匹配时紧跟着的一列做范围查询依然可以用上索引——先靠等值把范围收窄再在这个已排好序的小范围内做区间扫描。用于排序ORDER BY的列顺序如果和索引列顺序一致可以省去一次额外的文件排序filesort。前提是各列排序方向要一致不能 ASC、DESC 混用、排序列要来自同一个索引、且索引列不能被函数或表达式包裹。用于分组GROUP BY的列顺序与索引列顺序一致时同样可以省去在内存中分组的开销。六、回表的代价与覆盖索引二级索引的扫描是顺序 I/O索引列本身有序物理上也相邻而回表去聚簇索引取数据往往是随机 I/O主键值不连续。需要回表的记录越多走二级索引这条路就越不划算——极端情况下优化器甚至会放弃索引直接走全表扫描。这也是为什么LIMIT常常能让优化器更倾向于选择二级索引 回表需要回表的记录数变少了。要彻底避免回表可以使用覆盖索引查询列表里只写索引已经包含的列避免使用SELECT *这样二级索引查出的数据就已经够用不必再回聚簇索引查一次。七、挑选和设计索引的经验只为出现在WHERE、连接条件、ORDER BY、GROUP BY中的列建索引单纯出现在查询列表里的列不需要建索引。优先为基数大的列不重复值较多的列建索引——基数太小比如性别、状态位这类只有两三个取值的列索引的过滤效果有限回表比例也可能偏高。索引列的类型尽量选小能用INT就不用BIGINT主键尤其如此因为所有二级索引的叶子节点都会带一份主键值——主键类型越大所有二级索引也会跟着变大。长字符串列可以只索引前缀比如name(10)节省空间、加快比较速度但前缀索引会导致无法用索引完成排序前缀相同、后续字符不同的记录先后顺序无法确定。索引列必须单独出现在比较表达式中一旦被函数或运算包裹比如my_col * 2 4索引就会失效。主键最好使用AUTO_INCREMENT递增生成乱序插入主键容易导致数据页频繁分裂、记录移位自增主键则始终追加到最后一页性能更稳定。定期检查是否存在冗余索引比如已有(name, birthday)联合索引又单独建了(name)和重复索引同一列既是主键又建了唯一索引/普通索引这类索引只会增加维护成本没有额外收益。版本提示B 树索引的底层结构在 MySQL 5.7 和 8.0 上完全一致。8.0 在使用层面新增了几个实用特性降序索引INDEX (a DESC)真正生效5.7 里写了也是忽略的、不可见索引INVISIBLE让优化器暂时看不见某个索引用来灰度验证删了它会不会变慢而不用真删、函数索引可以直接给LOWER(name)这类表达式建索引绕开函数包裹列导致索引失效的限制。理解 InnoDB 索引的核心是抓住B 树如何从一个简单的页目录演化而来这条主线根页面不变、二级索引带主键、回表、最左前缀——这些都是这棵树的结构性质带来的自然结果而非人为规定的规则。想清楚这条推导过程索引能不能用上就变成了一个可以自行推理出的问题而不必依赖死记硬背。