给没学过数据结构的人看的版本
数据结构 · 零基础版
每个抽屉里放几张按大小排好的数字卡片,最多放 m−1 张。 抽屉塞满了,就把中间的数字升到上一层当路标;连顶楼也满了,就加盖一层。 因为它只往上长,所以整棵树永远是平衡的——这正是数据库索引喜欢它的原因。
左边是树,右边是同一时刻的 C++ 代码。点“播放”,看一个数字怎么被放进去、又怎么把树撑高。代码看不懂没关系,先看颜色和形状。想直接看极端情况,点「极端分裂」:一次插入会从叶子一路分裂到根。
输入一个数字,或点「示例」。
每一帧都会展示:它去了哪个抽屉、有没有把抽屉撑爆。
输入一个数字,或点「示例」载入一组数据。点播放,就能看到它一步一步被放进去。
这部分不用背。先记住一句话:每个抽屉不能太满,也不能太空;满了就往上分家。
先记住这个画面
把 B 树想成一栋文件柜。每一层有很多抽屉,每个抽屉里放着几张按大小排好的数字卡片。 找数字时,从顶楼开始,看抽屉里的卡片决定走哪条路;抽屉塞满了,就把中间那张卡片抽出来, 升到上一层当路标,剩下的卡片分成左右两个抽屉。如果连顶楼也满了,就加盖一层。 因为只在顶部加盖,所以不管从哪条路走,到最底层的层数都一样——这就是平衡。
“m”就是阶数,可以理解成抽屉的容量上限。抽屉里的卡片越多,能分出的岔路也越多。
例子:m=5 时,每个抽屉最多 4 张卡片、最多 5 条路。除根以外,每个节点至少要装到 2 张卡片(也就是至少 3 条路)。如果允许抽屉太空,树就会变得又高又瘦,查找变慢。
m=5 时:每个抽屉至少 2 张卡片;根可以例外。根是最顶层的节点。如果它下面还有楼层,至少要有 2 条路;如果整棵树只有它一个节点,它也可以只有 1 张卡片、0 条路。
整棵树刚创建时,根就是一个空抽屉——这是合法的。不管从根往哪条路走,到最底层(叶子)的步数都必须一样。这就是“平衡”的含义,也是 B 树查找稳定的原因。
所以 B 树只会在“顶部加盖”,绝不会在某一侧单独往下长。n 张卡片把数字范围切成 n+1 段,正好对应 n+1 条向下的路。找数字时,比较一下就知道该走哪条路。
例子:[10 | 20 | 30] 把数字分成 <10、10~20、20~30、>30 四段,对应 4 条路。
从顶楼开始,比较数字,走对应的路,一直走到最底层。
把新数字按顺序放进最底层的抽屉。如果没超过 m−1 张,就结束了。
超过上限时,取中间那张升到上一层,剩下的分成左右两个抽屉。
新建一层,中间的数字成为新根。树高 +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 树的优势。