主页 / dba / 问题 / 172669
Accepted
Revolucion for Monica
Asked: 2017-05-04 11:22:35 +0800 CST

如何将带有键的记录输入到最初为空的 B+ 树？

  • 772

将键为（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 之后的右叶上：

插入 4 & 5 后的 3 阶 B 树

btree

1 个回答

  1. Best Answer

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

    请注意，增长是在树的顶部，这是 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 - 我们拥有的唯一页面上。此外，“如果 [that node] 已满，它将被分成两个节点。” 页面已满，因此必须拆分。我们现在有

    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-Tree 中的 B 代表“平衡”。）

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

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

    我遇到过这种 B 树如何增长的交互式模拟。

    • 6

相关问题