InnoDB一棵B+树可以存放多少行数据?

一个问题?

InnoDB一棵B+树可以存放多少行数据?这个问题的简单回答是:约2千万。为什么是这么多呢?因为这是可以算出来的,要搞清楚这个问题,我们先从InnoDB索引数据结构、数据组织方式说起。

我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k,而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。

下面几张图可以帮你理解最小存储单元:文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。

innodb的所有数据文件(后缀为ibd的文件),他的大小始终都是16384(16k)的整数倍。

磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:

mysql> show variables like ‘innodb_page_size’;+——————+——-+| Variable_name | Value |+——————+——-+| innodb_page_size | 16384 |+——————+——-+1 row in set (0.00 sec)

数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。如果数据库只按这样的方式存储,那么如何查找数据就成为一个问题,因为我们不知道要查找的数据存在哪个页中,也不可能把所有的页遍历一遍,那样太慢了。所以人们想了一个办法,用B+树的方式组织这些数据。如图所示:

数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。如果数据库只按这样的方式存储,那么如何查找数据就成为一个问题,因为我们不知道要查找的数据存在哪个页中,也不可能把所有的页遍历一遍,那样太慢了。所以人们想了一个办法,用B+树的方式组织这些数据。如图所示:

我们先将数据记录按主键进行排序,分别存放在不同的页中(为了便于理解我们这里一个页中只存放3条记录,实际情况可以存放很多),除了存放数据的页以外,还有存放键值+指针的页,如图中page number=3的页,该页存放键值和指向数据页的指针,这样的页由N个键值+指针组成。当然它也是排好序的。这样的数据组织形式,我们称为索引组织表。现在来看下,要查找一条数据,怎么查?

如select * from user where id=5;

这里id是主键,我们通过这棵B+树来查找,首先找到根页,你怎么知道user表的根页在哪呢?其实每张表的根页位置在表空间文件中是固定的,即page number=3的页(这点我们下文还会进一步证明),找到根页后通过二分查找法,定位到id=5的数据应该在指针P5指向的页中,那么进一步去page number=5的页中查找,同样通过二分查询法即可找到id=5的记录:

5
zhao2
27

现在我们清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的,我们总结一下:

1、InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于存放键值+指针,在B+树中叶子节点存放数据,非叶子节点存放键值+指针。

2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中,进而在去数据页中查找到需要的数据;那么回到我们开始的问题,通常一棵B+树可以存放多少行数据?这里我们先假设B+树高为2,即存在一个根节点和若干个叶子节点,那么这棵B+树的存放总记录数为:根节点指针数*单个叶子节点记录行数。上文我们已经说明单个叶子节点(页)中的记录数=16K/1K=16。(这里假设一行记录的数据大小为1k,实际上现在很多互联网业务数据记录大小通常就是1K左右)。

那么现在我们需要计算出非叶子节点能存放多少指针,其实这也很好算,我们假设主键ID为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置为6字节,这样一共14字节,我们一个页中能存放多少这样的单元,其实就代表有多少指针,即16384/14=1170。那么可以算出一棵高度为2的B+树,能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放:1170117016=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层,它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。怎么得到InnoDB主键索引B+树的高度?

上面我们通过推断得出B+树的高度通常是1-3,下面我们从另外一个侧面证明这个结论。在InnoDB的表空间文件中,约定page number为3的代表主键索引的根页,而在根页偏移量为64的地方存放了该B+树的page level。如果page level为1,树高为2,page level为2,则树高为3。即B+树的高度=page level+1;下面我们将从实际环境中尝试找到这个page level。

在实际操作之前,你可以通过InnoDB元数据表确认主键索引根页的page number为3,你也可以从《InnoDB存储引擎》这本书中得到确认。SELECT b.name, a.name, index_id, type, a.space, a.PAGE_NO FROM information_schema.INNODB_SYS_INDEXES a, information_schema.INNODB_SYS_TABLES b WHERE a.table_id = b.table_id AND a.space <> 0;执行结果:

可以看出数据库dbt3下的customer表、lineitem表主键索引根页的page number均为3,而其他的二级索引page number为4。关于二级索引与主键索引的区别请参考MySQL相关书籍,本文不在此介绍。

下面我们对数据库表空间文件做想相关的解析:

因为主键索引B+树的根页在整个表空间文件中的第3个页开始,所以可以算出它在文件中的偏移量:16384*3=49152(16384为页大小)。另外根据《InnoDB存储引擎》中描述在根页的64偏移量位置前2个字节,保存了page level的值,因此我们想要的page level的值在整个文件中的偏移量为:16384*3+64=49152+64=49216,前2个字节中。

接下来我们用hexdump工具,查看表空间文件指定偏移量上的数据:

linetem表的page level为2,B+树高度为page level+1=3;

region表的page level为0,B+树高度为page level+1=1;

customer表的page level为2,B+树高度为page level+1=3;

这三张表的数据量如下:

总结:

lineitem表的数据行数为600多万,B+树高度为3,customer表数据行数只有15万,B+树高度也为3。可以看出尽管数据量差异较大,这两个表树的高度都是3,换句话说这两个表通过索引查询效率并没有太大差异,因为都只需要做3次IO。那么如果有一张表行数是一千万,那么他的B+树高度依旧是3,查询效率仍然不会相差太大。

region表只有5行数据,当然他的B+树高度为1。

最后回顾一道面试题有一道MySQL的面试题,

为什么MySQL的索引要使用B+树而不是其它树形结构?比如B树?

现在这个问题的复杂版本可以参考本文;

他的简单版本回答是:

因为B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保存大量数据,只能增加树的高度,导致IO操作变多,查询性能变低;

小结本文从一个问题出发,逐步介绍了InnoDB索引组织表的原理、查询方式,并结合已有知识,回答该问题,结合实践来证明。当然为了表述简单易懂,文中忽略了一些细枝末节,比如一个页中不可能所有空间都用于存放数据,它还会存放一些少量的其他字段比如page level,index number等等,另外还有页的填充因子也导致一个页不可能全部用于保存数据。关于二级索引数据存取方式可以参考MySQL相关书籍,他的要点是结合主键索引进行回表查询。

参考资料:

姜承尧 《MySQL技术内幕:InnoDB存储引擎》姜承尧 http://www.innomysql.com/查看-innodb表中每个的索引高度/

本文转自 SpringForAll社区 如有侵权,请联系删除

Image placeholder
cai947506122
未设置
  37人点赞

没有讨论,发表一下自己的看法吧

推荐文章
Github一天标星1k+,程序员需要知道的那些定理和法则

大数据文摘出品编译:蒋宝尚、曹培信摩尔定律知道么?帕金森定律讲的又是啥?作为一名合格的开发人员,除了本身码力超强外,或多或少要知道几条“”潜规则”,例如依赖倒置原则、鲁棒性原则……关于开发人员必须要知

【系列】股份制银行在职员工有多少?其中研发又有多少人?

本篇为系列文章第一篇,下一篇, 2018年,股份制银行在IT方面都花了多少钱,做了哪些事?摘要:虽然做过些与银行相关选题,比如《四大行、股份制银行、城商行都在使用什么数据库?》《银行数据库选型之秘》《

InnoDB到底支不支持哈希索引,为啥不同的人说的不一样?

继续回答水友提问(最近问MySQL的多):沈老师,我在网上看到不同的资料,有的说InnoDB支持哈希索引,有的说不支持,到底哪个是正确的呢?对于InnoDB的哈希索引,确切的应该这么说:(1)Inno

「完整版」农业银行数据库使用实践和发展规划!

摘要:中国农业银行(以下简称:农行)在信息化系统建设过程中,先是把关系型数据库作为联机交易型数据库使用,后来为满足分析型应用需要开始使用分析型数据库,近几年来随着应用场景细分,对基于Hadoop的大数

美漂数据科学家年薪多少?爬了6年H1B签证数据发现,招的人多了,但钱少了

大数据文摘出品来源:medium编译:张睿毅、曹培信自2012年起,一直被称为“最性感的工作”的数据科学家职位,吸引了大批远渡重洋到达硅谷,做着“数据梦”的留学生们。但他们也付出了不菲的前期投入,除了

学习 nodejs+mongodb+koa2 写接口(一) 环境布置

一.环境准备最近在学用Nodejs写后端接口,了解到koa2是Nodejs的一个框架。可以快速开发后端接口,同时也能更快熟悉Nodejs以下是所需的环境node  v7.6+,可以用nvm或者n安装指

学习 nodejs+mongodb+koa2 写接口(二) koa2教程入门

一.hellokoa安装koa2#初始化package.json npminit #安装koa2 npminstallkoahelloworld代码constKoa=require('koa') c

你公司所拥有的数据,真正被使用的有多少?

如今,很多公司的领导者基本都可以认定一个事实:你的公司有很多数据。但有一个非常重要问题是,任何组织内部,可能都会有大量数据从来没有被收集、处理或使用过,当然造成这种现象的原因有很多。我们可以把这些数据

MongoDB数据库因安全漏洞,导致Family Locator泄露二十多万名用户数据

摘要:本月第二次,未受保护的MongoDB数据库因大量安全漏洞而导致敏感信息泄露,受欢迎的家庭跟踪应用程序FamilyLocator已经暴露了超过238,000名用户的实时未加密位置数据。该应用程序非

面试高频:如何访问 Redis 中的海量数据?

目录前言事故产生分析原因解决方案总结前言有时候我们需要知道线上的redis的使用情况,尤其需要知道一些前缀的key值,那我们怎么去查看呢事故产生因为我们的用户token缓存是采用了【user_toke

如何在多云环境中管理数据?

在多云环境中建立数据治理策略没有灵丹妙药。在这里,我们将讨论为什么会有这种说法的原因,以及有关多云环境的IT领导者如何思考数据治理的一些方法。数据治理有点像健身:它不仅仅是一个目的,更是一个持续的过程

Go - 如何解析 JSON 数据?

概述最近掉进需求坑了,刚爬上来,评估排期出现了严重问题,下面三张图很符合当时的心境。谈需求估排期开始干为啥会这样,我简单总结了下: 与第三方对接。 跨团队对接。 首次用Go做项目。 业务流程没屡清楚就

DBA职业发展之路:去“IOE”等挑战之下,DBA将何去何从?

开篇随着近些年来,开源、自动化、云化的兴起,DBA职业也正悄然发生一些变化。经常有朋友咨询我,职业发展规划;特别是近期Oracle的大幅裁员之后,针对DBA这一职业未来该如何发展?本文是个人对此问题的

nodejs为什么叫node?

nodejs为什么叫node?最开始NodeJs作者Dahl取的名字叫web.js,仅仅是一个web服务器,是Apache和其他“阻塞”服务器的替代方案。但是该项目很快就超出了他最初的Web服务器库的

IT程序员工资一般多少钱?薪资水平如何?

  IT程序员工资普通几钱?薪资程度如何?程序员工资依据技术程度和地域差别薪资程度有很大的差距,北上广一线城市程序员工资大都在1万元左右,随着项目经历积聚薪资也呈现上升趋向。   IT程序员工资待遇引

我们不知道要花多少时间解决问题

分享链接:http://kyleprifogle.com/dear-startup/ 我在IT行业工作,发现一个奇怪的现象。职业生涯的早期,我从事Web开发,比如开发CRUD应用、构建API等。我注意

中国移动智能硬件质量报告解读 分布式路由市场你了解多少?

今年6月份,中国移动终端实验室发布了《中国移动2019年智能硬件质量报告》(第一期),并于近日对该报告进行了相关解读,同时对优秀智能硬件产品进行颁奖。根据介绍,本次报告在内容上主要包括手机产品综合评测

吊打面试官!MySQL灵魂100问,你能答出多少?

推荐阅读:面试机会不等人,资料看精不看多!史上最全Java技术资料合集!2019年中总结,400道一线大厂高频精选面试题合集(JVM+Spring+RabbitMQ+Mybatis+Redis+分布式

1px等于多少厘米?

首先要弄懂两个概念:像素(px):位图的一幅图像,是由若干个点组成的,每个点就叫做像素,.图像宽度上的点数乘以高度上的点数,就是这个图像的总像素,一幅图像点越多,图像就越大。分辨率:即图像的像素密度,

建一个5G基站,到底要花多少钱?

自从国内5G正式宣布商用之后,全国各地的5G网络建设速度明显加快了。5G基站的身影,出现在越来越多的城市、角落。5G信号的覆盖范围,也在不断扩大。这意味着,5G的投资已经全面启动,并且在不断增加。一直

MongoDB与阿里云达成战略合作,云将是数据库最佳载体

摘要:开源数据库厂商与云服务供应商两大阵营之间存在争议是事实,MongoDB与阿里云达成战略合作,背后意味着什么?对MongoDB,对阿里云分别意味着什么?对整个数据库产业又意味着什么?MongoDB

中信银行信用卡业务数据库实现国产替换,湖北银行新核心系统项目正式验收,阿里云与MongoDB达成战略合作

中信银行信用卡业务数据库实现国产替换10月31日,由IT168旗下ChinaUnix社区主办的第十一届中国系统架构师大会(SACC2019)在北京召开。会上,中信银行软件开发中心/技术平台开发处副处长

数据偏移、分区陷阱……我们这样避开DynamoDB的5个坑

摘要:本文主要介绍作者所在团队在具体业务中所遇到的挑战,基于这些挑战为何最终选型使用AmazonDynamoDB,在实践中遇到了哪些问题以及又是如何解决的。文中不会详细讨论AmazonDynamoDB

海量数据AtlasDB:把“数据库好用”这件事做到极致

导语:坚守初心、不辱使命,近期海量数据研发的企业级数据库AtlasDB获得了市场的普遍关注。这款以“好用”著称的国产数据库产品,不仅承载着海量数据公司对技术创新的坚持和投入,更凝结着一群拥有“工匠之心

计算存储分离 华为云多模NoSQL服务GeminiDB更易用

随着互联网技术架构的快速普及,企业对于NoSQL的需求也越来越大,在云计算的潮流下,如何将云服务的思维和技术纳入到数据库创新,成为摆在云服务厂商面前的一道难题。前不久,在第十届中国数据库技术大会(DT