mysql B+树的索引一般有多少层


写在前面

这个问题在实际工作中可能作用不大,但是面试过程中可能会被问到,这就涉及到对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+树一般有几层?能容纳多少数据量?



文章作者: Alex
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Alex !
  目录