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

相关文章

来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.4K7
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3625
来自专栏魂祭心

原 canvas绘制clock

5004
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2820
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

4179
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5717
来自专栏落花落雨不落叶

canvas画简单电路图

81311
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

38110
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

6906
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

5208

扫码关注云+社区