Innodb的B+树索引到底能存多少数据

Innodb的B+树能存多少数据

Innodb的数据组织的最小单位是page，默认情况下，page的大小为16K。

索引B+树的组织方式是：主键索引树是按照聚簇索引的方式，即叶子节点存数据，非叶子节点存线索，也就是说，一张Innodb表一定会有一棵主键索引树。并且非叶子节点的大小保持相等等于16K(为了IO方便，一次IO从磁盘读取一个page的大小，写入的时候也是一次IO写入一个page的大小)。所以有了这个，B+树上的节点的大小就是确定的，就是16K了，而B+树是一个m-n排序树，所以一个节点就是主键ID+指针(指向孩子节点的指针)构成的。

如下就是一个只有2层的B+树示意图：

1. 非叶子节点：存的就是主键索引的线索。
2. 叶子节点：注意并不是所有的行数据都在叶子节点上，只是父节点中线索指向的那些节点在树上，如上图，两个灰色的其实就不再树上。

所以行数据的组织方式是以page为最小单位，按照链表的方式来组织的。非叶子节点上的线索指向的叶子节点就算是在树上。而对于也字节点，一个page内是存放了多条行记录的，这多条记录是按照索引从小大大排序的，所以查询的过程首先是根据B+树索引定位到具体的page，然后page内使用二分法去找具体的行数据。

所以，叶子节点是个链表，理论上可以无限大，但是非叶子节点就是一个16k大小的page，所以对于一棵树能存多少数据，主要就看非叶节点能存下多少个[主键ID+指针]了。

ps:一个节点有多少个[主键ID+指针]，其实就是m树的m是多大了。

下面以一个高度=2，且主键ID是一个bigint(8字节)来分析可以存下多少数据(这个假设是有意义的，在绝大部分主键id都是一个自增的bigint)。

Innodb中一个指针是6字节长度。所以[主键ID+指针]总共就占14字节。所以一个16K大小的节点可以存下的[主键ID+指针]个数=16K/14=16384/14=1170，也就是说一个高度=2的B+树可以放下1170个叶子节点，即1170个用于存放行数据的page，即可以存放的行数据的大小=1170*16K=18720K=18M，准确的说这是树上的，还有很多不在树上的，所以实际能放下的数据不止1.8M。

ps:一个page内还有一些其他的数据，如next指针，LSN等，所以说一个page的16K不完全都拿来存行数据的。

如果下面我们分析高度=3，即有两层非叶子节点的B+树，能存放多少数据。根节点的16k的page可以存放16k/14=1170个[主键ID+指针]，即第二层就可以有1170个page。所以总共树上可以放的叶子节点的个数=1170*1170=1368900，所以能放下的数据=1368900*16K=21902400K=21G。同理，因为不是所有的行数据都在树上，所以高度=3的B+树不止放下21G的数据的。

再来，看下高度=4的，那么树上可以存下的叶子节点=1170*1170*1170=1601613000个，所以能存下的数据=1601613000*16K=25.6T。同理，实际存下的数据是可以不止这个量的。

所以，在实际中，绝大部分的表的索引树的高度都不会超过4。

ps：曾经遇到一个问题，聚簇索引叶子节点存数据，非叶子节点存索引，为什么这么设计，非叶子节点也存数据可不可以

我当时的回答：没必要，如果存了，确实能满足查询这个而需求，但是没必要，而且索引会加载到内存，如果非叶子节点放数据，那么会占用大量内存。

然后我将这个问题抛给另外一个大佬：大佬大概的说法是，影响读写，因为如果将非叶子节点存数据，那么一次IO读取的数据是有限的，影响性能。

我们现在来回答这个问题：大佬的回答其实是没问题的，只是跟IO没关系。如果非叶子节点存数据，那么一个节点能存下的数据就会少很多，对于一些大表，一个page都放不下一行数据。所以这种情况，势必会增大树的高度。一个极端情况，一个page只能存下一行记录，那么B+树其实就退化成链表了，如果我们想要查的数据在最后面，想想这个效率。如果总共有n条数据，那么就需要n次IO，如果是这样，这个系统几乎是没法使用的，数据量稍微一大，就没法搞了，而且性能非常不稳定。而且，当一个page放不下一行的时候，还面临如何拆分存储的问题，复杂度也更高了。

说到这，追问问题就来了，叶子节点存行数据，如果一行特别大怎么搞？第一：首先mysql一张表支持的字段数是有限的，第二：如若是大字段，如text，blog，varchar(很大)，实际存储在树上的，只是前k个字节(k的具体值忘了)。另外对于字符串类型的字段，mysql是支持前缀索引的 ，现在也大概明白为啥要这么支持了吧，我个人觉得就是mysql本身是有这个限制的(page的大小限制)，那么对于这种大字段，需要让使用者合理的去使用提供的功能。

ps：任何组件，任何框架都有它适合的场景，以及最佳实践方式，我们要做的就是去发现它的限制，以最佳实践的方式去使用他，这一点很重要，没有一个框架提供一个银弹解决方案的，一定要有取舍，取其长避其短。举个例子，mysql也支持倒排索引，但是你真的要用mysql作全文搜搜，Elasticsearch不香么？对于分页from+size的方式会有身份也的问题，比如es就有默认1w的限制，但是对于一个搜索功能，如果前1w条召回的记录都不能满足你的要求，你的搜索排序得由多不准啊，而且正常人有耐心给你翻1w行，如果你要杠精的说黑客？这不正是1w条限制的原因么，这是框架的一个自我保护机制啊。如果你要继续杠，老子要数据迁移，咋整，大佬给你想到了，scroll不香么。同样的，mysql的limit分页的问题不是一样的么，如果这不好理解，分库分表的分页就很明显了

B+树的高度

上面分析一个B+树能存下多少数据的时候，其实我们都是假设了树的高度。那么问题来了，Innodb中，树的高度是怎么确定的呢？

在Innodb中，是不能直接设定树的高度，或者m树的m的大小的，但是自mysql5.7后，提供了一个设定page大小的参数innodb_page_size，默认值是16K。

我们可以通过来改变page的大小来简介改变m树的m的大小。而page的大小也会间接影响到树的高度，比如我们现在要存20G大小的数据，那么page=16K和page=4K，树的高度是不一样的。换句话说，树的高度是根据你要存下的数据是多少来决定的。

另外这篇文章解释了一些背景以及作了一些实验：https://mp.weixin.qq.com/s/ceMTuWeL5DGQ2g-XjcEj0A