高级数据结构_Bstar树

B*

是B+树的变种, 在B+树的非根和非叶子结点再增加指向兄弟节点的指针。

定义

B*树定义了非叶子节点关键字个数至少为$(2/3)*M$, 即块的最低使用率为$2/3$, 代替了B+树的$1/2$;

B*和B+节点分裂的对比

B+

当一个结点满时，分配一个新的结点，并将原结点中$1/2$的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针;

B*

B*树的分裂当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制$1/3$的数据到新结点，最后在父结点增加新结点的指针;

所以，B*树分配新结点的概率比B+树要低，空间使用率更高，在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从$1/2$提高到$2/3$。