Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >10分钟梳理关系数据库基础知识(三):B+树

10分钟梳理关系数据库基础知识(三):B+树

原创
作者头像
刁寿钧
修改于 2017-06-27 02:32:38
修改于 2017-06-27 02:32:38
1.8K0
举报
文章被收录于专栏:刁寿钧的专栏刁寿钧的专栏

每天10分钟,用去食堂吃饭的时间解决一个知识点。

存在的意义

上一篇《10分钟梳理关系数据库基础知识(二):存储结构》中有强调,我们优化的目标,是尽量减少磁盘 IO 的次数。B+树这种数据结构就很适合这种场景。因为它高扇出,长得矮矮胖胖的,一层是一次IO。

为了直观地展现效果,我们可以做一个简单的估算。之前提到的块(block),在 InnoDB 中被称作页(page),大小是可以设的,默认为16KB。假设一行记录为100个 Byte,即每个块中能存160行记录。高度为4的 B+树,可存放的记录数就是:160×160×160×160=655360000行。而目前机械盘的IOPS一般在100~200,即使以100计算,4次IO意味着时间只需要0.04秒。是不是很美好?

当然这只是一个粗略的估算,大家感受下B+树存在的意义就好。

+在哪里

B+树是B-树的一个变种。与B-树主要有两个值得一提的不同,一是为了存放更多的指针,B+树在非叶子节点中只存放key,叶子节点中才有数据;二是叶子节点之间是有指针相联系的,这就方便了范围查询。

来,种一棵树

为了让大家有个更直观的认识,我手工画了一棵B+树构造的过程:

上图做了简化,没有考虑填充因子(fill factor)。填充因子指的是叶子节点满的程度,要求是在半满和全满之间,方便插入和删除。具体数值在InnoDB中是可以指定的,一般是75%,当然,要求至少半满,所以可设的最小值是50%。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
面试题:InnoDB中一棵B+树能存多少行数据?
因为这是可以算出来的,要搞清楚这个问题,我们先从 InnoDB 索引数据结构、数据组织方式说起。
良月柒
2019/06/10
6.5K2
面试题:InnoDB中一棵B+树能存多少行数据?
数据库底层数据结构 B树B+树LSM树 详解对比与总结
我们熟知常用数据库MySQL MongoDB HBase等底层存储都用了各种树结构,如B树LSM树,不过为什么要用这些结构呢?
大鹅
2021/06/16
5.6K0
从B 树、B+ 树、B* 树谈到R 树
说明:本文从B树开始谈起,然后论述B+树、B*树,最后谈到R 树。其中B树、B+树及B*树部分由weedge完成,R 树部分由Frankie完成,全文最终由July统稿修订完成。
bear_fish
2018/09/14
2.4K0
从B 树、B+ 树、B* 树谈到R 树
详述 MySQL 中 InnoDB 的索引结构以及使用 B+ 树实现索引的原因
在 MySQL 的众多存储引擎中,InnoDB 是最常用的存储引擎,也是 MySQL 现阶段唯一免费支持事务机制的存储引擎。在本文中,我们以 InnoDB 为例,介绍 MySQL 的索引结构以及其使用 B+ 树实现索引的原因。
CG国斌
2021/12/07
1.3K0
详述 MySQL 中 InnoDB 的索引结构以及使用 B+ 树实现索引的原因
B-树和B+树的应用:数据搜索和数据库索引
定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树: ⑴树中每个结点至多有m 棵子树; ⑵若根结点不是叶子结点,则至少有两棵子树;
黄规速
2022/04/14
7540
B-树和B+树的应用:数据搜索和数据库索引
MySQL索引底层:B+树详解
当我们发现SQL执行很慢的时候,自然而然想到的就是加索引。对于范围查询,索引的底层结构就是B+树。今天我们一起来学习一下B+树哈~
捡田螺的小男孩
2021/03/15
8210
为什么MySQL数据库索引选择使用B+树?
在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树!
Java后端技术
2018/08/09
1.7K0
为什么MySQL数据库索引选择使用B+树?
数据库之索引总结
索引在数据库中可以说是相当重要的一块知识点了,也是面试经常被问的,这篇文章就总结一下索引相关的知识点,包括索引的底层实现原理,索引的分类,最左匹配原则等。
秃头哥编程
2019/06/17
8360
数据库之索引总结
B树还是B+树,别再傻傻分不清了
B-Tree(B树)是一棵多路搜索平衡查找树,相对于二叉树,B树的每个节点有多个子节点,即多叉(路)。Oracle和MongoDB使用的索引技术就是基于B树的数据结构。
用户5921339
2025/05/20
2350
B树还是B+树,别再傻傻分不清了
重温数据结构:理解 B 树、B+ 树特点及使用场景
B 树就是常说的“B 减树(B- 树)”,又名平衡多路(即不止两个子树)查找树,它和平衡二叉树的不同有这么几点:
张拭心 shixinzhang
2019/05/27
4.7K0
MySQL数据库索引选择为什么使用B+树而不是跳表?
在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树!
小冷coding
2023/05/24
8650
MySQL数据库索引选择为什么使用B+树而不是跳表?
mysql b+树优点_基础B
大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景: 面试官:对于MySQL,你对他索引原理了解吗? 我:了解 面试官:MySQL的索引是用什么数据机构的? 我:B+树 面试官:为什么要用B+树,而不是B树? 我:… 面试官:用B+树作为MySql的索引结构,用什么好处? 我:…
全栈程序员站长
2022/11/16
6580
mysql b+树优点_基础B
10分钟梳理关系数据库基础知识(五):查询优化与连接算法
本文介绍了数据库查询优化和连接算法的相关内容。优化器是数据库中用于选择最佳执行计划的组件,分为基于代价的优化器和基于规则的优化器。优化器的目标是选择成本最低的访问计划,以最小的代价返回查询结果。连接算法是数据库中用于处理关系型数据库中的表连接操作,分为嵌套循环连接、块嵌套循环连接、索引嵌套循环连接等。在数据库应用中,优化器通过代价模型计算访问计划,选择成本最低的访问方式,提高查询效率。
刁寿钧
2017/06/27
1.8K0
为什么MySQL数据库索引选择使用B+树?
我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。
用户3467126
2019/08/05
1.6K0
为什么MySQL数据库索引选择使用B+树?
MySQL索引原理——B树
1、MyISAM是MySQL 5.5之前版本默认的存储引擎,从5.5之后,InnoDB开始成为MySQL默认的存储引擎。MyISAM和InnoDB都是使用B+树实现主键索引、唯一索引和非主键索引。
saintyyu
2021/11/22
7000
MySQL索引原理——B树
第15期:索引设计(索引组织方式 B+ 树)
谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。
爱可生开源社区
2020/11/03
3670
第15期:索引设计(索引组织方式 B+ 树)
女朋友问我:为什么 MySQL 喜欢 B+ 树?我笑着画了 20 张图
要解释这个问题,其实不单单要从数据结构的角度出发,还要考虑磁盘 I/O 操作次数,因为 MySQL 的数据是存储在磁盘中的嘛。
小林coding
2021/12/27
7340
女朋友问我:为什么 MySQL 喜欢 B+ 树?我笑着画了 20 张图
It's Design——为什么MySQL使用B+树?
相信每一个后台开发工程师在面试过程中,都曾经被问到过“MySQL的默认存储引擎是什么?MySQL索引是什么数据结构?”这样的问题。相信准备充分(熟读八股文)的大家都能很容易的回答出“MySQL的默认存储引擎是InnoDB,MySQL索引使用的是B+树。”这样的答案。但是为什么当初写MySQL的程序员大叔要这样子来设计呢?
yuann
2021/04/15
9460
It's Design——为什么MySQL使用B+树?
B树(B-树)、B+树 简述
说起来b树的发明主要是为了减少磁盘io操作 将树的结构设计成矮胖型而不是瘦高型,因为数据库索引是存储在磁盘上的,当数据量比较大时,我们不能把所有索引加载到内存中,只能逐一加载每一个磁盘页,这里的磁盘页对应索引树的节点
glm233
2021/03/08
1.2K0
图解:什么是B-树、B+树、B*树
6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
你好戴先生
2020/09/03
11K2
推荐阅读
相关推荐
面试题:InnoDB中一棵B+树能存多少行数据?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档