学习
实践
活动
工具
TVP
写文章

理解 B+ 算法

定义 参考百度百科及wiki百科定义:B +是一个N叉排序,每个节点通常有多个孩子,一棵B+包含根节点、内部节点和叶子节点。 所有叶子节点均出现在同一层;因为在实现上B+元素插入采用的是自底向上分裂算法(删除元素类似同理),具体实现可参看下节图示。 另外说明的一点,B+中的B并不是代表二叉(Binary),而是代表平衡(Balance)。 对于m阶B+,m的值越大,固定高度的B+存放的值就越多。 B+插入删除操作图示 插入基本算法(参考wiki定义): 执行搜索以确定新记录应该进入哪个节点。 如果节点不满,添加记录。 否则,拆分节点。 删除算法类似,但更为复杂些,插入算法节点之间只与父节点产生关系,而删除算法则需要考虑兄弟节点和父子节点的关系;在此不赘述了。

1.8K00

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个关键字,非叶子结点存储指向关键字范围的子结点

52270
  • 广告
    关闭

    年末·限时回馈

    热卖云产品年终特惠,2核2G轻量应用服务器6.58元/月起,更多上云必备产品助力您轻松上云

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

    数据结构b-b+_A票领导B算法

    BB+都是多叉 二、B B也称B-,它是一颗多路平衡查找。 3个数据项与四个子节点的四节点: 由于B的关键字集合可以分布在整颗树上,如果查找的数据离根节点很近,此时查找会比B+快 三、B+ B+具有以下特点: B+只有叶子节点存放数据(稠密索引), 而非叶子节点只作为索引(稀疏索引),这使得非叶子节点所能保存的关键字大大增加 B+的叶子节点存放的数据是有序的 相对BB+具有以下优点: B+查询速度更稳定:B+所有关键字数据地址都存在叶子节点上 ,所以每次查找的次数都相同 B+的层级更少:相较于BB+每个非叶子节点存储的关键字数更多,的层级更少所以查询数据更快; B+天然具备排序功能:B+所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便 ,数据紧密性很高,缓存的命中率也会比BB+全节点遍历更快:B+遍历整棵只需要遍历所有的叶子节点即可,而不需要像B一样需要对每一层进行遍历,这有利于数据库做全表扫描 也由于这些优点,在mysql

    7510

    B-B+B*

    1.减少磁盘的IO 2.更快的搜索算法 操作系统中, 管理内存是按照页page 4K 管理的 管理磁盘是按照block 16K 现在有n = 1000w个索引需要从磁盘中进行读取和搜索? 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*提高了结点的利用率。

    15130

    多叉 & 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+的基础上,在非根非叶子节点之间增加了指向兄弟节点的指针。

    41120

    BB-)、B+ 简述

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

    26340

    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+的非根和非叶子节点增加了指向兄弟的指针,如下图: ?

    23620

    B B+ B* 谈到R

    这个下界可以用一个称作B的最小度数(算法导论中文版上译作度数,最小度数即内节点中节点最小孩子数目)m(m>=2)表示。 根据算法我们发现:17<29<35,因此我们找到指针p2。 根据p2指针,我们定位到磁盘块3,并将其中的信息导入内存。 此外,还有读者反馈,说上面的B的高度计算公式与算法导论一书上的不同,而后我特意翻看了算法导论第18章关于B的高度一节的内容,如下图所示: ? 我想,此时,你也就明白了,算法导论一书上的高度的定义是从“0”开始计数的,而我们中国人的习惯是的高度是从“1”开始计数的。特此说明。July、二零一二年九月二十七日。 很显然,该算法进行的是一个迭代操作。 插入       R的插入操作也同B的插入操作类似。当新的数据记录需要被添加入叶子结点时,若叶子结点溢出,那么我们需要对叶子结点进行分裂操作。

    97710

    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只能进行随机查找。

    20541

    图解:什么是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+基础上,为非叶子结点也增加链表指针

    3.2K21

    红黑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+ 适合范围查询;

    15340

    红黑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+ 适合范围查询;

    18600

    数据结构与算法(十一)B

    B 是一种平衡的多路搜索,多用于文件系统、数据库的实现 •1个节点可以存储超过2个元素、可以拥有超过2个子节点•拥有二叉搜索的一些特质(小的子节点在左面 大的子节点在右面)•平衡,每个节点的所有子树高度一致 •比较矮 m阶B性质 一个节点最多拥有m个子节点 •假设一个节点存储元素个数为x•根节点:1 <= x <= m-1 •非根节点:(ceiling(m/2) - 1) <= x <=m-1•如果有子节点 B和二叉搜索的关系 •B其实适合二叉搜索是等价的•只要把二叉搜索和部分子节点与父节点结合就生成了b•多代节点合并,可以获得一个超级节点•两代合并最多有4个子节点•m阶B最多需要log{2^ 以4阶B添加举例 ? 删除 叶子节点 直接删除 非叶子节点 •找到前驱或者后继,覆盖删除所需要的元素的值。•在把前驱或者后继删掉。 (如果根节点下溢 就和子节点合并) 以4阶B删除举例 ?

    31130

    B-查找算法的简单实现

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

    11330

    算法数据结构(一)-B

    介绍 B的目的为了硬盘快速读取数据(降低IO操作次)而设计的一种平衡的多路查找。目前大多数据库及文件索引,都是使用B或变形来存储实现。 目录 为什么B效率高 B存储 B缺点 为什么B效率高 在大规模数据存储操作中,由于无法一次性加载到内存里。所以避免不了发生内外存交换。所以次数越少,效率表现也越高。 来看下面这张图: ? B的高效的前提是数据已排序。 B树结构 ? 这是B存储在硬盘的逻辑结构图。 其中根节点中17,35在称为关键字(key) ,实际中往往附带更多复杂类型数据。 3:每个叶节点具有相同的深度,即的高度h,而且不包含关键字信息。 度和阶都是描述子节点的数量的。 算法导论译版中是用度来描述的。 数据结构与算法分析是用阶来描述,网上大多也是。 但如果范围查的话,b每次都要从根节点查询一遍。 所以在实际应用中,往往采用b的变形,b+来存储,只有叶子节点存储数据,每个叶子节点都指向下一个。

    55340

    算法导论第十八章 B

    前面还留了两章:贪心算法和摊还分析,打算后面再来补充。 因此,B被设计成尽量减少磁盘访问的次数。知道了这一点,就会明白B的变形B+了,B+通过将数据存储在叶子节点从而增大了一个节点所包含的信息,进而更加减少了磁盘的访问次数。 前面提到过,在大多数系统中,B算法的运行时间主要由它所执行的disk-read和disk-write操作的次数所决定的,其余时间在内存中计算,速度不在一个量级。 ,就不一一述说了,《算法导论》书已经讲得非常清楚了,而且图文并茂,照着认真看,绝对是没问题的。 即所有的结点的Keys的个数应该t-1 <= n <= 2t-1,除了根结点可以最少为1个Key }; #endif//_B_TREE_H_ 四、B的引申——B+B* B+是对B的一种变形

    30260

    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+的区别

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

    3.8K40

    BB+(Balance Tree)

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

    55130

    算法和数据结构: 十 平衡查找B

    B,概括来说是一个节点可以拥有多于2个子节点的二叉查找。与自平衡二叉查找不同,B-为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。 B+是对B的一种变形,它与B的差异在于: 有k个子结点的结点必然有k个关键码; 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。 下面是B B+的区别图: ? 分析 对BB+的分析和对前面讲解的2-3的分析类似, 对于一颗节点为N度为M的子树,查找和插入需要logM-1N ~ logM/2N次比较。 所以BB+比较适合与文件系统的数据结构。下面是一颗B,用来进行内容存储。 ? 另外B/B+也经常用做数据库的索引,这方面推荐您直接看张洋的MySQL索引背后的数据结构及算法原理 这篇文章,这篇文章对MySQL中的如何使用B+进行索引有比较详细的介绍,推荐阅读。

    24730

    扫码关注腾讯云开发者

    领取腾讯云代金券