如何使用初始空的 B+ 树的键输入记录？

Question

显示按(1, 2, 3, 4, 5)的顺序输入带有键的记录到一个初始为空的B+-阶m = 3的树的结果。 如果溢出，将节点拆分，不要重新分配邻居的钥匙。是否可以以不同的顺序使用键输入记录以获得较低高度的树？

来自Relational DBMS Internals，第 5 章：动态树结构组织，第 50 页

我不擅长这个但我尝试过吗？左侧和 > 右侧：

直到插入 1,2 ：

然后，就我们必须拆分节点而不是将密钥重新分配给邻居（我将其理解为子节点）而言，我只在单元格的右侧插入了 2 ：

我在插入 5 时继续做同样的事情：

但这很奇怪，我从未见过这样的空节点......而且我不知道它是否尊重一些非常基本的 B 树属性：

• 每个节点最多有(m-1) 个键，至少有(?(m/2)?-1) 个键，除非一个键可以为空，我会将键理解为“指针”。

第一次尝试：订单上的错误显示一棵不明确的树

一开始我误解了“顺序”是什么（每个节点的最大子节点数）。所以我认为一个节点可以有三个空间（因此有 4 个孩子。我正在创建一个 4 阶树，我认为：

直到插入 1,2,3 ：

插入 4，只要我们必须拆分节点而不是将密钥重新分配给邻居（这似乎是矛盾的），我会让 1,2,3 和 4,5 在 3 之后的右叶上：

Answer 1

我认为您的页面创建颠倒了。当一个节点拆分它不会创造更多的节点下来（在你的儿子命名节点）的层次结构。相反，它向根部创造了更多的向上。正如书中所说

注意生长是在树的顶端，这是B树的一个内在特性，以确保它的重要特性是它总是具有同一层的所有叶子，并且每个与根不同的节点至少是50% 满。

（我的重点。）

来自链接的电子书：

定义 5.1 AB-m 阶树 (m ? 3) ... 每个节点最多包含 m ？1把钥匙

该练习针对 m=3，因此每个节点最多 2 个键。

前两个键很简单——它们进入第一页：

A:[1,2]

我将使用 ASCII 艺术。我将按照创建的顺序标记每个页面，并显示页面内的键/指针。因此，包含键值 k1 和 k2 的页面 P 将是P:[k1,k2]。

现在关键 3 出现了。根据第 5.2.1 节...插入，第一个任务是搜索。这决定了键 3 应该在页面 A 上——我们拥有的唯一页面。进一步“如果[那个节点]已满，它将被分成两个节点。” 页面已满，因此必须拆分。我们现在有

A:[1,2]    B:[3, ]

但这不是一棵树！正如书中所说：

将指向[新节点]，..的指针插入到[当前节点]的父节点..中，在这个节点[即父节点]中重复插入操作。如果有必要，这个分裂和向上移动的过程可以继续直到根，如果必须分裂，一个新的根节点将被创建..

（我强调显示处理继续沿着树向根方向向上，而不是向下向叶。）

所以我们必须将一个指向新页面（B）的指针放入当前页面（A）的父页面。必须有一个新的根节点：

      C:[2,3]
      /     \
A:[1,2]    B:[3, ]

我在非叶页面中有指向子（子）节点中最高值的指针。您的链接文本可能会以不同的方式执行此操作，但结果将是相同的。

键值4到了；按照我们搜索的算法来查找它应该在哪个页面上。它应该是页面 B。 它有空间，所以我们更新页面和页面 C 上的指针：

      C:[2,4]
      /     \
A:[1,2]    B:[3,4]

接下来我们插入键 5。它应该进入页面 B 但它已满。因此它分裂

      C:[2,4]
      /     \
A:[1,2]    B:[3,4]   D:[5, ]

我们必须更新父节点。它也很满，所以它分裂了：

      C:[2,4]    E:[5, ]
      /     \         \
A:[1,2]    B:[3,4]   D:[5, ]

分裂向上传播并形成一个新的根节点：

            F:[4,5]
            /     \
      C:[2,4]    E:[5, ]
      /     \         \
A:[1,2]    B:[3,4]   D:[5, ]

通过向上生长，树在每个分支中保持相同的深度。这对于可预测的性能很重要。（出于这个原因，有人说 B 树中的 B 代表“平衡”。）

至于第二部分——“是否有可能以不同的顺序用键输入记录以获得较低高度的树？” 每个节点有 5 个键和两个键，我们需要至少 3 个叶节点来保存所有值，并且需要高度为 3 来形成树。所以我的安排对于给定的数据、序列和算法是最佳的。

这本书使用了与我使用的完全不同的指针排列，以及不同的页面拆分排列。这将是重要的，导致部分完整的页面。第 42 页上有一个名为“数据加载”的部分，展示了如何通过加载键序列之外的方式来实现更完整的页面，这支持我的预感。但是，我希望我已经给了你足够的指导，你将能够使用本书的指针结构自己解决这个问题。

我遇到过这个关于 B 树如何生长的交互式模拟。