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

每天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%。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jerry的SAP技术分享

如何计算并测量ABAP及Java代码的环复杂度Cyclomatic complexity

代码的环复杂度(Cyclomatic complexity,有的地方又翻译成圈复杂度)是一种代码复杂度的衡量标准,在1976年由Thomas J. McCabe...

37590
来自专栏蜉蝣禅修之道

CMU算法求网络瓶颈链路

18760
来自专栏微信公众号:Java团长

Lucene全文检索的基本原理

根据http://lucene.apache.org/java/docs/index.html定义:

16110
来自专栏Play & Scala 技术分享

Scala Macro 现状介绍

39350
来自专栏SAP最佳业务实践

想学FM系列(20)-SAP FM模块:派生规则推导策略(3)-派生规则推导步骤-派生规则、增强

4.1.4 派生规则 派生规则简单来讲由通过枚举条件的值来推导出目标字段的值。比如已知一个变量作为条件,枚举变量值为:V1、V2……,再枚举出目标变量对等值为:...

1.2K70
来自专栏图形学与OpenGL

OpenGL开发库的详细介绍zz

开发基于OpenGL的应用程序,必须先了解OpenGL的库函数。它采用C语言风格,提供大量的函数来进行图形的处理和显示。OpenGL库函数的命名方式非常有规律...

32330
来自专栏吉浦迅科技

DAY38:阅读存储器修饰符

11730
来自专栏数据小魔方

左手用R右手Python——CSS网页解析实战

之前我陆陆续续写了几篇介绍在网页抓取中CSS和XPath解析工具的用法,以及实战应用,今天这一篇作为系列的一个小结,主要分享使用R语言中Rvest工具和Pyth...

46350
来自专栏Golang语言社区

麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏,感觉其中有不少值得记录的东西。 基础数据结构     数据结构确定决定了程序的开发难易程度,就像是游戏的骨架,对于电脑AI...

1.1K20
来自专栏Linyb极客之路

写出优质Java代码的4个技巧

如果现在要求对你写的Java代码进行优化,那你会怎么做呢?作者在本文介绍了可以提高系统性能以及代码可读性的四种方法,如果你对此感兴趣,就让我们一起来看看吧。

16210

扫码关注云+社区

领取腾讯云代金券