MySQL的索引底层为何使用 B+树？B树和B+树有哪些区别? 硬盘结构介绍、操作系统读取硬盘数据的过程、什么是IO操作?

矫情吗；* 2023-01-04 13:30 16阅读 0赞

> 相关文章 : [MySQL 索引底层为什么选择B+Tree][MySQL _B_Tree]

# 一、B+树介绍 #

*  B+树是B树的变体，常用于 **`数据库`和`操作系统的文件系统`** 中
 *  MySQL数据库的`索引`就是基于`B+树`实现的

**B+树的特点：**

*  分为 **`内部节点(非叶子)`**、**`叶子节点`** 两种节点
    
     *  内部节点 **只存储key, 不存储具体数据**
     *  叶子节点 **存储key(索引列) 和 具体数据(每一条记录)**
 *  **所有的叶子节点形成一条有序链表 (B树的叶子节点没有链)**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

*  m阶B+树非根节点的元素数量 x：`┌ m/2 ┐ ≤ x ≤ m`

**MySQL中的B+Tree**

*  MySQL索引数据结构对B+Tree进行了优化，在B+Tree的基础上，**`增加一个指向相邻叶子结点的链表指针`**，**就形成了带有顺序指针(双向链表)的B+Tree, 提高区间访问的性能。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMjM4_size_16_color_FFFFFF_t_70]

# 二、硬盘存储介绍 #

市面上常见的硬盘有：

*  **机械硬盘**（Hard Disk Drive，HDD）
 *  **固态硬盘**（Solid State Drive，SSD）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

后面的介绍针对 **机械硬盘**

## 2.1、盘片（platter）、盘面（side）、读写磁头（head） ##

*  硬盘一般由多个 **盘片** 组成，每个盘片包含2个 **盘面**，每个盘面有1个对应的 **读写磁头**; 盘面、磁头 **由上到下** 从0开始编号；  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

## 2.1、磁道（track）、扇区（sector） ##

*  盘面中的一圈圈灰色圆环为是一条条的 **磁道**：磁道 **由外到内** 从0开始编号；
 *  每条磁道上的一个弧段叫做一个**扇区**;
    
     *  **`扇区是磁盘的最小读写单位`**
     *  **一个扇区的大小通常是 512 字节（也有 4096 字节的）**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]

**早期硬盘的扇区细节**

*  每条磁道的扇区数相同
 *  所以外圈扇区的面积会比内圈扇区大

为了更好的读取数据，它们会存放相同的字节数

*  **所以外圈扇区的记录密度要比内圈小，会浪费大量的存储空间**

`硬盘的存储容量 = 磁头数 * 盘面磁道数 * 磁道扇区数 * 扇区字节数`

## 2.3、柱面（cylinder） ##

相同编号的磁道形成一个圆柱，称为**柱面**

*  磁盘的柱面数与一个盘面的磁道数是相等的  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]

## 2.4、磁盘块 (MySQL索引结构, 一个B+Tree节点存储的就是一个磁盘块) ##

*  磁盘块，在Windows中叫做 **簇（cluster）**，在Linux中叫做 **块（ block ）**
    
     *  相邻的 `2n` 个扇区组合在一起，形成一个 **`磁盘块`**
     *  **操作系统对磁盘进行管理时，以`磁盘块`作为最小读写单位**

**注意**

*  **磁盘块**是操作系统中的一个**虚拟概念**
 *  **扇区**是磁盘上**真实存在**的物理区域

## 2.5、操作系统读取硬盘数据的过程 ##

1.  操作系统将`LBA`传送给`磁盘驱动器`并启动读取命令；  
    LBA（Logical Block Address，**逻辑块地址**）  
    比如类似设备号4、磁头号4、磁道号8、扇区号16、扇区计数8这样的信息。
2.  磁盘驱动器根据 `LBA`将 **磁头移动到正确的磁道，盘片开始旋转，将目标扇区旋转到磁头下；**
3.  磁盘驱动器将**扇区数据**等信息传送到一个处于**磁盘界面的缓冲区**；
4.  磁盘驱动器向操作系统发出“数据就绪”信号；
5.  操作系统从磁盘界面的缓冲区读取数据；  
    既可以按照一个字节一个字节的方式读取，  
    也可以启动 DMA（Direct Memory Access，**直接内存访问**）命令读取。

## 2.6、磁盘完成IO操作的时间 ##

主要由 **`寻道时间`**、**`旋转延迟时间`**、**`数据传输时间`** 3 部分构成：

*  **`寻道时间`**（seek）：软件方面可以优化
    
     *  将**读写磁头**移动至**正确的磁道上所需要的时间**，这部分时间代价最高
 *  **旋转延迟时间**（rotation）：取决于硬件
    
     *  盘片旋转将目标扇区移动到读写磁头下方所需要的时间，**取决于磁盘转速**
 *  **数据传输时间**（transfer）：取决于硬件
    
     *  完成传输数据所需要的时间，**取决于接口的数据传输率**，通常远小于前两部分消耗时间

决定时间长短的大部分因素是和硬件相关的，但 **`所需移动的磁道数是可以通过操作系统来进行控制`**

*  减少所需移动的磁道数是减少整个硬盘读写时间的有效办法
 *  **合理安排磁头的移动以减少寻道时间**就是 **`磁盘调度算法`** 的目的所在

# 三、MySQL的索引底层为何使用B+树？ #

*  为了`减小 IO操作 数量`，一般把一个节点的大小设计成最小读写单位的大小
 *  **`MySQL 的存储引擎 InnoDB 的最小读写单位是 16K`**

对比B树, B+树的优势是：

*  每个节点存储的 key 数量更多，**树的高度更低**
 *  所有的具体数据都存在`叶子节点`上，所以每次查询都要查到叶子节点，**查询速度比较稳定**
 *  所有的叶子节点构成了一个有序链表，**做区间查询时更方便**
    
     *  例如查询某个范围内的数据，找到头结点后再通过链表往后找即可。

**解析：**

*  **`扫库、扫表能力更强`**：B-Tree 扫库扫表，会扫每一个枝节点，最后再扫子节点，基本都得扫一遍。B+Tree，只扫子节点即可。
 *  **`磁盘读写能力更强`**：B+Tree 枝节点不保存数据，只保存关键字和子节点引用。从理论上来将，能保存的关键字就更多，能加载的关键字就更多。从理论上来讲磁盘的读写能力就更强
 *  **`查询效率更加稳定`**：查询数据：比如使用 B-Tree 第一次查询比较幸运，第二层就出来了并返回，用了0.2s。B树是平衡树，此时如果又新插入一些数据，导致刚刚查询的数据到达了底层，那么此时第二次查询。时间就要大于0.2s了。即：指点数据节点的深度是会变化的，会随着数据的插入、删除而改变，从而导致查询时间有所不稳定数据更多的话，这个时间就会比第一次差距更大了（B+Tree查询，都会去叶子节点查找数据，相对B-Tree来说就更加稳定）

# B树 与 B\*树 #

B树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]

B\*树 是 B+树 的变体：给内部节点增加了指向兄弟节点的指针；

*  m阶 B\*树 非根节点的元素数量 x：`┌ 2m/3 ┐ ≤ x ≤ m`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]

[MySQL _B_Tree]: https://blog.csdn.net/lzb348110175/article/details/103999658
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221119/4f69d959262b44a6990cc348ffff72f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTEyMjM4_size_16_color_FFFFFF_t_70]: /images/20221119/99f774bcdf2d4aeab7eefa46c15625df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20221119/3e4f03c71b1a49e19b96475c729dcc81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20221119/9dab9f0c3ebc41caa82a0b2a76a13fc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: /images/20221119/3daeb08e1cbd4565a049353a62791e4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]: /images/20221119/c1b9f83e2b174720947b7d80d1a30f5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]: /images/20221119/c1197b5250674d44b4c0e6245a201a37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200427113450378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ==,size_16,color_FFFFFF,t_70