磁盘文件系统

1 首先介绍一下磁盘结构

信息存储在硬盘里，硬盘是由很多的盘片组成，通过盘片表面的磁性物质来存储数据。把盘片放在显微镜下放大，可以看到盘片表面是凹凸不平的，凸起的地方被磁化，代表数字 1，凹的地方没有被磁化，代表数字 0，因此硬盘可以通过二进制的形式来存储表示文字、图片等的信息。

硬盘有很多种，但是都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部分组成。

磁头：

所有的盘片都固定在一个旋转轴上，这个轴即盘片主轴。所有的盘片之间是绝对平行的，在每个盘片的盘面上都有一个磁头，磁头与盘片之间的距离比头发丝的直径还小。每个磁头同一时刻必须是同轴的，即从正上方往下看，所有磁头任何时候都是重叠的。盘片以每分钟数千转到上万转的速度在高速运转，这样磁头就能对盘片上的指定位置进行数据的读写操作。磁头靠近主轴接触的表面，即线速度最小的地方，是一个特殊的区域，它不存放任何数据，称为启停区或者着陆区，启停区外就是数据区。

盘面：

硬盘的盘片一般用铝合金材料做基片，硬盘的每一个盘片都有上下两个盘面，一般每个盘面都会得到利用，都可以存储数据，成为有效盘面，也有极个别的硬盘盘面数为单数。每一个这样的有效盘面都有一个盘面号，按顺序从上至下从 0 开始编号。

在硬盘系统中，因为每个盘面都会有一个对应的磁头，两者之间存在一一对应关系故盘面号又叫磁头号。

磁道：

磁盘在格式化时被划分成许多同心圆，这些同心圆轨迹叫做磁道。磁道从外向内从 0 开始顺序编号，硬盘的每一个盘面有 300-1024 个磁道，新式大容量硬盘每面的磁道数更多，信息以脉冲串的形式记录在这些轨迹中，这些同心圆不是连续记录数据，而是被划分成一段段的圆弧。这些圆弧的角速度一样，由于径向长度不一样，所以线速度也不一样，外圈的线速度较内圈的线速度大，即同样的转速度下，外圈在同样时间段里，划过的圆弧长度要比内圈划过的圆弧长度大。每段圆弧叫做一个扇区，扇区从 1 开始编号，每个扇区中的数据作为一个单元同时读出或写入。在最外圈，离主轴最远的地方是 “0” 磁道，硬盘数据的存放就是从最外圈开始的。

柱面：

所有盘面上的同一磁道从上而下构成一个圆柱，通常称作柱面。每个圆柱上的磁头由上而下从 0 开始编号，数据的读 / 写按柱面进行，即磁头读 / 写数据时首先在同一柱面内从 0 磁头开始进行操作，依次向下在同一柱面的不同盘面即磁头上进行操作。

只有在同一柱面所有的磁头全部读 / 写完毕后磁头才转移到下一柱面（同心圆再往里的柱面），因为选取磁头（只是同一个柱面上不同磁道选择）只需要通过电子切换即可，而选取柱面则必须机械切换，电子切换相当快，比在机械上的磁头向邻近磁道移动快得多。所以，数据的读 / 写按柱面进行，而不按盘面进行，也就是说，一个磁道写满数据后，就在同一柱面的下一个盘面来写，一个柱面写满后，才移到下一个扇区开始写数据，读数据也按照这种方式进行，这样就提高了硬盘的读 / 写效率。

扇区：

每个磁道上由多个扇区组成。操作系统以扇区形式将信息存储在硬盘上，每个扇区包括 512 个字节的数据和一些其他信息，一个扇区有两个主要部分：存储数据地点的标识符和存储数据的数据段。标识符就是扇区头标，包括组成扇区三维地址的三个数字：盘面号，柱面号，扇区号（块号）。

2 访盘请求过程

1）确定磁盘地址（柱面号，磁头号也就是盘面号，扇区号），内存地址（源 / 目）：

当需要从磁盘读取数据的时候，系统会将数据的逻辑地址传递个磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

2）为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点：

• A. 首先必须找到柱面和盘面，即磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间。

• B. 然后目标扇区旋转到磁头下，即磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

3）即一次访盘请求（读 / 写）完成过程由三个动作组成：

• A. 寻道（时间）：磁头移动定位到指定磁道。

• B. 旋转延迟（时间）：等待指定扇区从磁头下旋转经过。

• C. 数据传输（时间）：数据在磁盘与内存之间的实际传输。

系统将文件存储到磁盘上时，按柱面、磁头（盘面）、扇区的方式进行，即最先是第 1 磁道（最外层柱面）的第一磁头（磁面）下的所有扇区，然后是同一柱面的下一个磁头……。一个柱面存储满后就推进到下一个柱面，直到把文件内容全部写入磁盘。系统也以相同的顺序读出数据，读出数据时通过告诉磁盘控制器要读出扇区所在柱面号、磁头号和扇区号（物理地址的三个组成部分）进行。

为了提高效率，要尽量减少磁盘的 I/O，根据局部性原理，磁盘往往不是严格地按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。预读的长度一般为页（Page）的整数倍。页是计算机管理存储器的逻辑块，主存和磁盘以页为单位交换数据，当程序要读取的数据不在主存中时，会触发一个缺页异常。此时系统会向磁盘发出读盘信息，磁盘会找到数据的起始位置并向后连续读取一页或几页的数据载入内存中，然后异常返回，程序继续运行。

3 B树以及B+树实现磁盘文件系统

B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。

为了描述 B-Tree，首先定义一条数据记录为一个二元组 [key, data]，key 为记录的键值，对于不同数据记录，key 是互不相同的；data 为数据记录除 key 外的数据。B-Tree 中的每个节点根据实际情况可以包含大量的关键字信息和分支，例：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针也就是下一个磁盘块的地址，即指针存储的是子节点所在磁盘块的地址。

以根节点为例，关键字为 17 和 35，P1 指针指向的子树的数据范围为小于 17，P2 指针指向的子树的数据范围为 17~35，P3 指针指向的子树的数据范围为大于 35。

模拟查找关键字 29 的过程：

1. 根据根节点找到磁盘块 1，读入内存。【磁盘 I/O 操作第 1 次】

2. 比较关键字 29 在区间（17,35），找到磁盘块 1 的指针 P2。

3. 根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I/O 操作第 2 次】

4. 比较关键字 29 在区间（26,30），找到磁盘块 3 的指针 P2。

5. 根据 P2 指针找到磁盘块 8，读入内存。【磁盘 I/O 操作第 3 次】

6. 在磁盘块 8 中的关键字列表中找到关键字 29。

分析上面过程，发现需要 3 次磁盘 I/O 操作，和 3 次内存查找操作。

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构，

在 B-Tree 中，每个节点中有 key，也有 data，而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小。当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

由于 B+Tree 的非叶子节点只存储键值信息，假设每个磁盘块能存储 4 个键值及指针信息，则变成 B+Tree 后其结构如下图所示：