写点什么

MySql 的 InnoDB 的三层 B+ 树可以存储两千万左右条数据的计算逻辑

作者:Java-fenn
  • 2022 年 9 月 25 日
    湖南
  • 本文字数:1113 字

    阅读完需:约 4 分钟

B+树是一种在非叶子节点存放排序好的索引而在叶子节点存放数据的数据结构,值得注意的是,在叶子节点中,存储的并非只是一行表数据,而是以页为单位存储,一个页可以包含多行表记录。非叶子节点存放的是索引键值和页指针。

那么,在 MySql 数据库里,一个页的大小是多少呢?

可以通过查询语句进行查看:show variables like 'innodb_page_size'



查询结果 16384 字节,可以通过 1kb 等于 1024 字节方式,计算出 16384/1024 = 16kb,说明 MySql 数据库默认页大小是 16kb。

假设一行数据占用 1kb 的空间大小,然而实际上,除去字段很多的宽表外,其实很多简单的表行记录都远达不到 1kb 空间占比。这里我们用最坏的情况来假设一行记录大小为 1kb,那么,一个 16kb 的页就可以存储 16 行数据。

接下来,我们先画一个只要两层高的 B+树结构图。

假设第一层根节点存在以下情况:索引 1 对应页指针地址 10,索引 5 对应页指针地址 30,索引 8 对应页指针地址 50。

第二层节点作为叶子节点,存放的是大小为 16kb 的页数据,页数据里每一行记录大小为 1kb,那么,一个叶子节点的页里就可以存放 16 条数据。

既然已经知道一个叶子节点的页中可以存放 16 条数据,那么,只需要知道根节点存在多少页地址指针即可,就能通过 “根节点页地址指针数量 * 单个叶子节点记录行数”。

那么,根节点能存放多少个 索引:页地址指针的数据呢?

在一个节点大小为 16kb 的情况下,我们只需要知道索引键值和页地址指针两者大小总和即可。

根据一些资料得知,在 MySql 数据库当中,指针地址大小为 6 字节,若索引是 bigint 类型,那么就为 8 字节,两者加起来总共是 14 字节。

接下来,通过以下计算步骤,就可以统计出两层的 B+数大概可以存储多少条记录数据——

一、先计算一个节点的字节大小:16kb * 1024 = 16384 字节。

二、16384 字节 / 14 字节 = 1170 ,意味着,根节点有 1170 个页地址指针,然后,每个页地址指针指向的叶子节点可以存放 16 条数据。

三、那么,根据“根节点页地址指针数量 * 单个叶子节点记录行数”,计算 1170 * 16 = 18720 条记录,可见,两层 B+数可以存放 18720 条记录,当然,这个数字是存在出入的,只是作为参考。

既然已经知道两层 B+数可以存放 18720 条数据,那么,三层不就可以进一步算出了吗?

简单画一个三层 B+数的存放数据计算逻辑——

一、根节点最多有 1170 个指针数;

二、说明第二层最多会有 1170 个子节点,同时,每个子节点里最多有 1170 个指针数;

三、那么,第三层叶节点数量,可以通过 “第二层最多有 1170 个节点数量 * 每个节点里最多有 1170 个指针数量”,也就是 1170 * 1170

四、最后,计算第三层所有叶子数量 * 各个叶子节点存放的 16 条数据;

最后,1170 * 1170 * 16 = 21902400,得出两千万左右条数据。

综上所述,若面试当中遇到这样问题,可以按照这个流程计算回答。

用户头像

Java-fenn

关注

需要Java资料或者咨询可加我v : Jimbye 2022.08.16 加入

还未添加个人简介

评论

发布
暂无评论
MySql的InnoDB的三层B+树可以存储两千万左右条数据的计算逻辑_Java_Java-fenn_InfoQ写作社区