很多面试题都会问，MySQL的索引数据结构是什么，答案很简单，是B+Tree，然后又会问，为什么是采用B+Tree，而不是一般二叉树呢，原因也很简单，降低树的高度，可以减少io交互次数，也就是减少读写磁盘的次数。

那问题来了：为什么读写磁盘速度会慢呢？它是一个怎样的过程? 它到底慢在哪里呢？

磁盘

磁盘到底是什么

磁盘（disk）是指利用磁记录技术存储数据的存储器。磁盘是计算机主要的存储介质，可以存储大量的二进制数据，并且断电后也能保持数据不丢失。

磁盘的存储介质

用一堆可以存储正负电极的磁性材料组成，因为正负电极可以代表计算机中0和1。所以我们所熟知的视频、语音、图片、文字等这些 ，在磁盘存储形式都是0和1，映射到存储介质中，就是一堆的正负磁性材料。

磁盘到底长什么样

常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，每个盘片上面都有很多磁道，磁道是由一个一个的小圆环组成，每一个磁道了一个更小的划分，被称为扇区，如最右图所示，一个磁道由八个扇区组成。

每个盘面又有自己的磁头,磁头是用来读写数据的，当磁头处于某个扇区的正上方时可以读取该扇区的数据或者写入该扇区数据。

由于一个磁盘上面存在多个盘片，而多个磁头又是固定在机械臂杆上面的，那么多个盘片相同位置(相同编号)的磁道形成一个圆柱体,称为柱面。

一个磁道通常八个扇区，每个扇区存储512个字节数据，一个磁道的字节数据大小为4kb。

磁盘的寻址过程

1. 寻道(寻找磁道)： 磁头从当前磁道以磁盘中间点半径放心移动到目标磁道。这只在切换到不同磁道时才需要。

2. 旋转： 当磁头达到目标磁道后，盘片开始旋转，等待目标扇区旋转到磁头的正下方，这个过程称为旋转。

3. 传送： 一旦目标扇区位于磁头的正下方，就可以进行数据的读取或写数据了。需要注意的是并不是只读取一条数据，而是读取数据所在扇区的所有数据，因为扇区是磁盘的基本单位。

扇区是磁盘数据的基本存储单位，一般情况下在读取某一个扇区的内容时，会将附近扇区的数据也一起读取出来，这就是下面会介绍的预读。

上面的3个步骤就是读写磁盘io的整个过程了，整个过程的耗时 = 寻道时间 + 盘片旋转时间 + 读取和传输数据的时间 。

寻道需要磁头来回移动；而盘片旋转找扇区的时间可以忽略不计，因为现在的设备都是 5600r/s,7200r/s，转一圈的需要的时间微乎其微；从磁盘读取数据由于是按扇区直接读取，其时间也可以忽略不计；那么整个寻址过程中寻道是最耗时的，因为需要来回移动磁头，这是一个很重的物理操作。

磁盘读取数据的最小单位就是扇区，即使只需要读取里面的一个字节，也需要将整个扇区的内容全部读出，大多数情况下，会将周围扇区的数据也全部读取出来，称之为预读。

之前只知道读取磁盘IO会很慢，但是并不知道原因。现在知道的了，慢的原因就是寻道是哥非常耗时的操作。

PAGE_CACHE

PAGE_CACHE俗称磁盘高速缓存区，属于内核空间的一种缓存，也属于操作系统的内存。

如果采用缓存io的方式读取磁盘数据时，通常需要先经过PAGE_CACHE,它有俩个重要的特点：

• 预读: 由于计算机的局部性原理，通常读取磁盘中的某个数据时，该数据的周边数据也未来一段时间内被访问，所以会读取的数据+周边的数据一起写入PAGE_CACHE中。
  本质是为了减少读取磁盘IO的次数，如果周边数据下次真的被访问，那么直接读取PAGE_CACHE即可，而不需要再次访问磁盘。
• 合并IO: 将几个小的IO请求合并一个大的io请求来访问磁盘，这样做的目的是可以有效减少磁盘寻道的操作。至于为什么能减少可以看下磁盘的调度算法。

磁盘调度算法

带着疑问：为什么合并IO会有效减少磁盘的寻道次数呢？(也就是磁头移动的次数，磁头移动次数越多，耗时也就越多)。

磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。

寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。

假设有下面一个请求序列，每个数字代表磁道的位置，初始磁头当前的位置是在第 53 磁道。：

98，183，37，122，14，124，65，67

接下来，分别对以上的序列，作为每个调度算法的例子，那常见的磁盘调度算法有：

• 先来先服务算法
• 最短寻道时间优先算法
• 扫描算法
• 循环扫描算法
• LOOK 与 C-LOOK 算法

先来先服务算法

先来先服务（First-Come，First-Served，FCFS），顾名思义，先到来的请求，先被服务。

那按照这个序列的话：

98，183，37，122，14，124，65，67

那么，磁盘的写入顺序是从左到右，如下图：

先来先服务算法总共移动了 640个磁道的距离，这么一看这种算法，比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长。

最短寻道时间优先算法

短寻道时间优先（Shortest Seek First，SSF）算法的工作方式是，优先选择从当前磁头位置所需寻道时间最短的请求，还是以这个序列为例子：

98，183，37，122，14，124，65，67

那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序：

65，67，37，14，98，122，124，183

磁头移动的总距离是 236 磁道，相比先来先服务的总距离640磁道，寻道的次数减少不少。

又因为寻道是最耗时的，也就是说最短寻道时间算法会比先来先服务算法性能提高不少。

但这个算法可能存在某些请求的饥饿，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于 183 磁道的，那么 183 磁道可能永远不会被响应，于是就产生了饥饿现象，这里产生饥饿的原因是磁头在一小块区域来回移动。

扫描算法

最短寻道时间优先算法会产生饥饿的原因在于：磁头有可能再一个小区域内来回得移动,而导致有的区域不会被访问。

为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。

这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。

还是以这个序列为例子，磁头的初始位置是 53：

98，183，37，122，14，124，65，67

那么，假设扫描调度算先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序：

37，14，0，65，67，98，122，124，183

磁头先响应左边的请求，直到到达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。

扫描算法的总距离也是236磁道，扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。

剩下的几种算法就不一一介绍了，磁盘的调度算法就一个目的：减少磁道的总距离，选取合适的磁盘调度算法可以提高磁盘的响应时间。

调度算法小结

上面介绍了3种磁盘调度算法，可以发现先来先服务的算法性能是较差的，因为它的磁道总数是最大的。

还记得上面提到的PAGE_CACHE有个特点是合并IO吗？为什么合并IO可以有效减少寻道时间呢？

其实合并IO就是将多个IO请求一起请求磁盘；而如果不合并IO的话就是单独去请求磁盘。比如有a 、b、c、d 4个请求，

• 单个请求的寻道过程： 当每个 I/O 请求是单独的、独立的时候，磁盘的寻道过程是顺序的，即按照请求的顺序一个一个地寻道，其实就是上面提到的先来先服务算法。如果有独立的请求 a、b、c、d，寻道的顺序就是 a -> b -> c -> d。

• 合并IO请求的寻道过程： 当多个 I/O 请求被合并时，磁盘调度算法可以发挥作用。合并的请求可以被调度成一个更为优化的顺序，以最小化总体的寻道和旋转时间。。

总体而言，单个请求的寻道是按照请求的顺序进行的，即先来先服务算法，而合并请求的寻道可以受到磁盘调度算法的优化。磁盘调度算法的目标是提高磁盘 I/O 的整体性能，而不仅仅是单个请求的性能。

先来先服务算法的总磁道距离是最长的，合并请求后可以使用其他调度算法，比如最短寻道距离优先和扫描算法，这俩种算法的磁道距离肯定小于先来先服务算法，这也就是为什么合并IO请求可以有效减少寻道时间的原因。

顺序IO和随机IO

由于在磁盘中读取数据时，盘面旋转的时间和读取数据的时间可以忽略不计，主要是这个寻找磁道要花较多的时间，即移动磁头需要花费大量的时间，那么主要是在这个地方拉开时间差的。

由于顺序io是有序的，数据分布在同一个磁道里面或者相邻的磁道里，这样磁头寻道的时间就会很少,当顺序读取或写入时，磁头通常不需要频繁地寻道。这是因为在顺序 I/O 中，磁头可以保持在当前磁道上，按照逻辑顺序读取或写入相邻的数据；

具体来说，当进行顺序读取时，磁头可以依次读取一个磁道上的多个扇区，而不需要中途跳到其他磁道。这最大程度地减少了寻道的需求，因为磁头可以顺序地访问磁盘上的数据。

在顺序 I/O 中，主要的时间开销通常是由于磁盘旋转而引起的旋转延迟。一旦磁头位于正确的磁道上，连续的数据可以被顺序地读取或写入，最小化了寻道时间。

而随机IO的数据是无序的，可能数据分布在盘片中的任何一个磁道或者扇区中，这样磁头将会来回移动，进行多次寻道和旋转操作，这样的访问就是随机 I/O，寻道的时间将明显大于顺序IO的时间。

总体而言，顺序 I/O 通常更为高效，因为它能够充分利用相邻数据的顺序性，减少了寻道和旋转的时间。随机 I/O 的性能较差，因为它可能导致频繁的寻道和旋转操作。选择合适的 I/O 访问模式取决于具体的应用场景和数据存储的特点。

内存页

前面提到一个预读的概念：在读取磁盘中数据的时候通常不只读数据所在的扇区，而是将数据所在的扇区的周围扇区也一起读取，这样的做的好处是可以减少io次数；对于上面这句话有几个疑问：

• 谁在读取磁盘中的数据？
• 经常听减少IO次数，那么一次IO具体是怎么定义的?
• 到底一次IO读取磁盘中的多少数据？多少个扇区？是谁规定的？

现代的一台计算机，正常是由寄存器、 CPU Cahce、内存、到 SSD 或 HDD 硬盘这些设备组成，由上到下，访问速度越来越慢，存储容量越来越大。

每个存储器只和相邻的一层存储器设备打交道，并不会直接和每一种存储器设备直接打交道。

下图是cpu访问数据时的正常流程：

从上图中得知：读取磁盘数据的是内存，也就是内存读取数据时，不仅会将数据所在扇区的数据且会将周围扇区的数据一同写入内存中。

操作系统中内存有分段和分页俩种存储方式，对于不了解分页和分段的区别的同学可以查看我之前的一篇文章内存的段页存储。目前大多数是内存选择的是分页的方式，且每页存储大小为4kb；

页是内存读取或者写入数据的基本单位，也就是说内存从磁盘中读取时并不会一条一条的读，而是一次性会读取一页的大小，也就是4kb。看到这里，你应该知道上面提到预读时有个疑问：到底会一次性读取磁盘多少数据呢？

答案就是：内存一次性会读取磁盘一页的数据，也就是4kb的数据，而一个扇区大于为512字节，8个扇区正好是4kb，也就是说内存一次性会读取8个扇区的数据。

还记得上面提到的PAGE_CACHE吗？它就是属于操作系统内核空间的缓存（内存），且每页是4kb。

肯定有人听过，mysql中innodb引擎中的页大小为16kb，其实说的是buffer pool的页是16kb，是的buffer pool也操作系统的缓存，只是相对于page_cache的区别是：

• buffer pool是 InnoDB 存储引擎内存中的用户空间缓存，用于存储数据库表的页数据，而page_cache是操作系统内核空间的磁盘缓存，用于缓存文件系统中的数据页。
• 由于内核空间的缓存page_cache由于没有提供更多的系统函数供用户空间使用，对于用户空间来说很不友好，所以mysql团队决定自己在用户空间实现了一层缓存，这样操作更加灵活可控。
• 对于缓存io来说，都是先查询内核空间的page_cache,如果不存在时再查询磁盘。而对于mysql来说，是先查询用户空间的buffer pool，如果不存在时则在查询磁盘，中间则不会在走内核空间的缓存。
• page_cache的页大小为4kb,而buffer poll的页大小是16kb。也就是说page_cache一次性会读取磁盘4kb的数据，而buffer pool则会一次性读取磁盘的16kb的数据。

知道了上面这些知识后，来解答最后一个问题，什么叫做一次IO?

开门见山，一次IO操作就是内存读取一次磁盘的操作，换句话说就是内存读取磁盘一页数据的操作，也就是page_cache一次读取磁盘4kb的操作或者是buffer pool一次读取磁盘16kb的操作。

一次IO只能从磁盘读取内存一页大小的的数据，如果从磁盘读取的数据大小大于一页，就需要多次IO，多次IO就意味需要多次查询磁盘，而上面介绍了查询磁盘过程中是很耗时的，主要耗时操作是磁头移动寻道的过程，也就知道了为什么减少io操作是性能优化的关键。

这也是为什么B+tree树中的每个节点大小是16kb，正好是页大小的原因。如果节点小于16kb，容易造成内存页内碎片化；如果节点大于16kb,将会造成读取一个节点需要多次io的问题。

看到这里其实我有一个问题：为什么buffer pool要设置成页大小为16k,而不像page_cache一样设置成4k呢？肯定是有它的原因的，下面是我一些自己的想法，也不知道理解的对不对，如果有人知道可以评论区回复我：

假设需要读取磁盘中的16k的数据，磁盘每个扇区是512个字节，也就是需要读取16个扇区，4条磁道的数据：

1. 假设buffer poll的页大小设置为16k时只需要读取一次IO；而如果页大小设置为4kb的时候，将需要4次IO。很明显大页相对于小页读取相同数据时可以减少IO次数，对应的就是减小了系统开销，一定程度上提高了吞吐量。
2. mysql索引使用的是B+tree结构，该结构页内的行数据都是有序的，也就是页内数据在磁盘中是顺序io，而页和页之间是通过链表逻辑相连的，为了使页和页之前也能实现顺序io,mysql有一个区的概念，区内的所有页是顺序io，一个区大概是1M,也就是说最多16个页的是顺序io。
   说这么多背景，其实就是想说，不管buffer poll的页是设置成16k还是4k，读取的这个16k在磁盘中都是顺序io，且一个磁道是4k数据大小，也就是分布在4条磁道。
   那么1次io（顺序io从磁道1读取到磁道4）和4次io（分别寻道4次）的寻道时间（io中最耗时的操作）其实是相同的。
   而上面介绍的寻址时间 = 寻道时间 + 盘片旋转时间 + 读取和传输数据的时间，寻道时间和盘片旋转的时间对于1次io和4次io来说是大致相同的，但是可以却减少读取和传输的时间，因为1次io只需要一次读取和传输的时间而4次io却需要4次。所以虽然可以减少io次数，但是1次io和4次io的耗时我觉得也不会相差太多，不知道我理解的对不对？大神可评论区回复我。

下面是比较官方的一些解释：

1. 性能考虑：大页面可以容纳更多的数据，因此每次 I/O 操作涉及的数据量相对较大，从而减少 I/O 操作的次数。
   大页面可能导致更好的内存局部性，因为在一次 I/O 中读取的数据更可能被后续查询操作所使用，减少了内存访问的随机性。
2. 减少元数据开销：较大的页面大小可以降低页面管理的开销。每个页面都有一些元数据，包括页头等信息，较大的页面减少了这些开销的相对比例。
3. 磁盘块的特性：在某些情况下，与磁盘块大小（一条磁道的所有扇区数据）对齐的页面大小可能有助于提高 I/O 操作的效率。磁盘块通常是 4KB，因此选择 16KB 作为页面大小可以确保一个页面完全位于一个或多个磁盘块中。
4. 应对大型事务：较大的页面大小可以更好地支持大型事务，因为它们能够容纳更多的数据。这对于某些特定的应用场景可能是重要的。

较大页的优势：

• 减少 I/O 操作次数： 大的页大小意味着每次 I/O 操作可以传输更多的数据，从而减少了 I/O 操作的总数，提高了数据传输效率。
• 提高缓存命中率： 大的页可以容纳更多的数据，提高了在内存中的缓存命中率，减少了对磁盘的访问。
• 适用于大型数据块的操作： 对于大型数据块的操作（如大型查询），较大的页可以更好地利用传输带宽。

较大页可能带来的问题：

• 内存占用： 较大的页可能导致更多的内存占用，因为每个页都需要在内存中分配一块空间。
• 碎片问题： 如果数据库中存在很多小型的、零散分布的数据块，较大的页可能导致内部碎片问题，因为一页需要存储一整块数据。
• 冷热数据分离问题： 对于热点数据和冷数据，较大的页可能导致一些效率问题，因为每次 I/O 操作都会传输较大的数据块。

较小页的优势：

• 适用于小型数据块： 对于小型的、频繁访问的数据块，较小的页可以更好地适应。
• 减少内部碎片： 较小的页可以减少内部碎片问题，因为一页不需要存储大块的空闲空间。
• 适用于内存有限的环境： 如果系统的可用内存有限，较小的页可以更好地利用内存。
• 在选择页大小时，需要权衡这些因素，并考虑具体的应用场景和性能需求。对于大多数数据库系统，包括 MySQL InnoDB 存储引擎，默认的页大小通常已经在绝大多数情况下进行了合理的优化。

参考

顺序io和随机io
搞懂计算机磁盘实现原理