4阶B树（2-3-4树/TwoFourTree）之插入

作者：知新_RL | 2024-04-10 07:07:46

踩

4阶b树

B树插入满节点分裂有两种方法。一种是递归写法，即先往下找到要插入的节点，直接插入。满了就传值到上层进行分裂，一种是迭代写法，在找要插入的节点过程中遇到满节点就分裂，自然当插入的节点满了往上传时其父节点非满，不需要分裂。
下面分别说明：

递归

递归写法中，将包括带插入的值在内的4个值排序，左边两个留在原来的节点，第三个往上，第四个作为新节点，即原来节点的父节点的新的子节点，如图。
准备插入15
溢出，20上移，25右移
基本思想就是如此，加入30节点也是满的，则继续分裂。
在分裂时，情况众多，我的递归写法感觉还存在bug。生成1-100的值，使用shuffle随机打乱再插入。但总会出现少值或者树断了的情况。将所想到的情况描述

首先找到节点&

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/397262