数据结构：2-3树、B树、B+树、B*树

多路查找树

muitl-way search tree

在二叉树中，每个节点最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多路查找树，也叫多叉树。

节点的度

节点的子节点有几个。

树的度M

节点的度的最大值。

2-3树（二三树）

满足排序树的特点。

2-3树是最简单的B树。

2-3树所有叶子节点都在同一层（只要是B树都要满足所有节点在同一层这个条件）。

有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。

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

2-3树由二节点和三节点组成。

2-3-4树和2-3树类似，也是一种B树。

B树

注意：B-树，不是B减树，就是B树！

B：是Balance平衡的意思，不是Binary。

可以在非叶子节点命中数据。

B树的阶

节点的最多子节点的个数，比如2-3树的阶就是3，2-3-4树的阶就是4。

B+树

所有数据都在叶子节点的链表中，不可能在非叶子节点命中。

叶子节点有一个指针指向下一个叶子节点，所有适合范围查询（MySQL范围查询时适合建立B+Tree索引，等值查询时适合Hash索引）。

数据只能在叶子节点，也叫稠密索引。

非叶子节点相当于叶子节点的索引，稀疏索引。

更适合文件系统。

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。

非叶子节点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。

B*树分配新节点的概率比B+树要低，空间使用率更高。