tree - 在 b+ 树中拆分节点

Question

我试图弄清楚当节点溢出时到底发生了什么。
信息:
在我的 b+ 树中，每个块有 4 个指针和 3 个数据部分。
问题:
我知道当发生溢出时，我们分成 2 个节点，每个节点有 2 个
key ，
并将中间值插入父节点，而不从子节点中删除(与 b 树不同)。

但是我遇到了情况:

                                |21|30|50|

           |10|20|-|      |21|22|25|  |30|40|-| |50|60|80|  

我想插入键 23
首先我 split |21|22|25|进入:|21|22|-|和 |23|25|-|
现在我需要将键 23 插入父 |21|30|50|女巫导致另一次 split 。
|21|23|-|和 |30|50|-|
但是 30 之前的指针指向哪里呢？
有没有可能这个指针和23之后的指针都指向|23|25|-|
?

Answer 1

插入 23 时:

正如你所说，21|22|-|和 |23|25|-|已创建

2 个节点需要一个父节点

在根节点中创建一个父节点:|21|23|30|50|

根现在有太多元素

将根分成 2 个节点 |21|23|- 和 |30|50|-

为 2 个新节点(恰好是树的新根)添加一个新的父节点

基本上，该插入将使树的深度增加 1