HFS＋文件系统节点的综合应用

HFS＋文件系统用B−树结构组织数据。B−树是一种可以快速搜索、插入和删除的结构，它由节点构成，节点分为头节点、位图节点、索引节点、叶节点四种类型，其中索引节点和叶节点中包含关键字，对B−树进行的所有操作最终都是针对索引节点和叶节点以及存储在它们中的关键字进行的。

关键字在索引节点和叶节点有一定的排序规则，具体规则如下：

①关键字必须以升序方式排列在节点中；

②同一个层次中的所有节点必须由“下一个节点号”和“上一个节点号”两个参数链接起来。

③关键字值最小的节点必须位于链表的第一位，且“上一个节点号”参数值为0；

④关键字值最大的节点必须位于链表的最后，且“下一个节点号”参数值为0；

⑤对于任何一个节点，其中存放的所有关键字值必须小于链表中下一个节点中存放的关键字值，且大于链表中上一个节点中存放的关键字值。

对关键字采用上述这种排列规则可以快速地在B−树中搜索到需要的关键字，以便访问与关键字相关联的数据。

下面用一个简单的例子描述上述规则，在该例子中，我们用数字作为关键字，如图6-39所示。

图6-39　节点示例

从图6-39来看，在访问数据的时候，由头节点定位到根节点，从根节点的第一个记录开始，在关键字值小于等于要搜索的关键字值的记录范围内寻找最大的关键字值记录。

搜索的过程可以延伸到孩子节点，其中索引节点是典型的孩子节点，搜索往往需要重复进行，一直延伸到一个叶节点。如果叶节点中的关键字值与要搜索的关键字值相等，则该关键字所关联的就是要访问的数据的相关信息。如果叶节点中的关键字值与要搜索的关键字值不相等，则说明要访问的数据不在这个B−树中，需要到其他B−树中搜索。