B+ 树分裂全过程：MySQL 三层索引为什么能装 2000 万行

先给结论：16KB 的页，8 字节的 bigint 主键，每行 1KB，三层 B+ 树能装 2018 万行。

同一套公式把行大小改成 128 字节，三层能装 1.71 亿行。

这两个数不是背下来的，是我把页大小、索引 key、行大小、指针大小这四个数填进页面算出来的。

插入过程也做成了动画：新 key 落到哪个叶子、叶子什么时候写满、分裂成哪两个节点、往哪一层冒，一步一步看得见。

成品是一个单文件 index.html，双击就能跑，不联网，不引第三方库。

案例目录在这里，下载下来直接打开：

https://atomgit.com/deli007/demo_park/tree/main/codearts-bplus-tree-visualizer

为什么我要把分裂过程摆出来

「三层 B+ 树能装两千万行」这句话，面试背过的人很多。

但第三层是什么时候冒出来的、一次插入里到底裂了几次、裂完两个节点各剩几个 key，能现场说清的人不多。

我把这个问题拆成三件可以验证的事：一次插入触发了几次分裂，分裂完两边的 key 数各是多少，树高什么时候从二层变三层。

要带走的是判据，不是结论。

判据就一条：叶子里的 key 数超过 m-1 就该裂，裂完两边都不能低于 ⌈(m-1)/2⌉。

页面用 SVG 画整棵树，叶子之间用箭头连成链表，节点框里直接写 key。

分裂的瞬间，两个新节点变黄，旁边弹出文字气泡，写明这是第几次分裂、裂的是哪一层、上推的 key 是几。

左边是参数区，阶数 m 可以选 3 到 8，插入数量 N 可以选 100 到 2000，动画速度可调。

中间是树和逐条日志，右边是实时统计。

底下还有三块：顺序插入和随机插入的对照表、容量测算面板、自检面板。

一条插入指令走完的全程

点「顺序插入动画」，页面会按真实算法把 1 到 N 插一遍，每一步都渲染。

定位过程是蓝色高亮，落到叶子里是绿色，叶子写满变黄，分裂时新老节点一起闪。

页面的日志区会把每一步写出来，图 2 左下角那一串就是。

m=6、N=40 跑到第一次分裂时的原文是这样：

定位 → 定位叶子节点，准备插入 6
插入 → 插入 6 到叶子节点
溢出 → 叶子节点满 6/5，触发分裂
分裂 #1 → 第 1 次分裂：叶子层分裂为 [1,2,3] 和 [4,5,6]，上推 4

6 个 key 分成 3 和 3，两边都不低于下限 3。

上推的 4 成了新根，树高从 1 变成 2。

换成 m=6、N=60 全插完，统计面板给的是这一组数字：

这张表的随机那一列只是某一次的结果，换个随机顺序数字就会动，后面我会给 20 次的区间。

验证与踩坑：15 条断言，和我在验收时改掉的六处

页面底部的「自检」按钮，会把 15 条断言真跑一遍，逐条列出实测值和结论。

完整交付版本跑出来是 15/15 通过，m=3 到 8、N 取 10、60、200 这 18 组参数我都点过一遍，没有红条。

第一版交付时只有 14 条，而且都是「全部插完再看一眼」的终态检查，问题就藏在这个「看一眼」里。

第一处，分裂点算错了，这是最要紧的一处。

第一版叶子分裂写的是 ceil((key 数 + 1) / 2)。

m=6 时叶子溢出是 6 个 key，按这个式子分成 4 和 2，右边那个叶子只剩 2 个 key，比下限 3 还少。

内部节点一样：m=3 时内部节点溢出是 4 个孩子，第一版按 ceil((4+1)/2)=3 分成 3 和 1，右边那个内部节点只剩 1 个孩子，下限是 2。

修法是把两处都改成 ceil(n/2)，两边各拿一半。

改完我写了一个逐次检查的脚本，把 m=3 到 8、N 取 20、60、200，顺序和随机两种插入全跑一遍，每次插入之后都检查最小占用。

修复前的结果是 36 个场景里 34 个违规，只有 m=7、N=20 那两组侥幸没踩到。

修复后 36 个场景全部通过，一次违规都没有。

修复前的首次违规位置也很固定，顺序插入时报的是这几个：

第二处，断言只盯终态，所以第一处的问题一直没被抓到。

顺序插入是往最右边那个叶子塞 key，刚分出来的小叶子很快又被填满，等 N 插完回头看，它已经够数了。

真正暴露问题的是第 15 条断言，叫「每次插入后最小占用都成立」。

它每插一个 key 就复查一次全树，上线之后立刻把旧代码抓红了。

第三处，自检结果被上一次动画污染。

「分裂次数与节点数关系」那条断言，第一版报的原文是：节点数=26，期望=122（1+23次分裂+98次根分裂）。

26 个节点对得很，98 次根分裂离谱。

原因是自检复用了页面全局的步骤数组，上一次动画残留的步骤还在里面，被一起数成了根分裂。

修法是自检开头先把步骤数组清空。

第四处，有一条断言的方向写反了。

第一版写的是「随机插入分裂次数 ≥ 顺序插入分裂次数」，交付时跑出来是 17 对 20，看着还挺像那么回事。

我拿 20 组参数各跑 60 次复核，结果正好相反：m=3、N=60 时，随机 60 次全部比顺序多；m=6、N=60 和 m=8、N=200 时，随机 60 次全部比顺序少。

也就是说这条断言在阶数小的时候必挂，在阶数大的时候碰巧能过。

现在换成理论下限：分裂次数不低于 ⌈N/(m-1)⌉-1，这个式子跟插入顺序无关，不会漂。

第五处，容量测算把索引 key 和行当成同一个数。

第一版公式里 key 大小直接等于行大小，算出来的扇出比真实 InnoDB 小一个数量级。

拆成两个输入之后，8 字节 key、6 字节指针、16KB 页，单页扇出是 1160。

第六处是两个小瑕疵。

自检里「实测最小 key 数」那一栏，第一版打印的是下限，不是实测值，看着像自己给自己发及格证。

另外没有非根内部节点的时候，那栏会显示 Infinity。

现在打印真实的最小值和节点个数。

平衡分裂是有代价的，我说清楚：

裂得更均匀，叶子就被劈得更碎，同样的 key 数量要多开页、多分裂几次。

值不值，取决于你要的是省页还是守规矩，这个页面把两种代价都摆出来，让数字自己说话。

有四处边界要写清楚。

页面里的期望值是我手写进断言的，断言只能证明页面实际算出来的等于我写的期望，证明不了我没想到的第 16 条。

自检只跑顺序插入 1 到 N，随机顺序每次都漂，所以跟随机有关的断言只校验下限，不校验具体数值。

树形布局按叶子顺序均分宽度，节点一多就得横向滚动，页面不做自动缩放。

容量测算把页头开销固定在 126 字节，真实 InnoDB 里还有页目录、变长列偏移和聚簇索引的事务信息，实际每页能装的行数会比这里再少一点。

失败路径：修复前的版本，自检会报红

上面那条分裂 bug，我没有靠读代码发现，是自检抓出来的。

修复前的版本我留了一份副本，把阶数改成 4、插入数量改成 10，点自检，结果是 13/15。

报红的两条原文是「非根叶子最少 ⌈(m-1)/2⌉ 个 key」和「每次插入后最小占用都成立」。

第二条的说明写着：插入 4 之后出现占用不足的叶子节点。

同一个参数下，把两处分裂改成平衡分裂，再点自检，就是 15/15。

顺序插入和随机插入，到底谁更省页

这个问题我一开始想当然了，实测数据打了脸。

阶数小的时候，顺序插入更省。

m=3 的树一个叶子最多放 2 个 key，顺序插进去，每个叶子刚好被填满，填充率 100.0%，随机插入反而要多裂 7 到 22 次。

阶数大的时候反过来。

m=6 和 m=8 的树，顺序插入永远往最右边那个叶子塞，刚裂出来的右叶子马上又被灌满，填充率掉到 60.0% 和 57.1%；随机插入把 key 摊平到所有叶子，同样 60 个 key 只用 15 到 19 次分裂，填充率抬到 70.6% 以上。

想自己复现这一组数，把阶数设成 6、数量设成 60，点「运行对比测试」，表里就会出现顺序和随机两列。

随机那一列的差值是相对的，填充率那一行的绿色加号代表随机更省页。

容量测算：三层 2018 万行是怎么来的

容量面板会把每一步算式写在页面上，不是只丢一个结果。

16KB 的页，页头开销 126 字节，索引 key 8 字节，页号指针 6 字节。

单个内部节点能塞的孩子数这样算：

f × (指针 + key) + 指针 ≤ 页大小 - 页头
f × (6 + 8) + 6 ≤ 16384 - 126
f ≤ 16252 / 14 = 1160

叶子节点按行算：(16384 - 126) / 行大小。

行大小 1024 字节时每页 15 行，行大小 128 字节时每页 127 行。

三层树是根加中间层加叶子，叶子页数等于 f 的平方；四层就是 f 的三次方。

标题里那个 2000 万，出处就是表里第二行：1160 的平方乘以 15。

第一行那个 1.71 亿是同一套公式换了个行大小，两种都真实存在，取决于你的表一行占多少字节。

真实 InnoDB 的非叶节点只存主键和页号，行数据和索引是分开的，这也是为什么第 5 处改动要把 key 和行拆成两个输入。

本地复现

页面是单文件，不需要构建，双击 index.html 就能跑。

想用本地服务器打开也行：

python3 -m http.server 8080

浏览器打开 http://localhost:8080/index.html。

想核对上面的数字，按这个顺序点：

1. 阶数 6、数量 60，点「跳过动画」看统计面板的 26 个节点、23 次分裂
2. 点「自检」，看到 15/15 通过
3. 把阶数改成 4、数量改成 10，再点「自检」，确认还是 15/15
4. 点「运行对比测试」，看顺序和随机两列的分裂次数
5. 把行大小改成 1024，看容量面板变成 20184000

想完整复刻这套代码，仓库也可以直接克隆：

git clone https://atomgit.com/deli007/demo_park.git

准备环境：进入码道 Web

码道有三种使用方式：WebUI（浏览器对话）、TUI（终端命令行）和桌面 IDE（IDE 插件）。本文用 WebUI 版演示。

浏览器打开码道 Web 版：https://devcloud.cn-north-4.huaweicloud.com/chat?source=dmzntgwsf&sourcead=dmzntgwwbwz，登录后直接对话，不用装软件。

我提交给它的需求是这样一段话：

做一个单文件 index.html 的 B+ 树索引分裂可视化实验室，纯原生 JS 加 SVG，不要外部 CDN 和网络请求，中文界面。顶部参数区可选阶数 m 为 3 到 8、插入 key 的数量 N、页大小、行大小、索引 key 大小、指针大小，参数改了立刻重算。主视图用 SVG 画 B+ 树，节点框里显示 key，叶子用箭头串成链表，插入过程有动画，节点写满、中间节点分裂、叶子分裂、根分裂都要能看出来，分裂时把新老节点高亮并用文字气泡说明第几次分裂、裂的是哪一层。右侧统计面板显示节点总数、叶子数、树高、累计分裂次数、叶子平均填充率、最小最大 key。再加一个对比区，同一批 key 分别跑顺序插入和随机插入，给出树高、分裂次数、填充率、节点总数的对照表。再加容量测算面板，按输入的页大小、行大小、索引 key、指针算出每页扇出、每页行数、三层和四层的总行数，每一步算式都写在页面上。页面底部放自检脚本，至少 12 条断言，包括所有叶子在同一层、每个非叶节点孩子数在合理区间、key 数量不超过 m-1、key 守恒、全局有序、叶子链表有序、分裂次数与节点数关系、根节点唯一无父节点、每个 key 只出现一次，结果逐条显示在页面上并给出通过数量。最后写一段怎么复现的说明，包括这套模型和真实 InnoDB 页结构的差别。完成后打开预览，让我直接看到运行效果。

使用码道体会

这次最值钱的动作，是把验收口径直接写进需求里。

我在需求里点名要「页面底部放自检脚本，至少 12 条断言，结果逐条显示在页面上」，交付时就有了 15 条可点可验的断言，文章里的每个数字才有出处。

第二个动作是要求它真算，不是把正确答案印在页面上。

树是真插出来的，统计面板跟着每一步更新，分裂次数和填充率都是算出来的值。

第三个动作是截图逐张放大看。

分裂点写错这种问题，读代码很容易滑过去，因为它只在一部分阶数上错，在小树的终态上看不出来；把图放大，看到 6 个 key 分成 4 和 2 的那一刻才发现不对。

第四个动作是边界如实写。

修复代价、随机顺序会漂、容量模型和真实 InnoDB 的差距，这些写出来比藏起来有用。

总结

B+ 树分裂这事，记住一条就够用：key 数超过 m-1 就裂，裂完两边都不能低于一半。

真要看懂，还是得让树自己长一遍。

把这篇文章里的数字在页面上点出来的路径是：阶数 6、数量 60，点跳过动画，看 26 个节点和 23 次分裂；把行大小改成 1024，看三层容量变成 20184000；最后点自检，看 15 条断言全绿。

案例目录，下载下来双击就能跑：

https://atomgit.com/deli007/demo_park/tree/main/codearts-bplus-tree-visualizer