关于B树的一些简单的总结

概念

  先说一下,B-树,B树,是一个东西。B树和普通的平衡二叉树不同的是B树属于多叉树又名平衡多路查找树(查找的路径不只有2条),数据库索引技术里大量使用了B树。

规则

  (1)树中的每个节点最多拥有m个子节点且m>=2,空树除外(m阶代表一个树的节点最多有多少条查找路径,m阶=m路,当m=2则是平衡二叉树,当m=3时叫3阶B树)
  (2)除了根节点以外,每个节点的关键字数量大于等于 ceil(m/2)-1个 (ceil向上取整的函数),小于等于m-1个,非根节点关键字必须大于等于2。(关键字在节点中)
  (3)所有叶子节点均在同一层,叶子节点除了包含了关键字和关键字记录的指针外也有只想其他子节点的指针,只不过其地址都为null.
  (4)如果一个非叶子节点有N个子节点,则该结点的关键字个数等于N-1。(有3个子节点说明有3条路径,可以理解成2个关键字把一条数轴分成了3段,这每一段代表一条路径)。
  (5)所有节点关键字是按递增次序排列,并遵循左小右大原则。

例子

此处输入图片的描述

查找流程

如上图我要从上图中找到E字母
(1)获取根节点的关键字进行比较,当前根节点关键字为M,E要小于M(26个字母顺序),所以往找到指向左边的子节点(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点);

(2)拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点;

(3)拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null);

插入规则

(1)当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于ceil(5/2)-1小于等于5-1(关键字数小于cei(5/2) -1就要进行节点合并,大于5-1就要进行节点拆分,非根节点关键字数>=2);
(2)满足节点本身比左边节点大,比右边节点小的排序规则;

删除规则

(1)当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于cei(5/2)-1,小于等于5-1,非根节点关键字数大于2;

(2)满足节点本身比左边节点大,比右边节点小的排序规则;

(3)关键字数小于二时先从子节点取,取中间值往父节点放,子节点没有符合条件时就向向父节点取;

基本的东西就这些,如果还需要进一步的学习,可以看这篇文章
从B树、B+树、B*树谈到R 树

-------------本文结束感谢您的阅读-------------

本文标题:关于B树的一些简单的总结

文章作者:pspxiaochen

发布时间:2018年07月09日 - 09:07

原始链接:https://pspxiaochen.club/btree/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如果对你有帮助,方便的话麻烦给我的午饭加一颗卤蛋