srcmini本文概述
- B +树是平衡的二进制搜索树。它遵循多级索引格式。
- 在B +树中, 叶节点表示实际数据指针。 B +树确保所有叶节点保持相同的高度。
- 在B +树中, 叶节点使用链接列表链接。因此, B +树可以支持随机访问以及顺序访问。
B +树的结构
- 在B +树中, 每个叶节点与根节点的距离相等。 B +树的顺序为n, 其中每个B +树的n都是固定的。
- 它包含一个内部节点和一个叶节点。
内部节点
- B +树的内部节点可以包含除根节点以外的至少n / 2个记录指针。
- 树的内部节点最多包含n个指针。
叶节点
- B +树的叶节点可以包含至少n / 2个记录指针和n / 2个键值。
- 叶子节点最多包含n个记录指针和n个键值。
- B +树的每个叶节点都包含一个块指针P, 以指向下一个叶节点。
在B +树中搜索记录
假设我们必须在下面的B +树结构中搜索55。首先, 我们将获取中间节点, 该中间节点将定向到可以包含55条记录的叶节点。
因此, 在中间节点中, 我们将找到50到75个节点之间的分支。然后, 最后, 我们将被重定向到第三个叶节点。在这里, DBMS将执行顺序搜索以找到55。
B +树插入
假设我们要在下面的结构中插入一条记录60。它会在55之后到达第三个叶子节点。这是一棵平衡树, 并且该树的叶子节点已经满了, 因此我们无法在其中插入60。
在这种情况下, 我们必须拆分叶节点, 以便可以将其插入树中而不会影响填充因子, 平衡和顺序。
第三个叶子节点的值分别为（50、55、60、65、70）, 其当前根节点为50。我们将在中间拆分树的叶子节点, 以使其平衡不变。因此, 我们可以将（50, 55）和（60, 65, 70）分组为2个叶节点。
如果这两个必须是叶节点, 则中间节点不能从50个分支。它应该添加60个, 然后我们可以有一个指向新叶节点的指针。
这是我们如何在溢出时插入条目。在正常情况下, 很容易找到适合的节点, 然后将其放置在该叶节点中。
B +树删除
假设我们要从上面的示例中删除60。在这种情况下, 我们必须从中间节点以及第4个叶节点中删除60个。如果我们从中间节点删除它, 那么该树将不满足B +树的规则。因此, 我们需要对其进行修改以使其具有平衡的树。
从B +树上方删除节点60并重新排列节点后, 它将显示如下：
评论前必须登录！
注册