心态崩了，我怎么知道实际生产环境的 B+ 树索引有多少层？

发表于 3年以前 | 总阅读数：366 次

Q：在实际生产环境中，InnoDB 中一棵 B+ 树索引一般有多少层？可以存放多少行数据？

关于这个问题最近好像在牛客上经常看到，感觉没啥意义，可能主要考察的是对 B+ 索引的理解吧。先上答案：

A：一般是 2 ~ 3 层，可以存放约 两千万行 的数据。

前文说过，页是 InnoDB 磁盘管理的最小单位，在 InnoDB 存储引擎中，默认每个页的大小为 16KB。而页里面存放的东西就是一行一行的记录。

image-20210824093318336

假设一行数据的大小是 1k，那么一页就可以存放 16 行这样的数据。

众所周知，B+ 树的叶子节点存储真正的记录，而非叶子节点的存在是为了更快速的找到对应记录所在的叶子节点，所以可以简单理解为非叶子节点存放的是键值 + 指针。这里用指针来描其实述不是太准确，准确来说是页的偏移量，不过指针更好理解~

通过索引组织表的方式，数据行被存放在不同的页中。如下图所示：

假设我们要从上图这棵 B+ 树种找到主键是 20 这行数据 select * from table where id = 20;

首先找到 B+ 树的根节点，即存储的非叶子节点的页 page_number = 10，在该页上通过二分查找法以及指针定位到 id = 20 这行数据存在于 page_number = 12 这页上，然后同样的在这页上用二分查找即可快速定位 id = 20 这行记录。

说这些和文题不是很相关的话题，其实就是想要大家知道：页作为 InnoDB 磁盘管理的最小单位，不仅可以用来存放具体的行数据，还可以存放键值和指针。

回到文题，我们先从简单的入手，假设 B+ 树只有两层，即一个根节点和若干个叶子节点，如下图：

image-20210825095007784

那么对于这棵 B+ 树能够存放多少行数据，其实问的就是这棵 B+ 树的非叶子节点中存放的数据量，可以通过下面这个简单的公式来计算：

根节点指针数 * 每个叶子节点存放的行记录数

每个叶子节点存放的行记录数就是每页存放的记录数，由于各个数据表中的字段数量都不一样，这里我们就不深究叶子节点的存储结构了，简单按照一行记录的数据大小为 1k 来算的话（实际上现在很多互联网业务数据记录大小通常就是 1K 左右），一页或者说一个叶子节点可以存放 16 行这样的数据。

那么 B+ 数的根节点（非叶子节点）能够存储多少数据呢？

非叶子节点里面存的是主键值 + 指针，我们假设主键的类型是 BigInt，长度为 8 字节，而指针大小在 InnoDB 中设置为 6 字节，这样一共 14 字节。

为了方便行文，这里我们把一个主键值 + 一个指针称为一个单元，这样的话，一页或者说一个非叶子节点能够存放 16384 / 14=1170 个这样的单元。

也就是说一个非叶子节点中能够存放 1170 个指针，即对应 1170 个叶子节点，所以对于这样一棵高度为 2 的 B+ 树，能存放 1170（一个非叶子节点中的指针数） * 16（一个叶子节点中的行数）= 18720 行数据。

当然，这样分析其实不是很严谨，按照《MySQL 技术内幕：InnoDB 存储引擎》中的定义，InnoDB 数据页结构包含如下几个部分：

想要深究的小伙伴可以去看书中的 4.4 章节，这里我就不再多分析了。

OK，分析完高度为 2 的 B+ 树，同样的道理，我们来看高度为 3 的：

根页（page10）可以存放 1170 个指针，然后第二层的每个页（page:11,12,13）也都分别可以存放1170个指针。这样一共可以存放 1170 * 1170 个指针，即对应的有 1170 * 1170 个非叶子节点，所以一共可以存放 1170 * 1170 * 16 = 21902400 行记录。