点滴之间 聚沙成金

本文探讨硬盘分区中的数据结构。
先回顾一下数据结构的定义：
数据结构是据数据之间的关系，包括数据之间的逻辑关系，数据在计算机中的存储方式（存储结构）和数据的运算三个方面。
大家在学习计算机知识时一定不要思想僵化，比如学数据结构，就认为只有教科书上定义的什么树啊、链表啊、队列啊等等才是数据结构，其实从根本上说，凡是符合以上定义的东西都是数据结构，而这种东西在计算机里随处可见，比如这里说到的硬盘分区方式，以及FAT表、NTFS表，目录存储方式等等都是数据结构，而且有些是非标准的，比如今天讲到的硬盘分区方式就是树和链表的结合，而FAT实际上应该类似于位图的方式（？有待进一步研究），这些都不是标准的方式，其实也用不着研究那么多，在这里引用数据结构的概念是要大家注意硬盘分区所用到的逻辑关系（树和单链表），存储结构（分区表）和运算（硬盘分区的识别过程以及计算机硬盘方式启动的过程）。
闲话少说，书归正传。
一、硬盘的物理结构
硬盘存储数据是根据电、磁转换原理实现的。硬盘由一个或几个表面镀有磁性物质的金属或玻璃等物质盘片以及盘片两面所安装的磁头和相应的控制电路组成 ，其中盘片和磁头密封在无尘的金属壳中。
硬盘工作时，盘片以设计转速高速旋转，设置在盘片表面的磁头则在电路控制下径向移动到指定位置然后将数据存储或读取出来。当系统向硬盘写入数据时，磁头中 “ 写数据 ” 电流产生磁场使盘片表面磁性物质状态发生改变，并在写电流磁场消失后仍能保持，这样数据就存储下来了；当系统从硬盘中读数据时，磁头经过盘片指定区域，盘片表面磁场使磁头产生感应电流或线圈阻抗产生变化，经相关电路处理后还原成数据。因此只要能将盘片表面处理得更平滑、磁头设计得更精密以及尽量提高盘片旋转速度，就能造出容量更大、读写数据速度更快的硬盘。这是因为盘片表面处理越平、转速越快就能越使磁头离盘片表面越近，提高读、写灵敏度和速度；磁头设计越小越精密就能使磁头在盘片上占用空间越小，使磁头在一张盘片上建立更多的磁道以存储更多的数据。
硬盘由很多盘片 (platter) 组成，每个盘片的每个面都有一个读写磁头。如果有 N 个盘片。就有 2N 个面，对应 2N 个磁头 (Heads) ，从 0 、 1 、 2 开始编号。每个盘片被划分成若干个同心圆磁道 ( 逻辑上的，是不可见的。 ) 每个盘片的划分规则通常是一样的。这样每个盘片的半径均为固定值 R 的同心圆再逻辑上形成了一个以电机主轴为轴的柱面 (Cylinders) ，从外至里编号为 0 、 1 、 2…… 每个盘片上的每个磁道又被划分为几十个扇区 (Sector) ，通常的容量是 512byte ，并按照一定规则编号为 1 、 2 、 3…… 形成 Cylinders×Heads×Sector 个扇区。这三个参数即是硬盘的物理参数。我们下面的很多实践需要深刻理解这三个参数的意义。
二、硬盘分区的逻辑结构：
前面已经说过，硬盘分区的逻辑结构是树结构和链表结构的混合产物。其中主分区表和各主分区及扩展分区之间构成树结构，以主分区表为树根，各分区为子结点构成一棵二层的树。而扩展分区中各逻辑分区之间以链表结构存储，从第一逻辑分区到最后一个逻辑分区依次构成单链表。
从数据的逻辑结构上我们可以看出，其实硬盘的数据存储应该是很脆尽善弱的。在这种结构中一旦作为树根的主引导扇区被破坏，则整个硬盘分区信息都将被破坏，另一方面，如果逻辑分区表中中间的任一结点被破坏则后面结点（分区）的信息都将丢失，如果不幸恰好是第一个逻辑分区的分区表被破坏，则其后的所有逻辑分区信息都将丢失。
三、硬盘分区的存储结构：
简单的说：硬盘分区的存储结构有如下特点：
１、因为历史的原因，硬盘分区表总是和主引导代码（或分区引导代码）混合构成一个扇区（512bytes）进行存储，主引导扇区（存储主引导代码和主分区表）和各分区的引导扇区（存储分区引导代码和分区表）的结构完全相同。
２、分区表（主分区表和各分区中的分区表）的信息以记录方式（每个记录16bytes）顺序存领储（顺序表）。每个记录中以特定的指针指向下一个结点。
下面进行详细的解释：
（一）、分区表的结构：
引导扇区，包括主引导扇区和各分区的引导扇区均由三部分构成，即引导代码、分区表
和结束标志。
在主引导扇区MBS(master boot sector)——即硬盘的0柱0面1扇中，这三部分被称为MBR——Main/Mastr Boot Record主引导记录、DPT——Disk PArtition Table主分区表和MagicNumber结束标志
其中MBR占据整个512字节中的446个字节，DPT占据其中的64个字节，而结束标志只占２个字节。
（二）、主引导记录：偏移0–偏移1BDH
主引导记录中包含了硬盘的一系列参数和一段引导程序。引导程序主要是用来在系统硬件自检完后引导具有激活标志的分区上的操作系统。它执行到最后的是一条JMP指令跳到操作系统的引导程序去。
这一部分可以用fdisk /mbr(dos/win 95/win 98/win me)或fixmbr(win 2k/win xp)或　dd if=/boot/boot.NNNN of=/dev/hda bs=446 count=1(linux)进行恢复。
注释１：
“Fdisk /mbr”命令只是恢复主分区表，并不会对它重新构建，因此只适用于主引导区记录被引导区型病毒破坏或主引导记录代码丢失，但主分区表并未损坏的情况使用。而且这个命令并不适用于清除所有引导型病毒，因此使用的时候需要注意。 （ 微软的FDISK程序中本身包含这段代码）
微软的这段程序的功能是查找引导分区（活动分区）信息，如果没有或为两个以上，则显示：Invalid partition table, Error loading operating system,Missing operationg system.，否则再按引导分区项读取对应引导扇区，判断结尾是否为55AA，是的话把CPU控制权交给引导扇区的引导程序（JMP到相应程序），否则引导失败。
注释２：
在Windows 2000/XP中，我们一般会用到故障恢复控制台集成的一些增强命令，比如Fixmbr用于修复和替换指定驱动器的主引导记录、Fixboot用于修复知道驱动器的引导扇区、Diskpart能够增加或者删除硬盘中的分区、Expand可以从指定的CAB源文件中提取出丢失的文件、Listsvc可以创建一个服务列表并显示出服务当前的启动状态、Disable和Enable分别用于禁止和允许一项服务或者硬件设备等等，而且输入“help”命令可以查看到所有的控制命令以及命令的详细解释。
比如输入“fixmbr”命令可以让控制台对当前系统的主引导记录进行检查，然后在“确定要写入一个新的主启动记录吗?”后面输入“Y”进行确认，这样就完成了主引导记录的修复。
注释３：
dd if=/boot/boot.NNNN of=/dev/hda bs=446 count=1
上面的命令是为了修复可能被病毒修改了的主引导记录MBR，或者想把LILO卸载掉，而不是恢复整个主引导扇区。所以我们只把主引导扇区的备份文件boot.NNNN的前446个字节重写入主引导扇区。
boot.NNNN是我们在安装Linux之前整个主引导分区的备份。如果我们把512个字节全部写入主引导扇区就可能会把安装了Linux后改变了的硬盘DPT表也破坏掉。那就坏事了。 :-)
注释３：
对于这个MBR，MS非常霸道，如果你安装了LINUX的GRUB,你就别想在硬盘中安装WINDOWS，这个问题的最好解决办法是： fdisk /mbr，如果你硬盘中的什么东西都不要的话，也可以往MagicNumber中写入乱码，让WINDOWS安装程序认为MBS信息非法，然后用安装程序重新分区即可。
注释４：
许多操作系统都有自己的MBR，当然你也可以写出自己的MBR程序来做多重引导。
（三）、DPT——硬盘分区表：偏移1BEH–偏移1FDH
由4个16字节的分区信息记录组成，共64个字节。
每个分区信息记录格式如下：
偏移 长度 所表达的意义
0 字节 分区状态： 如0–>非活动分区　　80–> 活动分区
1 字节 该分区起始头(HEAD)
2 字 该分区起始扇区和起始柱面
4 字节 该分区类型： 如82–> Linux Native分区　　83–> Linux Swap 分区
5 字节 该分区终止头(HEAD)
6 字 该分区终止扇区和终止柱面
8 双字 该分区起始绝对分区
C 双字 该分区扇区数
注释1：
注意分区的起始地址（面/扇区/磁道）和结束地址（面/扇/道）中字节分配:
00000000 01000001 00010101
~~~~~~~~ ==^^^^^^ ========
~ 面(磁头) 8 位
^ 扇区 6 位
= 磁道 10 位
注释２：
分区的操作系统类型(文件格式标志码)
00H–未知类型或不用
01H–12位FAT
04H—DOS FAT1632M
0BH–FAT32容量最大2G
0CH–FAT32,采用LBA模式，调用int 13h扩展中断
0FH–扩展FAT32分区，采用LBA模式，调用int 13h扩展中断
07H—NTFS(OS/2)
82H–linux
83H—LINUX swap>64M
注释３：
DPT 总共64字节（01BE–01FD）, 如上所示每个分区占16个字节, 所以可以表示四个分区, 这也就是为什么一个磁盘的主分区和扩展分区(注意，不是逻辑分区)之和总共只能有四个的原因.
注释４：
硬盘分区规范规定：一个硬盘可以有多个主分区（Primary partition）,但最多只能有一个扩展分区。因此，你可以有四个主分区，三个主分区，二个主分区，一个主分区，一个主分区加一个扩展分区，二个主分区加一个扩展分区，三个主分区加一个扩展分区几种情形，但MS非常懒，规定只能有一个主分区，一个扩展分区，其他操作系统没有这个规定。MS的办法是在扩展分区中再设置逻辑分区。
扩展分区的信息位于以上所示的硬盘分区表（DPT）中, 而逻辑驱动器的信息则位于扩展分区的起始扇区, 即该分区的起始地址（面/扇区/磁道）所对应的扇区, 该扇区中的信息与硬盘主引导扇区的区别是不包含MBR, 而16字节的分区信息则表示的是逻辑驱动器的起始和结束地址等.
所以, 在磁盘仅含有一个主分区, 一个扩展分区(包含多个逻辑驱动器)的情况下, 即使由于病毒或其他原因导致硬盘主引导扇区的数据丢失(包括DPT), 也可以通过逻辑驱动器的数据来恢复整个硬盘.
(四）、MagicNumber结束标记(有的称为BRI——boot record ID引导记录标志)：偏移1FEH偏移1FFH
最后的两个标志“55 AA”是分区表的结束标志，如果这两个标志被修改(有些病毒就会修改这两个标志)，则系统引导时将报告找不到有效的分区表。