首页
学习
活动
专区
工具
TVP
发布

理解 B+ 算法

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

2.4K00

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

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

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

98430

数据结构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

32010

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

1.4K20

B B+ B* 谈到R

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

2.1K10

【数据结构】BB+B*

下面关于B结点的定义这部分内容,不再放出算法导论上抽象的描述,而是用我本人的理解来阐述,让枯燥的定义变得更像白话一些。...牢记:算法千万条,画图第一条,画图不规范,求职两行泪。 3....算法流程为: 先在B中进行搜索,如果找到了k,则返回k所在的结点与k的下标位置,如果没有找到k,则返回k如果要插入的话,应该插入的结点位置,以及插入到_keys数组中的哪个下标位置。...Insert算法流程为:(1) 先判断B+是否为空,如果为空,则我们创建两个B+树节点,一个作根一个作叶子,把插入的第一个值插入到根和叶子当中。...因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

6710

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

82541

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

78140

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

64200

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

7.7K43

数据结构之BB+B*

在计算机科学中,BB+B*是常用的数据结构,它们在数据库索引、文件系统等领域发挥着重要作用。本文将深入探讨这三种树形结构的原理、特性以及应用场景。 1....B的基础概念 1.1 B的定义 B是一种平衡的搜索,通常被广泛应用于数据库和文件系统中。其定义包括以下关键特点: 多路性: 每个节点可以拥有多个子节点。...以上是B基础概念的一个简要介绍,接下来将深入探讨B+B*的特性和应用。 2. B+的特性和应用 2.1 B+的定义 B+是在B的基础上进行改进的一种数据结构。...B*的优化和应用 3.1 B*的定义 B*是在B+的基础上进行了一些优化的数据结构。其目标是减少B+树节点的分裂和合并操作,以提高性能和降低维护成本。...3.2 B*的特性 3.2.1 非叶子节点的关键字个数更多 相对于B+B*的非叶子节点可以包含更多的关键字。这一特性减少了的高度,提高了查找效率。

8210

数据结构与算法(十一)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删除举例 ?

45630

算法数据结构(一)-B

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

74140

算法导论第十八章 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的一种变形

67860

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.4K110

B +

# B + # 什么是 B + B + 是在二叉查找的基础上进行了改造:中的节点并不存储数据本身,而是只是作为索引。每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。...那如何降低的高度呢? 我们来看下,如果我们把索引构建成 m 叉,高度是不是比二叉要小呢?...# 为什么需要 B + 关系型数据库中常用 B+ 作为索引,这是为什么呢? 思考以下经典应用场景 根据某个值查找数据,比如 select * from user where id=1234 。...实际上,数据库索引所用到的数据结构跟跳表非常相似,叫作 B+ 。不过,它是通过二叉查找演化过来的,而非跳表。...B + 的应用场景 # 参考资料 数据结构与算法之美 数据结构 二叉 B+

33030
领券