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 条评论
登录 后参与评论

相关文章

来自专栏PingCAP的专栏

Succinct Data Structure

最近看了一篇论文 SuRF: Practical Range Query Filtering with Fast Succinct Tries,里面提到使用一种...

2386
来自专栏瓜大三哥

Caffe、TensorFlow、MXnet

Caffe已经很久没有更新过了,曾经的霸主地位果然还是被tensorflow给终结了,特别是从0.8版本开始,tensorflow开始支持分布式,一声叹息…MX...

2969
来自专栏人工智能

从概念到实践,我们该如何构建自动微分库

选自Medium 作者:Maciej Kula 机器之心编译 参与:程耀彤、蒋思源 像 PyTorch 或 TensorFlow 这样通用的自动微分框架是非常有...

17910
来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

612
来自专栏机器之心

深度 | 从概念到实践,我们该如何构建自动微分库

2748
来自专栏深度学习与计算机视觉

TensorFlow 组合训练数据(batching)

在之前的文章中我们提到了TensorFlow TensorFlow 队列与多线程的应用以及TensorFlow TFRecord数据集的生成与显示,通过这些操作...

3177
来自专栏蜉蝣禅修之道

Max-Min Fairness带宽分配算法

1576
来自专栏人工智能LeadAI

你听过算法也是可以贪心的吗?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

3607
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

582
来自专栏Spark学习技巧

第2篇:数据库关系建模

第二篇:数据库关系建模 前言 ER建模环节完成后,需求就被描述成了ER图。之后,便可根据这个ER图设计相应的关系表了。 但从ER图到具体关系表的建立还需要经过两...

3046

扫码关注云+社区