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

怼烎@ 2023-07-22 08:00 4阅读 0赞

## 一、前言 ##

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

**这里是网友的提问：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xKRlBIUA_size_16_color_FFFFFF_t_70_pic_center][]

**文章链接：**[mysql的查询需要遍历几次B+树，理论上需要几次磁盘I/O？][mysql_B_I_O]

## 二、正式作答部分 ##

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

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

#### （1）B+树的大致结构 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xKRlBIUA_size_16_color_FFFFFF_t_70_pic_center 1]  
      由图片可以看到，`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数据 ####

这个`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`次数没什么关系的。

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

`InnoDB`页面大小 最大表空间大小：

<table> 
 <thead> 
  <tr> 
   <th>数据页大小</th> 
   <th>最大表空间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4KB</td> 
   <td>16TB</td> 
  </tr> 
  <tr> 
   <td>8KB</td> 
   <td>32TB</td> 
  </tr> 
  <tr> 
   <td>16KB</td> 
   <td>64TB</td> 
  </tr> 
  <tr> 
   <td>32KB</td> 
   <td>128TB</td> 
  </tr> 
  <tr> 
   <td>64KB</td> 
   <td>256TB</td> 
  </tr> 
 </tbody> 
</table>

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

### 5、参考链接 ###

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xKRlBIUA_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/ecdc7877ef0e4dfb8a3a3e90e665bf8a.png
[mysql_B_I_O]: https://blog.csdn.net/LJFPHP/article/details/97133701
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xKRlBIUA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/87bc273e42ac4a8fa119df736ecdd783.png