B+树，深度何知？

Q：在具体工作环境中，InnoDB 中一棵 B  树数据库索引一般有多少层？能够 储放是多少行数据信息？

有关这个问题近期仿佛在牛客上常常见到，觉得没啥实际意义，很有可能关键调查的是对 B  数据库索引的解释吧。先上回答：

A：一般是 2 ~ 3 层，能够 储放约 2000万行 的数据信息。

前文写过，页是 InnoDB 磁盘管理的最小单位，在 InnoDB 储存模块中，默认设置 每一个页的尺寸为 16KB。而页里边放置的東西便是一行一行的纪录。

假定一行数据信息的高低是 1k，那麼一页就可以储放 16 行那样的数据信息。

大家都知道，B  树的叶子节点储存真实的纪录，并非叶子节点的出现是因为更迅速的寻找相匹配纪录所属的叶子节点，因此 能够 简易解释为非叶子节点储放的是键值   表针。这儿用表针来描实际上述并不是太精确，精确来讲是页的偏移，但是表针更强了解~

根据数据库索引机构表的方法，数据信息行被储存在不一样的页中。如下图所显示：

假定我们要从图中这棵 B  绿化植物寻找外键约束是 20 这行数据信息 select * from table where id = 20;

最先寻找 B  树的根节点，即储存的非叶子节点的页 page_number = 10，在此页上根据二分查找法及其表针精准定位到 id = 20 这行数据信息存有于 page_number = 12 这页上，随后一样的在这里页上放二分查找就可以迅速精准定位 id = 20 这行纪录。

说这种和文题并不是很有关的话题讨论，实际上 便是要想大伙儿了解：页做为 InnoDB 磁盘管理的最小单位，不但能够用于储放实际的行数据信息，还能够储放键值和表针。

返回题目的含义，大家先从简易的下手，假定 B  树仅有双层，即一个根节点和多个叶子节点，如下图：

那麼针对这棵 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 行纪录。