IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> B-树和B+树的区别 -> 正文阅读

[数据结构与算法]B-树和B+树的区别

首先

B+树的应用最多的就是在MySQL中的索引,是InnoDB存储引擎的默认索引。那么这个在面试中也是经常被问到的。那么就做一个总结吧。

概念

要了解B+树那么就不得不提一下的是B-树,因为B+树和B-树是由很大的联系。
在这里插入图片描述
B树(B-tree) 是一种平衡的多路查找树,那么我们从图中也可以看到2-3树的影子,其实2-3树、2-3-4树是B树的一个特例。结点最大的孩子数目称为B树的阶,因此,2-3树是3阶的B树,而2-3-4是4阶的B树。再者B树的每个结点都会存储数据。
我们在来看B+树:
B+树
我们首先先比较B树和B+树在结构上的不同,其实整体都是2-3树的形式,但是B+树相对于B树的区别就是在于B+树的叶子结点这一部分,B+树的叶子结点是存储了所有的数据并且是按照非递减的顺序去排序的数据,其他的结点本身不存储数据而是存储指向叶子结点数据的指针

B+树的特征

  • 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引所有数据都保存在叶子节点。

  • 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。(链表)

  • 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素

  • B+树查找时是从上到下查找B-树则是从下往上查找(中序遍历)

B+树的优势

  • 单一节点存储更多的元素(这样该节点下分支变多了,树变矮胖了),使得查询的IO次数更少。
  • 所有查询都要查找到叶子节点查询性能稳定
  • 所有叶子节点形成有序链表,便于范围查询

B-树和B+树的区别?

首先我们上面提到的B+树相对于B树来说最大的不同就是叶子结点存储数据,并且将它们按照非递减的排序。那么这一个特性可以使得B+树很适合范围查询,并且B树的话它会存在一个回旋查询的问题,会导致查询的效率降低,那么B+树并不会回旋而是直接进行查询返回范围值。

结语

粗略的总结希望对你有帮助,后期还会继续补充~
收工~

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-04 12:36:03  更:2022-04-04 12:38:35 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 9:27:18-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码