B 树用大白话讲一次MySQL 索引为什么快一条 select 跑了十秒加个索引毫秒级返回。这中间发生了什么很多人背过「索引是 B 树」但账没算过于是面试讲不清工作里也不敢动。把账算一遍就懂了慢的单位从来不是「比较了多少次」是「读了多少个磁盘页」。慢的单位是页磁盘和内存差着几个数量级CPU 比一次大小快到可以忽略从磁盘读一页数据慢到必须计较。MySQL 的 InnoDB 把数据存在页里一页 16KB。全表扫描就是把表里的页从头读到尾十万行的表每页装十来行几千上万个页慢在每个页都是一次 IO。所以优化的目标从头就是少读几页。记住一句话索引省的是 IO不是比较次数。B 树的算术索引为什么快靠的是树矮。树每高一层查找就多一次 IO把树压矮就是把 IO 压少。B 树的办法是让每个节点正好装满一页一页里塞上千个「键加指针」这叫扇出。算一笔账。一页 16KB一个键值加指针十来个字节一页能装一千多个。两层的树能索引百万级的行三层能到十亿级。千万行的表B 树只有三层查找读三个页就到全表扫描要读几十万个页。差距是几万倍这还只是 IO 次数的账。叶子之间连成链表根节点页枝节点页枝节点页叶子页数据 指向下一页叶子页叶子页B 树的叶子节点排成链表这一点是专门为范围查询留的。where age between 20 and 30顺着叶子链表滑一段就行这就是范围查询快的原因。为什么不是二叉树和哈希二叉树的问题是瘦。每个节点只有两个叉百万行的树高二十层查一次读二十个页比 B 树的三页差一个数量级。树高的每一页都是 IO这就是不用二叉树的全部理由。哈希的问题是偏科。等值查询确实快一次定位但范围查询、排序、前缀匹配全都帮不上忙age 大于 20 这种条件哈希索引直接失灵。业务里的查询条件千奇百怪B 树的「都能凑合」比哈希的「一门极快」实用。跳表呢它把有序链表加了几层索引范围查询也快Redis 的有序集合就用它。但跳表的节点是分散在内存里的每个节点还要额外存好几层指针一页 16KB 装不下几个扇出远不如 B 树。同样是千万行B 树三层读完跳表要读的页多得多。磁盘场景下把节点紧凑地塞进一页、让树变矮才是王道。联合索引、回表和覆盖索引联合索引 (a, b, c) 的排序逻辑就是电话簿。先按姓排同姓按名排同名再按年龄排。找「姓张的」可以快速翻到那一段最左前缀找「名叫三的」就得整本翻因为名的顺序只在同姓内部有效。所以 where 条件里 a 必须出现跳过 a 直接用 b 或 c索引就用不上——最左前缀原则说的就是这件事。回表是索引查到主键之后再回数据页拿其他列。select * 逼着 MySQL 每行都回一次表索引省下的 IO 又还回去了——查一万行就多一万次回表等于把 B 树省下的几万页 IO 又赔进去。只查索引里就有的列不用回表这叫覆盖索引explain 的 Extra 里会写 Using index。select 你真正需要的列是免费的性能。亲手算账下面用一段 Python 把三种查找方式的 IO 账单算出来直接运行python io_bill.py数字可以按公式手算核对。# IO 账单计算器三种查找方式各读多少个磁盘页# InnoDB 页 16KB键加指针约 14B行约 1KB 时每页约 16 行示意值PAGE_SIZE16*1024KEY_AND_POINTER86# 主键大致 8B 页指针 6BFANOUTPAGE_SIZE//KEY_AND_POINTER# 一页能装多少个键deffull_scan(rows:int,rows_per_page:int16)-int:全表扫描每一页都要读。returnrows//rows_per_pagedefbinary_tree_height(rows:int)-int:二叉树每层一次 IO层高约 log2(行数)。returnmax(1,rows.bit_length())defbplus_tree_height(rows:int)-int:B 树每层一次 IO层高由扇出撑开。height,capacity1,FANOUTwhilecapacityrows:height1capacity*FANOUTreturnheightprint(f扇出 FANOUT {FANOUT}三层可索引约{FANOUT**3:,}行\n)forrowsin(10_000,1_000_000,10_000_000):print(f{rows:10,}行 | 全表{full_scan(rows):8,}页f | 二叉树{binary_tree_height(rows):2}层f | B 树{bplus_tree_height(rows)}层)print(\n结论索引把读页次数从万级压到个位数这就是快的全部来源。)跑完看这行账单千万行的表全表扫描几十万页B 树三层这就是「加索引变快」的全部秘密。原则就一条慢 SQL 先看读了多少页。动手验证原理落地到排查就看 explain 的三个字段。key 是不是用上了你以为的索引rows 是它估计要扫的行数Extra 里 Using index 是覆盖索引Using filesort 和 Using temporary 是排序和临时表开销见到就要留神。排查顺序固定下来先 explain看 key看 rows看 Extra再决定是改索引还是改 SQL。比如一条慢 SQL 的 rows 显示扫了 50 万行key 却是空的那多半是 where 条件没吃到索引优先考虑加索引而不是调 SQL。适用边界这一篇管单机的索引原理。分库分表后的全局索引、查询优化器选错索引的调参、以及页大小和行格式的细节是更大的题目官方文档为准。EXPLAIN 的输出字段随 MySQL 版本会变看到不认识的就查对应版本的文档。原理的账算过一遍面试讲得清慢 SQL 也知道从哪下手这一篇的目的就达到了。