mysqlbtree每个节点怎么存储_开门见山的问MySQL：InnoDB一棵B+树可以存放多少行数据？你如何作答？...

前言

开门见山&＃xff0c;面对这样一个问题&＃xff0c;你将如何作答&＃xff1f;

1千万&＃xff0c;2千万&＃xff0c;或者上亿条数据&＃xff1f;具体的答案不重要&＃xff0c;当然肯定也不会是一个固定的数目&＃xff0c;今天我们就一起来探讨探讨这个问题。

InnoDB是一种兼顾了高可靠性和高性能的通用存储引擎&＃xff0c;它拥有诸多功能和特性&＃xff0c;体系结构和工作原理也比较复杂。真要讲明白说透彻&＃xff0c;不是一两篇博文能够实现的&＃xff0c;也不是今天的重点。

所以&＃xff0c;本文不涉及太多的原理性知识&＃xff0c;咱们就针对开头提出的问题&＃xff0c;通过熟悉一些基本的概念和利用工具来验证&＃xff0c;对这个问题做到心中有数。

文件结构

我们知道&＃xff0c;InnoDB引擎是支持事务的&＃xff0c;所以表里的数据肯定都是存储在磁盘上的。如果在test数据库下创建两个表&＃xff1a;t1和t2&＃xff0c;那么在相应的数据目录下就会发现两个文件。

[root&＃64;localhost test]# ls

db.opt t1.frm t1.ibd t2.frm t2.ibd

[root&＃64;localhost test]# pwd

/var/lib/mysql/test

其中&＃xff0c;frm文件是表结构信息&＃xff0c;ibd文件是表中的数据。

表结构信息包含MySQL表的元数据(例如表定义)的文件&＃xff0c;比如表名、表有多少列、列的数据类型啥的&＃xff0c;不重要&＃xff0c;我们先不管&＃xff1b;

ibd文件存储的是表中的数据&＃xff0c;比如数据行和索引。这个文件比较重要&＃xff0c;它是今天我们的重点研究对象。

我们说&＃xff0c;MySQL表里的数据都是存放在磁盘上的。那么在磁盘上&＃xff0c;最小单元是扇区&＃xff0c;每个扇区可以存放512个字节的数据&＃xff1b;操作系统中最小单元是块(block)&＃xff0c;最小单位是4kb。

在Windows系统中&＃xff0c;我们可以通过fsutil fsinfo ntfsinfo c:来查看。

C:\Windows\system32>fsutil fsinfo ntfsinfo c:

NTFS 卷序列号: 0x78f40b2cf40aec66

NTFS 版本: 3.1

LFS 版本: 2.0

扇区数量: 0x000000001bcb6fff

簇总数: 0x0000000003796dff

可用簇: 0x0000000000a63a03

保留总数: 0x00000000000017c3

每个扇区字节数: 512

每个物理扇区字节数: 4096

每个簇字节数: 4096

每个 FileRecord 段字节数: 1024

每个 FileRecord 段簇数: 0

在Linux系统上&＃xff0c;可以通过以下两个命令查看&＃xff0c;这取决于文件系统的格式。

xfs_growfs /dev/mapper/centos-root | grep bsize

tune2fs -l /dev/mapper/centos-root | grep Block

我们拉回来接着说MySQL&＃xff0c;InnoDB存储引擎它也是有最小存储单位的&＃xff0c;叫做页(Page)&＃xff0c;默认大小是16kb。

我们新创建一个表 t3&＃xff0c;里面任何数据都没有&＃xff0c;我们来看它的ibd文件。

[root&＃64;localhost test]# ll

总用量 18579600

-rw-r-----. 1 mysql mysql 67 11月 30 20:59 db.opt

-rw-r-----. 1 mysql mysql 12756 12月 7 21:10 t1.frm

-rw-r-----. 1 mysql mysql 13077839872 12月 7 21:37 t1.ibd

-rw-r-----. 1 mysql mysql 8608 12月 7 21:43 t2.frm

-rw-r-----. 1 mysql mysql 5947523072 12月 7 21:52 t2.ibd

-rw-r-----. 1 mysql mysql 12756 12月 8 21:02 t3.frm

-rw-r-----. 1 mysql mysql 98304 12月 8 21:02 t3.ibd

不仅是t3&＃xff0c;我们看到&＃xff0c;任何表的ibd文件大小&＃xff0c;它永远是16k的整数倍。理解这个事非常重要&＃xff0c;MySQL从磁盘加载数据是按照页来读取的&＃xff0c;即便你查询一条数据&＃xff0c;它也会读取一页16k的数据出来。

聚簇索引

数据库表中的数据都是存储在页里的&＃xff0c;那么这一个页可以存放多少条记录呢&＃xff1f;

这取决于一行记录的大小是多少&＃xff0c;假如一行数据大小是1k&＃xff0c;那么理论上一页就可以放16条数据。

当然&＃xff0c;查询数据的时候&＃xff0c;MySQL也不能把所有的页都遍历一遍&＃xff0c;所以就有了索引&＃xff0c;InnoDB存储引擎用B&＃43;树的方式来构建索引。

聚簇索引就是按照每张表的主键构造一颗B&＃43;树&＃xff0c;叶子节点存放的是整行记录数据&＃xff0c;在非叶子节点上存放的是键值以及指向数据页的指针&＃xff0c;同时每个数据页之间都通过一个双向链表来进行链接。

如上图所示&＃xff0c;就是一颗聚簇索引树的大致结构。它先将数据记录按照主键排序&＃xff0c;放在不同的页中&＃xff0c;下面一行是数据页。上面的非叶子节点&＃xff0c;存放主键值和一个指向页的指针。

当我们通过主键来查询的时候&＃xff0c;比如id&＃61;6的条件&＃xff0c;就是通过这颗B&＃43;树来查找数据的过程。它先找到根页面(page offset&＃61;3)&＃xff0c;然后通过二分查找&＃xff0c;定位到id&＃61;6的数据在指针为5的页上。然后进一步的去page offset&＃61;5的页面上加载数据。

在这里&＃xff0c;我们需要理解两件事&＃xff1a;

上图中B&＃43;树的根节点(page offset&＃61;3)&＃xff0c;是固定不会变化的。只要表创建了聚簇索引&＃xff0c;它的根节点页号就被记录到某个地方了。还有一点&＃xff0c;B&＃43;树索引本身并不能直接找到具体的一条记录&＃xff0c;只能知道该记录在哪个页上&＃xff0c;数据库会把页载入到内存&＃xff0c;再通过二分查找定位到具体的记录。

现在我们知道了InnoDB存储引擎最小存储单元是页&＃xff0c;在B&＃43;树索引结构里&＃xff0c;页可以放一行一行的数据(叶子节点)&＃xff0c;也可以放主键&＃43;指针(非叶子节点)。

上面已经说过&＃xff0c;假如一行数据大小是1k&＃xff0c;那么理论上一页就可以放16条数据。那一页可以放多少主键&＃43;指针呢&＃xff1f;

假如我们的主键id为bigint类型&＃xff0c;长度为8字节&＃xff0c;而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16384 / 14 &＃61; 1170&＃xff0c;就是说一个页上可以存放1170个指针。

一个指针指向一个存放记录的页&＃xff0c;一个页里可以放16条数据&＃xff0c;那么一颗高度为2的B&＃43;树就可以存放 1170 * 16&＃61;18720 条数据。同理&＃xff0c;高度为3的B&＃43;树&＃xff0c;就可以存放 1170 * 1170 * 16 &＃61; 21902400 条记录。

理论上就是这样&＃xff0c;在InnoDB存储引擎中&＃xff0c;B&＃43;树的高度一般为2-4层&＃xff0c;就可以满足千万级数据的存储。查找数据的时候&＃xff0c;一次页的查找代表一次IO&＃xff0c;那我们通过主键索引查询的时候&＃xff0c;其实最多只需要2-4次IO就可以了。

那么&＃xff0c;实际上到底是不是这样呢&＃xff1f;我们接着往下看。

页的类型

在开始验证之前&＃xff0c;我们不仅需要了解页&＃xff0c;还需要知道&＃xff0c;在InnoDB引擎中&＃xff0c;页并不是只有一种。常见的页类型有&＃xff1a;

数据页&＃xff0c;B-tree Node&＃xff1b;

undo页&＃xff0c;undo Log Page&＃xff1b;

系统页&＃xff0c;System Page&＃xff1b;

事务数据页&＃xff0c;Transaction system Page&＃xff1b;

插入缓冲位图页&＃xff0c;Insert Buffer Bitmap&＃xff1b;

插入缓冲空闲列表页&＃xff0c;Insert Buffer Free List&＃xff1b;

未压缩的二进制大对象页&＃xff0c;Uncompressed BLOB Page&＃xff1b;

在这里我们重点来看 B-tree Node&＃xff0c;我们的索引和数据就放在这种页上。既然有不同的页类型&＃xff0c;我们怎么知道当前的页属于什么页呢&＃xff1f;

那么我们就需要大概了解下数据页的结构&＃xff0c;数据页由七个部分组成&＃xff0c;每个部分都有不同的含义。

File Header&＃xff0c;文件头&＃xff0c;固定38字节&＃xff1b;

Page Header&＃xff0c;页头&＃xff0c;固定56字节&＃xff1b;

Infimum &＃43; supremum&＃xff0c;固定26字节&＃xff1b;

User Records&＃xff0c;用户记录&＃xff0c;即行记录&＃xff0c;大小不固定&＃xff1b;

Free Space&＃xff0c;空闲空间&＃xff0c;大小不固定&＃xff1b;

Page Directort&＃xff0c;页目录&＃xff0c;大小不固定&＃xff1b;

File Trailer&＃xff0c;文件结尾信息&＃xff0c;固定8字节。

其中&＃xff0c;File Header用来记录页的一些头信息&＃xff0c;共占用38个字节。在这个头信息里&＃xff0c;我们可以获取到该页在表空间里的偏移值和这个数据页的类型。

接下来是Page Header&＃xff0c;它记录的是数据页的状态信息&＃xff0c;共占用56个字节。在这一部分&＃xff0c;我们可以获取到两个重要的信息&＃xff1a;该页中记录的数量和当前页在索引树的层级&＃xff0c;其中0x00代表叶子节点&＃xff0c;比如聚簇索引中的叶子节点放的就是整行数据&＃xff0c;它总是在第0层。

验证

前面我们已经说过&＃xff0c;ibd文件就是表数据文件。这个文件会随着数据库表里数据的增长而增长&＃xff0c;不过它始终会是16k的整数倍。里面就是一个个的页&＃xff0c;那我们就可以一个一个页的来解析&＃xff0c;通过文件头可以判断它是什么页&＃xff0c;找到 B-tree Node&＃xff0c;就可以看到里面的 Page Level&＃xff0c;它的值&＃43;1&＃xff0c;就代表了当前B&＃43;树的高度。

我们现在就来重新创建一个表&＃xff0c;为了使这个表中的数据一行大小为1k&＃xff0c;我们设置几个char(255)的字段即可。

CREATE TABLE &＃96;t5&＃96; (

&＃96;id&＃96; bigint(8) NOT NULL,

&＃96;c1&＃96; char(245) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c2&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c3&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c4&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

PRIMARY KEY (&＃96;id&＃96;)

) ENGINE&＃61;InnoDB DEFAULT CHARSET&＃61;utf8mb4;

然后笔者写了一个存储过程&＃xff0c;用来批量插入数据用的&＃xff0c;为了加快批量插入的速度&＃xff0c;笔者还修改了innodb_flush_log_at_trx_commit&＃61;0&＃xff0c;切记生产环境可不要这样玩。

BEGIN

DECLARE i int DEFAULT 0;

select ifnull(max(id),0) into i from t5;

set i &＃61; i&＃43;1;

WHILE i <&＃61; 100000 DO

insert into t5(id)value(i);

set i &＃61; i&＃43;1;

END WHILE;

END

innodbPageInfo.jar是笔者用Java代码写的一个工具类&＃xff0c;用来输出ibd文件中&＃xff0c;页的信息。

-path 后面是文件的路径&＃xff0c;-v 是否显示页的详情信息&＃xff0c;0是 1否。

上面我们创建了t5这张表&＃xff0c;一条数据还没有的情况下&＃xff0c;我们看一下这个ibd文件的信息。

[root&＃64;localhost innodbInfo]# java -jar innodbPageInfo.jar -path /var/lib/mysql/test/t5.ibd -v 0

page offset 00000000,page type

page offset 00000001,page type

page offset 00000002,page type

page offset 00000003,page type ,page level <0000>

page offset 00000000,page type

page offset 00000000,page type

数据页总记录数:0

Total number of page: 6

Insert Buffer Bitmap: 1

File Segment inode: 1

B-tree Node: 1

File Space Header: 1

Freshly Allocated Page: 2

[root&＃64;localhost innodbInfo]#

t5表现在没有任何数据&＃xff0c;它的ibd文件大小是98304&＃xff0c;也就是说一共有6个页。其中第四个页(page offset 3)是数据页&＃xff0c;page level等于0&＃xff0c;代表该页为叶子节点。因为目前还没有数据&＃xff0c;可以认为B&＃43;树的索引只有1层。

我们接着插入10条数据&＃xff0c;这个page level还是为0&＃xff0c;B&＃43;树的高度还是1&＃xff0c;这是因为一个页大约能存放16条大小为1k的数据。

page offset 00000003,page type ,page level <0000>

数据页总记录数:10

Total number of page: 6

当我们插入15条数据的时候&＃xff0c;一个页就放不下了&＃xff0c;原本为新分配的页(Freshly Allocated Page)就会变成数据页&＃xff0c;原来的根页面(page offset&＃61;3)就会升级成存储目录项的页。offset 04 和 05就变成了叶子节点的数据页&＃xff0c;所以现在整个B&＃43;树的高度为2。

page offset 00000003,page type ,page level <0001>

page offset 00000004,page type ,page level <0000>

page offset 00000005,page type ,page level <0000>

数据页总记录数:15

Total number of page: 6

继续插入10000条数据&＃xff0c;我们再来看一下B&＃43;树高的情况。当然现在信息比较多了&＃xff0c;我们把输出结果写到文件里。

java -jar innodbPageInfo.jar -path /var/lib/mysql/test/t5.ibd -v 0 > t5.txt

截取部分结果如下&＃xff1a;

[root&＃64;localhost innodbInfo]# vim t5.txt

page offset 00000003,page type ,page level <0001>

page offset 00000004,page type ,page level <0000>

page offset 00000005,page type ,page level <0000>

page offset 00000000,page type

数据页总记录数:10000

Total number of page: 1216

B-tree Node: 716

可以看到&＃xff0c;1万条1k大小的记录&＃xff0c;一共用了716个数据页&＃xff0c;根页面显示的树高还是2层。

前面我们计算过&＃xff0c;2层的B&＃43;树理论上可以存放18000条左右&＃xff0c;笔者测试大约13000条数据左右&＃xff0c;B&＃43;树就会成为3层了。

page offset 00000003,page type ,page level <0002>

数据页总记录数:13000

Total number of page: 1472

B-tree Node: 933

原因也不难理解&＃xff0c;因为每个页不可能只放数据本身。

首先每个页都有一些固定的格式&＃xff0c;比如文件头部、页面头部、文件尾部这些&＃xff0c;我们的数据放在用户记录这部分里的&＃xff1b;

其次&＃xff0c;用户记录也不只放数据行&＃xff0c;每个数据行还有一些其他标记&＃xff0c;比如是否删除、最小记录、记录数、在堆中的位置信息、记录的类型、下一条记录的相对位置等等&＃xff1b;

另外&＃xff0c;MySQL参考手册中也有说到&＃xff0c;InnoDB会保留页的1/16空闲&＃xff0c;以便将来插入或者更新索引使用&＃xff0c;如果主键id不是顺序插入的&＃xff0c;那可能还不是1/16&＃xff0c;会占用更多的空闲空间。

总之&＃xff0c;我们理解一个页不会全放数据就行了。所以&＃xff0c;实测跟理论上不一致也是完全正常的&＃xff0c;因为上面的理论没有排除这些项。

接着来&＃xff0c;我们再插入1000万条数据&＃xff0c;现在ibd文件已经达到11GB。

page offset 00000003,page type ,page level <0002>

数据页总记录数:10000000

Total number of page: 725760

B-tree Node: 715059

我们看到&＃xff0c;1千万条数据&＃xff0c;数据页已经有71万个&＃xff0c;B&＃43;树的高度还是3层&＃xff0c;这也就是说几万条数据和一千万条数据的查询效率基本上是一样的。 比如我们现在根据主键ID查询一条数据&＃xff0c;select * from t5 where id &＃61; 6548215; &＃xff0c;查询时间显示用了0.010秒。

什么时候会到4层呢&＃xff1f;大概在1300万左右&＃xff0c;B&＃43;树就会增加树高到4层。

什么时候会到5层呢&＃xff1f;笔者没测试出来&＃xff0c;因为插入到5000万条数据的时候&＃xff0c;ibd数据文件大小已经55G了&＃xff0c;虚拟机已经空间不足了。。

page offset 00000003,page type ,page level <0003>

数据页总记录数:50000000

B-tree Node: 3575286

即便是5000万条数据&＃xff0c;我们通过主键ID查询&＃xff0c;查询时间也是毫秒级的。

理论上要达到十亿 - 百亿行数据&＃xff0c;树高才能到5层。如果有小伙伴用这种方法&＃xff0c;测试出来5层高的数据&＃xff0c;欢迎在评论区留言&＃xff0c;让我看看。

另外&＃xff0c;朋友们有没有意识到一个问题&＃xff1f;其实影响B&＃43;树树高的因素&＃xff0c;不仅是数据行&＃xff0c;还有主键ID的长度。我们上面的测试中&＃xff0c;ID的类型是bigint(8)&＃xff0c;在其他字段长度均不变的情况下&＃xff0c;我们把ID的类型改为int(4)&＃xff0c;相同的树高就会容纳更多的数据&＃xff0c;因为它单个页能承载的指针数变多了。

CREATE TABLE &＃96;t6&＃96; (

&＃96;id&＃96; int(4) NOT NULL,

&＃96;c1&＃96; char(245) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c2&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c3&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

&＃96;c4&＃96; char(255) NOT NULL DEFAULT &＃39;1&＃39;,

PRIMARY KEY (&＃96;id&＃96;)

) ENGINE&＃61;InnoDB DEFAULT CHARSET&＃61;utf8mb4;

针对t6这张表&＃xff0c;我们插入16000条数据&＃xff0c;然后输出一下页面信息。

page offset 00000003,page type ,page level <0001>

数据页总记录数:16000

B-tree Node: 1145

我们来看&＃xff0c;如果按照主键ID类型bigint(8)来测试&＃xff0c;13000条数据的时候&＃xff0c;树高就已经是3了&＃xff0c;现在改为int(4)&＃xff0c;16000条数据&＃xff0c;树高依然还是2层。尽管数据页(B-tree Node)数量还是那么多&＃xff0c;变化并不大&＃xff0c;但是它不影响树高。

ok&＃xff0c;看到这里&＃xff0c;相信朋友们对开头提出的问题已经有自己的答案了&＃xff0c;如果你也跟着试一遍&＃xff0c;理解可能会更加深入。

看到这&＃xff0c;还有道经典的面试题&＃xff1a;为什么MySQL的索引要使用B&＃43;树而不是其它树形结构?比如B树&＃xff1f;

简单来说&＃xff0c;其中有一个原因就是B&＃43;树的高度比较稳定&＃xff0c;因为它的非叶子节点不会保存数据&＃xff0c;只保存键值和指针的情况下&＃xff0c;一个页能承载大量的数据。你想啊&＃xff0c;B树它的非叶子节点也会保存数据的&＃xff0c;同样的一行数据大小是1kb&＃xff0c;那么它一页最多也只能保存16个指针&＃xff0c;在大量数据的情况下&＃xff0c;树高就会速度膨胀&＃xff0c;导致IO次数就会很多&＃xff0c;查询就会变得很慢。

源码地址

本文的innodbPageInfo.jar代码是笔者参考 MySQL技术内幕(InnoDB存储引擎)一书中的工具包&＃xff0c;书里作者是用Python写的&＃xff0c;所以笔者在这里用Java重新实现了一遍。

朋友们可以拿这个工具看一看&＃xff0c;自己认为较大的表&＃xff0c;它的B&＃43;树索引到底有几层&＃xff1f;

最后

大家看完有什么不懂的可以在下方留言讨论.

谢谢你的观看。

觉得文章对你有帮助的话记得关注我点个赞支持一下&＃xff01;