面试官问我为啥B+树一般都不超过3层？3层B+树能存多少数据？

我今天逛了一下CSDN，又发现了一条显眼的数据，大概是说3层B+树足以容纳2000w条数据。我当时就蒙了，3层对2000w，心想这B+树也太厉害了吧，由此勾起了我求知的欲望，我一定要搞明白他这2000w是怎么来的。

重中之重

MySQL的执行流程如下图

在两阶段提交的情况下，是怎么实现崩溃恢复的？

前提：binlog本身不具备crash-safe能力，所以InnoDB考虑到这一点，自己实现了redo log来具备这个能力。

关键点：在写入redo log和binlog时，都会顺便记录当前事务ID。

会有如下三种崩溃情况：

1、在写redo log之前崩溃，那么此时redo log和binlog都没有这个ID，是一致的情况，崩溃也没事。

2、在写redo log 的prepare阶段后崩溃，此时redo log有这个ID，会根据ID去binlog查找这个ID，这个时候肯定是没有的，那么就会执行回滚操作。

3、在写binlog后崩溃，那么此时在redo log和binlog都存在这个ID，只是在redo log里的标记是prepare，所以这个时候直接commit就行。

也就是说，在崩溃恢复时，只要redo log不是处于commit阶段，那么就拿着redo log中的这个事务ID去binlog中查找，找得到就提交，找不到就回滚。这样就能确保redo log与binlog的数据一致性。

 

SQL语句的执行顺序如下图

 

B+树结构

关于B+树的结构，我在之前的文章有讲过，在这里就不细说了，简而言之，B+树的分支非常多，而且每个非叶子节点只存主键值（主键索引）和指针，数据存在于叶子节点。

也就是说，磁盘的IO次数与树的高度是相同的。

3层B+树可以存多少数据？

进入正题，前面说了，3层B+树大概可以存2000w条数据，这个是咋算出来的呢？

在Innodb存储引擎里面，咱们最小存储单元是页，而一个页的大小默认是16KB。

也即代表B+树的每个节点可以存16KB数据，这里我们假设我们的一行数据大小是1K，那么我们一个节点就可以存16行数据。注意：我们真正的数据都是存在叶子节点的，所以这里是指叶子节点可以存放16行数据。

我们前面也说了，非叶子节点存放的是主键值与指针，所以这里假设主键类型为bigint，占用8Byte，指针可以设置为占用6Byte，总共就为14Byte，这样就可以算出一个节点大概可以存放多少个指针了（指针指向下一层节点），大概为16KB/14Byte=1170个。

由此，可以推算出，2层B+树的话，可以存放1170*16=18720行数据。3层B+树的话，可以存放1170*1170*16=21902400行数据，也就差不多2000w条数据了。

附加题

为啥不用B树？

因为B树的节点（无论是叶子节点还是非叶子节点），都会保存数据，所以相当于B+树的话，B树的非叶子节点能保存的指针就变少了，保存同等数据量的情况下，B树指针变少了就只能增加树的高度了，就会导致磁盘IO次数变多，从而影响性能。