利用小偷程序做网站,体育新闻最新消息文章,游戏发卡中心网站源码,子域名在线查询目录 前言一、B树#xff08;一#xff09;B树的概念#xff08;二#xff09;B树的性质#xff08;三#xff09;B树的高度#xff08;四#xff09;B树的查找#xff08;五#xff09;B树的插入#xff08;六#xff09;B树的删除 二、B树#xff08;一#xf… 目录 前言一、B树一B树的概念二B树的性质三B树的高度四B树的查找五B树的插入六B树的删除 二、B树一B树的概念二B树的性质三B树的查找 前言
B树和B树属于树形查找算法中的一种主要用于数据库系统、文件系统和磁盘存取等方面都是用于存储和索引大量的数据以提高检索效率。例如在磁盘存储中通过将数据分散到多个磁盘块中并使用树形结构来组织这些磁盘块从而提高了查找速度和查找效率。若设B树中所有结点的孩子结点个数的最大值为m则该B树是一棵m阶B树另外B树则是B树的变形。
一、B树
一B树的概念 二叉排序树也称为查找树注意与二分查找的判定树不同其中各结点值的大小关系是左子树根结点右子树且左、右子树也是一棵二叉排序树满足其条件。 前面给过二叉查找树的定义简单的来说B树是二叉查找树的推广即一棵m阶B树可看作一棵m叉查找树但两者有些方面不同如下 1、结点与关键字不同二叉查找树遵循二叉树的原则每个结点最多只有两个孩子结点且每个结点只包含一个关键字而B树的每个结点最多有m个结点即最多含有m-1个关键字。 2、平衡性二叉查找树不一定是一棵平衡二叉树查找过程中查找效率可能随着查找树的结构变化而B树是一棵多路平衡查找树通过限制结点的子树和关键字数量使B树的高度保持相对稳定从而提高查找效率。B树也正是在保持平衡的前提下能够更高效地处理大量数据从而非常适合应用在需要高效存储和访问大量数据的场景中。
二B树的性质
B树中与二叉查找树相同的性质二叉查找树各结点值的大小关系是左子树根结点右子树而B树中关键字的值的大小关系是子树1关键字1子树2关键字2子树3…一棵m阶B树中除了根结点外所有结点中关键字个数为⌈m/2⌉-1 ≤ n ≤ m-1。例如一棵5阶B树中除了根结点外所有结点中关键字的个数为2 ≤ n ≤ 4即关键字个数最少为2最多为4。 1、m阶B树中根结点至多有m棵子树若B树的根结点不是终端结点则该B树至少有两棵子树。 2、B树中结点内关键字均以升序或降序排列。 3、B树是一棵多路平衡查找树所有结点的平衡因子均为0。 4、m阶B树中若根结点没有关键字则B树无子树B树为空若有关键字由于子树个数等于关键字个数加1所以子树一定大于或等于两棵。 5、m阶B树中根结点最少含1个关键字而除根结点外每个非叶子结点至少有⌈m/2⌉棵子树且至少有⌈m/2⌉-1个关键字由于最少情况下根结点至少有一个关键字所以B树中所有结点包括的关键字个数至少为(n-1)(⌈m/2⌉-1)1个。 6、结点的孩子结点的个数等于该结点关键字的个数加1即具有n个关键字的m阶B树应有n1个叶结点。另外B树中所有的叶子结点均在一层上且不带任何信息这一点与二分查找判定树中查找失败的结点类似实际上这些叶子结点不存在代表查找失败的情况如下
三B树的高度
在求B树的高度时不计入叶子结点若设m阶B树中包括n(n≥1)个关键字其高度为h可得到B树的最小高度和最大高度范围区间logm(n1) ≤ h ≤ log⌈m/2⌉[(n1)/2]1。 ⌈ ⌉表示向上取整取比自己大的最小整数⌊ ⌋表示向下取整取比自己小的最大整数。 四B树的查找
B树的查找类似二叉查找首先在B树中查找结点然后在结点所包含的关键字K1,…,Kn中查找给定的关键字可通过顺序查找或二分查找进行查找若找到等于给定值的关键字则查找成功否则继续查找直至找到或指针为空时此时查找失败即查找到B树的叶子结点时失败。
五B树的插入
B树的插入操作不仅需要找到要插入的位置定位而且需判断插入后是否会导致不满足B树的定义由于B树中查找成功结点的关键字个数在 ⌈m/2⌉-1 ≤ n ≤ m-1间如下 1、第一种情况若插入后结点的关键字个数小于m则直接插入。 2、第二种情况若插入后结点的关键字个数大于m-1则需要进行调整从关键字中间位置⌈m/2⌉处将关键字分为两部分左半部分放在原结点中右半部分放在新的相邻右边结点中中间关键字元素⌈m/2⌉上移到原结点的父结点中另外若父结点的空间也不够则继续按照以上方式进行调整。
六B树的删除
B树的删除分两种情况如下 1、第一种情况 若要删除的关键字在终端结点中时 1若要删除的关键字所在结点的关键字个数大于或等于⌈m/2⌉时即关键字删除后结点仍满足相应的关键字个数则可直接删去。 2若要删除的关键字当前所在结点的关键字个数等于⌈m/2⌉-1时且左/右兄弟很充裕时即其关键字个数大于或等于⌈m/2⌉时需要进行调整向兄弟借用当前结点的前驱/后继、前驱的前驱/后继的后继代替从而满足B树的定义。 3若要删除的关键字当前所在结点的关键字个数等于⌈m/2⌉-1时且左/右兄弟不是很充裕时即其关键字个数只等于⌈m/2⌉-1时则将关键字删除后需要进行合并即与当前结点的兄弟结点以及双亲结点中的关键字合并。 2、第二种情况 若要删除的关键字不在终端结点中时用该关键字的直接前驱或直接后继代替转换成第一种情况再进行删除。
二、B树
一B树的概念
B树可以由分块查找推广所以也称为多级分块查找即m阶B树它是B树的变形与B树相同B树和B树都是平衡的多叉树都用在文件索引结构和数据库索引中但B树更加适用。B树的结点包含关键字对应记录的存储地址且B树中的叶子结点不带信息而B树的叶子结点带信息而其中其他的非叶子结点只是作索引作用。
二B树的性质
B树中n个关键字对应n棵子树即每个关键字对应一棵子树且子树的个数与结点的关键字个数相等每个分支结点至少有 ⌈m/2⌉棵子树。 B树与B树中结点的关键字个数对比如下表
名称B树B树根结点关键字个数1 ≤ n ≤ m-12 ≤ n ≤ m非根结点关键字个数⌈m/2⌉-1 ≤ n ≤ m-1⌈m/2⌉ ≤ n ≤ m
三B树的查找
B树支持随机查找而B树支持顺序查找和随机查找。 B树不支持顺序查找的原因是查找时可能查找到树中的任何一层所以其查找速度和稳定性没有B树高。
