一、B树

B树，也叫B-树，它是一棵多路平衡搜索树。
一个m阶的B树满足以下条件：
1. 每个节点最多有m个子节点。（m>=2,m=2时是二叉搜索树）
2. 根节点至少有2个子节点，至少1个关键字.(除了一棵树只有根节点外)
3. 每个分支节点至少ceil(m/2)[取上限]个子节点（除根节点和叶子节点外）
4. 所有叶子节点在同一层。（叶子节点不包含任何信息，可看成额外的节点）
5. 有k个子节点的分支节点有k-1的关键字，按递增顺序排列。
6. 每个分支结点关键字数量要满足ceil（m/2）-1<=n<=m-1.
7. 分支节点包含n个关键字:（n，P₀，K₁，P₁，K₂，…,K_n,P_n）,满足K_i<P_i<K_i+1(相当于：左孩子<父节点<右孩子)

这个网站不错： 一个可视化B树的网站

优点：利用平衡树的优势，保证了查询稳定性、加快了查询速度。

关于B树的插入和删除操作原则要记住：在进行插入或删除操作后，一定要查看树是否满足约束条件，若不满足，则进行调整。

B树应用场景:B树可以优化，提高磁盘读取时定位的效率。由于一棵树中任意检查一个节点需要一次磁盘的访问，所以B树避免了大量的磁盘访问；而且B树是平衡树，每个节点到叶子节点的高度都相同，保证了查询的稳定性，查询时间复杂度为O（logN）（严格意义上写为log_mN，m为度数，N为节点数）。

B树的高度:T为度数（节点包含的最少子节点个数，T>=2）,也叫阶数，N为总元素个数或总关键字数。

二、B+树

B+树是B树的变体，为了适应文件系统所需而产生的。

B和B+树的区别：
1. 关键字数量不同。B树有m个节点，m-1个关键字；B+树有m个关键字，有m个叶子节点，关键字只是起到索引的作用。
2. 存储位置不同。B树的数据存储在每个节点上，并不仅仅存储在叶子节点上；B+树中的数据都存储在叶子节点上。
3. 分支节点构造不同。B+树的分支节点存储关键字信息和孩子指针，也就是说内部节点仅仅包含索引信息
4. 查询不同。B树在找到具体数值以后就结束，而B+树则需要通过索引找到叶子节点中的数据才结束，也就是说B+树的搜索过程中走了一条从根节点到叶子节点的路径，高度相同，相对来说更稳定。
5. 区间访问不同。B+树的叶子节点按顺序建立起链状指针，可进行区间访问。
6. B+树比B树更适合实际应用中操作系统文件索引和数据库索引。（1）B+树的磁盘读写代价更低；（2）B+树的查询更稳定

三、B*树

B树是B+树的变体，B树在分支节点中增加了指向兄弟节点的指针。B*树定义了非叶子节点关键字个数至少要(2/3)*m个，即最低使用率2/3.

B * 和B+的区别 :

1. B*树分配新结点的概率比B+树要低，空间使用率要高。
2. B*树的分裂影响兄弟节点，B+树的分裂只影响原节点和父节点，不会影响兄弟节点，所以不用指向兄弟指针。

总结：