之前对这一块内容很迷惑，尤其是多叉树空间利用率高。最近又复习了下，加深下印象。

二叉树，一般是一个节点外加左指针和右指针。

多叉树，是n个节点，对应n+1个指针。

对磁盘的读取，是基于块结构来进行的。磁盘对二叉树和多叉树，都可以打包多个节点。这里边唯一区别就是，多叉树可以根据指针快速指向目标，这个i/o的访问次数是远远低于二叉树的。

举个例子。

1. 先看反例：普通二叉树像 “写得很烂的笔记”

普通二叉树的节点是 “1 条数据 + 2 个指针”，就像你记笔记时：

每一页纸只写 1 句话（1 条数据），比如 “苹果：一种水果”；

这句话下面只画 2 个小箭头（2 个指针），一个指向 “比苹果小的水果”（左指针），另一个指向 “比苹果大的水果”（右指针）。

如果你想查 “西瓜”，就得这么翻：

翻第 1 页（苹果）→ 箭头指 “比苹果大的翻第 5 页”；

翻第 5 页（橙子）→ 箭头指 “比橙子大的翻第 12 页”；

翻第 12 页（菠萝）→ 箭头指 “比菠萝大的翻第 28 页”；

翻第 28 页（西瓜）→ 终于找到。

明明 1 页能写很多，结果你 1 页只写 1 句，查个东西要翻十几次 —— 这就是二叉树的问题：单页信息太少，导致翻页（I/O）次数多。

2. 再看正例：B 树的 “主动打包 + 多路子指针” 像 “精心排版的字典”

B 树的设计，就是把字典排得更高效，核心就是两招：

第一招：主动打包多个数据 = 让字典一页多写点内容

B 树不搞 “一页 1 条数据”，而是主动把很多相关数据挤在同一页（刚好装满 1 个磁盘块）。

比如字典的 “水果页” 里，一页就写满了：

“苹果、橙子、菠萝、草莓、西瓜、葡萄”（这些数据会按顺序排好，方便快速找）。

这样一来，你翻 1 次页（1 次 I/O），就能看到 6 种水果的信息，而不是 1 种 ——单页信息密度翻倍，同样查 10 个数据，翻页次数自然少了。

第二招：多路子指针 = 让字典一页给多个 “下一页方向”

普通笔记一页只给 2 个箭头（左 / 右），但 B 树的一页会给 “数据数量 + 1” 个箭头（多路子指针）。

比如刚才那页写了 6 种水果，就会给 7 个箭头，每个箭头对应一个 “范围”，直接指向下一页的位置：

箭头 1：“比苹果小的水果 → 翻第 3 页”（比如樱桃、蓝莓）；

箭头 2：“苹果和橙子之间的水果 → 翻第 8 页”（比如梨）；

箭头 3：“橙子和菠萝之间的水果 → 翻第 15 页”（比如芒果）；

...（中间 4 个箭头略）...

箭头 7：“比葡萄大的水果 → 翻第 42 页”（比如榴莲）。

这些箭头就是 “子指针”，它的作用是：你在当前页看完所有数据后，不用瞎猜下一页翻哪，直接按箭头指的 “范围” 跳 ——一次就能锁定下一页的精准位置，不用反复试错翻页。

通过上面的方法就能降低磁盘的查询效率。另外一点就是二查询查询效率不均衡，只有两个分支，容易退化成链表。

二叉树比当前节点小，左子树插入。 比当前节点大，右子树插入。