多叉树 & B树 & B+树 & B*树

1. 二叉树存在的问题：

二叉树虽然操作效率比较高，但是如果数据一多，就会有好多好多的节点，需要进行好多次的I/O操作，构建出来的二叉树就会很高很高，也会降低操作速度。

2. 怎么解决？

二叉树因为每个节点只能有两个子节点，所以数据一多构建出来的树的高度会很高。所以就出现了多叉树，顾名思义，每个节点可以有多个子节点，这样来降低树的高度。

3. 常见多叉树：

(1). 2-3树：

第二层左边的节点，有两个元素，7和5，它又有3个子节点，这就叫做2-3树，其中节点7 5称为3节点，节点9称为2节点。

2-3树

2-3树是最简单的B树，它有以下特点：

• 首先它也要满足排序树的特点，即左子节点都比父节点小，右子节点都比父节点大，如果3节点，那么中间那个元素要介于左节点和右节点之间，即6是介于4和11之间的；

• 所有的叶子节点都在同一层(B树都满足这个条件)；

• 有两个叶子节点的叫二节点，二节点要么两个子节点，要么没有子节点；

• 有三个子节点的节点叫三节点，三节点要么有三个子节点，要么没有子节点；

• 2-3树就是由二节点和三节点构成的树。

(2). 2-3-4树：

和2-3树的区别就是，它还允许节点有三个元素且有四个子节点。

4. B树：

B是balance，平衡的意思，所以，B树首先是一棵平衡树，而平衡树首先得是一棵排序数。所以B树就是一棵平衡的、排序的多叉树。B的相关说明如下：

• B树的阶：节点的最多子节点个数叫做阶。比如2-3树的阶就是3，2-3-4树的阶就是4；

• B树的搜索：从根节点开始，对节点内的元素进行二分查找，如果找到就结束，否则进入查找元素所属范围的子节点再进行二分查找，直到找到或者到达叶子节点；

• B树的所有节点都会存放数据；

5. B+树：

B+树是B树的变体，和B树的区别就是，B+树所有数据都存放在叶子节点。

• B+树所有的数据都存放在叶子节点的链表中，且链表中的数据也是有序的；

• 非叶子节点中存放的是索引，而不是要操作的数据，每个非叶子节点都会存放叶子节点的索引，也叫稀疏索引；

• B+树要进行搜素时，从根节点开始，通过与根节点索引的比较，就知道要往左子树查找还是往中间查找还是往右子树查找，到了子树的时候再通过与子树中存放的索引比较，又可以直到要往那一边查找。

• B+树一般用于文件系统；

6. B*树：

B*树又是B+树的变体，就是在B+树的基础上，在非根非叶子节点之间增加了指向兄弟节点的指针。