B树与B+树

简介: B树与B+树

B+树引出


在MySQL中,如果我们设置了主键, 那么对于该列表中的数据就有了一个索引,插入表中数据的主键值不能重复,而且不能为空.

那当我们插入数据的时候, 它是如何通过索引来判断主键值是否重复的呢?

我们想到它肯定是进行了一个查找, 关于查找那就是哈希或者二叉搜索树查找比较快啊, 但MySQL是用B+树来实现查找的.


为什么哈希和二叉树不行呢?


在MySQL中,我们可以查找范围内的数据,比如 大于3且小于5 的数据, 那在哈希中 我们只能查找某个值的数据,或者余数相同的数据,不能实现范围查找.

同样的, 二叉搜索树也是一样, 不能得出范围. 还有就是二叉搜索树的访问速度也慢, 因为二叉搜索树要进行多次比较 才能得出数据, 每次比较都要访问磁盘,多次访问磁盘效率自然很低.


要了解B+树,首先我们得知道B树.


什么是B树


B树与二叉搜索树很像, 可以把它理解为一个 N 叉搜索树, 如图:


3e29b52c035a4e60b9f86c6112a6d641.png


它一个节点可以对应多个key, 每个key都是一条数据,比如我们定义一个学生表,每个学生都有姓名和 id, 那 25 可能就代表 ‘张三’ 25 这么一条数据.

通过上图我们可以看出它的子节点是按照范围来确定的, 比如第一个节点, 它存的key是 25 30 50 70 , 那它可以分出5个节点, 节点key的范围分别为:

小于25

大于25且小30

大于30且小于50

大于50且小于70

大于70

这样相比二叉搜索树, B树的高度更矮, 这就意味着查询次数更少, 访问磁盘更少,效率高了一点.


什么是B+树


B+树也是N叉搜索树, 只不过是对B树进行了改进.

我们来画个B+树:


f43c533410554aa3b3207d401dec4c3c.png


从图中我们可以知道它的特点 :


1.一个节点可以存储N个key, N个key划分出N个区间(B树是N+1个区间)

2.每个节点的key值都会在子节点中存在 (同时key值是子节点的最大值)(这里保证了树的高度统一)

3.B+树的叶子节点是首尾相连的,相当于链表(便于范围查找)

4.在B+树这里, 我们只在叶子节点处存储完整数据,而非叶子节点只存储key值(大大节省了空间)


B+树的优点


它的优点即是它的特点, 这里再概括一下:


  1. 当前一个节点保存了更多的key时, 最终树的高度是更矮的,减少了IO访问次数,提高了效率(与B树一样)
  2. B+树所有查询所经历的IO访问次数一样(这样可以让程序员对代码运行速率有所把控)
  3. B+树的叶子节点构成一个链表, 此时方便范围查询.
  4. 由于数据都在叶子节点上, 非叶子节点只存储key, 导致非叶子节点占空间比较少, 这些非叶子节点就可能在内存中缓存(或者缓存一部分), 这样又进一步减少IO访问次数.

相关文章
|
SQL 存储 OLAP
适用于即席查询(Ad-Hoc)的OLAP引擎
即席查询(Ad Hoc)是用户根据自己的需求,灵活的选择查询条件,OLAP系统根据用户输入的查询条件实时返回查询结果。OLAP的即席查询与普通查询的不同之处就是很难对前者进行预先的优化,因为即席查询所响应的大都是随机性很强的查询请求。一个OLAP系统的即席查询能力越强,其应对不同用户的随机性和探索性分析的能力就越强。
594 0
适用于即席查询(Ad-Hoc)的OLAP引擎
|
NoSQL MongoDB
mongoTemplate批量保存数据mongoDB批量保存数据
mongoTemplate批量保存数据mongoDB批量保存数据
528 2
|
JSON 数据格式 物联网
HTTP协议接入物联网平台(Getman模拟)
物联网平台通过HTTP连接通信(Getman模拟)
3555 0
HTTP协议接入物联网平台(Getman模拟)
|
消息中间件 存储 监控
ActiveMQ系列: ActiveMQ 的死信队列与消费重试机制
maximumRedeliveryDelay:最大传送延迟,只在 useExponentialBackOff 为 true 时有效(V5.5),假设首次重连间隔为 10ms,倍数为 2,那么第二次重连时间间隔为 20ms,第三次重连时间间隔为 40ms,当重连时间间隔大的最大重连时间间隔时,以后每次重连时间间隔都为最大重连时间间隔。默认为 -1。
1202 0
ActiveMQ系列: ActiveMQ 的死信队列与消费重试机制
|
存储 数据库 索引
B树与B+树区别
B树与B+树区别
3145 1
|
12月前
|
调度 开发者 Python
python超详细的日期操作【建议收藏备用】
python超详细的日期操作【建议收藏备用】
153 0
|
7月前
|
存储 前端开发 JavaScript
在线教育网课系统源码开发指南:功能设计与技术实现深度解析
在线教育网课系统是近年来发展迅猛的教育形式的核心载体,具备用户管理、课程管理、教学互动、学习评估等功能。本文从功能和技术两方面解析其源码开发,涵盖前端(HTML5、CSS3、JavaScript等)、后端(Java、Python等)、流媒体及云计算技术,并强调安全性、稳定性和用户体验的重要性。
|
11月前
|
编译器 Python
递归下降解析器
递归下降解析器是一种自顶向下的解析技术,常用于编译器和解释器中,通过递归函数处理语法规则,构建语法树。适用于上下文无关文法(CFG),特别是LL(1)文法。其特点是实现简单、易于理解和调试,但可能面临性能问题和不支持回溯的限制。
188 3
|
缓存 前端开发
css内部样式和外部样式的性能比较和使用规范
CSS 的内部样式和外部样式各有优缺点,适用于不同场景。