更新时间：2022-08-25 18:49
树家族是为了实现方便快捷的查找而存在的。树的高度是命中查找的一个不可抗拒的时间下限。在一定的数据条件下，树的高度和宽度是互相制约的。（就像一定面积下，矩形的长和宽是互相制约的）而树家族中最简单的二叉树，尽管易于实现，却不能有实际的价值。其最最令人发指的是二叉树的高度太高。n叉树的提出和实现解决了二叉树的不足，典型的n叉树有：2-3-4树/红黑树和B树。
注意：根结点为叶子节点，整棵树只有一个根节点。
2-3-4树在计算机科学中是阶为4的B树。大体上同B树一样，2-3-4树是可以用做字典的一种自平衡数据结构。它可以在O（logn）时间内查找、插入和删除，这里的n是树中元素的数目。2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。
2-3-4树把数据存储在叫做元素的单独单元中。2-3-4树，就是有2个子女，3个子女，或4个子女的节点，这些含有2、3、或4个子女的节点就构成了我们的2-3-4树。所以，它们组合成节点，每个节点都是下列之一：
每个子节点都是（可能为空）一个子2-3-4树。根节点是其中没有父节点的那个节点；它在遍历树的时候充当起点，因为从它可以到达所有的其他节点。叶子节点是有至少一个空子节点的节点。同B树一样，2-3-4树是有序的：每个元素必须大于或等于它左边的和它的左子树中的任何其他元素。每个子节点因此成为了由它的左和右元素界定的一个区间。如图1所示（你可以看到，图中这棵2-3-4树是由2-结点，3-结点，4-结点元素组成的）：
尽管2-3-4树的流行和其简单实现（红黑树）已经逐渐被大家接纳，但是对于大量数据来说，用红黑树实现查找是不现实的。MySQL和Berkeley DB都是基于B树原理而建立数据库的。B树是一种可实现的平衡多路查找树。此次对B树的实现进行举例。
伪代码如下：