二叉排序树简单的实现在多数情况能够达到预期的查找效率，但是每个节点只能存储一个元素和只能有两个孩子，使得在大量数据下会造成二叉排序树的深度特别大，那么在进行查找时多次的访问会造成查找效率的下降，同时，在对二叉查找树进行插入时，可能会破坏二叉查找树的平衡。为了降低对于树的访问次数，实现树的平衡，我们需要新的数据结构来处理这样的问题。
多路查找树的每一个节点的孩子树可以多于两个，且每个节点处可以存储多个元素。多路查找树是一种特殊的查找树，所以其元素之间存在某种特定的排序关系。

一、2-3树

定义2-3树中每一个节点都具有两个孩子(我们称它为2节点)或三个孩子(我们称它为3节点)。

（1）一个2节点包含一个元素和两个孩子(只能包含两个孩子或没有孩子，不能出现有一个孩子的情况)，且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。
（2）一个3节点包含一小一大两个元素和三个孩子(只能包含三个孩子或没有孩子，不能出现有一个孩子或有两个孩子的情况)。如果某个3节点有孩子，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

1.1 查找

要判断查找的键值是否在树中，我们先将它和根结点中的键比较。如果它和其中的任何一个相等，查找命中。否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。

1.2 2-3树的插入实现

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用2-3树的主要原因就在于它能够在插入之后继续保持平衡。
2-3树插入可以分为三种情况：

（1） 对于空树，插入一个2节点即可
（2）插入节点到一个2节点的叶子上
（3）往3节点中插入一个新数据

由于其本身只有一个元素，所以只需要将其升级为3节点即可。

因为3节点本身就是2-3树的最大容量(已经有两个元素)，因此需要拆分。
分情况讨论如下所示：

（1）只有一个3-结点的树，向其插入一个新键

这棵树唯一的结点中已经没有可插入的空间了。我们又不能把新键插在其空结点上（破坏了完美平衡）。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个4-结点。创建一个4-结点很方便，因为很容易将它转换为一颗由3个2-结点组成的2-3树（如图所示），这棵树既是一颗含有3个结点的二叉查找树，同时也是一颗完美平衡的2-3树，其中所有空链接到根结点的距离都相等。

（2）向一个父节点为2节点的3节点中插入数据
假设未命中的查找结束于一个3-结点，而它的父结点是一个2-结点。在这种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。
我们先像刚才一样构造一个临时的4-结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。


这次转换并没有影响2-3树的主要性质，树仍然是有序的，因为中键被移动到父节点中去了。

（3）向一个父节点为3节点的3节点中插入数据

假设未命中的查找结束于一个3-结点，而它的父结点是一个3-结点。
我们再次和刚才一样构造一个临时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点，因此我们再用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。
我们就这样一直向上不断分解临时的4-结点并将中键插入更高的父结点，直至遇到一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根。


（4）父节点到根节点均是3节点

假设未命中的查找结束于一个3-结点，而它的父结点是一个3-结点。通过观察，到根节点都是满3节点。

我们发现(1、3)、(4、6)、(8、12)都是3节点，无法插入，意味着当前我们的树结构是三层已经不满足当前节点增加的需要了，于是将(1、3)拆分，(4、6)拆分，(8、12)拆分，树的深度增加一层。

1.3 2-3树的删除节点

对于2-3树的删除操作，分为3种情况：
（1）所删除元素位于一个3节点的叶子节点上
只需要在该节点处删除该元素即可，不会影响到整棵树的其他节点结构。

（2）所删除的元素位于非叶子的分支节点
通常是将树按中序遍历后得到此元素的前驱或后继元素，让他们来补位即可，再删除用于补位的前驱或后继元素。

如果我们要删除的分支节点是2节点，如上图，对于要删除的元素4，它的前驱是1，后继是6，显然(6、7)是3节点，只需要用6来补位即可。这里我们就不讲解删除的分支节点是3节点的情况了，和上述类似。

（3）所删除的元素位于一个2节点上
我们分析，如果删除一个2节点，很有可能造成2-3树平衡破坏的情况，因为对于每一个2节点，要么有两个子树要么没有，对于每一个3节点要么有三个子树要么没有，贸然删除一个2节点，很可能出现平衡遭到破坏，所以我们需要分情况讨论。

1）此节点的双亲节点是2节点，兄弟节点是3节点

将双亲节点移动到当前位置，再将兄弟节点中最接近当前位置的key移动到双亲节点中。
2）此节点的双亲是2节点，兄弟节点也是2节点

先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3节点；再进行a的操作


此时删除4，如果直接执行a会造成没有右孩子，因此需要对整棵树变形。我们让节点7变成3节点，那就让7的直接后继8下来，再让比8大的9补充到8的位置，在执行a操作。

3）此节点的双亲是一个3节点

拆分双亲节点使其成为2节点，再将再将双亲节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点

4）当前2-3树是一个满二叉树

将2-3树层树减少，并将兄弟节点合并到双亲节点中，同时将双亲节点的所有兄弟节点合并到双亲节点的双亲节点中，如果生成了4节点，再分解4节点即可。

二、2-3-4树

2-3-4树是对2-3树的概念扩展，包括了4节点的使用。一个4节点中包含小中大三个元素和四个孩子(要么有四个孩子要么没有，不存在其他情况)，如果某个4节点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素。如下图就是一个2-3-4树：

三、总结

（1）先找插入结点，若结点有空(即2-结点)，则直接插入。如结点没空(即3-结点)，则插入使其临时容纳这个元素，然后分裂此结点，把中间元素移到其父结点中。对父结点亦如此处理。（中键一直往上移，直到找到空位，在此过程中没有空位就先搞个临时的，再分裂。）

（2）2-3树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。所有局部变换都不会影响整棵树的有序性和平衡性。

（3）同时，通过上面树的深度增加的例子，可以看出2-3树和标准二叉树不同，标准的二叉树的的深度是由上到下的增加的，而2-3树的深度生长是由下至上的。