JFS 文件系统概述及布局分析（四）

B+树

这一节描述文件布局使用的B+树数据结构。选择B+树是为了提高读写盘区的性能，这是JFS必须进行的最普通操作。B+树为读取文件的特定盘区提供快速搜索。它还提供有效方法将盘区添加或插入文件中。较为少见的情形是：当删除文件时，JFS需要遍历整个B+树。为了保证JFS会删除B+树使用的块以及文件数据，对于遍历B+树效率也很高。

盘区分配描述符（xad结构）描述盘区并且又添加了表示文件所需的两个字段：描述盘区表示的逻辑字节地址的偏移量和标志字段。盘区分配描述符结构在jfs_xtree.h,structxad中定义。

xad结构为：
　　

以下为引用的内容： 　　structxad{ 　　unsignedflag:8; 　　unsignedrsvrd:16; 　　unsignedoff1:8; 　　uint32off2; 　　unsignedlen:24; 　　unsignedaddr1:8; 　　uint32addr2; 　　}xad_t;

　　
其中：

flag是包含各种标志的8位字段。这些标志能够表示写入时复制、是否分配了盘区但没有记录它、压缩信息等等。

rsvrd是保留供将来使用的16位字段。它总为零。

off1,off2是40位字段，包含盘区中第一个块的逻辑偏移量。逻辑偏移量是以聚集块尺寸为单位表示；也就是说，要取得一个字节，偏移量必须乘以聚集块尺寸。

len是24位字段，包含盘区的长度。长度以聚集块尺寸为单位表示。

addr1,addr2是40位字段，包含盘区的地址。地址以聚集块尺寸为单位表示。

xad结构描述了两个抽象范围：

磁盘上磁盘块的物理范围。它以聚集块号xad_address开始，并且延伸为xad_length聚集块。

文件内字节的逻辑范围。它以字节号xad_offset*AGBS（聚集块尺寸）开始，并且延伸为xad_length*AGBS字节。

当然，物理范围和逻辑范围有相同长度的字节。请注意，xad_offset以聚集块尺寸为单位存储（例如，在xad_offset中值"3"意味着3个聚集块，而不是3个字节）。它遵循文件内盘区总是以聚集块尺寸为边界。

JFS中的所有索引对象（除目录外），有一个类属B+树索引结构。索引的数据将取决于对象。B+树以由树描述的数据的xad偏移量为键。项按xad结构的偏移量排序。xad结构是B+树节点中的项。

磁盘inode第二扇区底部包含数据描述符，它描述在inode的后半部分内存储的内容。对于足够小的文件，后半部分可能包含内嵌数据。如果文件数据不适合inode的内嵌数据空间，它将包含在盘区中，inode将包含B+树的根节点。头部指出在使用的xad个数，可用的xad个数。通常，inode将包含8个xad结构B+树的根。如果文件有8个或更少盘区，那么这8个xad结构也是B+树的叶节点。它们将描述盘区。否则，inode中的8个xad结构将指向B+树的叶节点或内部节点。

一旦inode中的8个xad结构均已填充，为了有更多的xad结构，就会尝试使用inode的最后四分之一。如果INLINEEA位在inode的di_mode字段中设置，那么inode的最后四分之一可用。

一旦inode中所有可用的xad结构都被使用，就必须拆分B+树。JFS将把4K的磁盘空间分配给B+树的叶节点。叶节点逻辑上是带头的xad项的数组。头部指向节点中第一个空闲的xad项，没有分配紧跟其后的所有xad项。8个xad项从inode复制到叶节点，初始化头部以指向第9个项作为第一个空闲项。然后JFS将把B+树的根更新为inode的第一个xad结构；该xad结构将指向最新分配的叶节点。这个新的xad结构的偏移量是叶节点中第一个项的偏移量。将更新inode中的头部以表示当前B+树只使用1个xad。还需要更新inode头部以表示当前inode包含B+树的纯根。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有