拆分b +树中的节点

Question

我想弄清楚当节点溢出时到底发生了什么.info:在我的b +树中,每个块有4个指针和3个数据部分.问题:我明白当有溢出时我们分成2个节点,在我的情况下每个都有2个键,并插入父节点的中间值,而不从儿子中删除(与b树不同).

但是我遇到了这种情况:

                                |21|30|50|

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

我想首先插入键23我分裂| 21 | 22 | 25 | 成:| 21 | 22 | - | 和| 23 | 25 | - | 现在我需要将键23插入父| 21 | 30 | 50 | 巫婆导致另一个分裂.| 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