荐 mysql的B+树如何存储主键和数据,磁盘io和innodb页大小的一些问题

作者: CSDN  更新时间:2020-06-26 11:40:14  原文链接


一、前言

这篇文章动笔之前,光标题就思考了半天,因为文章的起源是一位网友的评论,问的问题比较犀利且分散,实在是不容易拟定标题。博主就借着这个机会研究下这些问题,分别作答一下。

这里是网友的提问:

文章链接: mysql的查询需要遍历几次B+树,理论上需要几次磁盘I/O?

二、正式作答部分

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

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

(1)B+树的大致结构

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

叶子节点是存放用户数据的,页内数据根据用户记录的主键大小排列成的单向链表。而页和页之间是根据主键大小顺序排成一个双向链表。( PS: 这里感谢评论区的同学指出错误,十分感谢!)

(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数据

这个 16kbinnodb 默认的页大小,为什么会有这个概念呢,因为当涉及到数据库读写的时候,规定数据库每次读写都是以 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 次数没什么关系的。

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

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

数据页大小 最大表空间
4KB 16TB
8KB 32TB
16KB 64TB
32KB 128TB
64KB 256TB

关于磁盘部分和 io 部分,博主这里也就不多做解释了(博主自己可能也是半斤八两的),大家可以网上百度百度,了解相关的概念。不得不说,这些基础原理部分还是需要学一学的。

5、参考链接

关于IO:https://segmentfault.com/a/1190000021388785
关于索引:https://juejin.im/post/5b4f710be51d45195c073912
掘金小册,从根儿上理解mysql(各位自行百度,我就不多介绍了)

欢迎大家指正,讨论!另外,今天是全国哀悼日,愿我中华蒸蒸日上,灾难始终会过去,未来可期!
end