问题背景
上一篇算清了"页"的账：一行数据带着记录头、NULL 位图和变长列表挤进 16KB 的页，页满就分裂。但那些页之间还只是零散文件，本篇解决下一个问题：三千万行的表，为什么WHERE id=8765432只读三四个页就能命中？答案是把页组织成一棵 B+Tree——InnoDB 全部索引（聚簇与二级）都长在这棵树上的统一结构里。而线上最常见的索引事故，几乎都源于对这棵树的两处细节理解不到位：一是二级索引叶子只存"索引列 + 主键"，拿其余列要回表；二是联合索引是整个元组排序，条件只有翻译成排序序列上的连续区间才能参与定位，这就是"最左前缀"的几何本质。LIKE 'abc%'为什么能走索引、LIKE '%abc'为什么不能，WHERE city='上海' AND age>25 AND level='gold'里level到底有没有被索引用到，都逃不出这两条。本篇回答四个问题：B+Tree 为什么是页存储的最优组织方式；聚簇与二级索引的两棵树怎么互相引用；联合索引的排序规则如何决定定位深度；以及索引设计的工程方法论。
核心原理
第一，为什么是 B+Tree 而不是别的。候选里哈希索引等值查找 O(1) 最快，但它只认全键相等，既不支持范围扫描也不支持排序，一个BETWEEN就退化全表；红黑树一类二叉树深度是 log2(n)，三千万行要下沉 25 层，每层一次页读，磁盘上不可接受。B+Tree 的关键设计是数据全在叶子层，内部节点只存"分隔键 + 页指针"：一个内部页 16KB 能塞上千个指针（BIGINT 键 8 字节 + 页号约 6 字节，扇出约 1023），于是树可以压得极矮——378 行/页 × 1023 × 1023，三层树就能覆盖约 3.9 亿行。所有叶子在同一层，任何主键查询路径长度相同、延迟稳定；叶子之间再用双向链表串起来，WHERE id BETWEEN和ORDER BY id沿着叶链走，不必回到上层。页是 IO 原子单位这个前提（上一篇）决定了树的高度就是读放大，所以"扇出大、层高矮"是页式存储索引的第一设计目标。
第二，一张表其实是多棵树。聚簇索引就是表本身：叶子页放整行数据，按主键排序（上一篇的槽式页正是它的叶子）。每个二级索引是另一棵独立的树：叶子不存行，只存"索引列值 + 聚簇主键值"。于是SELECT * FROM t WHERE city='上海'走二级索引要两跳：先在 city 树上定位、沿叶链拿到一批主键，再逐个主键回到聚簇树上捞整行——这就是回表，一次点查变成两次树下探。反过来，若查询要的列全在二级索引里（SELECT id, city），第二跳整个省掉，即"覆盖索引"。这也解释了上一篇的结论为何重要：主键越长，每个二级索引条目都跟着变肥，回表的路也越长。
第三，联合索引的排序规则决定最左前缀。KEY(city, age, level)不是三个索引而是一个：所有条目先按 city 排，city 相同再按 age，age 相同再按 level。B+Tree 能定位的前提是"把查询条件翻译成一串连续区间"：city=定出一段，段内age=再细分，level=继续细分——等值条件可以逐列传播；一旦出现age>25，区间被拉成一条长带，带内 level 不再有序，level='gold'就只能对扫到的每条索引记录做过滤（8.0 之前逐条回表后过滤，8.0 靠 ICP 索引条件下推在索引层先滤一遍，少回表但不少扫页）；跳过 city 只给age=，排序序列上 age 相同的记录散落各处，树定位失效。LIKE '上%'本质是>= '上' AND < '上0'的区间，能定位；LIKE '%上'无法表达成区间，只能全扫。
第四，选择性与优化器的取舍。索引值重复率决定扫描区间大小：WHERE gender=1选择性 50%，走索引等于扫半棵树的叶链，还倒贴几十万次随机回表，优化器宁可全表顺序扫。经验拐点在 20%~30% 附近，但真正的裁判是EXPLAIN里rows估算与key_len——后者直接告诉你联合索引用掉了几个列、多长，是验证最左前缀最硬的证据。
第一次代码实验及输出
下面用纯 Python 模拟一棵迷你 B+Tree（固定参数：演示用叶子容量 8、内部节点扇出 6，这是内存模型不是真实 InnoDB）：实现查找、插入与两种分裂——普通分裂从中间劈开，而"满页最右端追加"命中 InnoDB 的优化路径（旧页整页留满、只有新行进新页）。分别灌入自增键与固定随机种子产生的 UUID 风格随机键，对比树高、叶子页总数、分裂次数与平均填充率；最后按第 1 篇的真实常量（378 行/页、1023 指针/内部页）算生产量级的树高。
importrandom MAX_LEAF=8# 演示用: 一个叶子页最多放 8 条记录, 放不下就分裂MAX_KIDS=6# 演示用: 一个内部页最多 6 个孩子指针classNode:def__init__(self,leaf=True):self.leaf=leaf self.keys=[]# 叶子: 主键列表; 内部: 分隔键self.vals=[]# 叶子: 行数据(演示每行 40 字节)self.kids=[]# 内部: 子节点defnbytes(self):return(len(self.keys)*8+len(self.vals)*40)ifself.leaf \elselen(self.kids)*8defsplit_leaf(n,at):r=Node()r.keys,n.keys=n.keys[at:],n.keys[:at]r.vals,n.vals=n.vals[at:],n.vals[:at]returnr,r.keys[0]defsplit_internal(n):half=len(n.kids)//2r=Node(leaf=False)sep=n.keys[half]r.kids,n.kids=n.kids[half+1:],n.kids[:half+1]r.keys,n.keys=n.keys[half+1:],n.keys[:half]returnr,sepclassBPlusTree:def__init__(self):self.root=Node()self.splits=0defbisect(self,a,x):lo,hi=0,len(a)whilelo<hi:mid=(lo+hi)//2ifa[mid]<x:lo=mid+1else:hi=midreturnlodeffind_leaf(self,key):node,path=self.root,[]whilenotnode.leaf:i=self.bisect(node.keys,key)path.append((node,i))node=node.kids[i]returnnode,pathdefinsert(self,key,val):leaf,path=self.find_leaf(key)i=self.bisect(leaf.keys,key)full_and_append=len(leaf.keys)==MAX_LEAFandi==MAX_LEAF leaf.keys.insert(i,key)leaf.vals.insert(i,val)iflen(leaf.keys)>MAX_LEAF:# 顺序追加命中满页最右端: 旧页整页留满, 只有新行进新页at=MAX_LEAFiffull_and_appendelselen(leaf.keys)//2self.split_up(path,leaf,at,True)defsplit_up(self,path,node,at,is_leaf):self.splits+=1new,sep=split_leaf(node,at)ifis_leafelsesplit_internal(node)ifnotpath:r=Node(leaf=False)r.keys,r.kids=[sep],[node,new]self.root=rreturnparent,idx=path.pop()parent.keys.insert(idx,sep)parent.kids.insert(idx+1,new)iflen(parent.kids)>MAX_KIDS:self.split_up(path,parent,len(parent.kids)//2,False)defstats(self):leaves=[]defwalk(n):ifn.leaf:leaves.append(n)else:forkinn.kids:walk(k)walk(self.root)height,node=0,self.rootwhilenodeisnotNone:height+=1node=Noneifnode.leafelsenode.kids[0]used=sum(n.nbytes()forninleaves)cap=len(leaves)*MAX_LEAF*48returnheight,len(leaves),used/capdefrun(tag,keys):t=BPlusTree()forkinkeys:t.insert(k,"row")h,pages,fill=t.stats()print("%s: %d 行 -> 树高 %d 层, 叶子页 %d 个, 分裂 %d 次, 平均填充率 %.1f%%"%(tag,len(keys),h,pages,t.splits,fill*100))N=2000run("自增主键(顺序追加)",list(range(1,N+1)))random.seed(2026)run("随机主键(UUID 风格)",[random.randint(1,10**18)for_inrange(N)])per_leaf,fanout=378,1023# 真实 InnoDB: 见第 1 篇每页行数与指针密度forrowsin(3*10**7,4*10**8):cap,levels=per_leaf,1whilecap<rows:cap*=fanout levels+=1print("真实量级 %d 行: 树高 %d 层, 从根到叶 %d 次页读取即可定位任意主键"%(rows,levels,levels))运行输出：
自增主键(顺序追加): 2000 行 -> 树高 5 层, 叶子页 250 个, 分裂 327 次, 平均填充率 100.0% 随机主键(UUID 风格): 2000 行 -> 树高 5 层, 叶子页 369 个, 分裂 477 次, 平均填充率 67.8% 真实量级 30000000 行: 树高 3 层, 从根到叶 3 次页读取即可定位任意主键 真实量级 400000000 行: 树高 4 层, 从根到叶 4 次页读取即可定位任意主键同样是 2000 行，随机键比顺序键多用 119 个页（369 vs 250，行数是骗人的，占的是页），分裂多出 45%，填充率掉到 68%——真实 InnoDB 里随机分裂还常把"刚写过的新页"劈成两半，命中率更差；模型给出的 100% 是理想追加，生产上因页内保留自由空间实际约九成上下。更值得记住的是第三四行：三千万行的表树高只有 3 层，四亿行也才 4 层——根页和第二层页合计不过几百个页，几乎常驻 Buffer Pool，所以一次主键点查的真实磁盘 IO 往往只有最后一片叶子一跳。"索引为什么快"的答案不是玄学：快在把随机读次数压到了树高，而树高被扇出摁在个位数。
工程化改进
把树的结构变成索引设计规则，分四步。
第一步，联合索引按"等值在前、范围在后、排序收尾"排列列序。等值列之间谁先谁后按选择性从高到低排；范围条件放它前面所有等值列都出现之后，因为它会截断后续列的定位能力（下一篇实验会量化这一点）。若查询模式是city=+age>与city=+level=两类，一个(city, age, level)只服务好前者，后者需要另一个(city, level)或调整写法——索引列序必须对着真实 SQL 集合设计，而不是对着表结构。
第二步，用覆盖索引消灭回表。列表页 SQL 固定字段后，把 SELECT 的列并入联合索引尾部（MySQL 无 SQL Server 的 INCLUDE 语法，直接加列），EXPLAIN的Extra: Using index是覆盖成功的标志。代价要算清楚：索引每加一列，所有写入都要多维护一分，条目也更宽；只给高频关键查询做覆盖，别给每条 SQL 都配。
第三步，长字符串用前缀索引控制体积。utf8mb4 下 VARCHAR(255) 全列进索引要 1020 字节，逼近 3072 上限且扇出骤减；KEY(title(20))只占 80 字节。前缀长度用选择性选型：SELECT COUNT(DISTINCT LEFT(title,20))/COUNT(*) FROM articles，逼近 1 即可。记住前缀索引不能覆盖、LIKE只在模式前缀长于索引前缀时才多过滤一次。
第四步，杜绝"写得出但走不了索引"的谓词，并定期清冗余。时间查询别写DATE(create_time)=CURDATE()（列上套函数，树定位失效），改写成create_time >= 今天 AND < 明天的区间；连接层与列的字符集/排序规则保持一致，避免字符串列与数字比较把索引列整列 CAST；上线后周期跑sys.schema_redundant_indexes与sys.schema_unused_indexes，(a,b)已存在时单列(a)就是白吃写性能的冗余。
第二次代码实验及输出
下面把"最左前缀"做成可运行的判卷器：一个(city, age, level)联合索引物化成按元组整体排序的 14 条记录，analyze按索引列序逐列尝试把 WHERE 条件翻译成定位路径——等值与LIKE 前%可继续传播、范围可参与定位但终止传播、断列即停；随后对照"索引区间扫描条数"与"最终命中条数"，量化每个查询实际多扫了多少。
# 二级索引 (city, age, level): 索引里存的是按三列整体排序的键# 查询条件能否走索引, 取决于它能不能翻译成这个有序序列上的一段连续区间COLS=("city","age","level")INDEX=sorted([("北京",25,"gold"),("北京",25,"silver"),("北京",30,"gold"),("北京",35,"bronze"),("上海",22,"gold"),("上海",25,"gold"),("上海",25,"silver"),("上海",30,"bronze"),("上海",40,"gold"),("广州",28,"silver"),("广州",33,"gold"),("深圳",25,"bronze"),("深圳",25,"gold"),("深圳",41,"silver"),])defmatch(row,conds):fori,op,wantinconds:got=row[i]ifop=="="andgot!=want:returnFalseifop==">"andnotgot>want:returnFalseifop=="like"andnotgot.startswith(want):returnFalsereturnTruedefanalyze(conds):"""按索引列顺序逐列推进: 等值/LIKE 前缀能继续定位下一列; 范围条件可以参与定位, 但它之后的列只能退化为逐条过滤"""seek,stop,used=[],False,set()foriinrange(len(COLS)):ifstop:breakhit=[(op,v)for(j,op,v)incondsifj==iandopin("=","like")]rng=[(op,v)for(j,op,v)incondsifj==iandop==">"]ifhit:seek.append((i,hit[0]));used.add(i)ifhit[0][0]=="like"andhit[0][1].find("%")>=0:stop=Trueelifrng:seek.append((i,rng[0]));used.add(i);stop=Trueelse:breakfilters=[(i,op,v)for(i,op,v)incondsifinotinused]returnseek,filtersforname,condsin[("A. city='上海'",[(0,"=","上海")]),("B. city='上海' AND age=25",[(0,"=","上海"),(1,"=",25)]),("C. city='上海' AND age>25",[(0,"=","上海"),(1,">",25)]),("D. city='上海' AND age>25 AND level='gold'",[(0,"=","上海"),(1,">",25),(2,"=","gold")]),("E. age=25 (跳过 city)",[(1,"=",25)]),("F. city LIKE '上%'",[(0,"like","上")]),]:seek,filters=analyze(conds)path=" -> ".join("%s %s %r"%(COLS[i],op,v)fori,(op,v)inseek)\or"(无法定位, 全索引扫描)"rows=[rforrinINDEXifmatch(r,conds)]scanned=sum(1forrinINDEXifmatch(r,[(i,op,v)fori,(op,v)inseek]))print("%s"%name)print(" 索引定位路径: %s"%path)print(" 扫描后仍需过滤: %s"%([("%s %s %r"%(COLS[i],op,v))fori,op,vinfilters]or"无"))print(" 索引区间扫描 %d 条, 最终命中 %d 条\n"%(scanned,len(rows)))运行输出：
A. city='上海' 索引定位路径: city = '上海' 扫描后仍需过滤: 无 索引区间扫描 5 条, 最终命中 5 条 B. city='上海' AND age=25 索引定位路径: city = '上海' -> age = 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 C. city='上海' AND age>25 索引定位路径: city = '上海' -> age > 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 D. city='上海' AND age>25 AND level='gold' 索引定位路径: city = '上海' -> age > 25 扫描后仍需过滤: ["level = 'gold'"] 索引区间扫描 2 条, 最终命中 1 条 E. age=25 (跳过 city) 索引定位路径: (无法定位, 全索引扫描) 扫描后仍需过滤: ['age = 25'] 索引区间扫描 14 条, 最终命中 6 条 F. city LIKE '上%' 索引定位路径: city like '上' 扫描后仍需过滤: 无 索引区间扫描 5 条, 最终命中 5 条六个用例把最左前缀的三种"失效方式"各占了一样。D 是误区重灾区：level='gold'明明写在 WHERE 里，却进不了定位路径——age>把 level 拉出了有序轨道，它只能对扫到的 2 条做过滤；把它建到age前面的(city, level, age)就能定位到 1 条，这正是"等值在前、范围在后"的量化收益。E 说明"跳过首列"最惨：条件本身在索引里，却被迫扫穿全部 14 条，真实场景里这种 SQL 会被优化器判给全表扫描或另建(age)索引。F 和 A 输出完全相同，印证LIKE '上%'就是一个区间谓词；把它改成LIKE '%上%'，本模型连like分支都进不去，等价于 E。另外注意 B 与 C 的key_len差异在真实 MySQL 里直接可查：EXPLAIN显示 C 用到两列、B 也用到两列但类型不同，验证了"索引用到第几列"不是玄学而是可观测数字。
常见陷阱
其一，以为联合索引(a,b)对一切含 a、b 的查询都提速：WHERE b=1 AND a>5里 a 的范围一旦先出现，b 就无法参与定位（列序按索引定义走，不是按 WHERE 书写顺序），实际只剩(a)前缀的效果。其二，二级索引高比例回表反比全表慢：city上走索引命中 40% 行时，几十万次回表随机读被优化器的成本模型判给顺序扫描，看到type=ALL别急着骂索引失效，先看命中行数占比。其三，隐式类型转换方向性搞反：索引列是 VARCHAR、参数传数字（mobile=13800138000），转换发生在列上、索引报废；索引列是 BIGINT、参数传字符串，转换只发生在常量上、索引照用——同是"类型不匹配"，一个致命一个无害。其四，每个查询各建一个单列索引，指望 index_merge 拼出联合索引效果：交集合并要做两趟排序归并，多数场景远不如一个正确的联合索引，还养出一堆拖写入的闲置树。其五，ORDER BY不看索引方向：WHERE city=+ORDER BY age天然顺着(city, age)的叶链免排序，但 8.0 降序联合索引（KEY(city ASC, age DESC)）缺失时跨列混排会退化成 filesort。
落地清单
- 联合索引列序：等值列在前按选择性降序、范围列殿后，对着真实 SQL 集合而非表结构设计
- 高频列表查询做覆盖索引，以
EXPLAIN Extra: Using index与key_len为验收证据 - 长文本用前缀索引，长度以
COUNT(DISTINCT LEFT(col,n))/COUNT(*)逼近 1 为准 - 时间条件一律区间写法，禁止列上函数；连接串字符集与列排序规则保持一致
- 周期巡检
sys.schema_redundant_indexes/sys.schema_unused_indexes，删冗余保写吞吐
至此，数据"怎么放"和"怎么找"两本账都清楚了：页决定行开销，树决定读取路径。但索引只解决效率，不解决正确性——同一行被两个会话同时改，你读到的到底是改前的旧值还是改后的新值？为什么默认隔离级别下你的 UPDATE 会莫名等锁，而另一个 SELECT 却毫不受阻地读着旧版本？下一篇《MySQL 内核实战（3）：事务隔离级别与 MVCC 实现》拆开 InnoDB 的版本链与 ReadView，讲清并发正确性的实现。
参考来源
- MySQL 8.0 Reference Manual：How MySQL Uses Indexes：https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html
- MySQL 8.0 Reference Manual：Clustered and Non-Clustered Indexes：https://dev.mysql.com/doc/refman/8.0/en/clustered-indexes.html
- MySQL 8.0 Reference Manual：InnoDB Index Types（含前缀索引）：https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html
- MySQL 8.0 Reference Manual：EXPLAIN Output Format：https://dev.mysql.com/doc/refman/8.0/en/explain-output.html
- Wikipedia：B+ tree：https://en.wikipedia.org/wiki/B%2B_tree
👍 觉得有用就点个赞 + 收藏，方便回头查阅；有疑问直接在评论区留言，我看到都会回。
🚀 本文属于《MySQL 内核实战》系列，持续更新，关注不迷路。
📌 文章里的代码都能直接跑。想要可直接 clone 的完整工程 + 配套部署脚本 / 踩坑清单？评论一声或发邮件到cj2664@qq.com，我免费发你。
如果你正好在做类似系统、或有工程化难题想找人做，也欢迎邮件聊一句——我按实际情况评估，能落地的就接单或出方案。评论和邮件都能直接找到我，不用跳别的平台。
