江西网站建设企业,深圳网络安全公司排名,邯郸专业网站建设公司,网站设计模板免费下载一、B-树
1. B-树概念 B树是一种适合外查找的、平衡的多叉树。一棵m阶#xff08;m2#xff09;的B树#xff0c;是一棵平衡的M路平衡搜索树#xff0c;它可以是空树或满足以下性质#xff1a; #xff08;1#xff09;根节点至少有两个孩子。 #xff08;2#…一、B-树
1. B-树概念 B树是一种适合外查找的、平衡的多叉树。一棵m阶m2的B树是一棵平衡的M路平衡搜索树它可以是空树或满足以下性质 1根节点至少有两个孩子。 2每个分支节点都包含k-1个关键字和k个孩子其中ceil(m/2) k m。ceil表示向上取整 3每个叶子节点都包含k-1个关键字其中ceil(m/2) k m。 4所有叶子节点都在同一层。 5每个节点中的关键字从小到大排列节点中k-1个元素正好是k个孩子包含的元素的值域划分。 6每个节点的结构为n, A0, K1, A1, K2, A2……, Kn, An其中Ki(1in)为关键字且kiki 1(1in)。Ai(0in)为指向子树根节点的指针且Ai所指子树所有节点中的关键字均小于Ki1。n为节点中关键字的个数满足ceil(m/2)-1 n m-1。
2. B树的插入 采用m为3的一棵三叉B树的插入过程进行演示。根据B树性质可知m为3则每个节点最多有三个孩子(m-1个每个节点包含k-1个关键字2k3。注意插入只能插入到叶子节点。
1首先插入两个值2030 2插入第三个值25由于每个节点最多有2个关键字所以此时会进行分裂来维持B树平衡。 2.1 B树分裂规则 创建一个兄弟节点拷贝当前节点内右半区间的数据到兄弟节点中保留当前节点中左半区间的数据将该节点内的中位数提到父节点中若没有父节点则创建新的父节点。
3插入35 4 插入40 此时根节点的右侧孩子内数据超过2个则按照B树分裂规则分裂后如下 5插入33 6插入34 此时根节点的中间孩子内数据超过2两个进行分裂当提取33到父节点后根节点内数据也超过了2个则根节点也会进行分裂此时没有父节点则会创建新的父节点结构如下 三、B树
1. B树概念 B树是B树的变形它是在B树基础上进行优化的多路平衡搜索树B树的规则和B树基本类似但在其基础上进行了以下优化 1分支节点的子树指针与关键字个数相同 2分支节点的子树指针p[i]指向关键字值大小在[k[i], k[i1]]之间 3所有叶子节点增加一个链接指针链接在一起 4所有关键字及其映射数据都在叶子节点出现。 优点
1简化了B树孩子币关键字多一个的规则由多一个变成相等。
2所有值都在叶子节点中且叶子节点通过指针链接起来方便遍历。
2. B树的插入 B树的插入过程与B树基本类似区别在于 1第一次插入两层节点一层做分支一层做根 2B树在分裂时是将左半部分的数据保留右半部分的数据放入新建兄弟节点中并将新建节点中的最小值更新到父节点中。
三、B*树
1. B*树概念 B*树又是B树的变形做了以下改动 1在B树的非根和非叶子节点再增加指向兄弟节点的指针。 2节点在分裂时保证每个节点中值的数量至少为2/3 * M最多为M个也就是从1/2提高到了2/3提高空间利用率。 2. B*树的插入 B*树的插入与B树基本类似区别主要在于分裂规则B*树的分裂规则 如果它的下一个兄弟节点未满则将一部分数据移到兄弟节点中再在原节点中插入关键字最后修改父节点中兄弟节点的关键字因为兄弟节点的关键字范围发生了变化 如果兄弟节点也满了则在原节点与兄弟节点之间添加新节点并各复制1/3的数据到新节点中最后在父节点中添加新节点的指针。
四、B树系列的优缺点
1. 优点 1高效的查找操作B树系列的数据结构通过将数据分布在多层节点上使用索引快速导航到目标元素所在的叶子节点从而实现了高效的查找操作。其时间复杂度通常为O() 2适应大规模数据集B树系列的数据结构能够充分利用磁盘块的大小减少磁盘I/O操作的次数提高存储和访问效率。它们被广泛应用于数据库索引、文件系统等需要处理大规模数据集的场景。 3自平衡特性B树系列的数据结构通过节点的分裂和合并来自动保持树的平衡保证了各个节点的高度相对较小从而维持了高效的操作性能。 4支持范围查询由于B树系列的数据结构中数据是按照键的大小顺序进行排序因此可以很方便地进行范围查询操作。
2. 缺点 1空间利用率低消耗高。 2插入删除数据、分裂合并节点都必然存在数据挪动。 3虽然B树系列的高度更低但是在内存中和哈希、平衡搜索树的查找效率处于同一量级。
