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

阅读数:8 2019 年 12 月 26 日 17:26

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

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

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

概述

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

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

我们在使用 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 作为键对应的值。

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

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

本文转载自 Draveness 技术博客。

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

评论

发布