通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。本篇博客我们将介绍的——2-3-4树，它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。
1、2-3-4 树介绍2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：
①、有一个数据项的节点总是有两个子节点；
②、有二个数据项的节点总是有三个子节点；
③、有三个数据项的节点总是有四个子节点；
简而言之，非叶节点的子节点数总是比它含有的数据项多1。如果子节点个数为L，数据项个数为D，那么：L = D + 1
叶节点（上图最下面的一排）是没有子节点的，然而它可能含有一个、两个或三个数据项。空节点是不会存在的。
树结构中很重要的一点就是节点之间关键字值大小的关系。在二叉树中，所有关键字值比某个节点值小的节点都在这个节点左子节点为根的子树上；所有关键字值比某个节点值大的节点都在这个节点右子节点为根的子树上。2-3-4 树规则也是一样，并且还加上以下几点：
为了方便描述，用从0到2的数字给数据项编号，用0到3的数字给子节点编号，如下图：
①、根是child0的子树的所有子节点的关键字值小于key0；
②、根是child1的子树的所有子节点的关键字值大于key0并且小于key1；
③、根是child2的子树的所有子节点的关键字值大于key1并且小于key2；
④、根是child3的子树的所有子节点的关键字值大于key2。
简化关系如下图，由于2-3-4树中一般不允许出现重复关键值，所以不用考虑比较关键值相同的情况。
查找特定关键字值的数据项和在二叉树中的搜索类似。从根节点开始搜索，除非查找的关键字值就是根，否则选择关键字值所在的合适范围，转向那个方向，直到找到为止。
比如对于下面这幅图，我们需要查找关键字值为 64 的数据项。
首先从根节点开始，根节点只有一个数据项50，没有找到，而且因为64比50大，那么转到根节点的子节点child1。60|70|80 也没有找到，而且60<64<70，所以我们还是找该节点的child1,62|64|66，我们发现其第二个数据项正好是64，于是找到了。
3、插入新的数据项一般要插在叶节点里，在树的最底层。如果你插入到有子节点的节点里，那么子节点的编号就要发生变化来维持树的结构，因为在2-3-4树中节点的子节点要比数据项多1。
插入操作有时比较简单，有时却很复杂。
①、当插入没有满数据项的节点时是很简单的，找到合适的位置，只需要把新数据项插入就可以了，插入可能会涉及到在一个节点中移动一个或其他两个数据项，这样在新的数据项插入后关键字值仍保持正确的顺序。如下图：
②、如果往下寻找插入位置的途中，节点已经满了，那么插入就变得复杂了。发生这种情况时，节点必须分裂，分裂能保证2-3-4树的平衡。
ps：这里讨论的是自顶向下的2-3-4树，因为是在向下找到插入点的路途中节点发生了分裂。把要分裂的数据项设为A,B,C，下面是节点分裂的情况（假设分裂的节点不是根节点）：
1、节点分裂一、创建一个新的空节点，它是要分裂节点的兄弟，在要分裂节点的右边；
二、数据项C移到新节点中；
三、数据项B移到要分裂节点的父节点中；
四、数据项A保留在原来的位置；
五、最右边的两个子节点从要分裂处断开，连到新节点上。