# 一、为什么是有B树
二叉树存在的问题： 二叉树的构建是在内存中执行的，需要将磁盘中的文件通过 IO操作进行读取。如果二叉树的节点少，这样也没有问题，但是如果二叉树的节点很多（比如说一个亿），则存在如下问题：
【1】在构建二叉树时，需要多次进行 IO操作（海量数据存储在数据库或者文件中），节点海量，构建二叉树时，速度有影响。
【2】节点海量，也造成了二叉树的高度很高，会降低操作速度。
# 二、B树（多叉树）
【1】在二叉树中，一个节点最多可以有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树；
【2】2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。如下图就是一个2-3树；
【3】文件系统及数据库系统的设计者利用磁盘预读（预先读取）原理，将一个节点的大小设置为页<page:数据读取的最小单位>的大小（通常为4k），这样每个节点只需要一次 IO就能载入内存；B树(B+树)广泛应用于文件存储系统及数据库文件系统中。
2-3 树基本介绍： 最简单的 B树结构，具有如下特点：
■ 2-3 树的所有叶子节点都在同一层（只要是B树都满足这一点）；
■ 有两个子节点的叫二节点，二节点要么没有子节点，要么有两个子节点；
■ 有三个子节点的叫三节点，三节点要么没有子节点，要么有三个子节点；
■ 2-3 树是由二节点和三节点构成的树；
■ 当按照规则插入一个数到某个节点时，不能满足上述要求时，就需要拆分。先向上拆，如果上层满了，则拆本层。拆后仍需要满足上述条件；
■ 对于三节点的子树的值的大小仍然遵循（BST：二叉排序树）的规则；
B-Tree树即B（Balanced：平衡）树，有人将B-Tree 翻译成 B-树，容易让人产生误解，会以为 B-树是一种树。实际上，B-Tree就是B树。
# 三、B树、B+树、B*树
【1】B树介绍： 前面介绍的2-3、2-3-4树就是 B树，在MySql中经常听说某种索引是基于 B树、B+树的，如下图：
①、B树的阶：最多的节点个数。比如2-3树的阶=3，2-3-4树的阶=4；
②、B树的搜索，从根节点开始搜索，对节点内的关键字有序进行二分查找，如果命中则结束，否则进入关键字节点的孩子节点查找，直到所对应的儿子节点为空，或已经是叶子节点；
③、关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据；
④、搜索有可能在非叶子节点结束；
⑤、其搜索性能等价于在关键字全集内做一次二分查找；
【2】B+树介绍： B+ 树是B树的变体，也是一种多路搜索树，如下图：
①、B+树的搜索与B树基本相同，区别是B+树只有达到叶子节点才命中（B树可以在非叶子节点中命中），其性能也等价于在关键字全集中做一次二分查找；
②、所以关键字都出现在叶子节点的链表中（即数据只能存储在叶子节点【也叫稠密索引】），且链表中的关键字（数据）恰好是有序的；
③、不可能在非叶子节点命中；
④、非叶子节点相当于叶子节点的索引（稀疏索引），叶子节点相当于存储数据的数据层；
⑤、更适合文件索引系统；
⑥、B树与B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然；
【3】B*树介绍：B*树是B+树的变体，在B+树的非根和非叶子节点增加了指向兄弟的指针，如下图：
①、B*树定义了非叶子节点的关键字个数至少为(2/3)*M ，即块的最低使用率为2/3, 而B+树块的最低使用率为1/2;
②、从第一个特性可以看出，B*树分配新节点的概率比B+树低，空间使用率高;