1）多叉树
多叉树如果树中的节点可以包含更多的识别数据项，可以有更多的子节点，那么这样的树就是多叉树。
2）2-3-4树是什么
2-3-4树是一种特殊的多叉树，跟红黑树一样，它也是一种平衡树，效率比
红黑树稍差，其名字的含义是：
- 1）有一个识别数据项的节点可以有两个子节点
- 2）有两个识别数据项的节点可以有三个子节点
- 3）有三个识别数据项的节点可以有四个子节点
因此，2-3-4树的节点最多可以有四个子节点，所以也可以称为4叉树。
3）2-3-4树的数据组织规则
按照识别数据项分段存放 。
4）2-3-4树的实现和代码示例
4.1 搜索
2-3-4树的搜索算法跟二叉树搜索差不多，从根开始查找，判断要搜索的数据处于哪个区间，找到相应的字节点，判断是否匹配，否则重复这些动作。
4.2 插入
会有几种情况：
- 1）插入到未满的叶节点里面，直接插入数据即可，顶多会引起同一节点内数据项的移动，以保持数据项的顺序
- 2）插入到未满的子节点里面，子节点的编号就要发生变化，以此来保证树的结构
- 3）插入到已满的节点中，这就需要做节点分裂，算法如下：
step1.创建一个空节点，放置到分裂节点的右边
step2.最大数据项移动到新节点，中间数据项移动到父节点，最小的数据项不动
step3.重新设置最大和中间数据项的父子节点关系 - 4）插入到已满的根节点中，这就需要做根节点分裂，算法如下：
step1.创建一个空节点，作为分裂节点的父节点
step2.再创建一个空节点，作为分裂节点的兄弟节点
step3.最大数据项移动到新的兄弟节点中，中间数据项移动到新的父节点，最小的数据项不动
step4.重新设置最大和中间数据项的父子节点关系
4.3 删除
这个需要做节点的合并和调整，比较复杂。由于没有太大的必要，因此建议采用最简单的做法：给删除节点打标记，然后在业务处理时跳过即可。
5）2-3-4树和红黑树的关系和转换规则
2-3-4树和红黑树是同构的，可转化为红黑树。
2-3-4树转换成红黑树的规则 :
- 1）把只包含1个识别数据项和2个子节点的节点，转化为红黑树的黑色节点
- 2）把只包含2个识别数据项和3个子节点的节点，转化成一个子节点和一个父节点，哪个节点做父或子都可以；子节点有两个自己的子节点，这两个子节点要求是原本相邻的子节点，父节点有另一个子节点，子节点涂成红色，父节点涂成黑色
- 3）把只包含3个识别数据项和4个子节点的节点，转化成一个父节点，就是原本中间的识别数据项，两个子节点和四个孙子节点，原来前面的两个子节点作为最小项的子节点，原来后面的两个子节点作为最大项的子节点，子节点涂成红色，父节点涂成黑色
6）2-3-4树的效率
2-3-4树的效率 2-3-4树的层数比红黑树少，但每个节点的数据更多，因此其效率跟红黑树差不多，都是O(logN)。
