mysql 一棵 B+ 树能存多少条数据?

标签: | 发表时间:2021-06-09 23:06 | 作者:
出处:https://mp.weixin.qq.com

mysql 的InnoDB存储引擎 一棵B+树可以存放多少行数据?

图片

(答案在文章中!!)

要搞清楚这个问题,首先要从InnoDB索引数据结构、数据组织方式说起。

我们都知道计算机有五大组成部分:控制器,运算器,存储器,输入设备,输出设备。

其中很重要的,也跟今天这个题目有关系的是存储器。

我们知道万事万物都有自己的单元体系,若干个小单体组成一个个大的个体。就像拼乐高一样,可以自由组合。所以说,如果能熟悉最小单元,就意味着我们抓住了事物的本事,再复杂的问题也会迎刃而解。


存储单元


存储器范围比较大,但是数据具体怎么存储,有自己的最小存储单元。

1、数据持久化存储磁盘里,磁盘的最小单元是扇区, 一个扇区的大小是 512个字节

2、文件系统的最小单元是块, 一个块的大小是 4K

3、InnoDB存储引擎,有自己的最小单元,称之为页, 一个页的大小是16K


扇区、块、页这三者的存储关系?

图片



InnoDB引擎


如果mysql部署在本地,通过命令行方式连接mysql,默认的端口  3306 ,然后输入密码即可进入

  mysql -u root -p

查看InnoDB的页大小

  show variables like 'innodb_page_size';   

图片

mysql数据库中,table表中的记录都是存储在页中,那么一页可以存多少行数据?假如一行数据的大小约为1K字节,那么按  16K / 1K = 16,可以计算出一页大约能存放16条数据。

mysql 的最小存储单元叫做“页”,这么多的页是如何构建一个庞大的数据组织,我们又如何知道数据存储在哪一个页中?

如果逐条遍历,性能肯定很差。为了提升查找速度,我们引入了 B+树,先来看下 B+树的存储结构


图片

页除了可以存放 数据(叶子节点),还可以存放 健值和指针(非叶子节点),当然他们是有序的。这样的数据组织形式,我们称为索引组织表。

如:上图中 page number=3的页,该页存放键值和指向数据页的指针,这样的页由N个键值+指针组成


B+ 树是如何检索记录?

  • 首先找到根页,你怎么知道一张表的根页在哪呢?
  • 其实每张表的根页位置在表空间文件中是固定的,即page number=3的页
  • 找到根页后通过二分查找法,定位到id=5的数据应该在指针P5指向的页中
  • 然后再去page number=5的页中查找,同样通过二分查询法即可找到id=5的记录


如何计算B+树的高度?


InnoDB 的表空间文件中,约定 page number = 3表示主键索引的根页

  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
and b.name like '%sp_job_log';

图片

从图中可以看出,每个表的主键索引的根页的page number都是3,而其他的二级索引page number为4

在根页偏移量为 64的地方存放了该B+树的 page level。主键索引B+树的根页在整个表空间文件中的第3个页开始,所以算出它在文件中的偏移量: 16384*3 + 64 = 49152 + 64 =49216,前2个字节中。

首先,找到MySql数据库物理文件存放位置:

  show global variables like "%datadir%" ;   

图片


hexdump工具,查看表空间文件指定偏移量上的数据:

  hexdump -s 49216 -n 10  sp_job_log.ibd   

图片

page_level 值是 1,那么 B+树高度为  page level + 1 = 2


特别说明:

  • 查询数据库时,不论读一行,还是读多行,都是将这些行所在的整页数据加载,然后在内存中匹配过滤出最终结果。

  • 表的检索速度跟树的深度有直接关系,毕竟一次页加载就是一次IO,而磁盘IO又是比较费时间。 对于一张千万级条数B+树高度为3的表与几十万级B+树高度也为3的表,其实查询效率相差不大。



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


假设B+树的深度为2

这棵B+树的存储总记录数 =  根节点指针数 * 单个叶子节点记录条数


那么指针数如何计算?

假设主键ID为 bigint类型,长度为 8字节,而指针大小在InnoDB源码中设置为 6字节,这样一共 14字节

那么一个页中能存放多少这样的组合,就代表有多少指针,即  16384 / 14 = 1170。那么可以算出一棵高度为2 的B+树,能存放  1170 * 16 = 18720 条这样的数据记录。

同理:

高度为3的B+树可以存放的行数 =   1170 * 1170 * 16 = 21902400

千万级的数据存储只需要约3层B+树,查询数据时,每加载一页(page)代表一次IO。所以说,根据主键id索引查询约3次IO便可以找到目标结果。


对于一些复杂的查询,可能需要走二级索引,那么通过二级索引查找记录最多需要花费多少次IO呢?

图片

首先,从二级索引B+树中,根据 name 找到对应的主键id

图片

然后,再根据主键id 从 聚簇索引查找到对应的记录。如上图所示,二级索引有3层,聚簇索引有3层,那么最多花费的IO次数是:3+3 = 6

聚簇索引默认是主键,如果表中没有定义主键,InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引,InnoDB 会隐式定义一个主键来作为聚簇索引。

这也是为什么InnoDB表必须有主键,并且推荐使用整型的自增主键!!!

InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上

举例说明:

1、若使用 "where id = 14"这样的条件查找记录,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。

2、若对Name列进行条件搜索,则需要两个步骤:

  • 第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键值。
  • 第二步使用主键值在主索引B+树中再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。(重点在于通过其他键需要建立辅助索引)

实战演示


实际项目中,每个表的结构设计都不一样,占用的存储空间大小也各不相等。如何计算不同的B+树深度下,一个表可以存储的记录条数?

我们以业务日志表  sp_job_log 为例,讲解详细的计算过程:

1、查看表的状态信息

  show table status like 'sp_job_log'\G   

图片

图中看到 sp_job_log表的行平均大小为 153个字节

2、查看表结构

  desc sp_job_log;   

图片

3、计算B+树的行数

  • 单个叶子节点(页)中的记录数 = 16K / 153 = 105
  • 非叶子节点能存放多少指针, 16384 / 14 = 1170
  • 如果树的高度为3,可以存放的记录行数 =  1170 * 1170 * 105 = 143,734,500


最后加餐


普通索引和唯一索引在查询效率上有什么不同?

唯一索引就是在普通索引上增加了约束性,也就是关键字唯一,找到了关键字就停止检索。而普通索引,可能会存在用户记录中的关键字相同的情况,根据页结构的原理,当我们读取一条记录的时候,不是单独将这条记录从磁盘中读出去,而是将这个记录所在的页全部加载到内存中进行读取。InnoDB 存储引擎的页大小为 16KB,在一个页中可能存储着上千个记录,因此在普通索引的字段上进行查找也就是在内存中多几次 判断下一条记录的操作,对于 CPU 来说,这些操作所消耗的时间是可以忽略不计的。所以对一个索引字段进行检索,采用普通索引还是唯一索引在检索效率上基本上没有差别。


相关 [mysql 数据] 推荐:

mysql 数据分离

- - 数据库 - ITeye博客
网上看到一个读写分离的帖子,感觉不错. 构建高性能web之路------mysql读写分离实战(转). 一个完整的mysql读写分离环境包括以下几个部分:. 在本次实战中,应用程序client基于c3p0连接后端的database proxy. database proxy负责管理client实际访问database的路由策略,采用开源框架amoeba.

MySQL数据库的修复

- Xin - 博客园-首页原创精华区
找到mysql的安装目录的bin/myisamchk工具,在命令行中输入:. 然后myisamchk 工具会帮助你恢复数据表的索引. 好象也不用重新启动mysql,问题就解决了. 当你试图修复一个被破坏的表的问题时,有三种修复类型. 如果你得到一个错误信息指出一个临时文件不能建立,删除信息所指出的文件并再试一次--这通常是上一次修复操作遗留下来的.

同步mysql数据到hive

- - ITeye博客
地址为:http://archive.cloudera.com/cdh/3/下载相应版本,如sqoop-1.2.0-CDH3B4.tar.gz. 地址为:http://archive.cloudera.com/cdh/3/,版本可以为hadoop-0.20.2-CDH3B4.tar.gz. 3.解压 sqoop-1.2.0-CDH3B4.tar.gz ,hadoop-0.20.2-CDH3B4.tar.gz 到某目录如/home/hadoop/,解压后的目录为.

mysql数据整理命令

- - SQL - 编程语言 - ITeye博客
Analyze Table(修复索引). MySQL 的Optimizer(优化元件)在优化SQL语句时,首先需要收集一些相关信息,其中就包括表的cardinality(可以翻译为“散列程度”),它表示某个索引对应的列包含多少个不同的值——如果cardinality大大少于数据的实际散列程度,那么索引就基本失效了.

mysql 数据文件迁移

- - 数据库 - ITeye博客
1.新mysql存储路径:/data1/mysql/. 2.cp /var/lib/mysql到新存储路径:. 存储文件: cp -rp /var/lib/mysql /data1/mysql/data/. 日志文件: cp -rp /var/log/mysql /data1/mysql/log/.

excel数据导入mysql数据库

- - 互联网 - ITeye博客
1、excel另存为txt.       选中将要导出的数据列,然后另存为选择其它格式=>文本文件(制表符分割). E:\项目\fblike\game_code_san.txt. 2、txt导入到mysql数据库. load data infile 'E:\\项目\\fblike\\game_code_san.txt' into table game_code_san(code).

[MySQL] 生产环境MySQL数据库事务一直在RUNNING

- - CSDN博客数据库推荐文章
运营人员反映,有一单子提交卡住了,页面一直没有返回. 1,刚开始怀疑是应用服务器或者db压力过高hang住了,马上去check应用服务器以及db的负载,看起来都OK,蛮低的,应该不是DB性能问题. 2,最后去看下是否是表锁住了,查看到有2个事务一直RUNNING,没有结束. 3,通过trx_mysql_thread_id: 1662332的去查询information_schema.processlist找到执行事务的客户端请求的SQL线程.

Python3连接MySQL数据库之mysql-client - Ethan_zhang - 博客园

- -
要想使 python 可以操作 mysql 就需要 MySQLdb 驱动,它是 python 操作 mysql 必不可少的模块. 在此站点下载mysqlclient安装包:https://www.lfd.uci.edu/~gohlke/pythonlibs/# 进行本地安装. 以下是从这个网站上面检索到的mysqlclient的所有版本.

MySQL数据库的IO操作

- - haohtml's blog
         淘宝丁奇分享的PPT:MySQL数据库的IO操作,详细分享了四块的内容,并且告诉大家如何调整MySQL数据库IO操作相关的参数,给出了详细的选择策略,现替其整理成文章分享与此. 4.影响io行为的一些参数和选择策略. 一个简单的查询 select * from t where id>=(  select id from t where k1=100 limit 100000,1) limit 2;.

mysql数据备份3种方案

- - 开心平淡对待每一天。热爱生活
   mysql按照备份恢复方式分为逻辑备份和物理备份 逻辑备份是备份sql语句,在恢复的时候执行备份的sql语句实现数据库数据的重现. 物理备份就是备份数据文件了,比较形象点就是cp下数据文件,但真正备份的时候自然不是的cp这么简单. 这2种备份各有优劣,一般来说,物理备份恢复速度比较快,占用空间比较大,逻辑备份速度比较慢,占用空间比较小.