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

相关文章

来自专栏偏前端工程师的驿站

基础野:细说浮点数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

1768
来自专栏算法channel

不基于比较的基数排序原理图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

37913
来自专栏smy

海量数据相似度计算之simhash短文本查找

在前一篇文章 《海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据...

734
来自专栏攻城狮的动态

简谈快速排序

34910
来自专栏生信技能树

(11)仿写bowtie-生信菜鸟团博客2周年精选文章集

然后仿写了bowtie,对我的编程技术提高非常有帮助。目录如下: 自己动手写bowtie第一讲:BWT算法详解并建立索引 自己动手写bowtie第二讲:优化索引...

3046
来自专栏Eugene's Blog

一文总结学习 Python的14 张思维导图分类目录文章标签友情链接联系我们

1054
来自专栏小樱的经验随笔

用C#实现字符串相似度算法(编辑距离算法 Levenshtein Distance)

在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”,关于原理和C#实现做个记录。 据百度百科介绍: 编辑距离,又称Levenshtein距离(也叫...

5185
来自专栏机器学习从入门到成神

Pandas使用DataFrame进行数据分析比赛进阶之路(一)

这篇文章中使用的数据集是一个足球球员各项技能及其身价的csv表,包含了60多个字段。数据集下载链接:数据集

3768
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

461
来自专栏数据小魔方

左手用R右手Python系列之——json序列化与反序列化

json格式数据作为如今越来越流行的数据交换格式,几乎已经成为web端数据交互的标准,主流的数据科学语言R,Python都中都有非常完善的半结构化数据与json...

2757

扫码关注云+社区