写点什么

为什么 MySQL 使用 B+ 树 (三)

  • 2019-12-26
  • 本文字数:2143 字

    阅读完需:约 7 分钟

为什么 MySQL 使用 B+ 树 (三)

作者使用 macOS 系统的页大小就是 4KB,当然在不同的计算机上得到不同的结果是完全有可能的。


当我们需要在数据库中查询数据时,CPU 会发现当前数据位于磁盘而不是内存中,这时就会触发 I/O 操作将数据加载到内存中进行访问,数据的加载都是以页的维度进行加载的,然而将数据从磁盘读取到内存中所需要的成本是非常大的,普通磁盘(非 SSD)加载数据需要经过队列、寻道、旋转以及传输的这些过程,大概要花费 10ms 左右的时间。



我们在估算 MySQL 的查询时就可以使用 10ms 这个数量级对随机 I/O 占用的时间进行估算,这里想要说的是随机 I/O 对于 MySQL 的查询性能影响会非常大,而顺序读取磁盘中的数据时速度可以达到 40MB/s,这两者的性能差距有几个数量级,由此我们也应该尽量减少随机 I/O 的次数,这样才能提高性能。


B 树与 B+ 树的最大区别就是,B 树可以在非叶结点中存储数据,但是 B+ 树的所有数据其实都存储在叶子节点中,当一个表底层的数据结构是 B 树时,假设我们需要访问所有『大于 4,并且小于 9 的数据』:



如果不考虑任何优化,在上面的简单 B 树中我们需要进行 4 次磁盘的随机 I/O 才能找到所有满足条件的数据行:


  1. 加载根节点所在的页,发现根节点的第一个元素是 6,大于 4;

  2. 通过根节点的指针加载左子节点所在的页,遍历页面中的数据,找到 5;

  3. 重新加载根节点所在的页,发现根节点不包含第二个元素;

  4. 通过根节点的指针加载右子节点所在的页,遍历页面中的数据,找到 7 和 8;


当然我们可以通过各种方式来对上述的过程进行优化,不过 B 树能做的优化 B+ 树基本都可以,所以我们不需要考虑优化 B 树而带来的收益,直接来看看什么样的优化 B+ 树可以做,而 B 树不行。


由于所有的节点都可能包含目标数据,我们总是要从根节点向下遍历子树查找满足条件的数据行,这个特点带来了大量的随机 I/O,也是 B 树最大的性能问题。


B+ 树中就不存在这个问题了,因为所有的数据行都存储在叶节点中,而这些叶节点可以通过『指针』依次按顺序连接,当我们在如下所示的 B+ 树遍历数据时可以直接在多个子节点之间进行跳转,这样能够节省大量的磁盘 I/O 时间,也不需要在不同层级的节点之间对数据进行拼接和排序;通过一个 B+ 树最左侧的叶子节点,我们可以像链表一样遍历整个树中的全部数据,我们也可以引入双向链表保证倒序遍历时的性能。



有些读者可能会认为使用 B+ 树这种数据结构会增加树的高度从而增加整体的耗时,然而高度为 3 的 B+ 树就能够存储千万级别的数据,实践中 B+ 树的高度最多也就 4 或者 5,所以这并不是影响性能的根本问题。

总结

任何不考虑应用场景的设计都不是最好的设计,当我们明确的定义了使用 MySQL 时的常见查询需求并理解场景之后,再对不同的数据结构进行选择就成了理所当然的事情,当然 B+ 树可能无法对所有 OLTP 场景下的查询都有着较好的性能,但是它能够解决大多数的问题。


我们在这里重新回顾一下 MySQL 默认的存储引擎选择 B+ 树而不是哈希或者 B 树的原因:


  • 哈希虽然能够提供 O(1) 的单数据行操作性能,但是对于范围查询和排序却无法很好地支持,最终导致全表扫描;

  • B 树能够在非叶节点中存储数据,但是这也导致在查询连续数据时可能会带来更多的随机 I/O,而 B+ 树的所有叶节点可以通过指针相互连接,能够减少顺序遍历时产生的额外随机 I/O;


如果想要追求各方面的极致性能也不是没有可能,只是会带来更高的复杂度,我们可以为一张表同时建 B+ 树和哈希构成的存储结构,这样不同类型的查询就可以选择相对更快的数据结构,但是会导致更新和删除时需要操作多份数据。


从今天的角度来看,B+ 树可能不是 InnoDB 的最优选择,但是它一定是能够满足当时设计场景的需要,从 B+ 树作为数据库底层的存储结构到今天已经过了几十年的时间,我们不得不说优秀的工程设计确实有足够的生命力。而我们作为工程师,在选择数据库时也应该非常清楚地知道不同数据库适合的场景,因为软件工程中没有银弹。


到最后,我们还是来看一些比较开放的相关问题,有兴趣的读者可以仔细思考一下下面的问题:


  • 常用于分析的 OLAP 数据库一般会使用什么样的数据结构存储数据?为什么?

  • Redis 是如何对数据进行持久化存储的?常见的数据结构都有什么?


如果对文章中的内容有疑问或者想要了解更多软件工程上一些设计决策背后的原因,可以在博客下面留言,作者会及时回复本文相关的疑问并选择其中合适的主题作为后续的内容。

Reference

相关文章


本文转载自 Draveness 技术博客。


原文链接:https://draveness.me/whys-the-design-mysql-b-plus-tree


2019-12-26 17:261121

评论

发布
暂无评论
发现更多内容

Spring Boot 集成实战:AI 工具如何自动生成完整微服务模块

飞算JavaAI开发助手

全民豪车时代,享界S9增程版靠什么“一鼎定乾坤”?

脑洞汽车

AI

全民豪车时代,享界S9增程版靠什么“一鼎定乾坤”?

脑极体

AI

HarmonyOS:动画 motionPath 、 animateToImmediately API自学指南

李游Leo

HarmonyOS

dbops 助力 GreatSQL 单机架构安装部署

GreatSQL

淘宝商品详情 API 接口全解析:从接入到实战

tbapi

淘宝商品详情接口 淘宝API 淘宝商品数据采集

Flink + Doris 实时湖仓解决方案

Apache Flink

大数据 flink 实时计算 Doris

智能网络感知,打造极致流畅的鸿蒙版中国移动云盘图文体验

最新动态

外贸人必看!三步用云手机轻松收集产品反馈

Ogcloud

云手机 海外云手机 舆情监控 舆情监测 海外舆情监控

HarmonyOS @Reusable 装饰器自学指南:高性能组件复用实战指南

李游Leo

@Reusable

HarmonyOS:动画 motionPath 、 animateToImmediately API自学指南

李游Leo

HarmonyOS

镜舟科技荣膺“北京市用户满意企业”认证,以用户为中心驱动高质量发展

镜舟科技

数据 技术创新 LakeHouse StarRocks 镜舟科技

数据无界、湖仓无界,Apache Doris 湖仓一体典型场景实战指南(下篇)

SelectDB

数据湖 Doris LakeHouse trino 湖仓一体

MySQL 优化利器 SHOW PROFILE 的实现原理

不在线第一只蜗牛

MySQL 数据库

怎么用DeepSeek生成甘特图?DS高阶使用技巧分享!

职场工具箱

甘特图 在线白板 AIGC AI 绘图 DeepSeek

项目管理系统(源码+讲解+演示)

深圳亥时科技

“数字创新产品课程” 4月25-26日 · CSPO认证在线课程

ShineScrum

产品负责人 CSPO认证

SvelteKit 最新中文文档教程(12)—— 高级路由

冴羽

React Svelte SvelteKit

HarmonyOS:ArkTS 显式动画 animateTo 自学指南

李游Leo

HarmonyOS

平安证券 NoETL 指标平台实践:统一数据口径,驱动高效经营分析与智能决策

Aloudata

数据仓库 数据分析 大模型 指标平台 万数皆可问

谁是 AI 搜索先锋?阿里云携手 Elastic 正式启动先锋者招募!

阿里云大数据AI技术

elastic 阿里云 搜索 AI搜索

秒杀系统开发指南:用 AI 工具生成高并发代码的 5 个要点

飞算JavaAI开发助手

远程控制软件套路深?4款对比测评,只有贝锐向日葵最靠谱!

科技热闻

昆仑万维发布 Mureka TTS API 和音乐推理大模型;通义发布小尺寸端到端多模态模型 Qwen2.5-Omni丨日报

声网

“清华”天才们联合创立,这家具身智能领域创企完成2亿元天使轮融资!

机器人头条

科技 大模型 人形机器人 具身智能

鸿蒙摄像机,一场智能安防的“平权革命”

脑极体

AI

等保测评取消打分《网络安全等级测评报告模版(2025版)》变更

黑龙江陆陆信息测评部

关于 K8s 的一些基础概念整理-补充

不在线第一只蜗牛

Docker Kubernetes

2025年企业组网新趋势:SASE与SD-WAN发展解析

Ogcloud

SD-WAN 组网 企业组网 企业网络 SD-WAN服务商

2.5D封装为何成为AI芯片的“宠儿”?

E科讯

湖北文旅智能化财务共享中心正式上线,树立文旅行业数字化转型新标杆

用友智能财务

财务 会计

为什么 MySQL 使用 B+ 树 (三)_语言 & 开发_Draveness_InfoQ精选文章