【数据结构和算法】多叉树

数据结构之多叉树的介绍，由于多叉树涉及的代码比较复杂，此章并没有多叉树的代码实现

二叉树缺陷： 当二叉树的节点非常巨大的时候，二叉树相应的层数也很高。进而影响二叉树的构建速度，也影响二叉树的操作速度。因此为了解决数据量庞大的二叉树，引出多叉树的概念

多叉树(Multiway Tree)： 允许一个节点有更多的子节点，从而在庞大数据中来降低树的高度。2-3树和2-3-4树就是典型的多叉树。

2-3树： 2-3树是最简单的B树结构。其中的2、3指的是二节点（一个节点拥有两个子节点），三节点（一个节点拥有是三个节点）

特点：
（1）2-3树的所有叶子节点都在同一层（只要B树都满足这个条件）
（2）二节点要么没有子节点，要么有两个子节点（不能只有一个）
（3）三节点与二节点同理，要么没有子节点，要么有三个子节点
（4）2-3树是由二节点和三节点构成的树

2-3树的创建讲究拆分和组合
拆分： 即一个节点存储的数据已满，则需要将该节点的数据拆分，形参新的节点，按照排序树的规则组成满二叉树
组合： 即一个节点进行拆分后，一般都会导致树的结构不符合满二叉树（根节点拆分不会导致），需要向上将数据进行组合，形参满二叉树

B树（B-Tree） ：B为Balanced，平衡。由于翻译的原因，可能会将B-Tree翻译成B-树，这是错误翻译。会让人以为B树和B-树是两种不同的树
特点：
（1）数据存放在树的每个节点中
（2）其搜索性能类似在书中进行了一次二分查找

B+树：B+树是B树的一个变体
特点:
（1）数据只存放在叶子节点中，非叶子结点存放的是索引值
（2）叶子节点存放的数据是一个有序的链表

B*树：B+树的一个变体，在B+树的非根节点和非叶子结点再增加指向兄弟的指针
特点:
（1）非根节点和非叶子结点拥有新的指针指向兄弟节点