定义

每个节点有1，2，或者3个key，分别成为2-节点，3-节点，4-节点所有叶子节点到根节点的长度一致（即叶子节点都在同一层）每个节点的 key 从左到右保持了从小到大的顺序，两个 key 之间的子树中所有的 key 一定大于它的父节点的左 key ，小于父节点的右 key

相关操作

查找

类似二叉树的查找过程，通过键值的比较来决定遍历方向：

如果它和当前节点中的一个元素相等，就返回查找命中；如果它比当前节点任一元素要大，就选择右递归进行下一个节点；如果它比当前节点任一元素要小，就选择左递归进行下一个节点；直到树底下的空节点，返回查找未命中

例子一

例子二

插入

如果2-3-4树中已经存在当前插入的key，则插入失败，否则最终一定是在叶子节点中进行操作操作，因为查找过程的结束位置一定在叶子节点

非4-节点（3个key）插入

直接插入即可

2-节点中插入

3-节点中插入

4-节点插入

插入之后需要调整

根节点的父节点不是4-节点

如果待插入的节点是个 4- 节点，那么应该先分裂该节点然后再插入。一个 4- 节点可以分裂成一个根节点和两个子节点（这三个节点各含一个 key ）然后在子节点中插入，我们把分裂形成的根节点中的 key 看成向上层插入的 key ，然后重复上面

根节点的父节点是4-节点（根节点分裂）

如果是在 4 节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则 2-3-4 树会生长一层。

对于3-key节点，插入之后需要不断回溯（可能需要回溯到根节点），知道调整完成：

总结：

先找到待插入位置的节点的判断待插入位置是不是3-key （①） 不是：直接插入是： 先分裂待插入位置（一个父节点，两个子节点）将当前节点插入到某个子节点中（一定不需要分裂，因为它顶多形成一个三节点）现在需要将父节点向上融合 父节点的父节点是不是3-key（相当于回到了（①））

如下图所示，插入“125”，而此时待插入节点有3个key，需要对节点进行分裂，

　“100 125 130”节点分裂之后，如下图所示，分裂成父节点“120”与两个子节点“100”与“125 130”，此时将父节点“120”看作向上层插入的key， 而又由于“120”的上层节点是“60 70 80”是3个key的节点，则需要对3个key节点进行分裂，如下图所示，分裂成父节点”70”与子节点“60”与“80 120”，

将父节点“70”看作向上层插入的key，此时上层节点“22 50”是2个key，则直接插入即可，结果如下图所示，此时满足2-3-4树，完成调整。

删除

执行删除之前需要对删除 key 进行查找，若查找失败则无法删除。查找成功，才可删除 key 。

思路：

删除的是什么节点？删除了节点之后是否满足2-3-4树的性质？

删除非叶子节点

删除叶子节点

删除的节点是2-节点

当删除的叶子节点是 2- 节点，则将节点删除后，需要对树进行调整，调整规则如下：

删除的节点不是2-节点

删除的节点不为 2- 节点，则将要删除的目标 key 直接删除即可。

什么是2-3-4树？ 数据结构与算法——2-3-4树