目录

B树、B+树、B*树

B树(B-tree、B_tree)

概念

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),数据库索引工作里大量使用者B树和B+树的数据结构。

规则

  1. 排序方式,和bst一样,遵循左小右大原则
  2. 子节点数:子节点数记为n,有1<n<=M,且M>=2(M阶或者M路代表一个树节点最多有多少个查找路径,当M=2则是2叉树,M=3则是3叉树)
  3. 关键字树:非叶子节点的关键字数量记为n,有ceil(m/2)-1<=n<=M-1(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
  4. 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null

最后我们用一个图和一个实际的例子来理解B树(这里为了理解方便我就直接用实际字母的大小来排列C>B>A) https://gitee.com/lienhui68/picStore/raw/master/null/20200630161124.png

B树查询流程

同bst

B树插入节点流程

在线演示工具

定义一个5阶树(平衡5路查找树;),现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来; 遵循规则:

  1. 节点拆分规则:当前是要组成一个5路查找树,那么此时m=5,关键字数必须<=5-1(这里关键字数>4就要进行节点拆分);
  2. 排序规则:满足节点本身比左边节点大,比右边节点小的排序规则;

先插入 3、8、31、11 https://gitee.com/lienhui68/picStore/raw/master/null/20200630161508.png 当前节点已经满足5叉,当插入下一个节点时要进行节点的拆分,拆分规则是把节点中间的那个元素提取到父节点上,左右两边单独构成节点。如果父节点不满足5叉则依次类推,同时还要考虑子节点的分裂。

再插入23、29 https://gitee.com/lienhui68/picStore/raw/master/null/20200630161826.png

再插入50、28 https://gitee.com/lienhui68/picStore/raw/master/null/20200630161854.png

B树删除节点流程

遵循规则:

  1. 节点合并规则:当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于ceil(5/2)(这里关键字数<2就要进行节点合并);
  2. 满足节点本身比左边节点大,比右边节点小的排序规则;
  3. 关键字数小于二时先从子节点取中间值,子节点没有符合条件时就向向父节点取,依此类推。

删除节点N中的关键字28,N从父节点P中取29, P从另一个子节点取39。如下图: https://gitee.com/lienhui68/picStore/raw/master/null/20200630162214.png

B+树

概念

B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定;我们先看看两者的区别

规则

  1. B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加;
  2. B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样;
  3. B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针。
  4. 非叶子节点的子节点数=关键字数(根据各种资料 这里有两种算法的实现方式,另一种为非叶节点的关键字数=子节点数-1(来源维基百科),虽然他们数据排列结构不一样,但其原理还是一样的。Mysql的B+树是用第一种方式实现); https://gitee.com/lienhui68/picStore/raw/master/null/20200630163116.png https://gitee.com/lienhui68/picStore/raw/master/null/20200630163218.png

特点

  1. B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;
  2. B+树查询速度更稳定: B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;
  3. B+树天然具备排序功能: B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。
  4. B+树全节点遍历更快: B+树遍历整棵树只需要遍历所有的叶子节点即可,,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

B树相对于B+树的优点是,如果经常访问的数据离根节点很近,由于B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

B*树

规则

B*树是B+树的变种,相对于B+树他们的不同之处如下:

  1. 首先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),b*树的初始化个数为(cei(2/3*m))
  2. B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;

特点

在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高,而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少; https://gitee.com/lienhui68/picStore/raw/master/null/20200630163802.png

总结

  1. 相同的思想和策略 从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的,都是采用二分法和数据平衡策略来提升查找数据的速度;
  2. 不同的方式的磁盘空间利用 不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变,每一次演变都是为了让节点的空间更合理的运用起来,从而使树的层级减少达到快速查找数据的目的;

参考

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了