DBMS B+树

B+树 是一个平衡的二叉搜索树，它遵循多级索引格式。

• 在B+树中，叶节点表示实际的数据指针，B+树确保所有叶节点保持在相同的高度。
• 在B+树中，叶节点使用链表链接，因此，B+树可以支持随机访问以及顺序访问。

B+树的结构

在B+树中，每个叶节点与根节点的距离相等。B+树的顺序为n，其中n对于每个B+树是固定的。
它包含内部节点和叶节点。

内部节点

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

叶节点

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

在B+树中搜索记录

假设要在下面的B+树结构中搜索55。 首先，获取中间节点，该节点将指向可包含55的记录的叶节点。

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

B+树插入

假设要在下面的结构中插入记录60。 它将在55之后转到第3个叶子节点。它是一个平衡树，并且该树的叶节点已经满了，所以不能在那里插入60。

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

第3个叶节点具有值(50,55,60,65,70)，其当前根节点为50。在中间拆分树的叶节点，以便不改变其平衡。 因此，可以将(50,55)和(60,65,70)分组为2个叶节点。

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

这是在有溢出时插入条目的方法。 在正常情况下，很容易找到它所适合的节点，然后将其放在该叶节点中。

B+树删除

假设要从上面的例子中删除60。 在这种情况下需要从中间节点以及第4叶节点中删除60。 如果从中间节点中删除它，那么树将不满足B+树的规则。 所以需要修改它以获得平衡的树。

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