故事要从多年前说起。想必大家都听说过数据库单表推荐最大2kw条数据的说法。如果超过，性能会下降得更厉害。巧合的是。我也听说过。但是我不接受它的建议，干脆单表加载1亿条数据。这时，我们组的新实习生看到后，天真地问我：“不是建议单只表最高2000万吗？为什么这只表1亿不分库分表？”？”我能说我懒吗？当初设计的时候，没想到这块表能涨这么快。..我不能。说出来等于承认自己是开发组的毒瘤。虽然我是，但我不能承认。我觉得自己如坐针毡，如芒刺在背，如刺在喉咙。一波骚乱开始了。“我这样做很有意义。”“虽然这张表很大，但是你有没有发现它的查询速度其实非常快？”“这2kw是一个建议值，我们看看这2kw是怎么来的。”数据库单表最大行数是多少？我们先来看看理论上单表的最大行数。建表的SQL是这样写的，CREATETABLE`user`(`id`int(10)unsignedNOTNULLAUTO_INCREMENTCOMMENT'primarykey',`name`varchar(100)NOTNULLDEFAULT''COMMENT'name',`age`int(11)NOTNULLDEFAULT'0'COMMENT'age',PRIMARYKEY(`id`),KEY`idx_age`(`age`))ENGINE=InnoDBAUTO_INCREMENT=100037DEFAULTCHARSET=utf8;其中id是主键。主键本身是唯一的，也就是说主键的大小可以限制表的上限。如果主键声明为int大小，也就是32位，可以支持2^32-1，也就是21亿左右。如果是bigint，就是2^64-1，但是这个数太大了，一般在达到这个限制之前磁盘是承受不住的。变得离谱。如果我声明主键为tinyint，一个字节，8位，最大为2^8-1，也就是255。CREATETABLE`user`(`id`tinyint(2)unsignedNOTNULLAUTO_INCREMENTCOMMENT'primarykey',`name`varchar(100)NOTNULLDEFAULT''COMMENT'name',`age`int(11)NOTNULLDEFAULT'0'COMMENT'age',PRIMARYKEY(`id`),KEY`idx_age`(`age`))ENGINE=InnoDBAUTO_INCREMENT=0DEFAULTCHARSET=utf8;如果我想插入一个id=256的数据，就会报错。mysql>INSERTINTO`tmp`(`id`,`name`,`age`)VALUES(256,'',60);ERROR1264(22003):Outofrangevalueforcolumn'id'atrow1is说，tinyint主键限制表中最多255条数据。除了主键，还有哪些因素会影响行数呢？索引的结构在索引内部使用了一个B+树。这也是一只老八股，想必大家都心知肚明。为了不让大家对丑有太强的评判疲劳，今天我试着从另一个角度给大家讲讲这件事情。页面的结构假设我们有这样一张用户数据表。user表，其中id是唯一的主键。这看起来像一行数据，为了方便，我们稍后将它们称为记录。这个表看起来像一个excel表。excel数据是硬盘上的一个xx.excel文件。上面的user表数据在硬盘上其实也是类似的，都是放在user.ibd文件下的。意思就是user表的innodb数据文件，专业上也叫表空间。尽管在数据表中它们似乎彼此相邻。但实际上，它们在user.ibd中被分成了很多小数据页，每个大小为16k。类似下面的。ibd文件里面有大量的页面。让我们聚焦透视并将其放在页面上。整页16k，不大，但是这么多条记录，一页肯定放不下，所以会分成很多页。而且16k总不能全部用来录音吧？因为记录被分成很多份，放在很多页中，为了唯一标识是哪一页，需要引入页码（其实就是一个表空间的地址偏移量）。同时，为了关联这些数据页，引入前后指针指向前后页。这些都添加到标题中。需要读写页，16k不小，写到一半可能电源线被拔掉，所以为了保证数据页的正确性，还引入了校验码。这被添加到页脚。剩下的空间用来放我们的记录。但是，如果记录的行数较多，进入页面时逐条遍历效率不高，所以会为这些数据生成一个页面目录，具体实现细节并不重要。只需要知道它可以通过二分查找将查找效率从O(n)变为O(lgn)。从页到索引的页结构如果我们要查一条记录，可以把表空间的每一页都捞出来，然后再把里面的记录捞出来，判断是不是我们要找的。当行数较少时，这样做没有错。行数越大，性能越慢，所以为了加快查找速度，我们可以在每个数据页中选择主键id最小的记录，只需要它们的主键id和页码他们所在的页面。形成一条新记录，放入新生成的数据页中。这个新的数据页和之前的页结构一样，大小还是16k。但是为了和前面的数据页区别开来。页级信息添加到数据页中，从0开始向上计数。所以页面之间就有上下级的概念，如下。两层的B+树结构，在页面之间突然看起来像一棵倒挂的树。也就是我们常说的B+树索引。最底层，页级为0，也就是所谓的叶节点，其余的称为非叶节点。上面显示了一个两层树。如果数据较多，我们可以用类似的方法往上建一层。它变成了三层树。三层B+树结构现在我们可以使用这样一棵B+树来加速查询。例如。假设我们要查找行数据5。我们将从首页的记录开始。该记录包含主键id和页码（页地址）。看下图中的黄色箭头，左边最小的id是1，右边的最小id是7，如果id=5的数据存在，那肯定是在左边的箭头上。于是顺着记录的页地址走到6号数据页，再判断id=5>4，所以肯定是在右边的数据页，所以加载105号数据页。在数据页中找到id=5的数据行，完成查询。B+树查询过程中还有一点需要注意的是，上述页的页码不是连续的，它们在磁盘中不一定相邻。在这个过程中，查询了三个页面。如果这三个页面都在磁盘上（没有提前加载到内存中），那么最多需要三个磁盘IO查询才能加载到内存中。B+树携带的记录数从上面的结构可以看出，记录数据放在B+树的最后一个叶子节点。用于加速查询的索引数据放在非叶节点中。也就是说：对于同一个16k的页面，非叶子节点中的每一条数据都指向一个新的页面，新的页面有两种可能。如果是最后一个叶子节点，那么里面就有记录数据行。如果是非叶子节点，则继续循环指向新的数据页。假设非叶节点中指向其他内存页的指针个数为x。一个叶节点可以容纳的记录数为y。B+树的层数为z。总行数的计算方法，这个B+树中放置的行数据总量等于(x^(z-1))*y。如何计算x让我们回过头来看看数据页的结构。页结构的非叶子节点主要存放索引查询相关的数据，包括主键和指向页码。假定主键为bigint（8Byte），页码在源码中称为FIL_PAGE_OFFSET（4Byte），所以非叶子节点中的一条数据大约为12Byte。整个数据页16k，页首尾数据加起来大概128Byte，页目录估计占1k。剩下的15k除以12Byte等于1280，即可以指向x=1280页。我们常说的二叉树是指一个节点可以发散成两个新的节点。在一棵m叉树中，一个节点可以指向m个新节点。这种指向新节点的操作称为扇出。至于上面的B+树，竟然可以指向1280个新节点，很恐怖。可以说扇出度很高。y计算叶子节点和非叶子节点的数据结构是一样的，所以也假设剩下的15kb可以使用。真正的行数据放在叶节点中。假设一行数据为1kb，那么一页可以放y=15行。行总计计算回公式(x^(z-1))*y。已知x=1280，y=15。假设B+树是两层，那么z=2。那么(1280^(2-1))*15≈2w。假设B+树是三层，那么z=3。是(1280^(3-1))*15≈2.5kw。这个2.5kw就是我们常说的建议单表最大行数2kw的由来。毕竟再加一层，数据就有点离谱了。三层数据页最多对应三个磁盘IO，这也是合理的。行数超过1亿会不会很慢？假设单行数据使用1kb，那么一个数据页可以容纳15行数据。例如，如果我不需要单行那么多数据，则只使用250byte。那么单个数据页可以容纳60行数据。那也是三层B+树，单表支持的行数为(1280^(3-1))*60≈1亿。看我1亿条数据，其实是三层B+树。要在这棵B+树中找到一行数据，最多需要3次磁盘IO。所以不慢。这个在文章开头就很好的解释了，为什么我单表1亿，但是查询性能没有问题。B树携带的记录数说到这里，我们再多聊聊这个话题。我们都知道mysql的索引现在都是B+树，还有一种树和B+树很像，叫做B树，也叫B-树。它和B+树最大的区别是B+树只把数据表行数据放在最后一个叶子节点，而B树叶子节点和非叶子节点都放。因此，B-tree的结构类似这样：B-tree结构B-tree在非叶子节点上存储行数据，假设每个数据页还是16kb，每页剩下的15kb从中切掉从头到尾，一张数据表的行数据还占1kb，即使不考虑各种页指针，也只能放15条数据。数据页扇出明显减少。计算可承载总行数的公式也变成了几何级数。15+15^2+15^3+...+15^z其中z表示层数。为了存储大约2kw的数据，需要z>=6。也就是说树需要有6层，一次查询需要访问6个页面。假设这6页不连续，要查询其中一条数据，最坏情况下需要6次磁盘IO。同样的情况下，B+树可以存储2kw左右的数据，一次check最多3次磁盘IO。磁盘IO越多，速度越慢，两者性能差距略大。为此，B+树比B树更适合做mysql的索引。综上所述，B+树的叶子节点和非叶子节点的数据页都是16k，数据结构是一致的。区别在于叶子节点存储的是真正的行数据，而非叶子节点存储的是主键和下一页的地址。B+树一般有两到三层。由于其高扇出，三层可以支持2kw以上的数据，一次查询最多可以进行1到3次磁盘IO，性能还不错。存储同样量级的数据，B-tree比B+树层次更高，所以磁盘IO更多，所以B+树更适合作为mysql的索引。索引结构不会影响单表的最大行数，2kw只是一个推荐值。超过这个值可能会导致更高的B+树级别并影响查询性能。单表的最大值还受主键大小和磁盘大小的限制。参考资料《MYSQL内核：INNODB存储引擎 卷1》最后，虽然我单表塞了一亿条数据，但是这个操作的前提是我很清楚这不会对性能造成太大的影响。这一波解说，天衣无缝，无可挑剔。到目前为止，连我自己都被说服了。估计实习生也是。妈的，这该死的毒瘤居然有点“见多识广”。
