MySQL的B+树如何存储主键和数据?

网友投稿 841 2022-05-30

一、前言

文章的起源是一位网友的评论,问的问题比较犀利且分散。借着这个机会研究下这些问题,分别作答一下。

这里是网友的提问:

二、正式作答部分

这里分析完这个网友的提问之后,可以大致分为4个问题来回答,下面分别尝试作答一下,有不正确的地方欢迎大家留言讨论~

1、关于B+树的非叶子节点存储问题

(1)B+树的大致结构

由图片可以看到,innodb中的B+树,非叶子节点主要是存储主键的记录值,按照主键的大小顺序排成一个单向链表。

叶子节点是存放用户数据的,页内数据根据用户记录的主键大小排列成的单向链表。而页和页之间是根据主键大小顺序排成一个双向链表。

(2)模拟计算下B+树存储的数据量

我们这里计算下,假设非叶节点不同元素占用情况为:下一条记录指针占4Byte,id值8Byte,目标记录指针4Byte,那么一个4Kb的磁盘块将大致可以容纳250个下级指针。

我们假设,一个4kb的磁盘块可以容纳100条数据(用户的实际数据):

如果B+树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放100条记录。

如果B+树有2层,最多能存放250×100=2.5W条记录。

如果B+树有3层,最多能存放250×250×100=625W条记录。

(3)网友的问题答案

原来的计算方式确实是不严谨的,只有非叶子节点才会存有叶子节点的页记录,也就是所谓的“下级指针”。实际的存储方式应该是这篇重写的部分。

2、磁盘IO次数计算问题

(1)什么是一次IO

每次IO其实是磁盘控制器向磁盘发出一次读/写指令,给出开始扇区的地址和向后连续读/写的扇区的个数。控制器发出的这种指令+数据,就是一次IO,读或者写。

(2)IO次数的计算

首先要明确,我们每次IO都是读取数据到内存中进行一些计算。当我们遍历主键索引的B+树查找数据的时候,IO次数是近似于B+树的层数-1,因为根节点是一直在内存中的。

基本上可以理解为,每次io都是在树的一层查找符合的id范围的页数据,通过对比页里面的最大最小主键来确定下层的查找范围。

3、磁盘预读以及如何保证每次都能拿到innodb的一页也就是16kb的数据

(1)磁盘预读

预读其实就是利用了局部性原理,具体过程是:对于每个文件的第一个读请求,系统读入所请求的页面并读入紧随其后的少数几个页面(通常是三个页面),这时的预读称为同步预读。

我们知道对大部分操作系统来说,磁盘的一页数据是4kb,那么算上预读的3页:

4kb(磁盘一页的大小) + 12kb(预读三个页面) = 16kb

(2)关于每次读取16kb数据

这个16kb是innodb默认的页大小,为什么会有这个概念呢,因为当涉及到数据库读写的时候,规定数据库每次读写都是以16k为单位的,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。

(3)磁盘io固定是每次读取4kb的吗

答案明显不是的,io读取是可大可小的,具体看指令的内容,并不是每次只能读取固定的1页。比如上面解释一次io概念的时候,我们提到了指令,这个指令是类似于给出两个参数,第一个参数是要开始读取的扇区地址,第二个参数是要读取多少扇区。

所以每次io的大小是根据指令来决定的,并不是每次只能读取磁盘的一页数据,也就是4kb。

(4)网友的问题

主要是明确磁盘中的一页数据(4kb)和数据库innodb规定的一页数据(16kb),这两个的概念是不一样的。磁盘io的大小也是根据指令来规定的。对应数据库读写来说,会按照数据库的配置,每次最少读写一页数据,也就是16kb。

4、设置页大小为64kb,是否一次io就拿不到对应的数据了,需要多次io?

其实这个问题上面已经给出了答案。设置innodb页大小为64kb之后,我们每次数据库的读写就必须操作64kb的数据了而已,和io次数没什么关系的。

MySQL的B+树如何存储主键和数据?

经过看文档,也没看到有说到64kb页大小有什么缺陷之类的,只知道会增大表空间上限:

InnoDB页面大小 最大表空间大小:

关于磁盘部分和io部分,这里也就不多做解释了。

往期精彩回顾

Mysql-B+TREE索引原理

MySQL为什么选择B+树存储索引

深入了解 B-Tree 和 B+Tree 的区别

图解 MySQL 索引 —— B-Tree、B+Tree

MySQL的查询需要遍历几次B+树,理论上需要几次磁盘I/O?

MySQL

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:【Linux】指令与文件的搜寻
下一篇:云原生时代,领域驱动设计思想(DDD)如何落地?
相关文章