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

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

每个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所示。

图6-32　一个节点的标准结构

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

图6-33　一个节点的部分内容

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

节点描述符

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

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

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

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

节点记录列表

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

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

节点记录起始偏移量列表

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

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

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

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

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

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

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

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

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

图6-34　头节点的结构图

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

图6-35　一个头节点的内容

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

头节点描述符

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

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

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

头记录

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

表6-20　头记录的结构

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

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

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

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

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

图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的节点记录起始偏移量列表参数及解释