栏目分类

热点资讯

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

2021-10-07 00:04

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

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

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

前文说过,页是 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 行记录。

【编辑推荐】

鸿蒙官方战略合作共建——HarmonyOS技术社区 在终端监控你的 Linux 系统 五款新型 Linux 命令行工具,实用! Linux 中 cron 系统的四种替代方案 Linux C核心技术 Oracle 19c RAC For Linux安装部署

Powered by 短篇合集500全文目录-短篇合集500篇手机官网-一个山村里 @2013-2021 RSS地图 HTML地图

Copyright 365建站 © 2013-2021 365建站器 版权所有