手工遍历HFS＋的B-树

在学习了HFS＋文件系统的结构之后，我们知道HFS＋使用B−树对宗卷中的文件进行管理。为了更进一步加深对这种管理方式的理解，下面用一个例子实际体会一下HFS＋的B−树结构。我们将用手工遍历HFS＋的B−树的方法定位一个文件，对B−树的原理不了解的读者请先学习本书1.4节。

在一个Apple磁盘的HFS＋宗卷根目录下有4个目录和88个文件。为了在Windows系统下能够读取Apple系统的分区，我们运行了MacDrive（在6.3.17节讲解）程序，这样就能够在Windows系统下打开Apple的分区了，如图6-56所示。

图6-56　Apple分区内的数据

假设该宗卷中的“80.jpg”文件是我们的访问目标。下面将以HFS＋文件系统的工作方式手工定位到“80.jpg”这个文件在宗卷中的存放地址。

第1步　定位卷头。

通过该宗卷所在硬盘的Apple分区映射表定位到宗卷的开始位置，在512号扇区，而卷头位于宗卷的第三个扇区，也就是514号扇区了。

第2步　定位编录文件。

文件的入口在编录文件中，所以需要先找到这个文件。

在卷头的编录文件信息中记录着编录文件的起始块号及大小等信息，通过这些信息很容易定位到编录文件的开始地址。

第3步　定位根目录的节点号。

通过第二步找到了编录文件，其第一个节点是头节点，其部分内容如图6-57所示。

图6-57　编录文件的头节点

用WinHex模板查看一下其中的参数，如图6-58所示。

图6-58　头节点的模板

从模板中可以看到根目录的节点号是3，那么如何定位到3号节点的位置呢？这很容易，用节点号乘以每节点字节数就可以得到该节点在编录文件中的偏移量了，即3×8192＝24576，以编录文件的起始位置为0偏移，24 576号偏移处就是3号节点的开始位置了。

第4步　分析关键字。

定位到根目录的节点后，就可以看到索引节点了，如图6-59所示。

图6-59　索引节点的内容

该索引节点内的参数用WinHex模板查看，具体如图6-60所示。

图6-60　索引节点的模板

根据B−树结构中节点的排列原理，可以从索引节点的指针记录中描述的关键字分析出“80.jpg”文件的文件记录一定在2号记录项所描述的子节点号中，即4号节点。

第5步　定位“80.jpg”文件的文件记录。

通过第4步已经分析出“80.jpg”文件的文件记录在4号节点。根据前文讲过的定位节点起始地址的方法，找到4号节点。这个节点中的关键字是从“62.jpg”开始，只需要在该节点中做一下顺序遍历，很快就找到了“80.jpg”文件的文件记录，如图6-61所示。“80.jpg”文件记录的具体参数如图6-62所示。