数据结构 —— B*树

﹏ヽ暗。殇╰゛Y 2021-10-19 10:34 327阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]

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

## B\*树的说明： ##

*  B\*树定义了非叶子结点关键字个数至少为(2/3)\*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
 *  从第1个特点我们可以看出，B\*树分配新结点的概率比B+树要低，空间使用率更高

## 分裂 ##

*  `B+树` 的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针。  
    B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
 *  `B*树` 的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；  
    如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B\*树分配新结点的概率比B+树要低，空间使用率更高；

## 比较 ##

*  **二叉搜索树：** 二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
 *  **B树：** 多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点； 所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
 *  **B+树：** 在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
 *  **B\*树：** 在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

## 参考文章： ##

https://www.cnblogs.com/biyeymyhjob/archive/2012/07/25/2608880.html  
https://blog.csdn.net/u013411246/article/details/81088914

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]: /images/20211018/f6d7d0f131284a4f83b80132d85a63d4.png