展开

关键词

B-

概念 B-可以理解为平衡二叉的拓展, 它也是平衡的, 但是每个节点可以有多个关键字. ‘B’ 后面的 ‘-‘ 不是减号. 下面是一棵 B-的例子: image.png B-的存储结构 image.png 其中, n 为当前结点关键字个数, \text{p}_i 是指向孩子结点的指针. 性质 对于 m 阶 B-: image.png 注意: 严格来讲, B-的阶数不是指含有最多关键字结点的度数. 有争议的问题: B-的高度是否应该包含失败结点? 此处认为是不包括的. 插入(以 5 阶 B-为例) image.png 删除(以 5 阶 B-为例) 直接删除, 位于终端, 且删除后该结点的关键字数仍然大于等于 \lceil m/2 \rceil image.png

7610

B-,B+,B*

avl和m为300的B-? avl的高度:log2n = 24层 最差的情况一个节点只存储一个索引? 最差需要24次磁盘IO B-高度:log(300)n = 3 层 最多花费3次磁盘IO B+ B+B-的一种变形 非叶子结点只存储索引,不存储数据 B+的叶子结点包含全部的关键字信息 ,而B-的数据分散在各个结点当中。 B+存放的索引项相对于B-能够存储的更多。 B* B*是B+的变体,在B+的非根和叶子结点在增加指向兄弟结点的指针 B*提高了结点的利用率。

12930
  • 广告
    关闭

    腾讯云校园大使火热招募中!

    开学季邀新,赢腾讯内推实习机会

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    BB-)、B+ 简述

    要是那个人说bb-不一样 那你可以认为他是zz了hh,b就是b- 说起来b的发明主要是为了减少磁盘io操作 将的结构设计成矮胖型而不是瘦高型,因为数据库索引是存储在磁盘上的,当数据量比较大时 ,我们不能把所有索引加载到内存中,只能逐一加载每一个磁盘页,这里的磁盘页对应索引的节点 一个m阶的B具有如下几个特征: 1.根结点至少有两个子女。 一个m阶的B+具有如下几个特征: 1.有k个子树的中间节点包含有k个元素(B中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。 下图是一个b+b-改造加链表) ?

    21840

    数据结构 B-

    B-定义 B-,有时又写为B_(其中的“-”或者“-_只是连字符,并不读作“B减”),一颗 m 阶的 B-,或者本身是空,否则必须满足以下特性: 中每个结点至多有 m 棵子树; 若根结点不是叶子结点 B-插入关键字 B-也是从空开始,通过不断地插入新的数据元素构建的。B-在插入新的数据元素时并不是每次都向中插入新的结点。 为: image.png 插入关键字 7:从根结点开始依次做判断,最终判定在 c 结点中添加,添加后发现 c 结点需要分裂,分裂规则同上面的方式一样,结果导致关键字 7 存储到其双亲结点 b 中;后 例如在上图中 B-的情况下删除关键字 12 时,结点 c 中只有一个关键字,然后做删除关键字 37 的操作。 在删除结点 b 的同时,由于 b 中仅剩指向结点 c 的指针,所以连同其双亲结点中的 45 一同合并到其兄弟结点 e 中,最终的B-为: image.png 上图删除37后的B-

    21710

    B B- B+ B*

    实际使用的B都是在原B的基础上加上平衡算法,即“平衡二叉”;如何保持B结点分布均匀的平衡算法是平衡二叉的关键;平衡算法是一种在B中插入和删除结点的策略; B- 是一种多路搜索(并不是二叉的 B-的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点; B-的特性:        M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并; B+        B+B-的变体,也是一种多路搜索:        1.其定义基本与B-同,除了:        2.非叶子结点的子树指针与关键字个数相同 B+的搜索与B-也基本相同,区别是B+只有达到叶子结点才命中(B-可以在 非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;     B+的特性:        1.所有关键字都出现在叶子结点的链表中 B+要低,空间使用率更高; 小结 B:二叉,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B-:多路搜索,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点

    48170

    图解:什么是B-、B+、B*

    B-是两种树 特此声明:B-就是指的B 好了,本章结束 ? 什么是B- 首先B-是一种多路平衡搜索 简单来说,就是每个节点不止存储一个数据值 每个节点也不止有两个子节点 比起平衡二叉,它能很大程度减低的高度 提高的检索效率 3.1 B-的特点 下面来具体介绍一下一个 举个栗子,这就是一个B- ? )是小于003的,005是大于003且小于006的,007是大于006的 3、这是一个3阶B-,每个节点最多有两个元素,每个节点最多有三个子孩子 好了,这样是不是就清晰多了 3.2 B-查询操作 查询数值 什么是B+ B+B-的变体,也是一种多路搜索 4.1 B+的特点 其定义基本和特性与B-同,除了: 1.非叶子结点的子树指针与关键字个数相同 2.非叶子结点的子树指针P[i],指向关键字值属于

    2.3K21

    漫画:什么是B-

    ———————————— ———————————— 二叉查找的结构: 第1次磁盘IO: 第2次磁盘IO: 第3次磁盘IO: 第4次磁盘IO : 下面来具体介绍一下B-(Balance Tree),一个m阶的B具有如下几个特征: 1.根结点至少有两个子女。 删除11后,节点12只有一个孩子,不符合B规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。

    8430

    图解 MySQL 索引:B-、B+

    二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引,对于频繁访问的表,innodb会透明建立自适应hash索引,即在B索引基础上建立hash 三、问题 问:为什么索引结构默认使用B-Tree,而不是hash,二叉,红黑? hash:虽然可以快速定位,但是没有顺序,IO复杂度高。 二叉的高度不均匀,不能自平衡,查找效率跟数据有关(的高度),并且IO代价高。 红黑的高度随着数据量增加而增加,IO代价高。 问:为什么官方建议使用自增长主键作为索引。

    67220

    B-查找算法的简单实现

    B-树节点类定义 struct node { int n; //关键字个数 int key[maxsize]; //关键字数组 node *ptr[maxsize+1]; //指向孩子节点的指针的数组 }; //在以root为根节点的B中查找值为x的节点 node *dfs(node *root, int x) { if (!

    10630

    数据库索引(结合B-和B+

    用B-Tree作为索引结构效率是非常高的 1)B- B-Tree是一种多路搜索(并不是二叉的):        1.定义任意非叶子结点最多只有M个儿子;且M>2;        2.根结点的儿子数为 B+ 中,数据对象的插入和删除仅在叶节点上进行。 这两种处理索引的数据结构的不同之处:   1、B-中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。 2、因为B-键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+相比来说是一种较好的折中。    3、B-的查询效率与键在中的位置有关,最大时间复杂度与B+相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+的时候复杂度对某建成的是固定的。 为什么选用B+、B-   索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。

    546130

    校门外的C语言

    《肖申克的救赎》 校门外的 题目描述 某校大门外长度为L的马路上有一排,每两棵相邻的之间的间隔都是1米。 现在要把这些区域中的(包括区域端点处的两棵)移走。你的任务是计算将这些都移走后,马路上还有多少棵。 输入 500 3 150 300 100 200 470 471 输出 298 ‍‍ 源代码: #include<stdio.h> int main(){ int l,j,m,a[10000],c= for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); for(j=x;j<=y;j++) a[j]=0; } for(i=0;i<=l;i++) if(a[i]==1) c+ +; printf("%d\n",c); } 运行结果:‍‍‍‍ ?

    65640

    这1次彻底搞懂B+B-

    二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引,对于频繁访问的表,innodb会透明建立自适应hash索引,即在B索引基础上建立hash 案例:假设有一张学生表,id为主键 在MyISAM引擎中的实现(二级索引也是这样实现的) 在InnoDB中的实现 三、问题 问:为什么索引结构默认使用B-Tree,而不是hash,二叉,红黑 二叉的高度不均匀,不能自平衡,查找效率跟数据有关(的高度),并且IO代价高。 红黑的高度随着数据量增加而增加,IO代价高。 问:为什么官方建议使用自增长主键作为索引。

    40000

    数据结构——AVL(C语言)

    AVL(Adelson-Velskii 和 Landis)是带有平衡条件的二叉查找。在计算机科学中,AVL是最先发明的自平衡二叉查找。 在AVL中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(lngn)。 增加和删除可能需要通过一次或多次旋转来重新平衡这个。 节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或-1的结点被认为是平衡的。 AVL的基本操作一般涉及运作同在不平衡的二叉查找所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。 以下图标表示的四种情况,就是AVL旋转中常见的四种。 ("中序遍历二叉: \n"); InorderTravel(T); printf("后序遍历二叉: \n"); PostorderTravel(T); printf

    38321

    数据结构——AVL(C语言)

    AVL(Adelson-Velskii 和 Landis)是带有平衡条件的二叉查找。在计算机科学中,AVL是最先发明的自平衡二叉查找。 在AVL中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(lngn)。 增加和删除可能需要通过一次或多次旋转来重新平衡这个。 节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或-1的结点被认为是平衡的。 AVL的基本操作一般涉及运作同在不平衡的二叉查找所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。 以下图标表示的四种情况,就是AVL旋转中常见的四种。 ("中序遍历二叉: \n"); InorderTravel(T); printf("后序遍历二叉: \n"); PostorderTravel(T); printf

    43721

    原 BC语言代码实现

    void btree_delete(BTree tree, int key); //删除中的关键字 #endif 程序btree.c: #include "btree.h" #include * 当为有且只有一个关键字,且已满时,需要建立新的结点作为的根结点, * 而当原的根结点作为新结点的子结点,进行分裂操作 * 否则,直接进行非满结点插入操作 */ void btree_insert C代码。 btree_max(tree); btree_min(tree); free(tree); return 0; } [root@localhost ~]# gcc -o btree btree.c 输出关键字的做大最小值: the max is 100 the min is 1 输出5,33的位置 the 5 key's location is 1 in the node 0x9ff50c0

    1.8K111

    c语言数据结构(数组

    /************************************************************************/ /* 课程要求:完成的基本操作 的创建和销毁 2. 中节点的搜索 3. 中节点的添加与删除 4. 中节点的遍历 BOOL CreateTree(Tree **pTree, Node *pRoot);//Tree **pTree ,Node *pRoot 根节点 //创建树 void DestroyTree(Tree *pTree); //销毁 Node *SearchNode if((*pTree)->root == NULL)//分配内存失败 { free(*pTree);//释放容器内存 return FALSE; } for(int i = 0; i

    7920

    C语言实现跳动的圣诞,自学C语言圣诞表白!

    “要成为绝世高手,并非一朝一夕,除非是天生武学奇才,但是这种人…万中无一” ——包租婆 这道理放在C语言学习上也一并受用。 在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从C语言小白进阶到高手,需要经历的是日积月累的学习。 那么如何学习呢?当然是每天都练习一道C语言题目!! 经典:如何用C语言画一个“圣诞”,我使用了左右镜像的Sierpinski triangle,每层减去上方一小块,再用符号点缀。 可生成不同层数的「圣诞」 源代码演示: #include <math.h> #include <stdio.h> #include <stdlib.h>   #define PI 3.14159265359

    4.4K3419

    c语言数据结构术语解析

    :节点的有限集合(当中的节点数量是有限的). 举个例子: 以这个树结构为例子。 孩子:a的孩子是bcd。b的孩子是ef。d的孩子是gh.c没有孩子. 叶子(终端节点):c是终端节点。efgh也是终端节点. 根(非终端节点):bd 有序: 这个就是有序.(顺序的abcdefg…) 无序.:没有规律的。 深度: 举个例子,这个数的深度是3. 二叉: 定义:所有结点的度都小于等于2 有序. 举个例子: 这个不是二叉 这个是二叉 二叉的遍历:(顺序是过程哦) 满二叉:每个节点都有只能==两个节点。 完全二叉:(相对于满二叉来说的) 完全二叉的特点: 二叉树前序遍历:根 左 右 二叉中序遍历:左 根 右 二叉后序遍历:左右根 二叉的存储结构: 解析:1是根节点

    7560

    B-和B+的应用:数据搜索和数据库索引

    一、B- 1 .B-定义:有序数组+平衡多叉 B-是一种平衡的多路查找,它在文件系统中很有用。 删除后的如图4.2(c)所示。 图4.2(c) 如果因此使双亲结点中的关键字数目小于ceil(m/2)-1,则依次类推。 [例如],在 图4.2(c)的B-中删去关键字37之后,双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,删除后的B-如图 4.2(d)所示。 性能’还有很多种B-的变型,力图对B-进行改进 二、B+ ---- B+是应文件系统所需而产生的一种B-的变形。 1、节点存储关键字多,IO次数少:B-和B+最重要的一个区别就是B+只有叶节点存放数据,其余节点用来索引,而B-是每个索引节点都会有Data域。

    10620

    C语言二叉的实现

    因此根也叫做根节点 子节点/孩纸:就是一个节点的下面离它最近的的节点,比如A的子节点是BC而不是BCDEFG,E的子节点是G,G没有子节点 父节点/父亲:这里就是倒置了一下,比如G的父节点是E,EF的父节点是C, struct node *create_binary_tree(){ struct node *root; struct node *a=new node,*b=new node,*c=new node,*d=new node,*e=new node,*f=new node,*g=new node; a->data='A'; b->data='B'; c->data='C'; d-> data='D'; e->data='E'; f->data='F'; g->data='G'; a->lchild=b; a->rchild=c; b->lchild=d; b->rchild =NULL; c->lchild=e; c->rchild=f; d->lchild=NULL; d->rchild=NULL; e->lchild=g; e->rchild=NULL;

    81320

    扫码关注腾讯云开发者

    领取腾讯云代金券