1）引言

在前几篇文章中介绍了 2-3 树的定义以及插入删除操作

。本篇文章将在 2-3 树的基础上更进一步，介绍比 2-3 树更为复杂的数据结构 2-3-4树 。之所以介绍 2-3-4 树是因为 2-3-4 树与极为重要的红黑树有着等价关系，通过先学习2-3-4 树为后面学习红黑树打下基础，增进对于红黑树的理解。

2） 2-3-4树

2-3 树不再是单纯的二叉树了，因为 2-3 树中除了 2- 节点之外还存在 3- 节点。在 2-3 树的基础上进一步扩展， 2-3-4 树在 2-3 树的基础上添加 4- 节点。4- 节点可以存储 3 个键值，最多可以拥有 4 棵子树。

3）定义

（1）每个节点每个节点有 1、2 或 3 个 key ，分别称为 2- 节点，3- 节点，4- 节点。

（2）所有叶子节点到根节点的长度一致（也就是说叶子节点都在同一层）。

（3）每个节点的 key 从左到右保持了从小到大的顺序，两个 key 之间的子树中所有的 key 一定大于它的父节点的左 key ，小于父节点的右 key 。

例如图 3.1 所示的一棵 2-3-4 树：

图3.1

4） 查找

2-3-4 树的查找类似了二叉树的查找过程，通过键值的比较来决定遍历方向。

例如在图3.1所示树中查找22：

例如在图 3.1 所示树中查找 15 ：