问题

今天来研究一个问题:

在InnoDB中一个3层B+树最多大概可以存放多少行数数据??

基础要点

先明确几个基本的要点。

  1. 在innodb存储引擎里面,最小的存储单元是页(page),一个页的大小时16KB。
  2. B+树的非叶子节点存放索引,不存放数据(这里的数据指的是表中的行记录数据),叶子节点才会存放数据。

上一张B+树的图,有个清晰的概念:

假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。那如果想查找某个页里面的一个数据的话,得首先找到他所在的页,但是如果按照普通方法,也就是遍历的话,就得一个页一个页的查找,显然太慢了。innodb存储引擎我们都知道使用B+树的结构来组织数据。如果是在主键上建立的索引就是聚簇索引,即只有在叶子节点才存储行数据,而非叶子节点里面的内容其实是键值和指向数据页的指针。

这里B+树的每一个节点都是一个页,比如根节点就是page:3(在InnoDB的表空间文件中,约定page number为3的代表主键索引的根页),存储的就是主键值和页指针。

比如执行select * from user where id=5;整个过程是:

首先找到根页,这里是page:3,然后利用二分法中间id=7,大于5向左,4<5,所以找到了page:5的指针,进入page:5。然后再利用二分查找在这一页里面查找id=5的数据。

二层B+树分析

基于上面的知识,我们首先来计算二层的B+树能够存放多少数据。

第一层存放的都是索引+指针(指针指向的是第二层的page页),我们假设 索引占用空间+指针占用空间=16字节,假设一行记录占用的空间是1KB,那么我们来看:

第一层最大能够存放多少个page指针呢?

页的大小/(索引占用空间+指针占用空间),也就是最多存放16KB/16B=1024个page指针,也就是第二层最多有1024个page页。

第二层的每个page页里面都存放的是行记录数据,一行记录1KB,一个page页大小16KB,那么每个page页最多存放16KB/1KB=16行记录。

所以二层B+树最多存放的数据记录数是:(16KB / 16B) X ( 16KB / 1KB) = (16 X 1024 / 16) X (16 X 1024 /1024) =1024 X 16=16384行记录

三层B+树分析

我们再来算一算三层B+树能够存放多少行数据记录。

和上面的计算方式类似,

首先第一层最多存放 16 X 1024 /16 个page指针(也就是第二层的page页的个数);

第二层的page页共有 16 X 1024 /16 个,每个page页也是 16 X 1024 /16 个page指针,所以第二层共有(16 X 1024 /16 )X (16 X 1024 /16 ) 个page指针(也就是第三层的page页的数量);

第三层存放的是数据(行记录),每个page页最多存放16X1024 /1024 = 16行 记录,所以第三层总共存放的行记录数是(16 X 1024 /16 )X (16 X 1024 /16 ) X16 。

这个最后算出来是16777216,接近2千万,也就是说一个 三层的B+树能够存放的数据是千万级别了。

参考资料

【MySQL】面试题之:在InnoDB中一个3层B+树最多大概可以存放多少行数数据??