By

本文详细介绍一下B*树的相关原理及实现。

1. B*树

B*树是B+树的变体，在B+树的非根和非叶子节点增加指向兄弟的指针；B*树定义了非叶子节点关键字个数至少为(2/3)*m，即块的最低使用率为2/3（代替B+树的1/2)。

ds-bmulti-tree

  • B+树的分裂： 当一个节点满时，则先分裂成两个节点X和Y，并且他们各自所含的关键字个数分别为： u=⌈(m+1)/2⌉, v=⌊(m+1)/2⌋。最后在父节点中增加新节点的指针。B+树的分裂只影响原节点和父节点，而不会影响兄弟节点，所以它不需要指向兄弟节点的指针。

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

所以，B*树分配新节点的概率比B+树要低，空间使用效率更高。



[参看]:

  1. B-树，B+树，B*树详解

  2. 浅析——B树，B+树，B*树以及分析MySQL的两种引擎