写在前面
这个问题在实际工作中可能作用不大,但是面试过程中可能会被问到,这就涉及到对B+树以及InnoDB页的了解。本文将分析这个问题。
答案
首先回答这个问题:一般是1-3层。
InnoDB页
在 MySQL 中我们的 InnoDB 页的大小默认是 16k,当然也可以通过参数设置。
在查找数据时一次页的查找代表一次 IO,所以通过主键索引查询通常只需要 1~3 次 IO 操作即可查找到数据。
一个非叶节点可容纳约1170个指针,这里假设一行记录数据大小为 1k,那么底层叶节点一页16k就能存16条记录。叶节点数 * 一个叶节点能存放的记录数 = 1170 * 16 = 18720条 记录数。
具体推导过程如图:
同理可得:高度为3的B+树能存的记录数为:1170117016=21902400,2190w条记录,约2000w条记录。
为什么MySQL用B+树而不用B树呢?
因为B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保存大量数据,只能增加树的高度,导致IO 操作变多,查询性能变低。
总结
- 一层的话,只能保存16条数据。一般表都不止16条数据。
- 二层的话,可以保存16*1170条数据,大概是2w条数据。
- 三层的话,可以保存1611701170条数据,大概是2kw条数据。所以绝大多数表的B+树都是二层或者三层。
- 四层,表的数据超过大概2kw条数据,B+索引层次就达到了4层,这就会影响性能,需要考虑分库分表。所以mysql表数据一般不要超过2kw条。
参考
[1] Innodb引擎中B+树一般有几层?能容纳多少数据量?