展开

关键词

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+要低,空间使用率更高; 小结 B:二叉,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B-:多路搜索,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点

47670

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*提高了结点的利用率。

12430
  • 广告
    关闭

    腾讯云+社区系列公开课上线啦!

    Vite学习指南,基于腾讯云Webify部署项目。

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

    多叉 & B & B+ & B*

    (2). 2-3-4: 和2-3的区别就是,它还允许节点有三个元素且有四个子节点。 4. BB是balance,平衡的意思,所以,B首先是一棵平衡,而平衡首先得是一棵排序数。 所以B就是一棵平衡的、排序的多叉B的相关说明如下: B的阶:节点的最多子节点个数叫做阶。 比如2-3的阶就是3,2-3-4的阶就是4; B的搜索:从根节点开始,对节点内的元素进行二分查找,如果找到就结束,否则进入查找元素所属范围的子节点再进行二分查找,直到找到或者到达叶子节点; B的所有节点都会存放数据 B+B+B的变体,和B的区别就是,B+所有数据都存放在叶子节点。 B+一般用于文件系统; 6. B*B*又是B+的变体,就是在B+的基础上,在非根非叶子节点之间增加了指向兄弟节点的指针。

    29320

    BB-)、B+ 简述

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

    20840

    BB+B*——简单介绍

    BB+B*——简单介绍 强烈推介IDEA2020.2破解激活,IntelliJ 翻译成 B-,容易让人产生误解,会以为 B-是一种。 实际上,B-Tree就是B。 三、BB+B* ---- 【1】B介绍:前面介绍的2-3、2-3-4就是 B,在 MySql 中经常听说某种索引是基于 BB+的,如下图: ? 【2】B+介绍:B+ B的变体,也是一种多路搜索,如下图: ? 【3】B* 介绍:B* B+的变体,在B+的非根和非叶子节点增加了指向兄弟的指针,如下图: ?

    18520

    B B+ B* 谈到R

    说明:本文从B开始谈起,然后论述B+B*,最后谈到R 。其中BB+B*部分由weedge完成,R 部分由Frankie完成,全文最终由July统稿修订完成。 3.B- 3.1什么是B- 具体讲解之前,有一点,再次强调下:B-,即为B。 因为B的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-是一种,而B又是一种一种。 (t=2的意思是,mmin=2,m可以>=2)时的B是最简单的(有很多人会因此误认为B就是二叉查找,但二叉查找就是二叉查找B就是BB是一棵含有m(m>=2)个关键字的平衡多路查找) 7.总结 通过以上介绍,大致将BB+B*总结如下: B:有序数组+平衡多叉B+:有序数组链表+平衡多叉B*:一棵丰满的B+

    92310

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

    什么是B B,即B-treeB是Balanced首字母,平衡的意思 因为B的原英文名称为B-tree 很多人喜欢把B-tree译作B-,然后读作B 其实,这么是不对的 容易让人会以为B B-是两种树 特此声明:B-就是指的B 好了,本章结束 ? 什么是B+ B+B-的变体,也是一种多路搜索 4.1 B+的特点 其定义基本和特性与B-同,除了: 1.非叶子结点的子树指针与关键字个数相同 2.非叶子结点的子树指针P[i],指向关键字值属于 什么是B*B+的变体,在B+的非根和非叶子结点再增加指向兄弟的指针 B*定义了非叶子结点元素个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+的1/2) B*的查询、插入和删除操作和 ,且只出现一次,非叶子结点可以命中; B+:在B-基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+总是到叶子结点才命中; B*:在B+基础上,为非叶子结点也增加链表指针

    2.1K21

    红黑BB+

    B/B+ B 即:多路平衡查找B 的巧妙之处在于: 将一个节点的大小设置为一页的大小; 一个节点可以存放多个关键字(多叉); 自平衡; 这 3 点结合起来就可以做到: 一个节点大小为一页, B/B+的索引数量 B 的节点中存储:指针、关键字(主键)、数据 B+ 的非叶子节点:指针、关键字 B+的叶子节点:指针(链表)、关键字、数据 注意,这里不是绝对的,比如有的 B+ 中叶子节点存储的不是数据 而且上述是假设数据为 1KB,如果数据没那么大,高度为 3 的 B 能存储更多的数据,但是如果用在大型数据库索引上还是不够。 B+ B+ 如上图,B+的核心在于非叶子节点不存储数据。 B/B+的优点 更适合磁盘存储,减少了的层级,进而减少 I/O 次数; B B+ 对比 都是 B ,但是 B+更适合范围查询,比如 Mysql,且查询次数很稳定,为 logn。 而 B 更适合键值对型的聚合数据库,比如 MongoDB,查询次数最优为 O(1); 红黑更适合内存存储,B 更适合键值对存储,B+ 适合范围查询;

    13000

    BB+

    BB+都是用于外查找的数据结构,都是平衡多路查找。 两者的区别 在B+中,具有n个关键字的结点含有n棵子树,即每个关键字对应一颗子树;而在B中,具有n个关键字的结点含有(n+1)棵子树。 在B+中,除根节点外,每个结点中的关键字个数n的取值范围是[m/2]~m,根节点n的取值范围是2~m;而在B中,除根节点外,其他所有非叶结点的关键字个数n的取值范围是[m/2]-1~m-1,根节点n B+中的所有叶结点包含了全部关键字,即其他非叶结点中的关键字包含在叶结点中;而在B中,关键字是不重复的。 B+中的所有非叶结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不包含该关键字对应记录的存储地址;而在B中,每个关键字对应一个记录的存储地址。 通常在B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶结点,所有叶结点链接成一个不定长的线性链表,所以B+可以进行随机查找和顺序查找;而B只能进行随机查找。

    15441

    红黑BB+

    B/B+ B 即:多路平衡查找B 的巧妙之处在于: 将一个节点的大小设置为一页的大小; 一个节点可以存放多个关键字(多叉); 自平衡; 这 3 点结合起来就可以做到: 一个节点大小为一页, B/B+的索引数量 B 的节点中存储:指针、关键字(主键)、数据 B+ 的非叶子节点:指针、关键字 B+的叶子节点:指针(链表)、关键字、数据 注意,这里不是绝对的,比如有的 B+ 中叶子节点存储的不是数据 而且上述是假设数据为 1KB,如果数据没那么大,高度为 3 的 B 能存储更多的数据,但是如果用在大型数据库索引上还是不够。 B+ B+ 如上图,B+的核心在于非叶子节点不存储数据。 B/B+的优点 更适合磁盘存储,减少了的层级,进而减少 I/O 次数; B B+ 对比 都是 B ,但是 B+更适合范围查询,比如 Mysql,且查询次数很稳定,为 logn。 而 B 更适合键值对型的聚合数据库,比如 MongoDB,查询次数最优为 O(1); 红黑更适合内存存储,B 更适合键值对存储,B+ 适合范围查询;

    8640

    B

    B是为磁盘或其他存取的辅助存储设备而设计的一种平衡搜索B类似于红黑,但是在降低磁盘I/O方面表现很好。   B和红黑不同之处在于B的节点可以有很多孩子,从数个到数千个。 B的严格高度可能比一棵红黑的高度要小很多,因此可以使用B数在O(lgn)内完成一些动态集合的操作。   如果B的一个内部节点x包含x.n个关键字,那么节点x就要x.n+1个孩子。 对存储在磁盘上的一棵B,通常分支因子在50-2000不等,具体取决于一个关键字相对于一页的大小,大的分支因子可以降低的高度以及查找任何一个关键字所需的磁盘的存取次数。 B的定义 一棵BT是具有以下性质的有根(树根表示为T.root)    1.每个节点x具有下面的性质:     (1)x.n,当前存储在节点x中的关键字的个数;     (2)x.n个关键字本身 B的高度 B树上大部分操作所需的磁盘存取次数与B的高度成正比。 查找元素的例子 ?

    1.1K110

    BB+(Balance Tree)

    B的产生是为了: 解决因为大量数据时,红黑/二叉查找的深度太深,如数据库的索引数据存放在磁盘上,而如果使用红黑的话,深度太深,每一个查找一个节点都需要寻道+磁盘读写

    51330

    BB+的区别

    B+的叶节点是链接的,所以对中的所有对象进行全扫描只需要一次线性遍历所有叶节点。另一方面,B需要遍历中的每一层。这种全遍历可能会涉及比B+叶的线性遍历更多的高速缓存未命中。 B+的叶子节点由一条链相连,而B的叶子节点各自独立。 使用B+的好处 由于B+的内部节点只存放键,不存放值,因此,一次读取,可以在内存页中获取更多的键,有利于更快地缩小查找范围。 数据库为什么使用B+而不是B B相比二叉虽好,但还是存在以下问题:        1.每个节点中既要存索引信息,又要存其对应的数据,如果数据很大,那么当的体量很大时,每次读到内存中的的信息就会不太够 2.B遍历整个的过程和二叉本质上是一样的,B相对二叉虽然提高了磁盘IO性能,但并没有解决遍历元素效率低下的问题。         针对以上两个问题,B+诞生了,B+相比B,本质上是一样的,区别就在与B+的所有根节点都不带有任何数据信息,只有索引信息,所有数据信息全部存储在叶子节点里,这样,整个的每个节点所占的内存空间就变小了

    3.7K40

    数据结构 —— BB+

    B详解以及B+B的不同 数据结构 —— BB+ 1. 背景 ​ 最近在学习数据库相关的知识,了解到数据库很多是采用B-/+作为索引,例如Mysql的InnoDB引擎使用的B+、MongoDB默认采用B作为索引。 B,概括来说是一个一般化的二叉查找(binary search tree)一个节点可以拥有2个以上的子节点。与自平衡二叉查找不同,B适用于读写相对大的数据块的存储系统,例如磁盘。 特征:在 m 阶 B 中叶子节点的元素符合(m/2)-1<= K <=m-1 3. B数的相关操作 3.1 查找 B的搜索和二叉搜索类似。从根节点开始,从上到下递归的遍历。 (而 B 的非终节点也包含需要查找的有效信息); 参考 B B + 详解 B- 维基百科,自由的百科全书

    12740

    图解 MySQL 索引:B-B+

    二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引,对于频繁访问的表,innodb会透明建立自适应hash索引,即在B索引基础上建立hash B-Tree索引(MySQL使用B+Tree) B-Tree能加快数据的访问速度,因为存储引擎不再需要进行全表扫描来获取数据,数据分布在各个节点之中。 ? 相比B-Tree来说,进行范围查找时只需要查找两个节点,进行遍历即可。而B-Tree需要获取所有节点,相比之下B+Tree效率更高。 ? 三、问题 问:为什么索引结构默认使用B-Tree,而不是hash,二叉,红黑? hash:虽然可以快速定位,但是没有顺序,IO复杂度高。 二叉的高度不均匀,不能自平衡,查找效率跟数据有关(的高度),并且IO代价高。 红黑的高度随着数据量增加而增加,IO代价高。 问:为什么官方建议使用自增长主键作为索引。

    62520

    BB+到底是什么?

    B B又称多路平衡查找B中所有结点的孩子个数的最大值称为B的阶,通常用m表示。一般从查找效率考虑,通常要求m>=3. B的高度 B的高度不包括最后的不带任何信息的叶结点所在的那一层。 若n>=1,则对任意一棵包含n个关键字、高度为h、阶数为m的B: 因为B中每个结点最多有m棵子树,m-1个关键字,所以在一棵高度为h的m阶B中关键字的个数应满足n<=(m-1)(1+m+m^2 + B的查找包含两个基本操作: 在B中找结点 在结点内找关键字。 由于B常存储在磁盘上,因此前一个查找操作是在磁盘上进行的,而后一个查找操作是在内存中继续的。 B+ B+是对应数据库所需而出现的一种B的变形

    32640

    B+,索引

    引言 时隔一年,我又想起当初看数据库时,看到的B+,就是数据库的索引使用的数据结构。再整理一下,看看自己没有忘记很多吧。 概述 B+之前,先来看一下二叉查找(1,2,3,4,5,6,7) ? 但想想数据库查找数据的场景: select * from user where id > 10, 显然,对于这种查找区间来说,二叉查找并不高效。那么B+是如何解决这个问题的呢? 没错,这就是B+。 这个结构是怎么想出来的我不知道啊,但是我今天突然发现,他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发?亦或是跳表受到了B+的启发?咱也不知道。 引申 很好,B+整明白了,新的问题出现了。如果数据库使用这种数据结构存储,全部放到内存中肯定是不现实的,势必要将其存储到硬盘中,待查找时再到文件中读取。 B+是不是分叉越多越好 那肯定不是越多越好啊,要是一层就把所有数据都存储了,要他还有什么用,根本没有起到快速定位的作用。 但我想说的并不是这。

    25020

    树结构系列(三):BB+

    B B-Tree 其实就是 B ,很多人都会说成 B,其实是错的,要注意。 B 不要和二叉混淆,B 不是二叉,而是一种自平衡数据结构。 B+ B+ 是应文件系统所需而产生的 B 的变形B+ 的特征: 有 m 个子树的中间节点包含有 m 个元素(B 中是 k-1 个元素),每个元素不保存数据,只用来索引。 与 B 相比,B+ 有着如下的好处: B+ 的磁盘读写代价更低 B+ 的内部结点并没有指向关键字具体信息的指针,所以其内部结点相对 B 更小。 参考资料 B _百度百科 B + _百度百科 关于B/B+的对比。 B B + 详解 - Assassin の - 博客园 漫画 B B - _sinat_36118365 的博客 - CSDN 博客 漫画:什么是 B +

    38110

    B-+

    ---- B- B是二叉平衡的升级版,可以多路自平衡,而且属于外查找,即数据是放在外存之中的,这时候就要考虑 IO 操作优化了,相比二叉查找他们的时间复杂度都是O(log N),优势在于B的深度相比小很多 ,在数据很大的情况下从磁盘读取次数小了,加快了查找速度,所以B及其同类经常用在文件系统或数据库中,下面先来说一下B B的节点中含有孩子的最大值称为该的阶,通常用m表示,(m >= 2) 若根节点不是叶子结点 B+ B+又是B-的升级版,一颗m阶的B+,在B-的前提下又有下面的区别: 根节点的最大元素是整棵的最大元素 中间节点有多少个孩子,就有多少个元素(元素不保存数据了,只用于索引,所有数据都存在叶子节点中 二者区别 B+中只有叶子节点才有指向数据记录的存储地址,B-的节点则都有 B+因为中间元素没有数据记录的存储地址,同样的磁盘页可以存储更多节点元素(即同样元素,B+更矮,IO次数更少) B+单查询必须查到叶子节点 ,因为叶子才有数据记录的存储地址,而B-则查到就返回,不稳定 B+范围查询只需在叶子节点遍历链表即可,而B-需要中序遍历才能确定范围

    18720

    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

    7010

    相关产品

    • Serverless HTTP 服务

      Serverless HTTP 服务

      Serverless HTTP 基于腾讯云 API 网关平台,为互联网业务提供 0 配置、高可用、弹性扩展的对外 RESTful API 能力,支持 swagger/ openAPI 等协议。便于客户快速上线业务逻辑,通过规范的 API 支持内外系统的集成和连接。

    相关资讯

    热门标签

    扫码关注腾讯云开发者

    领取腾讯云代金券