为什么有些btree图在同一层有多个节点？

Question

为什么有些图表的每个节点没有值，而是有 2 个值？他们想代表什么？

如果 8 的左右节点分别为 6 和 7，则第二个图有意义。我不明白为什么在第一个图中 100 有 2 个左节点和 2 个右节点。

我在这里缺少什么？

Answer 1

我不明白为什么在第一个图中 100 有 2 个左节点和 2 个右节点。

首先，B 树不是二叉（搜索）树：B 树中的节点被设计为允许多个键，最多可达固定的最大值。在第一个图像中，一个框代表一个可能具有多个键的“单个”节点。在第二张图片中，按键之间有分隔线，但原理相同。因此，用通常的术语来说，第一个图显示了一个只有两个子节点的根节点，而不是四个。

为什么有些图表的每个节点没有值，而是有 2 个值？

您指的是单个节点中包含的

keys

。每个节点都有固定数量的可被键占用的槽位，但这是动态的。在节点的生命周期中，它可能具有不同数量的密钥，但在一定限制内。 图像描绘了 3 阶 B 树（使用

Knuth 的阶数定义

，即最大分支因子）。