# MySQL 一棵 B + 树可以存多少条数据?

作者:顾恙ツ (opens new window)编程导航星球 (opens new window) 编号 2784

八股文,MySQL 一棵B+树可以存多少数据?

# 📚引言

首先我们需要分析 MySQL 数据是用什么样的形式去组织存储的,我们现在来看一下:

  1. 数据持久化一般都是将数据存储到磁盘中,而磁盘的最小单元就是扇区,这里记下第一个重点:一个扇区的大小是 512 字节,即 0.5 KB
  2. 在扇区以上,便是我们常常说的,文件系统块,一个块的由 8 个扇区构成,所以一个文件系统块大概是 4K
  3. 到上面就是我们今天的重点 InnoDB 存储引擎了,其最小的存储单元就是页,一个页的大小是 4 个文件块,即 16K 这里我们用一张图来表示一下以上的关系:

总结一下:一页的大小大约是 16 K 即 4 个文件系统块,32 个扇区;

# ✨InnoDB引擎

在简单地介绍了数据的组织形式之后,接下来就是我们今天的重点 InnoDB 存储引擎,相信不少学习过 MySQL 的小伙伴都知道 InnoDB 存储引擎是我们现在数据库创建表的时候默认使用的存储引擎了,所以我们这里拿 MySQL 来举例: 首先就是通过命令行的方式连接 MySQL,这里用本机的 MySQL 为例,默认端口是 3306,然后输入密码就可以进入数据库了。

mysql -u root -p
1

查看 InnDB 页的大小:

show variables like 'innodb_page_size';
1

如上图所示,InnoDB 的页大小为 16384 Byte,换算一下大约 16K,与我们在上面表示的数据是一致的

那么一页大概可以放多少行数据呢?

这里我们假设,一行数据的大小大约是 1 KB ,即 1024 个字节,则其一页大概可以存放 16 条数据。 MySQL 的最小存储单元叫做“页”,这么多的页是如何构建一个庞大的数据组织,我们又如何知道数据存储在哪一个页中? 如果采用逐条遍历的方式,那么查询效率不用说都知道,肯定很低,这里我们就使用 InnoDB 存储引擎底层的数据结构 B+ 树 ,这里放一个网站,如果之前没有了解过 B+ 树的同学可以看看:

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

我们这里补充一个点,那就是页除了存放数据(叶子节点),还可以存放键值和指针(非叶子节点),不过需要补充一个点:他们之间的关系是有序的,如图中所示1接下去就是 3 和 4,这样的数据组织形式,我们称其为索引组织表。

那我们来说一下,B + 树是如何进行数据查找的?

  1. 根据索引找到对应位置的根页,因为每张表的根页位置在表空间文件中是固定的,这里我们的根页就是 3,即我们所说的 Page Number;
  2. 找到根页之后,通过二分查找的方式,定位到 id = 3 的数据应该在 P4 指向的页中,这个时候我们就去 P4 页所指向的指针寻找数据
  3. 最后通过二分查找的方式查找 Page Number = 4 的页中的数据,最后找到 id = 3 的记录,返回就可以了。

🔭B+树的高度

在说完 InnoDB 的存储引擎之后,接下来我们来聊一下 B+ 树的高度问题,这里我们继续约定 page number = 3表示主键索引的根页,然后在命令行输入对应的雨具进行查找

SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <> 0
and b.name like '%sp_job_log';
1
2
3
4
5
6
7
8

从上图可以看出,每个表的主键索引的根页的 Page Number 大部分都是 3,而其他的二级索引 Page Number 是 4 或者 5 在根页偏移量为 64 的地方存放了该B+树的 page level。主键索引 B+ 树的根页在整个表空间文件中的第3个页开始,所以算出它在文件中的偏移量:16384 x 3 + 64 = 49152 + 64 =49216 。 这里,我们找到 MySQL 的数据库物理文件存放的目录(这个地方可能每个人都不一样,我这里是在我自己的电脑上):

然后我们使用 hexdump 工具来分析,查看那个表空间文件指定偏移量上的数据:

hexdump -s 49216 -n 10  sp_job_log.ibd
1

这里我们查看图中的值,Page_level 用二进制进行换算,0100 即换算成 2 那么最终得出的 B+ 树的高度为 page level + 1 = 3;

这里进行一些补充说明:

  1. 在你查询数据库的时候,无论是读取单行还是多行,都是先将这些行所在的整页数据加载到内存中,然后在内存中匹配得出最终结果。
  2. 表的检索速度只和树的深度有直接关系,因为一次页加载就是一次 IO,而磁盘 IO是比较耗费时间的。所以对于一张千万级条数B+树高度为3的表与几十万级B+树高度也为3的表,其实查询效率相差不大。

# 🕹️一颗树可以存放多少行数据

这里我们假设 B+ 树的深度为 2

B+树的存储总数据数 = 根节点指针数 * 单个叶子节点记录条数

那么指针数怎么计算?

假设主键ID为 bigint 类型,长度为 8 字节 ,而指针大小在InnoDB源码中设置为 6 字节,这样一共 14 字节。 那么如果一个页中能存放多少这样的组合,就代表有多少指针,即 16384 / 14 = 1170.那么可以算出,一棵高度为 2 的 B+ 树,可以存放 1170 * 16 = 18720 条这样的数据记录。 同理: 高度为3的B+树可以存放的行数 = 1170 * 1170 * 16 = 21902400

这里相信大家都很熟悉,因为千万级数据的存储只需要 3 层 B+树就可以了,查询数据的时候,每加载一页(page)就代表一次 IO。所以锁,根据主键 id 索引查询 3 次 IO 就可以找到目标结果了。

那对于一些需要走二级索引的复杂查询,通过二级索引查找记录最多需要花费多少次 IO 呢?

首先,从二级索引 B + 树中,根据 name 查找对应主键的 id

然后接着根据主键 id 从聚簇索引查找到对应的记录。

如上图所示,二级索引有3层,聚簇索引有3层,那么最多花费的IO次数是:3+3 = 6

聚簇索引默认是主键,如果表中没有定义主键,InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引,InnoDB 会隐式定义一个主键来作为聚簇索引。

这也是为什么InnoDB表必须要设置主键,并且推荐使用整型的自增主键。 InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上

# 🚇综合计算

实际项目中,每个表的结构设计都不一样,占用的存储空间大小也各不相等。如何计算不同的B+树深度下,一个表可以存储的记录条数? 这里我们利用 MySQL 库下面的 User 表来示例一下,讲解详细的计算过程:

  1. 查看表的状态信息
show table status like 'subject_info'\G
1

图中可以看到 user 表的行平均大小为 2730 字节

  1. 查看表结构
desc subject_info;
1

  1. 计算 B + 树的行数

● 单个叶子节点(页)中的记录数 = 16 K / 2730 = 5

● 非叶子节点能存放多少指针:16384 / 14 = 1170

● 如果树的高度为3,可以存放的记录行数 = 1170 * 1170 * 5 = 6844500

最近更新: 12/11/2023, 4:33:48 PM
编程导航   |