问题背景上一篇算清了页的账一行数据带着记录头、NULL 位图和变长列表挤进 16KB 的页页满就分裂。但那些页之间还只是零散文件本篇解决下一个问题三千万行的表为什么WHERE id8765432只读三四个页就能命中答案是把页组织成一棵 BTree——InnoDB 全部索引聚簇与二级都长在这棵树上的统一结构里。而线上最常见的索引事故几乎都源于对这棵树的两处细节理解不到位一是二级索引叶子只存索引列 主键拿其余列要回表二是联合索引是整个元组排序条件只有翻译成排序序列上的连续区间才能参与定位这就是最左前缀的几何本质。LIKE abc%为什么能走索引、LIKE %abc为什么不能WHERE city上海 AND age25 AND levelgold里level到底有没有被索引用到都逃不出这两条。本篇回答四个问题BTree 为什么是页存储的最优组织方式聚簇与二级索引的两棵树怎么互相引用联合索引的排序规则如何决定定位深度以及索引设计的工程方法论。核心原理第一为什么是 BTree 而不是别的。候选里哈希索引等值查找 O(1) 最快但它只认全键相等既不支持范围扫描也不支持排序一个BETWEEN就退化全表红黑树一类二叉树深度是 log2(n)三千万行要下沉 25 层每层一次页读磁盘上不可接受。BTree 的关键设计是数据全在叶子层内部节点只存分隔键 页指针一个内部页 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 相同再按 ageage 相同再按 level。BTree 能定位的前提是把查询条件翻译成一串连续区间city定出一段段内age再细分level继续细分——等值条件可以逐列传播一旦出现age25区间被拉成一条长带带内 level 不再有序levelgold就只能对扫到的每条索引记录做过滤8.0 之前逐条回表后过滤8.0 靠 ICP 索引条件下推在索引层先滤一遍少回表但不少扫页跳过 city 只给age排序序列上 age 相同的记录散落各处树定位失效。LIKE 上%本质是 上 AND 上0的区间能定位LIKE %上无法表达成区间只能全扫。第四选择性与优化器的取舍。索引值重复率决定扫描区间大小WHERE gender1选择性 50%走索引等于扫半棵树的叶链还倒贴几十万次随机回表优化器宁可全表顺序扫。经验拐点在 20%~30% 附近但真正的裁判是EXPLAIN里rows估算与key_len——后者直接告诉你联合索引用掉了几个列、多长是验证最左前缀最硬的证据。第一次代码实验及输出下面用纯 Python 模拟一棵迷你 BTree固定参数演示用叶子容量 8、内部节点扇出 6这是内存模型不是真实 InnoDB实现查找、插入与两种分裂——普通分裂从中间劈开而满页最右端追加命中 InnoDB 的优化路径旧页整页留满、只有新行进新页。分别灌入自增键与固定随机种子产生的 UUID 风格随机键对比树高、叶子页总数、分裂次数与平均填充率最后按第 1 篇的真实常量378 行/页、1023 指针/内部页算生产量级的树高。importrandom MAX_LEAF8# 演示用: 一个叶子页最多放 8 条记录, 放不下就分裂MAX_KIDS6# 演示用: 一个内部页最多 6 个孩子指针classNode:def__init__(self,leafTrue):self.leafleaf self.keys[]# 叶子: 主键列表; 内部: 分隔键self.vals[]# 叶子: 行数据(演示每行 40 字节)self.kids[]# 内部: 子节点defnbytes(self):return(len(self.keys)*8len(self.vals)*40)ifself.leaf \elselen(self.kids)*8defsplit_leaf(n,at):rNode()r.keys,n.keysn.keys[at:],n.keys[:at]r.vals,n.valsn.vals[at:],n.vals[:at]returnr,r.keys[0]defsplit_internal(n):halflen(n.kids)//2rNode(leafFalse)sepn.keys[half]r.kids,n.kidsn.kids[half1:],n.kids[:half1]r.keys,n.keysn.keys[half1:],n.keys[:half]returnr,sepclassBPlusTree:def__init__(self):self.rootNode()self.splits0defbisect(self,a,x):lo,hi0,len(a)whilelohi:mid(lohi)//2ifa[mid]x:lomid1else:himidreturnlodeffind_leaf(self,key):node,pathself.root,[]whilenotnode.leaf:iself.bisect(node.keys,key)path.append((node,i))nodenode.kids[i]returnnode,pathdefinsert(self,key,val):leaf,pathself.find_leaf(key)iself.bisect(leaf.keys,key)full_and_appendlen(leaf.keys)MAX_LEAFandiMAX_LEAF leaf.keys.insert(i,key)leaf.vals.insert(i,val)iflen(leaf.keys)MAX_LEAF:# 顺序追加命中满页最右端: 旧页整页留满, 只有新行进新页atMAX_LEAFiffull_and_appendelselen(leaf.keys)//2self.split_up(path,leaf,at,True)defsplit_up(self,path,node,at,is_leaf):self.splits1new,sepsplit_leaf(node,at)ifis_leafelsesplit_internal(node)ifnotpath:rNode(leafFalse)r.keys,r.kids[sep],[node,new]self.rootrreturnparent,idxpath.pop()parent.keys.insert(idx,sep)parent.kids.insert(idx1,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,node0,self.rootwhilenodeisnotNone:height1nodeNoneifnode.leafelsenode.kids[0]usedsum(n.nbytes()forninleaves)caplen(leaves)*MAX_LEAF*48returnheight,len(leaves),used/capdefrun(tag,keys):tBPlusTree()forkinkeys:t.insert(k,row)h,pages,fillt.stats()print(%s: %d 行 - 树高 %d 层, 叶子页 %d 个, 分裂 %d 次, 平均填充率 %.1f%%%(tag,len(keys),h,pages,t.splits,fill*100))N2000run(自增主键(顺序追加),list(range(1,N1)))random.seed(2026)run(随机主键(UUID 风格),[random.randint(1,10**18)for_inrange(N)])per_leaf,fanout378,1023# 真实 InnoDB: 见第 1 篇每页行数与指针密度forrowsin(3*10**7,4*10**8):cap,levelsper_leaf,1whilecaprows:cap*fanout levels1print(真实量级 %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 往往只有最后一片叶子一跳。索引为什么快的答案不是玄学快在把随机读次数压到了树高而树高被扇出摁在个位数。工程化改进把树的结构变成索引设计规则分四步。第一步联合索引按等值在前、范围在后、排序收尾排列列序。等值列之间谁先谁后按选择性从高到低排范围条件放它前面所有等值列都出现之后因为它会截断后续列的定位能力下一篇实验会量化这一点。若查询模式是cityage与citylevel两类一个(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)INDEXsorted([(北京,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:gotrow[i]ifopandgot!want:returnFalseifopandnotgotwant:returnFalseifoplikeandnotgot.startswith(want):returnFalsereturnTruedefanalyze(conds):按索引列顺序逐列推进: 等值/LIKE 前缀能继续定位下一列; 范围条件可以参与定位, 但它之后的列只能退化为逐条过滤seek,stop,used[],False,set()foriinrange(len(COLS)):ifstop:breakhit[(op,v)for(j,op,v)incondsifjiandopin(,like)]rng[(op,v)for(j,op,v)incondsifjiandop]ifhit:seek.append((i,hit[0]));used.add(i)ifhit[0][0]likeandhit[0][1].find(%)0:stopTrueelifrng:seek.append((i,rng[0]));used.add(i);stopTrueelse:breakfilters[(i,op,v)for(i,op,v)incondsifinotinused]returnseek,filtersforname,condsin[(A. city上海,[(0,,上海)]),(B. city上海 AND age25,[(0,,上海),(1,,25)]),(C. city上海 AND age25,[(0,,上海),(1,,25)]),(D. city上海 AND age25 AND levelgold,[(0,,上海),(1,,25),(2,,gold)]),(E. age25 (跳过 city),[(1,,25)]),(F. city LIKE 上%,[(0,like,上)]),]:seek,filtersanalyze(conds)path - .join(%s %s %r%(COLS[i],op,v)fori,(op,v)inseek)\or(无法定位, 全索引扫描)rows[rforrinINDEXifmatch(r,conds)]scannedsum(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 age25 索引定位路径: city 上海 - age 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 C. city上海 AND age25 索引定位路径: city 上海 - age 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 D. city上海 AND age25 AND levelgold 索引定位路径: city 上海 - age 25 扫描后仍需过滤: [level gold] 索引区间扫描 2 条, 最终命中 1 条 E. age25 (跳过 city) 索引定位路径: (无法定位, 全索引扫描) 扫描后仍需过滤: [age 25] 索引区间扫描 14 条, 最终命中 6 条 F. city LIKE 上% 索引定位路径: city like 上 扫描后仍需过滤: 无 索引区间扫描 5 条, 最终命中 5 条六个用例把最左前缀的三种失效方式各占了一样。D 是误区重灾区levelgold明明写在 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 b1 AND a5里 a 的范围一旦先出现b 就无法参与定位列序按索引定义走不是按 WHERE 书写顺序实际只剩(a)前缀的效果。其二二级索引高比例回表反比全表慢city上走索引命中 40% 行时几十万次回表随机读被优化器的成本模型判给顺序扫描看到typeALL别急着骂索引失效先看命中行数占比。其三隐式类型转换方向性搞反索引列是 VARCHAR、参数传数字mobile13800138000转换发生在列上、索引报废索引列是 BIGINT、参数传字符串转换只发生在常量上、索引照用——同是类型不匹配一个致命一个无害。其四每个查询各建一个单列索引指望 index_merge 拼出联合索引效果交集合并要做两趟排序归并多数场景远不如一个正确的联合索引还养出一堆拖写入的闲置树。其五ORDER BY不看索引方向WHERE cityORDER 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 ManualHow MySQL Uses Indexeshttps://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.htmlMySQL 8.0 Reference ManualClustered and Non-Clustered Indexeshttps://dev.mysql.com/doc/refman/8.0/en/clustered-indexes.htmlMySQL 8.0 Reference ManualInnoDB Index Types含前缀索引https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.htmlMySQL 8.0 Reference ManualEXPLAIN Output Formathttps://dev.mysql.com/doc/refman/8.0/en/explain-output.htmlWikipediaB treehttps://en.wikipedia.org/wiki/B%2B_tree 觉得有用就点个赞 收藏方便回头查阅有疑问直接在评论区留言我看到都会回。 本文属于《MySQL 内核实战》系列持续更新关注不迷路。 文章里的代码都能直接跑。想要可直接 clone 的完整工程 配套部署脚本 / 踩坑清单评论一声或发邮件到cj2664qq.com我免费发你。如果你正好在做类似系统、或有工程化难题想找人做也欢迎邮件聊一句——我按实际情况评估能落地的就接单或出方案。评论和邮件都能直接找到我不用跳别的平台。
问题背景上一篇算清了页的账一行数据带着记录头、NULL 位图和变长列表挤进 16KB 的页页满就分裂。但那些页之间还只是零散文件本篇解决下一个问题三千万行的表为什么WHERE id8765432只读三四个页就能命中答案是把页组织成一棵 BTree——InnoDB 全部索引聚簇与二级都长在这棵树上的统一结构里。而线上最常见的索引事故几乎都源于对这棵树的两处细节理解不到位一是二级索引叶子只存索引列 主键拿其余列要回表二是联合索引是整个元组排序条件只有翻译成排序序列上的连续区间才能参与定位这就是最左前缀的几何本质。LIKE abc%为什么能走索引、LIKE %abc为什么不能WHERE city上海 AND age25 AND levelgold里level到底有没有被索引用到都逃不出这两条。本篇回答四个问题BTree 为什么是页存储的最优组织方式聚簇与二级索引的两棵树怎么互相引用联合索引的排序规则如何决定定位深度以及索引设计的工程方法论。核心原理第一为什么是 BTree 而不是别的。候选里哈希索引等值查找 O(1) 最快但它只认全键相等既不支持范围扫描也不支持排序一个BETWEEN就退化全表红黑树一类二叉树深度是 log2(n)三千万行要下沉 25 层每层一次页读磁盘上不可接受。BTree 的关键设计是数据全在叶子层内部节点只存分隔键 页指针一个内部页 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 相同再按 ageage 相同再按 level。BTree 能定位的前提是把查询条件翻译成一串连续区间city定出一段段内age再细分level继续细分——等值条件可以逐列传播一旦出现age25区间被拉成一条长带带内 level 不再有序levelgold就只能对扫到的每条索引记录做过滤8.0 之前逐条回表后过滤8.0 靠 ICP 索引条件下推在索引层先滤一遍少回表但不少扫页跳过 city 只给age排序序列上 age 相同的记录散落各处树定位失效。LIKE 上%本质是 上 AND 上0的区间能定位LIKE %上无法表达成区间只能全扫。第四选择性与优化器的取舍。索引值重复率决定扫描区间大小WHERE gender1选择性 50%走索引等于扫半棵树的叶链还倒贴几十万次随机回表优化器宁可全表顺序扫。经验拐点在 20%~30% 附近但真正的裁判是EXPLAIN里rows估算与key_len——后者直接告诉你联合索引用掉了几个列、多长是验证最左前缀最硬的证据。第一次代码实验及输出下面用纯 Python 模拟一棵迷你 BTree固定参数演示用叶子容量 8、内部节点扇出 6这是内存模型不是真实 InnoDB实现查找、插入与两种分裂——普通分裂从中间劈开而满页最右端追加命中 InnoDB 的优化路径旧页整页留满、只有新行进新页。分别灌入自增键与固定随机种子产生的 UUID 风格随机键对比树高、叶子页总数、分裂次数与平均填充率最后按第 1 篇的真实常量378 行/页、1023 指针/内部页算生产量级的树高。importrandom MAX_LEAF8# 演示用: 一个叶子页最多放 8 条记录, 放不下就分裂MAX_KIDS6# 演示用: 一个内部页最多 6 个孩子指针classNode:def__init__(self,leafTrue):self.leafleaf self.keys[]# 叶子: 主键列表; 内部: 分隔键self.vals[]# 叶子: 行数据(演示每行 40 字节)self.kids[]# 内部: 子节点defnbytes(self):return(len(self.keys)*8len(self.vals)*40)ifself.leaf \elselen(self.kids)*8defsplit_leaf(n,at):rNode()r.keys,n.keysn.keys[at:],n.keys[:at]r.vals,n.valsn.vals[at:],n.vals[:at]returnr,r.keys[0]defsplit_internal(n):halflen(n.kids)//2rNode(leafFalse)sepn.keys[half]r.kids,n.kidsn.kids[half1:],n.kids[:half1]r.keys,n.keysn.keys[half1:],n.keys[:half]returnr,sepclassBPlusTree:def__init__(self):self.rootNode()self.splits0defbisect(self,a,x):lo,hi0,len(a)whilelohi:mid(lohi)//2ifa[mid]x:lomid1else:himidreturnlodeffind_leaf(self,key):node,pathself.root,[]whilenotnode.leaf:iself.bisect(node.keys,key)path.append((node,i))nodenode.kids[i]returnnode,pathdefinsert(self,key,val):leaf,pathself.find_leaf(key)iself.bisect(leaf.keys,key)full_and_appendlen(leaf.keys)MAX_LEAFandiMAX_LEAF leaf.keys.insert(i,key)leaf.vals.insert(i,val)iflen(leaf.keys)MAX_LEAF:# 顺序追加命中满页最右端: 旧页整页留满, 只有新行进新页atMAX_LEAFiffull_and_appendelselen(leaf.keys)//2self.split_up(path,leaf,at,True)defsplit_up(self,path,node,at,is_leaf):self.splits1new,sepsplit_leaf(node,at)ifis_leafelsesplit_internal(node)ifnotpath:rNode(leafFalse)r.keys,r.kids[sep],[node,new]self.rootrreturnparent,idxpath.pop()parent.keys.insert(idx,sep)parent.kids.insert(idx1,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,node0,self.rootwhilenodeisnotNone:height1nodeNoneifnode.leafelsenode.kids[0]usedsum(n.nbytes()forninleaves)caplen(leaves)*MAX_LEAF*48returnheight,len(leaves),used/capdefrun(tag,keys):tBPlusTree()forkinkeys:t.insert(k,row)h,pages,fillt.stats()print(%s: %d 行 - 树高 %d 层, 叶子页 %d 个, 分裂 %d 次, 平均填充率 %.1f%%%(tag,len(keys),h,pages,t.splits,fill*100))N2000run(自增主键(顺序追加),list(range(1,N1)))random.seed(2026)run(随机主键(UUID 风格),[random.randint(1,10**18)for_inrange(N)])per_leaf,fanout378,1023# 真实 InnoDB: 见第 1 篇每页行数与指针密度forrowsin(3*10**7,4*10**8):cap,levelsper_leaf,1whilecaprows:cap*fanout levels1print(真实量级 %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 往往只有最后一片叶子一跳。索引为什么快的答案不是玄学快在把随机读次数压到了树高而树高被扇出摁在个位数。工程化改进把树的结构变成索引设计规则分四步。第一步联合索引按等值在前、范围在后、排序收尾排列列序。等值列之间谁先谁后按选择性从高到低排范围条件放它前面所有等值列都出现之后因为它会截断后续列的定位能力下一篇实验会量化这一点。若查询模式是cityage与citylevel两类一个(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)INDEXsorted([(北京,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:gotrow[i]ifopandgot!want:returnFalseifopandnotgotwant:returnFalseifoplikeandnotgot.startswith(want):returnFalsereturnTruedefanalyze(conds):按索引列顺序逐列推进: 等值/LIKE 前缀能继续定位下一列; 范围条件可以参与定位, 但它之后的列只能退化为逐条过滤seek,stop,used[],False,set()foriinrange(len(COLS)):ifstop:breakhit[(op,v)for(j,op,v)incondsifjiandopin(,like)]rng[(op,v)for(j,op,v)incondsifjiandop]ifhit:seek.append((i,hit[0]));used.add(i)ifhit[0][0]likeandhit[0][1].find(%)0:stopTrueelifrng:seek.append((i,rng[0]));used.add(i);stopTrueelse:breakfilters[(i,op,v)for(i,op,v)incondsifinotinused]returnseek,filtersforname,condsin[(A. city上海,[(0,,上海)]),(B. city上海 AND age25,[(0,,上海),(1,,25)]),(C. city上海 AND age25,[(0,,上海),(1,,25)]),(D. city上海 AND age25 AND levelgold,[(0,,上海),(1,,25),(2,,gold)]),(E. age25 (跳过 city),[(1,,25)]),(F. city LIKE 上%,[(0,like,上)]),]:seek,filtersanalyze(conds)path - .join(%s %s %r%(COLS[i],op,v)fori,(op,v)inseek)\or(无法定位, 全索引扫描)rows[rforrinINDEXifmatch(r,conds)]scannedsum(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 age25 索引定位路径: city 上海 - age 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 C. city上海 AND age25 索引定位路径: city 上海 - age 25 扫描后仍需过滤: 无 索引区间扫描 2 条, 最终命中 2 条 D. city上海 AND age25 AND levelgold 索引定位路径: city 上海 - age 25 扫描后仍需过滤: [level gold] 索引区间扫描 2 条, 最终命中 1 条 E. age25 (跳过 city) 索引定位路径: (无法定位, 全索引扫描) 扫描后仍需过滤: [age 25] 索引区间扫描 14 条, 最终命中 6 条 F. city LIKE 上% 索引定位路径: city like 上 扫描后仍需过滤: 无 索引区间扫描 5 条, 最终命中 5 条六个用例把最左前缀的三种失效方式各占了一样。D 是误区重灾区levelgold明明写在 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 b1 AND a5里 a 的范围一旦先出现b 就无法参与定位列序按索引定义走不是按 WHERE 书写顺序实际只剩(a)前缀的效果。其二二级索引高比例回表反比全表慢city上走索引命中 40% 行时几十万次回表随机读被优化器的成本模型判给顺序扫描看到typeALL别急着骂索引失效先看命中行数占比。其三隐式类型转换方向性搞反索引列是 VARCHAR、参数传数字mobile13800138000转换发生在列上、索引报废索引列是 BIGINT、参数传字符串转换只发生在常量上、索引照用——同是类型不匹配一个致命一个无害。其四每个查询各建一个单列索引指望 index_merge 拼出联合索引效果交集合并要做两趟排序归并多数场景远不如一个正确的联合索引还养出一堆拖写入的闲置树。其五ORDER BY不看索引方向WHERE cityORDER 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 ManualHow MySQL Uses Indexeshttps://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.htmlMySQL 8.0 Reference ManualClustered and Non-Clustered Indexeshttps://dev.mysql.com/doc/refman/8.0/en/clustered-indexes.htmlMySQL 8.0 Reference ManualInnoDB Index Types含前缀索引https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.htmlMySQL 8.0 Reference ManualEXPLAIN Output Formathttps://dev.mysql.com/doc/refman/8.0/en/explain-output.htmlWikipediaB treehttps://en.wikipedia.org/wiki/B%2B_tree 觉得有用就点个赞 收藏方便回头查阅有疑问直接在评论区留言我看到都会回。 本文属于《MySQL 内核实战》系列持续更新关注不迷路。 文章里的代码都能直接跑。想要可直接 clone 的完整工程 配套部署脚本 / 踩坑清单评论一声或发邮件到cj2664qq.com我免费发你。如果你正好在做类似系统、或有工程化难题想找人做也欢迎邮件聊一句——我按实际情况评估能落地的就接单或出方案。评论和邮件都能直接找到我不用跳别的平台。
