个性化阅读
专注于IT技术分析

DBMS和B+树原理

点击下载

本文概述

  • B +树是平衡的二进制搜索树。它遵循多级索引格式。
  • 在B +树中, 叶节点表示实际数据指针。 B +树确保所有叶节点保持相同的高度。
  • 在B +树中, 叶节点使用链接列表链接。因此, B +树可以支持随机访问以及顺序访问。

B +树的结构

  • 在B +树中, 每个叶节点与根节点的距离相等。 B +树的顺序为n, 其中每个B +树的n都是固定的。
  • 它包含一个内部节点和一个叶节点。
DBMS和B+树原理

内部节点

  • B +树的内部节点可以包含除根节点以外的至少n / 2个记录指针。
  • 树的内部节点最多包含n个指针。

叶节点

  • B +树的叶节点可以包含至少n / 2个记录指针和n / 2个键值。
  • 叶子节点最多包含n个记录指针和n个键值。
  • B +树的每个叶节点都包含一个块指针P, 以指向下一个叶节点。

在B +树中搜索记录

假设我们必须在下面的B +树结构中搜索55。首先, 我们将获取中间节点, 该中间节点将定向到可以包含55条记录的叶节点。

因此, 在中间节点中, 我们将找到50到75个节点之间的分支。然后, 最后, 我们将被重定向到第三个叶节点。在这里, DBMS将执行顺序搜索以找到55。

DBMS和B+树原理

B +树插入

假设我们要在下面的结构中插入一条记录60。它会在55之后到达第三个叶子节点。这是一棵平衡树, 并且该树的叶子节点已经满了, 因此我们无法在其中插入60。

在这种情况下, 我们必须拆分叶节点, 以便可以将其插入树中而不会影响填充因子, 平衡和顺序。

DBMS和B+树原理

第三个叶子节点的值分别为(50、55、60、65、70), 其当前根节点为50。我们将在中间拆分树的叶子节点, 以使其平衡不变。因此, 我们可以将(50, 55)和(60, 65, 70)分组为2个叶节点。

如果这两个必须是叶节点, 则中间节点不能从50个分支。它应该添加60个, 然后我们可以有一个指向新叶节点的指针。

DBMS和B+树原理

这是我们如何在溢出时插入条目。在正常情况下, 很容易找到适合的节点, 然后将其放置在该叶节点中。

B +树删除

假设我们要从上面的示例中删除60。在这种情况下, 我们必须从中间节点以及第4个叶节点中删除60个。如果我们从中间节点删除它, 那么该树将不满足B +树的规则。因此, 我们需要对其进行修改以使其具有平衡的树。

从B +树上方删除节点60并重新排列节点后, 它将显示如下:

DBMS和B+树原理
赞(0)
未经允许不得转载:srcmini » DBMS和B+树原理

评论 抢沙发

评论前必须登录!