一种HFS+文件系统数据恢复方法及装置

摘要

本发明涉及一种HFS+文件系统数据恢复方法及装置，方法包括以下步骤：A、以扇区为单位对存储介质中的文件进行扫描；B、从被扫描文件中查找卷头，如果查找到卷头，执行步骤C，否则执行步骤A，扫描下一扇区；C、从所查找到的卷头所对应的目录文件中查找头节点，如果查找到头节点，则执行步骤F，否则执行步骤D；D、判断所查找的卷头是否是备份卷头，如果是备份卷头，执行步骤E，否则执行步骤A，扫描下一扇区；E、定位头节点，如果定位到头节点，则执行步骤F，否则执行步骤A，扫描下一扇区；F、遍历所有定位到的头节点中所包含的B-树，恢复文件数据。采用上述方法可以恢复存储介质上曾经存在过的HFS+格式文件系统中的文件。

权利要求

1.一种HFS+文件系统数据恢复方法，其特征在于，包括以下步骤：

A、以扇区为单位对存储介质中的文件进行扫描；

B、从被扫描文件中查找卷头，如果查找到所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

C、根据头节点的节点描述符中的各字段和头档案中的各字段,从所查找到的所述卷头所对应的目录文件中查找头节点，如果查找到头节点，则执行步骤F，否则执行步骤D；

D、判断所述卷头是否是备份卷头，如果是备份卷头，执行步骤E，否则执行步骤A，扫描下一扇区；

E、根据所述备份卷头的位置逆推出所述卷头的位置，再根据所述卷头位置和备份卷头的各个字段定位头节点，如果定位到头节点，则执行步骤F，否则执行步骤A，扫描下一扇区；

F、遍历所有定位到的头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据；

所述步骤C中，查找所述头节点方法为：

判断所述头节点的节点描述符中的各字段和所述头节点的头档案的各字段，如果所述头节点的节点描述符中的上一个节点号等于0、节点类型等于1、节点高度等于0、档案数等于3以及保留字段等于0；

且所述头节点的头档案的根节点号大于0且小于节点总数、未使用节点数小于节点总数、第一个叶节点号小于节点总数、最后一个叶节点号以及小于节点总数，则认为是所述头节点；

所述步骤F包括步骤：

F1、查找叶节点，从所述头节点的开始偏移处读出B树的每个节点，判断所读出节点的节点描述符的各字段，如果所读出节点的节点描述符的节点类型等于-1、节点高度小于

16、且保留字段等于0，则判断为所述叶节点，执行步骤F2；F2、恢复文件数据，解析所述叶节点中记录的档案信息，分解出目录档案项和文件档案项，根据所述文件档案项中的数据叉记录的位置信息和大小信息恢复文件。

2.根据权利要求1所述的HFS+文件系统数据恢复方法，其特征在于，所述步骤B中，查找所述卷头时，判断文件的卷头签名，如果所述文件的卷头签名16进制为0x482b、且版本等于4，或者所述文件的卷头签名16进制为0x4858、且版本等于5，则为所述卷头。

3.根据权利要求2所述的HFS+文件系统数据恢复方法，其特征在于，所述步骤B还包括以下步骤的任意一个或并列多个：步骤B1、判断文件的卷属性，如果所述卷属性等于0x80002000或者等于0x80000000，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

步骤B2、判断文件的最后装载版本，如果所述最后装载版本16进制为0x4846534a或者

0x46534b21，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；步骤B3、判断文件的创建日期，如果所述创建日期不等于0、且修改日期不等于0、且校验日期不等于0，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

步骤B4、判断文件的分配块大小，如果所述分配块大小等于0x1000、且资源叉默认块组大小等于0x10000、且数据叉默认块组大小等于0x10000，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

步骤B5、判断文件中的分配文件、域溢出文件、目录文件、属性文件和启动文件，如果所述分配文件、域溢出文件、目录文件、属性文件和启动文件的逻辑大小等于分配块大小乘以总块数、且域描述符的分配块数的总和等于总块数，则为所述卷头。

4.根据权利要求1所述的HFS+文件系统数据恢复方法，其特征在于，所述步骤C中，所述头节点的头档案还需要满足以下任意一个或多个条件：节点大小介于512与32768之间；

节点类型为0；

树最大高度大于0且小于16。

5.根据权利要求1所述的HFS+文件系统数据恢复方法，其特征在于，所述步骤F1中，查找所述叶节点还需满足以下任意一个条件或两个条件：所读出节点的节点描述符的下一个节点小于或等于头节点的头档案的节点总数；所读出节点的上一个节点号小于或等于头节点的头档案的节点总数。

6.一种HFS+文件系统数据恢复装置，其特征在于，包括扇区扫描模块、卷头查找模块、头节点查找模块、备份卷头判断模块、头节点定位模块和文件恢复模块：其中，所述扇区扫描模块，用于以扇区为单位对存储介质中的文件进行扫描；

所述卷头查找模块，用于从被扫描文件中查找卷头，如果查找到所述卷头，则触发所述头节点查找模块，查找头节点，否则触发所述扇区扫描模块，继续扫描下一扇区；

所述头节点查找模块，用于根据头节点的节点描述符中的各字段和头档案中的各字段,从所查找到的所述卷头所对应的目录文件中查找头节点，如果定位到所述头节点，则触发所述文件恢复模块，恢复文件数据，否则触发所述备份卷头判断模块，判断卷头是否是备份卷头；

所述备份卷头判断模块，用于判断所述卷头是否是备份卷头，如果查找到所述备份卷头，则触发所述头节点定位模块，定位头节点，否则触发所述扇区扫描模块，继续扫描下一扇区；

所述头节点定位模块，用于根据所述备份卷头的位置逆推出所述卷头的位置，再根据所述卷头位置和备份卷头的各个字段定位头节点，如果定位到所述头节点，则触发所述文件恢复模块，恢复文件数据，否则触发所述扇区扫描模块，继续扫描下一扇区；

所述文件恢复模块，用于遍历所有定位到的头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据；所述文件恢复模块还用于查找叶节点，从所述头节点的开始偏移处读出B-树的每个节点，判断所读出节点的节点描述符的各字段，如果所读出节点的节点描述符的节点类型等于-1、节点高度小于16、且保留字段等于0，则判断为所述叶节点，并恢复文件数据，解析所述叶节点中记录的档案信息，分解出目录档案项和文件档案项，根据所述文件档案项中的数据叉记录的位置信息和大小信息恢复文件；

所述头节点查找模块包括：

头节点判断单元，用于判断所述头节点的节点描述符中的各字段和所述头节点的头档案的各字段，如果所述头节点的节点描述符中的上一个节点号等于0、节点类型等于1、节点高度等于0、档案数等于3以及保留字段等于0，且所述头节点的头档案的根节点号大于0且小于节点总数、未使用节点数小于节点总数、第一个叶节点号小于节点总数、最后一个叶节点号以及小于节点总数，则认为是所述头节点。

7.根据权利要求6所述的HFS+文件系统数据恢复装置，其特征在于，所述卷头查找模块包括：卷头签名判断单元，用于在查找所述卷头时，判断文件的卷头签名，如果所述文件的卷头签名16进制为0x482b、且版本等于4，或者所述文件的卷头签名16进制为0x4858、且版本等于5，则为所述卷头。

说明书

一种HFS+文件系统数据恢复方法及装置

技术领域

[0001] 本发明涉及计算机应用技术领域，更具体地说，涉及一种HFS+文件系统数据恢复方法及装置。

背景技术

[0002] 分层文件系统(Hierarchical File System，HFS)是苹果机的Mac操作系统所使用的一种文件系统，Mac操作系统早期使用HFS文件系统，HFS+是HFS的升级版本，在HFS的基础上做了一些重要的改进，HFS+卷的组织结构如图1所示。

[0003] 其中包括：保留区域(Reservide)，该区域数据为全0；卷头(Volume Header)，每个HFS+卷都必须有一个卷头，卷头内存储着各种与卷相关的信息，如卷建立的日期和时间，卷内的文件数量等，还有卷的其他重要结构的存储位置；备份卷头(Alternate Volume Header)，卷头的备份；分配文件(Alternate File)，用来描述一个分配快是被占用还是空闲；域溢出文件(Extents Overflow File)，多于8个域的文件信息，超出的部分保存在这里；目录文件(Catalog File)，用来描述卷内的文件和目录层次结构，它存储着卷内所有文件和目录的重要信息，目录文件的B-树(B-tree)结构可以快速而有效地在一个层次很多的大目录中寻找目标文件；属性文件(Attributes File)，用来保存文件或目录的附加信息；启动文件(Startup File)。

[0004] 苹果机用B-tree结构来对数据进行管理，用它作为索引，通过这个索引就可以找到我们需要的文件。B-tree是一种多路搜索树，它必须满足：1、定义任意非叶子节点最多只有M个儿子，且M＞2；2、根节点的儿子数为[2，M]；3、除根节点以外的非叶子节点的儿子数为[M/2，M]；4、每个节点存放至少M/2-1(取上整)和至多M-1个关键字(至少2个关键字)；5、非叶子节点的关键字个数＝指向儿子的指针个数-1；6、非叶子节点的关键字：K[1]，K[2]，...K[M-1]；且K[i]＜K[i+1]；7、非叶子节点的指针：P[1]，P[2]，...，P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1]，K[i])的子树；8、所有叶子节点位于同一层。

[0005] B-tree文件被分割成固定大小的“节点(Node)”每个节点中都包含相应的档案项。每个档案项由一个关键字(key)和一些数据组成。HFS+文件中，共有4种节点：头节点，图节点，索引节点和叶节点。其中，索引节点和叶节点如图2所示，索引节点用于索引其他的索引节点，或者索引叶节点，叶节点用于查找数据，节点的每个记录项的内容格式是什么，要看这个节点是子节点还是叶子节点，且是属于目录文件还是域溢出文件等等。

[0006] B-tree文件中的头节点是B-tree的第一个节点，每棵B-tree有一个唯一的头节点，结构如图3所示，它包含B-tree中如何找到其他节点的信息，其中包括：节点描述(Node Descriptor)、B-树头记录(B-tree Header Record)、用户数据记录(User Data Record)、B-树地图记录(B-tree Map Record)、偏移至空余空间(Offset to Free Space)、偏移至记录2(Offset to Record 2)、偏移至记录1(Offset to Record 1)、偏移至记录0(Offset to Record 0)。

[0007] 现有的苹果机系统中，当本来是HFS+文件系统分区被重新分区，或被重新格式化，或者分区表损坏无法识别分区，或者无法识别是什么格式的文件系统时，采用目前的各种数据恢复软件均无法恢复之前HFS+文件系统中的文件，因此会导致用户丢失重要文件信息。

发明内容

[0008] 本发明要解决的技术问题在于，针对现有技术的上述缺陷，提供一种HFS+文件系统数据恢复方法及装置，采用该方法及装置可恢复存储介质中的HFS+格式文件。

[0009] 本发明解决其技术问题所采用的技术方案是：

[0010] 构造一种HFS+文件系统数据恢复方法，其中，包括以下步骤：

[0011] A、以扇区为单位对存储介质中的文件进行扫描；

[0012] B、从被扫描文件中查找卷头，如果查找到所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

[0013] C、根据头节点的节点描述符中的各字段和头档案中的各字段，从所查找到的所述卷头所对应的目录文件中查找头节点，如果查找到头节点，则执行步骤F，否则执行步骤D；

[0014] D、判断所述卷头是否是备份卷头，如果是备份卷头，执行步骤E，否则执行步骤A，扫描下一扇区；

[0015] E、根据所述备份卷头的位置逆推出所述卷头的位置，再根据所述卷头位置和备份卷头的各个字段定位头节点，如果定位到头节点，则执行步骤F，否则执行步骤A，扫描下一扇区；

[0016] F、遍历所有定位到的头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据。

[0017] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤B中，查找所述卷头时，判断文件的卷头签名，如果文件的卷头签名16进制为0x482b、且版本等于4，或者文件的卷头签名16进制为0x4858、且版本等于5，则为所述卷头。

[0018] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤B还包括以下步骤的任意一个或并列多个：

[0019] 步骤B1、判断文件的卷属性，如果所述卷属性等于0x80002000或者等于0x80000000，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

[0020] 步骤B2、判断文件的最后装载版本，如果所述最后装载版本16进制为0x4846534a或者0x46534b21，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

[0021] 步骤B3、判断文件的创建日期，如果所述创建日期不等于0、且修改日期不等于0、且校验日期不等于0，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

[0022] 步骤B4、判断文件的分配块大小，如果所述分配块大小等于0x1000、且资源叉默认块组大小等于0x10000、且数据叉默认块组大小等于0x10000，则为所述卷头，执行步骤C，否则执行步骤A，扫描下一扇区；

[0023] 步骤B5、判断文件中的分配文件、域溢出文件、目录文件、属性文件和启动文件，如果所述分配文件、域溢出文件、目录文件、属性文件和启动文件的逻辑大小等于分配块大小乘以总块数、且域描述符的分配块数的总和等于总块数。

[0024] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤C中，查找所述头节点方法为：

[0025] 判断所述头节点的节点描述符中的各字段和所述头节点的头档案的各字段，如果所述头节点的节点描述符中的上一个节点号等于0、节点类型等于1、节点高度等于0、档案数等于3以及保留字段等于0，且所述头节点的头档案的根节点号大于0且小于节点总数、未使用节点数小于节点总数、第一个叶节点号小于节点总数、最后一个叶节点号以及小于节点总数，则认为是所述头节点。

[0026] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤C中，所述头节点的头档案还需要满足以下任意一个或多个条件：

[0027] 节点大小介于512与32768之间；

[0028] 节点类型为0；

[0029] 树最大高度大于0且小于16。

[0030] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤F包括步骤：

[0031] F1、查找叶节点，从所述头节点的开始偏移处读出B-树的每个节点，判断所读出节点的节点描述符的各字段，如果所读出节点的节点描述符的节点类型等于-1、节点高度小于16、且保留字段等于0，则判断为所述叶节点，执行步骤F2；

[0032] F2、恢复文件数据，解析所述叶节点中记录的档案信息，分解出目录档案项和文件档案项，根据所述文件档案项中的数据叉记录的位置信息和大小信息恢复文件。

[0033] 本发明所述的HFS+文件系统数据恢复方法，其中，所述步骤F1中，查找所述叶节点还需满足以下任意一个条件或两个条件：

[0034] 所读出节点的节点描述符的下一个节点小于或等于头节点的头档案的节点总数；

[0035] 所读出节点的上一个节点号小于或等于头节点的头档案的节点总数。

[0036] 本发明还提供了一种HFS+文件系统数据恢复装置，包括扇区扫描模块、卷头查找模块、头节点查找模块、备份卷头判断模块、头节点定位模块和文件恢复模块：其中，[0037] 所述扇区扫描模块，用于以扇区为单位对存储介质中的文件进行扫描；

[0038] 所述卷头查找模块，用于从被扫描文件中查找卷头，如果查找到所述卷头，则触发所述头节点查找模块，查找头节点，否则触发所述扇区扫描模块，继续扫描下一扇区；

[0039] 所述头节点查找模块，用于根据头节点的节点描述符中的各字段和头档案中的各字段，从所查找到的所述卷头所对应的目录文件中查找头节点，如果定位到所述头节点，则触发所述文件恢复模块，恢复文件数据，否则触发所述备份卷头判断模块，判断卷头是否是备份卷头；

[0040] 所述备份卷头判断模块，用于判断所述卷头是否是备份卷头，如果查找到所述备份卷头，则触发所述头节点定位模块，定位头节点，否则触发所述扇区扫描模块，继续扫描下一扇区；

[0041] 所述头节点定位模块，用于根据所述备份卷头的位置逆推出所述卷头的位置，再根据所述卷头位置和备份卷头的各个字段定位头节点，如果定位到所述头节点，则触发所述文件恢复模块，恢复文件数据，否则触发所述扇区扫描模块，继续扫描下一扇区；

[0042] 所述文件恢复模块，用于遍历所有定位到的头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据。

[0043] 本发明所述的HFS+文件系统数据恢复装置，其中，所述卷头查找模块包括：

[0044] 卷头签名判断单元，用于在查找所述卷头时，判断文件的卷头签名，如果所述文件的卷头签名16进制为0x482b、且版本等于4，或者所述文件的卷头签名16进制为0x4858、且版本等于5，则为所述卷头。

[0045] 本发明所述的HFS+文件系统数据恢复装置，其中，所述头节点查找模块包括：

[0046] 头节点判断单元，用于判断所述头节点的节点描述符中的各字段和所述头节点的头档案的各字段，如果所述头节点的节点描述符中的上一个节点号等于0、节点类型等于1、节点高度等于0、档案数等于3以及保留字段等于0，且所述头节点的头档案的根节点号大于0且小于节点总数、未使用节点数小于节点总数、第一个叶节点号小于节点总数、最后一个叶节点号以及小于节点总数，则认为是所述头节点。

[0047] 本发明的有益效果在于：通过扫描存储介质中的文件，并查找到卷头，再通过卷头查找到头节点，然后遍历所有定位到的目录文件头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据，采用这样的数据恢复方式后，只要是存储介质上曾经存在过HFS+格式的文件系统，就有可能将其中的HFS+格式文件恢复出来，即使是已经被删除的HFS+格式文件也有可能会被恢复出来。

附图说明

[0048] 下面将结合附图及实施例对本发明作进一步说明，附图中：

[0049] 图1是现有技术中的HFS+卷的组织结构示意图；

[0050] 图2是现有技术中的B-树文件中的索引节点和叶节点示意图；

[0051] 图3是现有技术中的B-树文件中的头节点示意图；

[0052] 图4是本发明较佳实施例的HFS+文件系统数据恢复方法流程；

[0053] 图5是本发明较佳实施例的HFS+文件系统数据恢复方法中步骤S130流程图；

[0054] 图6是本发明较佳实施例的HFS+文件系统数据恢复装置原理框图；

[0055] 图7是本发明较佳实施例的HFS+文件系统数据恢复装置中卷头查找模块原理框图。

具体实施方式

[0056] 本发明较佳实施例的HFS+文件系统数据恢复方法流程如图4所示，该方法S100开始于步骤S110。

[0057] 在步骤S120中，以扇区为单位对存储介质中的文件进行扫描。HFS+格式的文件系统中，卷头在存储介质上的位置是以扇区为单位的，且卷头的前两个扇区为保留区域，所以以扇区为单位从存储介质的第二个扇区开始对文件进行扫描，以查找文件的卷头。

[0058] 在步骤S130中，从被扫描文件中查找卷头，如果查找到卷头，执行步骤S140，否则执行步骤S120，扫描下一扇区。由于文件的卷头中包含有各种与卷相关的信息，如卷建立的日期和时间，卷内的文件数量等，还有卷的其他重要结构的存储位置，因此找到卷头之后，可以根据卷头中的信息来查找文件的头节点，然后可以头节点中的B-树信息来做索引，通过这个索引既可定位到需要恢复的文件。

[0059] 优选地，在上述步骤S130中，查找文件的卷头时，主要判断文件的卷头签名，如果文件的卷头签名(signature)等于“H+”，16进制为0x482b、且版本等于4，或者文件的卷头签名16进制为0x4858、且版本等于5，则为卷头。

[0060] 更优选地，如图5所示，步骤S130除了包括步骤S131，即判断卷头签名16进制是否为0x482b、且版本等于4，或者文件的卷头签名16进制是否为0x4858、且版本等于5之外，还进一步包括步骤S132、S133、S134、S135、S136中的一步或多步，即进一步判断文件的下述各项中的一种或多种是否满足条件，包括：卷属性、最后装载版本、创建日期、分配块大小，或者同时判断卷头中分配文件、域溢出文件、目录文件、属性文件和启动文件的逻辑大小。

[0061] 对上述各项的判断条件如下：

[0062] 在步骤S132中，判断文件的卷属性，如果卷属性(attributes)等于0x80002000或者等于0x80000000，则为卷头，否则舍弃；

[0063] 在步骤S133中，判断文件的最后装载版本，如果最后装载版本(last Mounted Version)等于“HFSJ”(16进制为0x4846534a)，或者等于“FSK！”(16进制为0x46534b21)，则为卷头，否则舍弃；

[0064] 在步骤S134中，判断文件的创建日期，如果创建日期(create Date)不等于0、修改日期(modify Date)不等于0、且校验日期(check Data)不等于0，则为卷头，否则舍弃；

[0065] 在步骤S135中，判断文件的分配块大小，如果分配块大小(block Size)等于0x1000、且资源叉默认块组大小(rsrc Clump Size)等于0x10000、且数据叉默认块组大小(data ClumpSize)等于0x10000，则为卷头，否则舍弃；

[0066] 在步骤S136中，判断卷头中的分配文件、域溢出文件、目录文件、属性文件和启动文件，由于这些文件都使用的是叉数据结构(HFS Plus Fork Data结构)，如果卷头中的分配文件、域溢出文件、目录文件、属性文件和启动文件均满足逻辑大小(logical Size)等于分配块大小乘以总块数(total Blocks)且域描述符(HFS Plus Extent Descriptor)的分配块数(block Count)的总和要等于总块数(total Blocks)。

[0067] 当包括步骤S132、S133、S134、S135、S136中的两步以上时，每一步骤的执行可与判断文件的卷头签名过程同时进行，相互之间没有时间先后顺序，可按照技术人员的需求自定义。当然，对卷头的约束条件越多，所得到的卷头也越准确，当同时判断上述所有项，则可能得到文件中的所有卷头。

[0068] 因此，在步骤S137中，可以设置为当S132、S133、S134、S135、S136中有一个判断结果为是时，则确定为卷头，执行步骤S140；还可将步骤S137设定为，当步骤S132、S133、S134、S135、S136中所有判断结果均为是时，才确定为卷头，执行步骤S140，否则执行步骤S120。或者是根据需要设定的其他条件，而不应局限于图5中所示的步骤。

[0069] 在步骤S140中，根据头节点的节点描述符中的各字段和头档案中的各字段，从所查找到的卷头所对应的目录文件中查找头节点，如果查找到头节点，则执行步骤S170，否则执行步骤S150。

[0070] 具体地，头节点中的节点描述符(BT Node Descriptor)的各字段必须同时满足下列条件：

[0071] (1-1)、上一个节点号(b Link)等于0；

[0072] (1-2)、节点类型(kind)等于1；

[0073] (1-3)、节点高度(height)等于0；

[0074] (1-4)、档案数(num Records)等于3；

[0075] (1-5)、保留字段(Reserved)等于0。

[0076] 头节点的头档案(BT Header Rec)的各字段必须同时满足下列条件：

[0077] (2-1)、根节点号(root Node)大于0且小于节点总数(total Nodes)；

[0078] (2-2)、未使用节点数(free Nodes)小于节点总数(total Nodes)；

[0079] (2-3)、第一个叶节点号(first Leaf Node)小于节点总数(total Nodes)；

[0080] (2-4)、最后一个叶节点号(last Leaf Node)小于节点总数(total Nodes)。

[0081] 当头节点的节点描述符中的各字段和头档案中的各字段满足上述条件时，则认为是头节点，执行步骤S170，否则执行步骤S150。

[0082] 进一步地，头节点的头档案还需要满足以下条件：

[0083] (2-5)、节点大小(node Size)，用字节表示必须是2的整数次幂，介于512与32768之间；

[0084] (2-6)、节点类型(btree Type)为0；

[0085] (2-7)、树最大高度(tree Depth)大于0且小于16。

[0086] 可以根据需要设定：当头节点的节点描述符中的各字段满足条件(1-1)、(1-2)、(1-3)、(1-4)、(1-5)，且头档案中的各字段满足(2-1)、(2-2)、(2-3)、(2-4)、(2-5)、(2-6)、(2-7)时，才则认为是头节点，执行步骤S170，否则执行步骤S150。这样可以保证头节点判断更加准确，以确保所恢复数据的完整性。

[0087] 在步骤S150中，判断所查找的卷头是否是备份卷头，如果是备份卷头，执行步骤S160，否则执行步骤S120，扫描下一扇区。其中，判断是否为备份卷头的方法是，判断所查找的卷头的最后装载版本，如果卷头的最后装载版本等于“10.0”，16进制为0x31302e30，则为备份卷头。

[0088] 在步骤S160中，根据备份卷头的位置逆推出卷头的位置，再根据卷头位置和备份卷头的各个字段定位头节点，如果定位到头节点，则执行步骤S170，否则执行步骤S120，扫描下一扇区。备份卷头是卷头的副本，当卷的总大小正好是分配块大小(block Size)的整数倍时，卷的总大小等于卷头/备份卷头的分配块总数(total Blocks)乘以卷头/备份卷头的分配块大小(block Size)。而当卷大小不是分配块大小(block Size)的整数倍时，则分配块总数(total Blocks)记录的块数就不包含尾部多出的不够一个分配块的空间。所以可以从备份卷头逆推卷头的位置，但是存在分配块大小(block Size)除去512(一个扇区的大小，因为分配块大小一定是扇区大小的整数倍，卷大小也一定是扇区大小的整数倍)个扇区的偏差。

[0089] 则先假设卷的大小为分配块的整数倍，逆推出卷头的位置，根据卷头位置和备份卷头的各个字段，定位到目录文件的头节点，发现这个头节点定位正确，则证明所逆推的卷头正确。如若不正确，则试着用原逆推的位置每次减去一个扇区，再来定位目录文件的头节点，直到定位的头节点是正确的，或者减分配块大小(block Size)除去512个扇区的次数。找到成对的卷头和备份卷头就可以确认卷头了，而不成对的卷头和备份卷头可能是被损坏或者非卷头。

[0090] 在步骤S170中，遍历所有定位到的目录文件头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据。头节点的开始偏移就是B-tree的开始偏移，从头节点的节点大小(node Size)得知每个节点的大小，节点总数(total Nodes)得知节点的总数，则从头节点的开始偏移处将每个节点读取出来，节点可能会是索引节点也可能是叶节点或者唯一的头节点，这三种节点都有一个节点描述符(BT Node Descriptor)结构。

[0091] 具体包括：a、查找叶节点，从头节点的开始偏移处读出B-树的每个节点，判断所读出节点的节点描述符的各字段，如果所读出节点的节点描述符的节点类型等于-1、节点高度小于16、且保留字段等于0，则判断为叶节点，执行步骤b；

[0092] b、恢复文件数据，解析叶节点中记录的档案信息，分解出目录档案项(HFS Plus Catalog Folder)和文件档案项(HFS Plus Catalog File)，根据文件档案项中的数据叉(data Fork)记录的位置信息和大小信息，恢复文件。

[0093] 优选地，上述步骤a中，查找叶节点还需满足条件为：所读出节点的节点描述符的下一个节点小于或等于头节点的头档案的节点总数。或者更进一步的包括判断所读出节点的上一个节点号，如果所读出节点的上一个节点号小于或等于头节点的头档案的节点总数。

[0094] 上述方法S100结束于步骤S180。

[0095] 在本发明的另一实施例中，还提供了一种HFS+文件系统数据恢复装置，如图6所示，包括：扇区扫描模块10、卷头查找模块20、头节点查找模块30、备份卷头判断模块40、头节点定位模块50和文件恢复模块60。其中，扇区扫描模块10，用于以扇区为单位对存储介质中的文件进行扫描，HFS+格式的文件系统中，卷头在存储介质上的位置是以扇区为单位的，且卷头的前两个扇区为保留区域，所以以扇区为单位从存储介质的第二个扇区开始对文件进行扫描，以查找文件的卷头。

[0096] 卷头查找模块20，用于从被扫描文件中查找卷头，如果查找到卷头，则触发头节点查找模块30，查找头节点，否则触发扇区扫描模块10，继续扫描下一扇区。由于文件的卷头中包含有各种与卷相关的信息，如卷建立的日期和时间，卷内的文件数量等，还有卷的其他重要结构的存储位置，因此找到卷头之后，可以根据卷头中的信息来查找文件的头节点，然后可以头节点中的B-树信息来做索引，通过这个索引既可定位到需要恢复的文件。

[0097] 头节点查找模块30，用于根据头节点的节点描述符中的各字段和头档案中的各字段，从所查找到的卷头所对应的目录文件中查找头节点。如果定位到头节点，则触发文件恢复模块60，恢复文件数据，否则触发备份卷头判断模块40，判断卷头是否是备份卷头。

[0098] 备份卷头判断模块40，用于判断卷头是否是备份卷头。其中，判断是否为备份卷头的方法是，判断所查找的卷头的最后装载版本，如果卷头的最后装载版本等于“10.0”，16进制为0x31302e30，则为备份卷头。如果查找到备份卷头，则触发头节点定位模块50，定位头节点，否则触发扇区扫描模块10，继续扫描下一扇区。

[0099] 头节点定位模块50，用于根据备份卷头的位置逆推出卷头的位置，再根据卷头位置和备份卷头的各个字段定位头节点。如果定位到头节点，则触发文件恢复模块60，恢复文件数据，否则触发扇区扫描模块10，继续扫描下一扇区。由于备份卷头是卷头的副本，当卷的总大小正好是分配块大小(block S1ze)的整数倍时，卷的总大小等于卷头/备份卷头的分配块总数(total Blocks)乘以卷头/备份卷头的分配块大小(block Size)。而当卷大小不是分配块大小(block Size)的整数倍时，则分配块总数(total Blocks)记录的块数就不包含尾部多出的不够一个分配块的空间。所以可以从备份卷头逆推卷头的位置，但是存在分配块大小(block Size)除去512(一个扇区的大小，因为分配块大小一定是扇区大小的整数倍，卷大小也一定是扇区大小的整数倍)个扇区的偏差。

[0100] 文件恢复模块60，用于遍历所有定位到的头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据。头节点的开始偏移就是B-tree的开始偏移，从头节点的节点大小(node Size)得知每个节点的大小，节点总数(total Nodes)得知节点的总数，则从头节点的开始偏移处将每个节点读取出来，节点可能会是索引节点也可能是叶节点或者唯一的头节点，这三种节点都有一个节点描述符(BT Node Descriptor)结构。

[0101] 具体包括：a、查找叶节点，从头节点的开始偏移处读出B-树的每个节点，判断所读出节点的节点描述符的各字段，如果所读出节点的节点描述符的节点类型等于-1、节点高度小于16、且保留字段等于0，则判断为叶节点，执行步骤b；

[0102] b、恢复文件数据，解析叶节点中记录的档案信息，分解出目录档案项(HFSPlus Catalog Folder)和文件档案项(HFS Plus Catalog File)，根据文件档案项中的数据叉(data Fork)记录的位置信息和大小信息，恢复文件。

[0103] 优选地，上述步骤a中，查找叶节点还需满足条件为：所读出节点的节点描述符的下一个节点小于或等于头节点的头档案的节点总数。或者更进一步的包括判断所读出节点的上一个节点号，如果所读出节点的上一个节点号小于或等于头节点的头档案的节点总数。

[0104] 在进一步的实施例中，如图7所示，上述HFS+文件系统数据恢复装置的卷头查找模块20包括：卷头签名判断单元21，用于在查找卷头时，判断文件的卷头签名，如果文件的卷头签名16进制为0x482b、且版本等于4，或者文件的卷头签名16进制为0x4858、且版本等于5，则为卷头。

[0105] 在更进一步的实施例中，如图7所示，上述卷头查找模块20还包括：卷属性判断单元22、最后装载版本判断单元23、创建日期判断单元24、分配块大小判断单元25以及文件逻辑大小判断单元26中的个或多个。分别用于进一步的判断文件的下述各项是否满足条件，包括：卷属性、最后装载版本、创建日期、分配块大小，或者同时判断卷头中分配文件、域溢出文件、目录文件、属性文件和启动文件的逻辑大小。

[0106] 其中，卷属性判断单元22，用于判断文件的卷属性，如果卷属性(attributes)等于0x80002000或者等于0x80000000，则为卷头，否则舍弃；最后装载版本判断单元23，用于判断文件的最后装载版本，如果最后装载版本(last Mounted Version)等于“HFSJ”(16进制为0x4846534a)，或者等于“FSK！”(16进制为0x46534b21)，则为卷头，否则舍弃；创建日期判断单元24，用于判断文件的创建日期，如果创建日期(create Date)不等于0、修改日期(modify Date)不等于0、且校验日期(check Data)不等于0，则为卷头，否则舍弃；分配块大小判断单元25，用于判断文件的分配块大小，如果分配块大小(block Size)等于
0x1000、且资源叉默认块组大小(rsrc Clump Size)等于0x10000、且数据叉默认块组大小(data ClumpSize)等于0x10000，则为卷头，否则舍弃；文件逻辑大小判断单元26，用于判断卷头中的分配文件、域溢出文件、目录文件、属性文件和启动文件，由于这些文件都使用的是叉数据结构(HFS Plus Fork Data结构)，如果卷头中的分配文件、域溢出文件、目录文件、属性文件和启动文件均满足逻辑大小(logical Size)等于分配块大小乘以总块数(total Blocks)且域描述符(HFS Plus Extent Descriptor)的分配块数(block Count)的总和要等于总块数(total Blocks)。

[0107] 当卷头查找模块20包括卷属性判断单元22、最后装载版本判断单元23、创建日期判断单元24、分配块大小判断单元25以及文件逻辑大小判断单元26中的两个以上时，各个单元的执行可与卷头签名判断单元同步，相互之间没有时间先后顺序，可按照技术人员的需求自定义。当然，对卷头的约束条件越多，所得到的卷头也越准确，当同时判断上述所有项，则可能得到文件中的所有卷头。

[0108] 在进一步的实施例中，上述HFS+文件系统数据恢复装置的头节点查找模块30包括：头节点判断单元，用于判断头节点的节点描述符中的各字段和头节点的头档案的各字段，如果头节点的节点描述符中的上一个节点号等于0、节点类型等于1、节点高度等于0、档案数等于3以及保留字段等于0；且头节点的头档案的根节点号大于0且小于节点总数、未使用节点数小于节点总数、第一个叶节点号小于节点总数、最后一个叶节点号以及小于节点总数，则认为是头节点。

[0109] 在更进一步的实施例中，上述头节点判断单元还进一步用于判断节点大小(node Size)，用字节表示必须是2的整数次幂，是否介于512与32768之间；节点类型(btree Type)是否为0；树最大高度(tree Depth)是否大于0且小于16。以保证头节点判断更加准确，确保所恢复数据的完整性。本发明的HFS+文件系统数据恢复方法及装置，通过扫描存储介质中的文件，并查找到卷头，再通过卷头查找到头节点，然后遍历所有定位到的目录文件头节点中所包含的B-树，得到其中的文件和目录信息，恢复文件数据，采用这样的数据恢复方式后，只要是存储介质上曾经存在过HFS+格式的文件系统，就有可能将其中的HFS+格式文件恢复出来，即使是已经被删除的HFS+格式文件也有可能会被恢复出来。解决了现有技术中由于某些原因导致无法识别是什么格式的文件系统，或者误操作格式化为其他文件系统等原因，导致本来是HFS+文件系统的存储介质，已经无法被识别的问题。

[0110] 应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换，而所有这些改进和变换都应属于本发明所附权利要求的保护范围。