B树、B+树和B*树

---

一、B树(Balance Tree)

是一种比AVL树更平衡的树。
 
一颗m阶B树满足以下特点：

1. 树中每个节点最多包涵m个子节点；
2. 除根节点和叶子结点之外，其它节点至少有$\lceil \frac{m}{2}\rceil$个子节点；
3. 除根节点外，其他节点中的关键字个数至少是$\lceil \frac{m}{2}\rceil -1$个（叶子节点也要满足）；
4. 所有的叶子结点都在同一层；
    
   B树和B树结点的样子如下图所示：
   
   B树的搜索和二叉树的搜索类似；
    
   B树的插入和二叉树类似，只是如果插入新节点之后，如果结点中的元素个数超出了m阶的限制，就要对结点进行分裂；
    
   B树删除元素，如果节点不满足m阶B树的性质，需要从丰满的兄弟节点借元素，并调整父节点关键字使其满足搜索树性质，如果兄弟都不丰满，就和兄弟节点进行合并。

二、B树的优势

B树的优势体现在数据量非常大的搜索场景中。
常在文件索引系统，数据库索引中应用。
 
大数据量搜索会有如下问题：
数据量非常大 --> 磁盘会给数据创建索引 --> 给数据进行排序，加速搜索
需要解决两个问题：
1、更少的磁盘I/O
假设有n个索引需要从磁盘中进行读取并且搜索
用AVL树，平均高度为$lo{g}_{2}n$
用300阶B树，平均高度为$lo{g}_{300}n$，每一层代表一次磁盘I/O
2、更快的搜索算法
在B树中因为节点关键字有序，所以用二分搜索也比较高效。
 

二、B+树

B+树是B树的一种变形，
和B树的区别：

1. 所有叶子结点包含关键字信息，及指向含有这些关键字记录的指针，且叶子结点中关键字进行有序排列
2. 非叶子结点相当于叶子结点的索引，叶子结点相当于存储数据的数据层
    

三、B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的节点，
B*树分配新节点的概率比B+树低，提高了结点的空间使用率。