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

BB+区别

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

3.8K40
  • 广告
    关闭

    热门业务场景教学

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

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

    LSM B+比较

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

    14220

    B B- B+ B*

    B在经过多次插入删除后,有可能导致不同结构: ? M/2结点;删除结点时,需将两个不足M/2兄弟结点合并; B+        B+B-变体,也是一种多路搜索:        1.其定义基本B-同,除了:        2.非叶子结点子树指针关键字个数相同 B+搜索B-也基本相同,区别B+只有达到叶子结点才命中(B-可以在 非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;     B+特性:        1.所有关键字都出现在叶子结点链表中 4.更适合文件索引系统; B*B+变体,在B+非根和非叶子结点再增加指向兄弟指针; ?    ;B+总是到叶子结点才命中; B*:在B+基础上,为非叶子结点也增加链表指针,将结点最低利用率从1/2提高到2/3;

    54370

    B-B+B*

    1.减少磁盘IO 2.更快搜索算法 操作系统中, 管理内存是按照页page 4K 管理 管理磁盘是按照block 16K 现在有n = 1000w个索引需要从磁盘中进行读取和搜索? avl和m为300B-? avl高度:log2n = 24层 最差情况一个节点只存储一个索引? 最差需要24次磁盘IO B-高度:log(300)n = 3 层 最多花费3次磁盘IO B+ B+B-一种变形 非叶子结点只存储索引,不存储数据 B+叶子结点包含全部关键字信息 ,而B-数据分散在各个结点当中。 B+存放索引项相对于B-能够存储更多。 B* B*B+变体,在B+非根和叶子结点在增加指向兄弟结点指针 B*提高了结点利用率。

    16130

    BB+B*——简单介绍

    BB+B*——简单介绍 强烈推介IDEA2020.2破解激活,IntelliJ 【3】文件系统及数据库系统设计者利用磁盘预读(预先读取)原理,将一个节点大小设置为页<page:数据读取最小单位>大小(通常为4k),这样每个节点只需要一次 IO就能载入内存;B(B+)广泛应用于文件存储系统及数据库文件系统中 拆后仍需要满足上述条件;   ■  对于三节点子树大小仍然遵循(BST:二叉排序规则; 2-3 插入和删除节点案例:链接 B-TreeB(Balanced:平衡),有人将B-Tree 三、BB+B* ---- 【1】B介绍:前面介绍2-3、2-3-4就是 B,在 MySql 中经常听说某种索引是基于 BB+,如下图: ? 【2】B+介绍:B+ B变体,也是一种多路搜索,如下图: ? 【3】B* 介绍:B* B+变体,在B+非根和非叶子节点增加了指向兄弟指针,如下图: ?

    27520

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

    22841

    多叉 & B & B+ & B*

    (2). 2-3-4: 和2-3区别就是,它还允许节点有三个元素且有四个子节点。 4. BB是balance,平衡意思,所以,B首先是一棵平衡,而平衡首先得是一棵排序数。 B+B+B变体,和B区别就是,B+所有数据都存放在叶子节点。 B+所有的数据都存放在叶子节点链表中,且链表中数据也是有序; 非叶子节点中存放是索引,而不是要操作数据,每个非叶子节点都会存放叶子节点索引,也叫稀疏索引; B+要进行搜素时,从根节点开始 ,通过根节点索引比较,就知道要往左子树查找还是往中间查找还是往右子树查找,到了子树时候再通过子树中存放索引比较,又可以直到要往那一边查找。 B+一般用于文件系统; 6. B*B*又是B+变体,就是在B+基础上,在非根非叶子节点之间增加了指向兄弟节点指针。

    45020

    BB-)、B+ 简述

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

    29740

    红黑BB+

    二叉 I/O 次数分析 先说 I/O 次数: 其实相比于二叉B B+, CPU 运算次数并没有变化,甚至增多。 B/B+索引数量 B 节点中存储:指针、关键字(主键)、数据 B+ 非叶子节点:指针、关键字 B+叶子节点:指针(链表)、关键字、数据 注意,这里不是绝对,比如有的 B+ 中叶子节点存储不是数据 而且上述是假设数据为 1KB,如果数据没那么大,高度为 3 B 能存储更多数据,但是如果用在大型数据库索引上还是不够。 B+ B+ 如上图,B+核心在于非叶子节点不存储数据。 高度为 3 B+ 进行两次 I/O 就可以索引千万级别的数据,高度为 4 B+ ,进行 3 次 I/O 就能索引十亿级别的数据量,这个效果还是很好B/B+优点 更适合磁盘存储,减少了层级,进而减少 I/O 次数; B B+ 对比 都是 B ,但是 B+更适合范围查询,比如 Mysql,且查询次数很稳定,为 logn。

    22700

    红黑BB+

    二叉 I/O 次数分析 先说 I/O 次数: 其实相比于二叉B B+, CPU 运算次数并没有变化,甚至增多。 B/B+索引数量 B 节点中存储:指针、关键字(主键)、数据 B+ 非叶子节点:指针、关键字 B+叶子节点:指针(链表)、关键字、数据 注意,这里不是绝对,比如有的 B+ 中叶子节点存储不是数据 而且上述是假设数据为 1KB,如果数据没那么大,高度为 3 B 能存储更多数据,但是如果用在大型数据库索引上还是不够。 B+ B+ 如上图,B+核心在于非叶子节点不存储数据。 高度为 3 B+ 进行两次 I/O 就可以索引千万级别的数据,高度为 4 B+ ,进行 3 次 I/O 就能索引十亿级别的数据量,这个效果还是很好B/B+优点 更适合磁盘存储,减少了层级,进而减少 I/O 次数; B B+ 对比 都是 B ,但是 B+更适合范围查询,比如 Mysql,且查询次数很稳定,为 logn。

    20340

    B+,索引

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

    30120

    B+

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

    26420

    B B+ B* 谈到R

    本blog之前介绍红黑很相似,但在降低磁盘I/0操作方面要更好一些。许多数据库系统都一般使用B或者B各种变形结构,如下文即将要介绍B+B*来存储信息。   B红黑最大不同在于,B结点可以有许多子女,从几个到几千个。那为什么又说B红黑很相似呢? 一棵m阶B+和m阶B异同点在于:       1.有n棵子树结点中含有n-1 个关键字; (此处颇有争议,B+到底是B n棵子树有n-1个关键字 保持一致,还是不一致:Bn棵子树结点中含有 这也佐证了咱们之前观点。删除操作完。 7.总结 通过以上介绍,大致将BB+B*总结如下: B:有序数组+平衡多叉B+:有序数组链表+平衡多叉B*:一棵丰满B+。 Bucket Li:"mysql 底层存储是用B+实现,知道为什么么。内存中B+是没有优势,但是一到磁盘,B+威力就出来了"。

    1K10

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

    什么是B+ B+B-变体,也是一种多路搜索 4.1 B+特点 其定义基本和特性B-同,除了: 1.非叶子结点子树指针关键字个数相同 2.非叶子结点子树指针P[i],指向关键字值属于 比起B-B+所有的节点数值都会出现在叶子节点中 并且,所有叶子节点组成了一个增序链表 4.2 B+查询 查询数值11 ? 4.3 B+插入 插入数值16 ? 4.4 B+删除 删除值16 ? 5. 什么是B*B+变体,在B+非根和非叶子结点再增加指向兄弟指针 B*定义了非叶子结点元素个数至少为(2/3)*M,即块最低使用率为2/3(代替B+1/2) B*查询、插入和删除操作和 ,且只出现一次,非叶子结点可以命中; B+:在B-基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点索引;B+总是到叶子结点才命中; B*:在B+基础上,为非叶子结点也增加链表指针

    3.5K21

    浅谈 B+

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

    15020

    树结构系列(三):BB+

    文章首发于「陈义」公众号及个人博客 shuyi.tech,欢迎访问更多有趣有价值文章。 B+ B+ 是应文件系统所需而产生 B 变形 B 相比,B+ 有着如下好处: B+ 磁盘读写代价更低 B+ 内部结点并没有指向关键字具体信息指针,所以其内部结点相对 B 更小。 B+ 查询效率更加稳定 由于非终结点并不是最终指向文件内容结点,而只是叶子结点中关键字索引。所以 B+ 中任何关键字查找必须走一条从根结点到叶子结点路。 B+ 便于范围查询(最重要原因,范围查找是数据库常态) B 在提高了 IO 性能同时,并没有解决元素遍历效率低下问题。为了解决这个问题,B+ 应用而生。 B+ 只需要去遍历叶子节点就可以实现整棵遍历。在数据库中基于范围查询是非常频繁,因此 MySQL Innodb 引擎就使用了 B+ 作为其索引数据结构。

    55110

    数据结构 —— BB+

    B详解以及B+B不同 数据结构 —— BB+ 1. 背景 ​ 最近在学习数据库相关知识,了解到数据库很多是采用B-/+作为索引,例如MysqlInnoDB引擎使用B+、MongoDB默认采用B作为索引。 B,概括来说是一个一般化二叉查找(binary search tree)一个节点可以拥有2个以上子节点。自平衡二叉查找不同,B适用于读写相对大数据块存储系统,例如磁盘。 B+ 4.1 B+特征 有 m 个子树中间节点包含有 m 个元素(B 中是 k-1 个元素),每个元素不保存数据,只用来索引; 所有的叶子结点中包含了全部关键字信息,及指向含有这些关键字记录指针 (而 B 非终节点也包含需要查找有效信息); 参考 B B + 详解 B- 维基百科,自由百科全书

    22540

    图解 MySQL 索引:B-B+

    2️⃣从应用层次来分:普通索引,唯一索引,复合索引 3️⃣根据中数据物理顺序键值逻辑(索引)顺序关系:聚集索引,非聚集索引。 就像手机分类:安卓手机,IOS手机 华为手机,苹果手机,OPPO手机一样。 二、索引底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引,对于频繁访问表,innodb会透明建立自适应hash索引,即在B索引基础上建立hash 在InnoDB中实现 ? ? 三、问题 问:为什么索引结构默认使用B-Tree,而不是hash,二叉,红黑? hash:虽然可以快速定位,但是没有顺序,IO复杂度高。 二叉高度不均匀,不能自平衡,查找效率跟数据有关(高度),并且IO代价高。 红黑高度随着数据量增加而增加,IO代价高。 问:为什么官方建议使用自增长主键作为索引。

    90120

    BB+到底是什么?

    B+ B+是对应数据库所需而出现一种B变形区别B+中,具有n个关键字结点只含有n棵子树,即每个关键字对应一棵子树;而在B中,具有n个关键字结点含有n+1棵子树。 在B+中,每个结点(非根内部结点)关键字个数n范围是【m/2】<=n<=m(根节点:1<=n<=m); 在B中,每个结点(非根叶结点)关键字个数n范围是【m/2】-1<=n<=m-1(根节点 在B+中,叶结点包含信息,所有非叶结点仅起索引作用,非叶节点中每个索引项只含有对应子树最大关键字和指向该子树指针,不含有该关键字对应记录存储地址。 在B+中,叶结点包含了全部关键字,即在非叶结点中出现关键字也会出现在叶结点中;而在B中,叶结点包含关键字和其他结点包含关键字是不重复

    50140

    关注

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

    相关产品

    • 备份一体机

      备份一体机

      备份一体机(TStor B2000)是将备份功能、容灾功能、存储功能和服务器硬件融合于一体的企业级数据保护产品,定位于解决混合云场景下的数据存储。TStor B2000支持本地与云端数据的协同,为用户数据提供云下快速备份恢复、云上容灾、云上归档、云上云下灾难恢复等功能,可以轻松解决混合云场景下的各种数据存储和管理问题。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券