您当前的位置:首页 > 计算机 > 文件格式与编码

HFS+文件系统的头节点分析

时间:01-02来源:作者:点击数:

HFS+文件系统的节点及其分类

HFS+文件系统用B-树结构组织数据,包括元数据和用户数据,在文件系统的卷头中描述了每个B-树的数据分支大小和盘区地址。

B-树的详细内容请参见第1章。

每个B-树包含若干个“节点(Node)”,每个节点中又包含一定的“记录(Records)”,而记录则由“关键字(Key)”和数据内容组成。

B-树的作用就是有效地组织数据,它组织数据的方式则是通过关键字对相应的数据形成映射,这样,通过关键字就能找到需要的数据。而为了能够高效地访问目标数据,关键字的排列方式是很重要的。

一个B-树的大小等于该B-树包含的节点数与每个节点大小的乘积,节点的大小被定义为2的整数次幂字节,其取值范围是512字节到32 768字节之间。B-树的大小是在创建该B-树时就设定了。

HFS+文件系统的节点分为4种,它们是头节点、位图节点、索引节点、叶节点。

①头节点(Header Nodes)。头节点是B-树的第一个节点,其中包含有头记录和位图记录。每个B-树只能包含一个头节点。

②位图节点(Map Nodes)。位图节点中只包含一个位图记录。当头节点中的位图记录不足以管理该B-树中的节点分配情况时,就需要位图节点进一步管理。

③索引节点(Index Nodes)。索引节点用来存放定义B-树结构的指针记录。

④叶节点(Leaf Nodes)。叶节点包含与某个关键字相关联的数据记录,每个数据记录的关键字都是唯一的。

HFS+文件系统的节点基本结构

每个节点都有自身的一个节点号,其节点号可以通过该节点在其B-树文件中的偏移量计算出来,计算方法为:节点在其B-树文件中的偏移量除以每节点字节数。

节点具有相同的结构,它们的基本结构包括三个组成部分:节点描述符、节点记录列表、节点记录起始偏移量列表,如图6-32所示。

HFS+文件系统的头节点分析
图6-32 一个节点的标准结构

为了进一步说明,下面给出一个节点的实例,如图6-33所示。

HFS+文件系统的头节点分析
图6-33 一个节点的部分内容

这个节点的完整大小是8192字节,也就是16个扇区,图6-33中给出的是该节点的头部和尾部,中间空闲空间的15个扇区被省略,下面对每一个组成部分进行分析:

节点描述符

节点描述符的大小一般固定为14个字节,其结构见表6-16。

表6-16 节点描述符的结构

字节偏移(相对偏移) 字段名和定义 字段长度(字节)
0x00~0x03 4  下一个节点的节点号,如果已经是最后一个,则置0
0x04~0x07 4  上一个节点的节点号,如果当前就是第一个,则置0
0x08~0x08 1  节点类型,表示方法:
叶节点为-1;索引节点为0;头节点为1;图节点为2
0x09~0x09 1  本节点在B-树中的高度,各种类型节点的高度为:头节点高度为0;叶节点高度为1;索引节点的高度比它指向的子节点的高度高一层;图节点高度为0
0x0A~0x0B 2  该节点中的记录数
0x0C~0x0D 2  保留

本例中的节点描述符实际数值见表6-17。

表6-17 图6-33的节点描述符实际数值及解释

字节偏移(相对偏移) 字段长度(字节) 实际值 解释
0x00~0x03 4 0 为0说明这是最后一个节点
0x04~0x07 4 0 为0说明这也是第一个节点
0x08~0x08 1 0 为0说明是索引节点
0x09~0x09 1 3 本节点在B-树中的高度为3
0x0A~0x0B 2 6 该节点中有6个节点记录
0x0C~0x0D 2 0 保留

节点记录列表

因为节点描述符的大小一般为14个字节,所以节点记录列表起始于该节点的14偏移处。节点记录列表中由若干个节点记录组成,由于节点记录的类型和所描述的信息不一样,导致每个节点记录的大小也可能不一样。

图6-33所示的节点中,节点记录开始于0EH偏移处,也就是十进制的14,结束于1FE1H偏移处,其中包含6个节点记录和一大段空闲空间。

节点记录起始偏移量列表

节点记录起始偏移量列表由若干个表项构成,每个表项占用2个字节,用于描述一个节点记录的起始偏移地址,节点就是通过这个节点记录起始偏移量列表中的表项来定位和访问每个节点记录。

节点记录起始偏移量列表在描述节点记录起始位置时,每个表项都采取倒序的方式排列,即第一个节点记录的偏移地址由节点记录起始偏移量列表的最后一个表项描述;第二个节点记录的偏移地址由节点记录起始偏移量列表的倒数第二个表项描述,以此类推。

因为第一个节点记录总是开始于该节点的14偏移处,所以每个节点最后两个字节的值总是0EH。

另外,节点记录起始偏移量列表中的表项总是比节点中的记录数多1,多出的这个表项描述的是节点中空闲空间的起始地址,同时也说明了节点中最后一个记录的结束地址。如果节点中没有空闲空间,多出的这个表项描述它本身在节点中的起始偏移。

在图6-33的例子中,节点记录起始偏移量列表包含7个表项,其中6个描述节点记录的起始偏移,一个描述空闲空间的起始偏移,具体描述方法见表6-18。

表6-18 图6-33的节点记录起始偏移量列表参数及解释

表项编号 表项值(十六进制) 解释
0 00 0E 第一个节点记录开始于该节点的0EH偏移处
1 00 30 第二个节点记录开始于该节点的30H偏移处
2 00 3C 第三个节点记录开始于该节点的3CH偏移处
3 00 5A 第四个节点记录开始于该节点的5AH偏移处
4 00 9C 第五个节点记录开始于该节点的9CH偏移处
5 00 A8 第六个节点记录开始于该节点的A8H偏移处
6 00 B4 空闲空间开始于该节点的B4H偏移处

HFS+文件系统的头节点结构

B-树的第一个节点都是头节点,也就是说头节点都是0号节点,其中包含着整个B-树的基本信息。

在头节点的节点描述符后面跟着三个节点记录,第一个称为头记录,大小为106字节;第二个是保留记录,大小为128个字节;第三个是位图记录,它占用保留记录到节点记录偏移量列表之间的所有空间。

头节点的结构如图6-34所示。

HFS+文件系统的头节点分析
图6-34 头节点的结构图

下面用一个实例详细讲解,图6-35是一个头节点的内容。

HFS+文件系统的头节点分析
图6-35 一个头节点的内容

这个节点的完整大小是8192字节,也就是16个扇区,图6-35中给出的是该节点的头部和尾部,中间位图记录部分的15个扇区被省略,下面对该节点的结构进行分析。

头节点描述符

头节点描述符占用头节点的前14个字节,其结构见表6-19。

表6-19 头节点描述符的结构

字节偏移(相对偏移) 字段长度(字节) 字段名和定义
0x00~0x03 4 第一个位图节点的节点号,如果没有位图节点,则置0
0x04~0x07 4 上一个节点的节点号,头节点中该值总为0
0x08~0x08 1 节点类型,头节点中该值为1
0x09~0x09 1 本节点在B−树中的高度,头节点高度为0
0x0A~0x0B 2 该节点中的记录数,头节点中该值总为3
0x0C~0x0D 2 保留

对照图6-35的头节点描述符可以看出,其实际数值完全符合表6-19给出的定义。

头记录

头节点的第一个记录是头记录,其具体结构见表6-20。

表6-20 头记录的结构

字节偏移(相对偏移) 字段长度(字节) 字段名和定义
0x00~0x01 2  B−树深度,该值总是等于根节点的节点高度
0x02~0x05 4  根节点的节点号
0x06~0x09 4  叶节点包含的记录总数
0x0A~0x0D 4  第一个叶节点的节点号,如果没有叶节点则为0
0x0E~0x11 4  最后一个叶节点的节点号,如果没有叶节点则为0
0x12~0x13 2  每节点字节数,该值为2的整数次幂,其大小范围为512~32 768
0x14~0x15 2  节点中关键字的最大长度
0x16~0x19 4  节点总数
0x1A~0x1D 4  未用节点数
0x1E~0x1F 2  保留
0x20~0x23 4  块组大小,HFS+忽略此参数,因为在卷头的分支数据结构中已经描述过此参数,不过为了保持最大的兼容性,此处也会记录同样的值
0x24~0x24 1  B−树的类型,HFS+的B−树类型为0
0x25~0x25 1  保留
0x26~0x29 4  属性(具体见表6-21)
0x2A~0x69 64  保留

头记录中0x26~0x29偏移处“属性”的定义见表6-21。

表6-21 头记录中“属性”的定义

属性位 属性定义 含义
0位 非正常关闭位  如果设置此位,说明B−树没有正常地关闭,需要调用一致性检查程序进行检查。此位在HFS+文件系统的B−树中并未使用,视为保留
1位 关键字长度位  如果设置了此位,索引和叶节点中关键字的“关键字长度”字段被定义为“无符号16位整型”,否则被定义为“无符号8位整型”。HFS+文件系统的B−树必须对此位进行设置,也就是说在HFS+的B−树中,关键字的长度使用两个字节描述
2位 索引关键字
定义位
 如果此位被设置,索引节点中的关键字的字节数由它的“关键字长度”参数定义;如果此位被清除,索引节点的关键字总是等于“节点中关键字的最大长度”定义的值。HFS+文件系统编录文件的B−树必须设置此位,而盘区的B−树则清除此位
3~31位 未定义 保留

图6-35中的头节点具体数值见表6-22。

表6-22 图6-35中的头节点参数取值

字节偏移(相对偏移) 字段长度(字节) 字段名和定义 数值及解释
0x00~0x01 2 B−树的深度,该值总是等于根节点的节点高度  3,也就是说根节点的高度为3
0x02~0x05 4 根节点的节点号  217,说明217号节点为根节点
0x06~0x09 4 叶节点包含的记录总数  22370,说明该B−树中所有的节点共包含22 370个节点记录
0x0A~0x0D 4 第一个叶节点的节点号,如果没有叶节点则为0  145,说明145号节点为第一个叶节点
0x0E~0x11 4 最后一个叶节点的节点号,如果没有叶节点则为0  630,说明630号节点为最后一个叶节点
0x12~0x13 2  每节点字节数,该值为2的整数次幂,其大小范围介于512~32 768  8192,说明每个节点占用16个扇区
0x14~0x15 2 节点中关键字的最大长度  516,说明在索引节点或叶节点中每个关键字最大长度为516字节
0x16~0x19 4 节点总数  3200,说明该B−树中一共有3200个节点
0x1A~0x1D 4 未用节点数  2661,说明该B−树中有2661个节点空闲
0x1E~0x1F 2 保留  
0x20~0x23 4  块组大小,HFS+忽略此参数,因为在卷头的分支数据结构中已经描述过此参数,不过为了保持最大的兼容性,此处也会记录同样的值  26214400
0x24~0x24 1 B−树的类型,HFS+的B−树类型为0 0
0x25~0x25 1 保留  
0x26~0x29 4 属性  06H,即设置了1位和2位,说明其关键字的长度使用两个字节描述,并且其索引节点中的关键字的字节数由它的“关键字长度”参数定义
0x2A~0x69 64 保留  

我们再用WinHex的模板查看一下该头节点的节点描述符和头记录的参数,如图6-36所示。

HFS+文件系统的头节点分析
图6-36 头节点的模板

保留记录

头节点中的第二个节点记录是被保留的,其大小总是128个字节。

位图记录

头节点的保留记录之后,就是第三个节点记录了,这个记录是位图记录。位图记录的作用是描述B−树中哪些节点已经使用以及哪些节点空闲未用,这一信息在HFS+文件系统的分配文件中也用同样的方法做了记录。

在头节点中,节点描述符占用14个字节,头记录占用106个字节,保留记录占用128个字节,位于节点末尾的节点记录起始偏移量列表占用8个字节,这四部分加在一起共占用了256个字节,头节点中这四部分以外的空间都属于位图记录,这样就可以把位图记录的大小计算出来了。计算方法是每节点字节数减去256。在本例中节点大小为8192字节,计算得到位图记录的大小为7936字节。

有时候B−树中的节点数可能很多,已经超过了头节点中的位图记录所能描述的个数,这时则需要使用“位图节点”来管理位图记录管理不下的节点。

头节点的节点记录起始偏移量列表

因为头节点中有3个节点记录,所以在节点记录起始偏移量列表中就需要用3个表项描述这3个节点记录的起始地址。又因为位图记录占用了头节点中保留记录和节点记录起始偏移量列表之间的所有空间,所以头节点没有空闲空间。这样,节点记录起始偏移量列表的最后一个表项用来描述节点记录起始偏移量列表自身的起始地址。

在图6-35的例子中,节点记录起始偏移量列表包含4个表项,它们按照倒序排列,其中3个描述节点记录的起始偏移,最后一个描述其自身的起始偏移,具体描述方法见表6-23。

表6-23 图6-35的节点记录起始偏移量列表参数及解释

表项编号 表项值(十六进制) 解释
0 000E 头记录开始于该节点的0EH偏移处
1 0078 保留记录开始于该节点的78H偏移处
2 00F8 位图记录开始于该节点的F8H偏移处
3 1FF8 节点记录起始偏移量列表开始于该节点的1FF8H偏移处
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门