操作系统--硬盘与B+树

对于操作系统方面的知识不是很了解,现在偷偷补习下。

机械硬盘

结构与概念

机械硬盘仍然是数据存储的主流,一块机械硬盘往往有以下组件构成:

  • 盘片:一块机械硬盘是由多个盘片叠加组成,盘片为了提高存储能力,一般设计成双面结构。
  • 磁道:磁盘格式化时划分出来的同心圆,磁盘有存储磁道也有备份磁道,所以一般格式化后的容量比真实容量少一些。
  • 柱面:每个盘面上相同磁道构成的一个圆柱面,称为柱面,当文件在一个磁道写满后,会继续在同一柱面下的下一个磁道进行写入。
  • 块:机械硬盘本身没有块的概念,操作系统层面为了速度更快,会把多个连续扇区映射为一个块,一般是4k,对于操作系统最小的读取写入单位就是块。
  • 扇区:磁道会划分为多个扇区,每个扇区固定大小,扇区是读取和写入最小单位。也就是说读取1byte的数据和读取一个扇区(512byte)的所有数据是一个代价的。

清单1:磁盘构造

  • 传动臂:一根轴与多个读写针头组成的结构,每一个盘片都有一个独立的读写针头,读写针头通过半径上的移动可以获取到对应盘面的所有数据。
  • 磁盘控制器:相当于中间层,解耦I/O总线和磁盘的依赖关系,其会翻译I/O总线的指令,然后控制磁盘获取到数据后再回复I/O总线,相当于软件设计中的proxy层。

清单2:磁盘传动臂

如何读写数据?

由上述结构可以发现,磁盘上一个具体数据的坐标为(盘面,磁道,扇区)三元组构成,因此CPU在读取数据时会依次发送三条指令(磁盘读或写,数据逻辑块地址,对应的主内存地址),由于CPU(ns)和硬盘(ms)之间有着非常大的速度差异,因此CPU不会等待硬盘读写完成,而是去完成其他的任务。硬盘控制器接收到CPU的指令,会转换为对应的数据块地址,然后通过DMA(直接内存访问)的方式,传输到对应的主存中,再向CPU发起一个通知告知其数据已准备完毕,CPU再转过来继续之前的任务。

这种做法和后端常说的异步非阻塞I/O比较类似,可以类比来理解,异步体现在当硬盘读写完毕后是主动通知CPU,而不是CPU主动询问,非阻塞体现在CPU发起一个读或者写之后仍然可以做其他的事情。

固态硬盘

结构与概念

固态硬盘相比机械硬盘有着更高的读取写入速度,但是寿命却短的多,其一般有以下结构:

  • 闪存:可以类比为机械硬盘的盘面。其内部由多个块组成。
  • 块:可以类比为机械硬盘的磁道。一般由32页-128页组成。
  • 页:可以类比为机械硬盘的扇区。一般由512byte到4kb大小
  • 闪存翻译层:可以类比为机械硬盘的传动臂,接收I/O总线的指令后翻译为固态硬盘的地址,这也是proxy最大的解耦优势,因此对于操作系统来说机械和固态并无本质区别,只是一个快一个慢而已。

清单3:固态硬盘结构

寿命如何保证?

SSD每个块的寿命相比机械硬盘的磁道要短得多,本质原因是SSD每一个块的擦除寿命有限,因此SSD在数据写入时会均衡的使用每一个块,利用块的数量优势最大化整个硬盘的寿命,因此需要记录每个块的擦除次数,然后每次重新写入时选择最小次数的块。

B+树如何利用磁盘结构?

Mysql的索引以及一些文件系统经常会用到B+树作为底层数据机构,这其中的原因就是B+树的设计结合了硬盘的工作原理,使得每次查找尽可能的使用最少的磁盘I/O操作
清单4:B+树结构

上述结构图蓝色部分可以理解为索引,黄色部分是指向下一层的指针,紫色部分则是具体的文件数据。B+树最大的特点就是非叶子节点存储大量索引信息,叶子节点存储具体的数据,并且叶子节点使用链表串联起来方便遍历,对于一个范围查找,根据索引定位到具体的起始点之后便可以直接遍历链表进行查找,速度自然会快很多。

那么这和硬盘有什么关系呢?
由于硬盘速度远小于内存,因此当进行查找时的一个原则是:使用最少的磁盘I/O,获得更多的数据信息,那么B+树就是为这原则而定制的,对于B+树来说其树的深度一般不会超过5层,500w的数据三层即可解决,那么就只需要3次磁盘I//O,第二由于操作系统一般按照块来读取,因此B+树的每一个节点尽可能的存放更多的索引信息,占满一个块,一次磁盘I/O就能够获取到更多的索引信息,进而变相的降低磁盘I/O的数量。

对于操作系统相关的知识对于我来说只需要理解,并不需要深究,因此可能会有些描述错误,如有问题还请指出。

Hadoop--Map与Reduce
小宁子 --《曾经我也想过一了百了》