B

B 树 · 零基础动画演示

给没学过数据结构的人看的版本

数据结构 · 零基础版

B 树:会自己长高的文件柜

每个抽屉里放几张按大小排好的数字卡片,最多放 m−1 张。 抽屉塞满了,就把中间的数字升到上一层当路标;连顶楼也满了,就加盖一层。 因为它只往上长,所以整棵树永远是平衡的——这正是数据库索引喜欢它的原因。

01 · 动画演示

看它怎么长

左边是树,右边是同一时刻的 C++ 代码。点“播放”,看一个数字怎么被放进去、又怎么把树撑高。代码看不懂没关系,先看颜色和形状。想直接看极端情况,点「极端分裂」:一次插入会从叶子一路分裂到根。

m=5 时,每个抽屉最多 4 个数字
0数字
0节点(抽屉)
0树高(层数)
0叶子(最底层)
m = 5当前阶数
每个节点最多 4 个数字 · 除根外最少 2 个
树形结构 · 按住画布可以拖动
100%
空树 · 等待第一个数字

还没有节点

输入一个数字,或点「示例」。
每一帧都会展示:它去了哪个抽屉、有没有把抽屉撑爆。

拖动 / 滚轮查看
正在走的路 刚放进去 中间的数字 升上去 / 新顶层 装不下了
0 / 0
准备

输入一个数字,或点「示例」载入一组数据。点播放,就能看到它一步一步被放进去。

插入顺序: 0 个
还没有数字,先来一个吧。
02 · 规则讲解

为什么它一直这么“矮”?

这部分不用背。先记住一句话:每个抽屉不能太满,也不能太空;满了就往上分家。

先记住这个画面

把 B 树想成一栋文件柜。每一层有很多抽屉,每个抽屉里放着几张按大小排好的数字卡片。 找数字时,从顶楼开始,看抽屉里的卡片决定走哪条路;抽屉塞满了,就把中间那张卡片抽出来, 升到上一层当路标,剩下的卡片分成左右两个抽屉。如果连顶楼也满了,就加盖一层。 因为只在顶部加盖,所以不管从哪条路走,到最底层的层数都一样——这就是平衡。

01

每个抽屉最多放 m−1 张卡片,最多 m 条向下的路

“m”就是阶数,可以理解成抽屉的容量上限。抽屉里的卡片越多,能分出的岔路也越多。

例子:m=5 时,每个抽屉最多 4 张卡片、最多 5 条路。
m=5:最多 4 张,第 5 张就装不下 10 20 30 40 50 5 张 > 上限 4 张 → 装不下 10 20 40 50 30 30 升到上一层,左右分成两个抽屉
装不下时,中间的数字 30 升上去当路标,剩下的分成左右两个抽屉。
02

除了最顶层的根,每个抽屉不能太空

除根以外,每个节点至少要装到 2 张卡片(也就是至少 3 条路)。如果允许抽屉太空,树就会变得又高又瘦,查找变慢。

m=5 时:每个抽屉至少 2 张卡片;根可以例外。
每个抽屉的“水位线” 10 20 30 40 0 张:太瘦,树会被迫长高 2 张:刚好达到下限 4 张:达到上限,再来一张就分家 除根外,每个节点至少 ⌈m/2⌉−1 = 2 张
抽屉不能太空,否则树会又高又瘦;也不能超过上限。
03

根可以特殊一点

根是最顶层的节点。如果它下面还有楼层,至少要有 2 条路;如果整棵树只有它一个节点,它也可以只有 1 张卡片、0 条路。

整棵树刚创建时,根就是一个空抽屉——这是合法的。
根节点 30 10 40 ✓ 根:1 张也可以 普通节点 30 10 40 ✗ 普通节点:至少 2 张
根是全树唯一的例外;其他节点不能只有一张卡片。
04

所有最底层必须在同一深度

不管从根往哪条路走,到最底层(叶子)的步数都必须一样。这就是“平衡”的含义,也是 B 树查找稳定的原因。

所以 B 树只会在“顶部加盖”,绝不会在某一侧单独往下长。
所有叶子都在同一条水平线上 30 | 65 10 | 20 50 | 60 70 | 80 ✓ 三个叶子都在第 2 层
不管走哪条路,到最底层的步数都一样——这就是平衡。
05

抽屉里的卡片从小到大排

n 张卡片把数字范围切成 n+1 段,正好对应 n+1 条向下的路。找数字时,比较一下就知道该走哪条路。

例子:[10 | 20 | 30] 把数字分成 <10、10~20、20~30、>30 四段,对应 4 条路。
n 张卡片把数字切成 n+1 段 10 20 30 < 10 10–20 20–30 > 30 25 25 落在 20–30 这一段 → 走第 3 条路
先比较抽屉里的数字,就能把查找范围缩小到某一段。
插入的四步 动画里反复出现的,其实就这四件事。
STEP 01

找位置

从顶楼开始,比较数字,走对应的路,一直走到最底层。

STEP 02

放卡片

把新数字按顺序放进最底层的抽屉。如果没超过 m−1 张,就结束了。

STEP 03

装不下就分家

超过上限时,取中间那张升到上一层,剩下的分成左右两个抽屉。

STEP 04

顶楼也满了就长高

新建一层,中间的数字成为新根。树高 +1,这是 B 树唯一的长高方式。

用在哪里?

数据库索引(MySQL InnoDB 的 B+ 树变体、SQLite 等)、文件系统(NTFS、ext4)的目录索引,以及一切“一次读一大块、少跑几趟磁盘”的场景。

为什么快?

树很矮,通常 3~4 层就能装下几百万条数据;每个节点一次读进内存,能比较很多数字;因此磁盘 I/O 次数很少。

有 n 个数字时,树高大约是 logₘ n 层;查找 O(log n),插入 O(m · logₘ n),空间 O(n)。记不住也没关系,知道它“很快、很矮”就够了。

为什么不能把所有数字都放在一个抽屉里?

放不下,而且查找时要挨个比较,太慢。把数字分散到多个抽屉、再用路标指路,每次只需要看很少的几个数字。

为什么分裂时升上去的是“中间”的数字?

因为它正好把剩下的数字分成“左边都比它小、右边都比它大”两半,升到上一层后可以同时当两边的路标,树仍然有序。

为什么所有最底层必须在同一深度?

这样不管找哪个数字,走的层数都差不多,查找时间稳定;如果允许某一侧特别深,最坏情况就会退化,失去 B 树的优势。

一句话记住:满了就分家,中间的数字升上去;顶楼也满了,就加盖一层。因为只往上长,所以它永远是平衡的。
原创合成 · 适合科普演示的轻背景乐