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

B+

三、B+ B+是B-的变体,也是一种多路搜索,其定义基本与B相同,除了: 非叶子结点的子树指针与关键字个数相同; 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1 四、BB+的对比 B和B+的区别在于,B+的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。 2、B+的优点 由于B+在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。 因此访问叶子几点上关联的数据也具有更好的缓存命中率; B+的叶子结点都是相链的,因此对整棵的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。 而B则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+好。 3、应用 BB+经常被用于数据库中,作为MySQL数据库索引。

26420

B+,索引

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

30220
  • 广告
    关闭

    热门业务场景教学

    个人网站、项目部署、开发环境、游戏服务器、图床、渲染训练等免费搭建教程,多款云服务器20元起。

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

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

    23241

    浅谈 B+

    目前常见的主要的三种存储引擎是:哈希、B+、LSM。LSM下次再说,hash讲过了。 没有什么B-,那是 B-tree,国内一直翻译成B-,其实就是B。 B我也不想说了,因为已经被升级过了,叫B+。 下图来自 小灰的算法之旅,懂得人自然就懂了: ---- 对比一下B: 这个是B。 ---- B+对于B的改进 1、所有数据都在叶子节点。算法更容易理解了。回头抽空手写一下B+,正好跳表也要重写了。 2、底层叶子节点使用链表串起来了。 这第二个改进不可谓不秀。 单这么看自然是不明所以的,但是凡事都要放在上下文中去看,B+的上下文对应的就是磁盘IO的索引呐,那如果我要范围查询呢?比如说我要上面里面 4-10 的所有数据,B 怎么作为?B+怎么作为?

    15120

    LSMB+比较

    这就是B+的原理,但是写起来就很糟糕,因为会产生大量的随机IO,磁盘寻道速度跟不上。 关于b B+最大的性能问题是会产生大量的随机io。随着新数据的插入,叶子节点会慢慢分裂。 例如,Oracle 的常用索引使用 B+ 。下面是一个B+的例子 根节点和分支节点很简单,记录每个叶子节点的最小值,用指针指向叶子节点。 关于lsm LSM 本质上是读写之间的平衡。与B+相比,它牺牲了部分读取性能来提高写入性能。 读取的时候,因为我们不知道数据在哪棵树上,所以必须遍历所有的,但是每棵中的数据都是有序的。 以上就是LSM最本质的原理,有了原理,再看具体的技术就很简单了: 关于lsm内存结构,可以是B+,还可以为跳跃表(skip-list)或是一个有序字符串表(SSTables)。

    14920

    红黑、BB+

    二叉的 I/O 次数分析 先说 I/O 次数: 其实相比于二叉,B B+, CPU 的运算次数并没有变化,甚至增多。 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+ 适合范围查询;

    22900

    红黑、BB+

    二叉的 I/O 次数分析 先说 I/O 次数: 其实相比于二叉,B B+, CPU 的运算次数并没有变化,甚至增多。 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+ 适合范围查询;

    20740

    BB+、B*——简单介绍

    BB+、B*——简单介绍 强烈推介IDEA2020.2破解激活,IntelliJ 如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉; 【2】2-3,2-3-4就是多叉,多叉通过重新组织节点,减少的高度,能对二叉进行优化。如下图就是一个2-3; ? 【3】文件系统及数据库系统的设计者利用磁盘预读(预先读取)原理,将一个节点的大小设置为页<page:数据读取的最小单位>的大小(通常为4k),这样每个节点只需要一次 IO就能载入内存;B(B+)广泛应用于文件存储系统及数据库文件系统中 三、BB+、B* ---- 【1】B介绍:前面介绍的2-3、2-3-4就是 B,在 MySql 中经常听说某种索引是基于 BB+的,如下图: ? 【2】B+介绍:B+ 是B的变体,也是一种多路搜索,如下图: ? 【3】B* 介绍:B* B+的变体,在B+的非根和非叶子节点增加了指向兄弟的指针,如下图: ?

    27720

    多叉 & B & B+ & B*

    二叉因为每个节点只能有两个子节点,所以数据一多构建出来的的高度会很高。所以就出现了多叉,顾名思义,每个节点可以有多个子节点,这样来降低的高度。 3. (2). 2-3-4: 和2-3的区别就是,它还允许节点有三个元素且有四个子节点。 4. B: B是balance,平衡的意思,所以,B首先是一棵平衡,而平衡首先得是一棵排序数。 B+B+是B的变体,和B的区别就是,B+所有数据都存放在叶子节点。 B+所有的数据都存放在叶子节点的链表中,且链表中的数据也是有序的; 非叶子节点中存放的是索引,而不是要操作的数据,每个非叶子节点都会存放叶子节点的索引,也叫稀疏索引; B+要进行搜素时,从根节点开始 B+一般用于文件系统; 6. B*: B*又是B+的变体,就是在B+的基础上,在非根非叶子节点之间增加了指向兄弟节点的指针。

    45320

    B B- B+ B*

    M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并; B+        B+是B-的变体,也是一种多路搜索:        1.其定义基本与B-同,除了:        2.非叶子结点的子树指针与关键字个数相同 B+的搜索与B-也基本相同,区别是B+只有达到叶子结点才命中(B-可以在 非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;     B+的特性:        1.所有关键字都出现在叶子结点的链表中 是B+的变体,在B+的非根和非叶子结点再增加指向兄弟的指针; ?    B*定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+的1/2);       B+的分裂:   当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点 ;       所有关键字在整颗中出现,且只出现一次,非叶子结点可以命中; B+:在B-基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+总是到叶子结点才命中

    54570

    理解 B+ 算法

    定义 参考百度百科及wiki百科定义:B +是一个N叉排序,每个节点通常有多个孩子,一棵B+包含根节点、内部节点和叶子节点。 B+ 主要价值在于存储用于在面向块的存储环境中高效检索的数据,通常用于数据库和操作系统的文件系统中。B+ 的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。 B+ 元素自底向上插入。 另外说明的一点,B+中的B并不是代表二叉(Binary),而是代表平衡(Balance)。 对于m阶B+,m的值越大,固定高度的B+存放的值就越多。 而B+内部结点只需要1个盘块。当需要把内部结点读入内存中的时候,B 就比B+多一次盘块查找时间(在磁盘中就是盘片旋转寻道的时间)。

    1.8K00

    从B B+ 、B* 谈到R

    说明:本文从B开始谈起,然后论述B+、B*,最后谈到R 。其中BB+及B*部分由weedge完成,R 部分由Frankie完成,全文最终由July统稿修订完成。 c点么? 为了进一步详细讨论删除的情况,再举另外一个实例: 这里是一棵不同的5序B,那咱们试着删除C ? 于是将删除元素C的右子结点中的D元素上移到C的位置,但是出现上移元素后,只有一个元素的结点的情况。 7.总结 通过以上介绍,大致将BB+,B*总结如下: B:有序数组+平衡多叉B+:有序数组链表+平衡多叉; B*:一棵丰满的B+。 Bucket Li:"mysql 底层存储是用B+实现的,知道为什么么。内存中B+是没有优势的,但是一到磁盘,B+的威力就出来了"。

    1K10

    BB+的区别

    B+的叶节点是链接的,所以对中的所有对象进行全扫描只需要一次线性遍历所有叶节点。另一方面,B需要遍历中的每一层。这种全遍历可能会涉及比B+叶的线性遍历更多的高速缓存未命中。 B+的叶子节点由一条链相连,而B的叶子节点各自独立。 使用B+的好处 由于B+的内部节点只存放键,不存放值,因此,一次读取,可以在内存页中获取更多的键,有利于更快地缩小查找范围。 针对以上两个问题,B+诞生了,B+相比B,本质上是一样的,区别就在与B+的所有根节点都不带有任何数据信息,只有索引信息,所有数据信息全部存储在叶子节点里,这样,整个的每个节点所占的内存空间就变小了 不仅如此,B+还有一个相应的优质特性,就是B+的查询效率是非常稳定的,因为所有信息都存储在了叶子节点里面,从根节点到所有叶子节点的路径是相同的。 那么,我们最后再总结一下B+的优点:        (1) B+的磁盘读写代价更低               B+的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B更小。

    3.8K40

    树结构系列(三):BB+

    B+ B+ 是应文件系统所需而产生的 B 的变形B+ 的特征: 有 m 个子树的中间节点包含有 m 个元素(B 中是 k-1 个元素),每个元素不保存数据,只用来索引。 与 B 相比,B+ 有着如下的好处: B+ 的磁盘读写代价更低 B+ 的内部结点并没有指向关键字具体信息的指针,所以其内部结点相对 B 更小。 B+ 便于范围查询(最重要的原因,范围查找是数据库的常态) B 在提高了 IO 性能的同时,并没有解决元素遍历效率低下的问题。为了解决这个问题,B+ 应用而生。 B+ 只需要去遍历叶子节点就可以实现整棵的遍历。在数据库中基于范围的查询是非常频繁的,因此 MySQL 的 Innodb 引擎就使用了 B+ 作为其索引的数据结构。 B+ 比起 B ,最大的差异是非叶子节点不再存储具体数据,以及叶子节点是链表结构。非叶子节点不再存储具体数据,这使得 B+ 更加扁平化,查找效率更高。

    55310

    MySQL 的B+索引.

    B+ 是为磁盘或其他直接存取辅助设备设计的一种平衡查找B+ 中的 B 不是代表二叉(binary),而是代表平衡(balance)。 在 B+ 中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接,叶子节点之间组成一个双向链表。 ? B+ 索引的本质就是 B+ 在数据库中的实现,但是 B+ 索引在数据库中有一个特点是高扇出性(数据库分区),因此在数据库中,B+ 的高度一般都在 2-4 层,这也就是说查找某一键值的行记录时最多只需要 数据库中的 B+ 索引可以分为 聚集索引和辅助索引。 B+ 索引并不能找到一个给定键值的具体行。B+ 索引能找到的只是被查找数据行所在的页。 从本质上来说,联合索引也是一棵B+ 。那么什么时候会使用到联合索引呢?"

    44820

    漫画:什么是B+

    在上一篇漫画中,我们介绍了B-的原理和应用,没看过的小伙伴们可以点击下面的链接: 漫画:什么是B-? 这一次我们来介绍B+。 一个m阶的B+具有如下几个特征: 1.有k个子树的中间节点包含有k个元素(B中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。 B-中的卫星数据(Satellite Information): B+中的卫星数据(Satellite Information): 需要补充的是,在数据库的聚集索引(Clustered Index 11,遍历结束: B+的范围查找过程 自顶向下,查找到范围的下限(3): 通过链表指针,遍历到元素6, 8: 通过链表指针,遍历到元素9, 11,遍历结束: B+的特征: 1.有 B+的优势: 1.单一节点存储更多的元素,使得查询的IO次数更少。 2.所有查询都要查找到叶子节点,查询性能稳定。 3.所有叶子节点形成有序链表,便于范围查询。 —————END—————

    11730

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • 自然语言处理

      自然语言处理

      腾讯云自然语言处理(NLP)深度整合了腾讯内部顶级的 NLP 技术,依托千亿级中文语料累积,提供16项智能文本处理能力,包括智能分词、实体识别、文本纠错、情感分析、文本分类、词向量、关键词提取、自动摘要、智能闲聊、百科知识图谱查询等,满足各行各业的文本智能需求。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券