10 月,开发者不可错过的开源大数据大会-2021 WeDataSphere 社区大会深圳站 了解详情
写点什么

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

2019 年 12 月 26 日

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

为什么这么设计(Why’s THE Design)是一系列关于计算机领域中程序设计决策的文章,我们在这个系列的每一篇文章中都会提出一个具体的问题并从不同的角度讨论这种设计的优缺点、对具体实现造成的影响。如果你有想要了解的问题,可以在文章下面留言。


为什么 MySQL 使用 B+ 树是面试中经常会出现的问题,很多人对于这个问题可能都有一些自己的理解,但是多数的回答都不够完整和准确,大多数人都只会简单说一下 B+ 树和 B 树的区别,但是都没有真正回答 MySQL 为什么选择使用 B+ 树这个问题,我们在这篇文章中就会深入分析 MySQL 选择 B+ 树背后的一些原因。


概述

首先需要澄清的一点是,MySQL 跟 B+ 树没有直接的关系,真正与 B+ 树有关系的是 MySQL 的默认存储引擎 InnoDB,MySQL 中存储引擎的主要作用是负责数据的存储和提取,除了 InnoDB 之外,MySQL 中也支持 MyISAM 作为表的底层存储引擎。



我们在使用 SQL 语句创建表时就可以为当前表指定使用的存储引擎,你能在 MySQL 的文档 Alternative Storage Engines 中找到它支持的全部存储引擎,例如:MyISAMCSVMEMORY 等,然而默认情况下,使用如下所示的 SQL 语句来创建表就会得到 InnoDB 存储引擎支撑的表:


SQL


CREATE TABLE t1 (    a INT,    b CHAR (20), PRIMARY KEY (a)) ENGINE=InnoDB;
复制代码


想要详细了解 MySQL 默认存储引擎的读者,可以通过之前的文章 『浅入浅出』MySQL 和 InnoDB 了解包括 InnoDB 存储方式、索引和锁等内容,我们在这里主要不会介绍 InnoDB 相关的过多内容。


我们今天最终将要分析的问题其实还是,为什么 MySQL 默认的存储引擎 InnoDB 会使用 B+ 树来存储数据,相信对 MySQL 稍微有些了解的人都知道,无论是表中的数据(主键索引)还是辅助索引最终都会使用 B+ 树来存储数据,其中前者在表中会以 <id, row> 的方式存储,而后者会以 <index, id> 的方式进行存储,这其实也比较好理解:


  • 在主键索引中,id 是主键,我们能够通过 id 找到该行的全部列;

  • 在辅助索引中,索引中的几个列构成了键,我们能够通过索引中的列找到 id,如果有需要的话,可以再通过 id 找到当前数据行的全部内容;


对于 InnoDB 来说,所有的数据都是以键值对的方式存储的,主键索引和辅助索引在存储数据时会将 idindex 作为键,将所有列和 id 作为键对应的值。



在具体分析 InnoDB 使用 B+ 树背后的原因之前,我们需要为 B+ 树找几个『假想敌』,因为如果我们只有一个选择,那么选择 B+ 树也并不值得讨论,找到的两个假想敌就是 B 树和哈希,相信这也是很多人会在面试中真实遇到的问题,我们就以这两种数据结构为例,分析比较 B+ 树的优点。


本文转载自 Draveness 技术博客。


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


2019 年 12 月 26 日 17:26349

评论 1 条评论

发布
用户头像
主键索引和普通索引同时存在 数据结构是什么样子呢
2021 年 04 月 13 日 19:21
回复
没有更多了
发现更多内容

这些相见恨晚的命令行工具,你用过几个?

王坤祥

bash Linux Tool

我一怒之下写了个抄袭举报工具!只因一觉醒来我的文章被多个平台抄袭!

1_bit

Python selenium 签约计划 文本分析 文章查重

uni-app跨端开发H5、小程序、IOS、Android(八):理解uni-app生命周期

黑马腾云

小程序 uni-app ios android H5

和面试官简单聊聊 Elasticsearch

escray

elasticsearch elastic 4月日更 技术编辑能力考核

干货版“测试小品”欢乐场景

清菡

自动化测试

聪明人的训练(十一)

Changing Lin

4月日更

【LeetCode】丑数 IIJava题解

HQ数字卡

算法 LeetCode 4月日更

美团面试题:String s = new String("111") 会创建几个对象?

Java小咖秀

Java 面试 string java对象

手把手教你基于Prometheus搭建监控告警系统

Java全栈封神

云原生 Prometheus 监控告警

如何从零搭建技术团队

石云升

团队建设 28天写作 职场经验 管理经验 4月日更

从零开始带你打开批处理大门

xiezhr

doc 批处理 cmd

机器学习水水笔记之——世界是积木吗?

Nydia

签约计划

全网首发:Android Camera2 集成人脸识别算法

小驰嘻嘻

android 音视频 人脸识别 引航计划

数据中台前世今生

李孟

大数据 数据中台 签约计划

如何设计一款用户想要的产品——“Design Thinking”培训笔记

gavin

产品设计 design thinking

ElasticSearch 如何使用 ik 进行中文分词?

程序员历小冰

中文分词 elasticsearch ik 全文搜索

【音视频】手把手带你实现超实用实时音视频工具

轻口味

android 音视频 WebRTC 移动端 OpenGL ES

线程池的引入和实践案例分享

小诚信驿站

线程池 线程池工作原理

区块链国富论——财富不是物,而是全球信用共识

CECBC区块链专委会

黄金交易

树莓派4B+OpenVINO快速实现人脸识别

IT蜗壳-Tango

音视频 IT蜗壳教学 4月日更

「免费开源」基于Vue和Quasar的前端SPA项目crudapi后台管理系统实战之动态表关系管理(六)

crudapi

Vue crud crudapi quasar 表关系

2021 年带你漫游语音识别技术

清秋

人工智能 语音识别 智能音箱 签约计划 4月日更

自古彭城列九州 龙争虎斗几千秋|靠谱点评

无量靠谱

自己挖的坑,自己填|靠谱点评

无量靠谱

数据结构和算法难?盘他!-快速入门

Aldeo

数据结构 算法 时间复杂度 复杂度 算法和数据结构

从运营、产品和技术,多角度思考电商的营销体系建设

邴越

电商营销 优惠券

100万级车辆数据监控的hadoop大数据架构探索与实践

黑马腾云

大数据 flink hadoop 分布式 车联网

移动端混合开发选型方案分析

花花

移动端 移动开发· 签约计划

开源| DewCloud——通用物联网平台

云原生

开源 物联网平台 物联网 工业互联网 DewCloud

声网 Agora 初体验

若尘

声网 Agora

一篇文章带你彻底了解MySQL各种约束

若尘

MySQL 数据库 约束 4月日更

为什么 MySQL 使用 B+ 树 (一)-InfoQ