理清B树、B-树、B+树、B*树索引之间的区别和联系

B树：二叉搜索树

  • 所有非叶子节点至多拥有两个子结点
  • 所有节点存储一个关键字
  • 非叶子节点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。
B树的搜索：从根节点开始，如果查询的关键字与结点的关键字相等，那么就命中。否则如果查询的关键字比节点小，就进入左儿子；如果比节点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，那么报告找不到相应的关键字；
如果B树的所有非叶子节点的左右子结点数目均保持差不多，那么B树的搜索性能就逼近二分查找；但它比连续内存空间的二分查找优点是，改变B树结构（插入和删除）不需要移动大段的内存数据，甚至通常是常数开销。


但B树经过多次的插入，有可能导致不同的结构：
如下所示，有图也是一个B树，但搜索性能已经是线性的了。
所以实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”



B-树

是一种多路搜索树（并不是二叉树），B-树索引是基于二叉树结构的。
B-树索引结构有3个基本组成部分：
  • 根节点：只有一个根节点，位于树的最顶端分支节点
  • 分支节点：包含的条目指向索引里其他的分支节点或者是叶子节点
  • 叶子节点：包含条目直接指向表里的数据行

B-树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子节点；重复，知道所对应的儿子指针为空，或已经是叶子节点。
B-树的特性：
  • 关键字集合分布在整棵树中
  • 任何一个关键字出现且只出现在一个节点中
  • 搜索有可能在非叶子节点结束
  • 其搜索性能等价于在关键字全集内做一次二分查找
  • 自动层次控制

B+树（适合做文件索引系统）

B+树是B-树的遍体，也是一种多路搜索树。
  1. 其定义基本等同于B-树，除了：
  2. 非叶子节点的子树指针与关键字个数相同
  3. 非叶子节点的子树指针p[i]，指向关键字值属于[K[i],K[i+1])
  4. B-树是开区间
  5. 为所有叶子节点增加一个链指针
  6. 所有关键字都在叶子节点出现；如：（M=3）

B+的搜索与B-树基本相同，区别是B+树只有达到叶子节点才命中，而B-树可以在非叶子节点命中，其性能也等价于在关键字全集做一次二分查找。
B+的特性：
  • 所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的
  • 不可能在非叶子节点命中
  • 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层
  • 更适合文件索引系统

B*树

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


B*树定义了非叶子节点关键字个数至少为（2/3）*M，即块的最低使用率为2/3（代替B+树的1/2）
B+树的分裂：当一个节点满时，分配一个新的节点，并将原节点中的1/2的数据复制到新节点，最后在父结点中增加新节点的指针；B+树的分裂只影响原节点和父结点，而不会影响兄弟节点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父结点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）
如果兄弟也满了，则在原节点和兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父结点增加新节点的指针。
所以B*树分配新节点的概率比B+树要地，空间使用率更高。

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