B+树

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

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

xad结构为：
　　

　　
其中：

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+树的纯根。

当把新盘区添加到文件时，将以必需的次序，继续把它们添加到相同的叶节点。这将持续直到节点填满为止。一旦节点填满了，将为B+树的另一个叶节点分配新的4K磁盘空间。将把该inode的第二个xad结构设置成指向新分配的节点。

这将持续直到填满inode的所有8个xad结构为止，这时，将再次拆分B+树。这种拆分将创建B+树的内部inode，它们是纯粹用来记录树的搜索路径。JFS将为B+树的内部inode分配4K磁盘空间。内部节点看起来如同叶节点。从inode复制8个xad项到内部节点，初始化头部以指向第9个项作为第一个空闲项。然后，通过使inode的第一个xad结构指向新分配的内部节点，JFS更新B+树的根。将更新inode中的头部以表示当前B+树只使用1个xad。

文件jfs_xtree.h在structxtpage_t中描述B+树根的头部。文件jfs_btree.h是在structbtpage_t中的内部节点或叶节点的头部。

例子

下列例子进一步分析了盘区描述符和xad结构的用法：

连续分配的1041377字节文件。

同的1041377字节文件，但在磁盘上拆分成三段。

1041377字节的文件，但里面有一个"洞"（稀疏文件）。

连续分配的16GB文件。

在所有这些例子中，聚集块尺寸都是1KB。

连续分配的1041377字节尺寸文件：该文件需要1017个1KB聚集块，（在最后一个聚集块中，有31个字节丢失成为内部存储碎片）。要描述这个连续文件只需要一个xad结构：

flag这里不讨论

以下为引用的内容： 　　offset0/*thebeginningofthefile*/ 　　length1017/*10171KBaggregateblocks*/ 　　addressxxxxx/*aggregateblock#*/

　　
相同的xad结构能够表示任何长度为1040385（1016*1024+1）到1041408（1017*1024）的连续文件，因为盘区描述符只表示小于聚集块大小粒度的尺寸。只有inode的di_size字段记录字节粒度。

在1041377字节文件分三段：假设相同的文件拆分成磁盘上三个不同盘区：一个为495个聚集块长，一个为22，一个为500。需要三个xad结构来表示该文件，每个物理盘区需要一个：
　　

以下为引用的内容： 　　xad#0: 　　flag这里不讨论 　　offset0/*thebeginningofthefile*/ 　　length495/*4951KBaggregateblocks*/ 　　addressxxxxx/*aggregateblock#*/ 　　 　　xad#1: 　　flag这里不讨论 　　offset495/*thebeginningofthefile*/ 　　length22/*221KBaggregateblocks*/ 　　addressyyyyy/*aggregateblock#*/ 　　 　　xad#2: 　　flag这里不讨论 　　offset517/*thebeginningofthefile*/ 　　length500/*5001KBaggregateblocks*/ 　　addresszzzzz/*aggregateblock#*/

　　
该例中，0号xad描述文件开始的495个物理聚集块。xad_offset字段包含0，因为该xad描述以逻辑偏移量0开始的字节。第二个xad，1号xad，描述文件接下来的22个物理聚集块。xad_offset字段包含495，因为该xad描述以逻辑偏移量506880(495*1024)开始的字节；前面的字节由xad0描述。最后一个xad描述文件的最后500块。这里，xad_offset字段是517。请注意，对于非稀疏文件，给定xad的xad_offset字段等于所有以前xad结构长度和（在本例中，517=495+22）。如果这一关系总是成立的，那么xad_offset字段就是冗余的，可以消除。然而，下一个例子显示，对于稀疏文件，xad_offset字段不是冗余的。

1041377字节的稀疏文件：考虑经由以下POSIX风格的操作而创建的文件：
　　

以下为引用的内容： 　　fd=create("newfile",blahblahblah); 　　write(fd,"hi",2); 　　 　　lseek(fd,1041374,0); 　　write(fd,"bye",3);

　　
该文件有以逻辑字节偏移量0开始的两字节数据（"hi"），还有以逻辑字节偏移量1,041,374开始的三字节数据("bye")，并且在这两者之间全为0（稀疏的）。文件的长度为1041377字节。

通常，JFS不分配物理磁盘空间以保存从不写入文件的字节范围。因此，将占用两个xad结构来表示该文件：一个为包含"hi"数据的盘区，一个为包含"bye"数据的盘区：
　　

以下为引用的内容： 　　xad#0: 　　flag这里不讨论 　　offset0/*thebeginningofthefile*/ 　　length1/*11KBaggregateblocks*/ 　　addressxxxxx/*aggregateblock#*/ 　　 　　xad#1: 　　flag这里不讨论 　　offset1016/*thebeginningofthefile*/ 　　length1/*11KBaggregateblocks*/ 　　addressyyyyy/*aggregateblock*/

　　
在该例中，第一个盘区(xad0)包含字节"hi"，紧接着是1022字节0。最后一个盘区(xad1)包含990字节0，紧接着是3字节"bye"。1KB盘区中剩余的31字节不是文件的组成部分。（它们与第一个例子中丢失成为内部存储碎片的31个字节相同）。
　　
请注意，该例中，xad_offset字段是必需的；这是知道xad1表示文件内在无法预料的逻辑偏移量字节序列的唯一方法（也即，xad1的偏移量不等于xad0的偏移量加长度）。这是表示稀疏文件的方法。
　　
inode的di_size字段包含写入的最后一个字节偏移值加1。
　　
连续分配的16GB的文件：xad结构中的长度字段仅有24位长：因此，它能包含的最大值是2(24)-1。如果聚集块大小是1KB（例如），那么一个xad能够表示的最大盘区是(2(24)-1)*2(10)=1KB，小于16G。暗示这也是xad结构能够表示的最大盘区。因此，如果文件够大的话，就算它在磁盘上是相连的，也需要多个xad结构来表示它。本例中显示了这样一个连续分配的文件：一个16G文件，它从聚集块号12345开始连续分配，获取16777216个1KB的聚集块(16G)。
　　

以下为引用的内容： 　　xad#0: 　　flag这里不讨论 　　offset0/*thebeginningofthefile*/ 　　length16777215/*11KBaggregateblocks*/ 　　address12345/*aggregateblock*/ 　　 　　xad#1: 　　flag这里不讨论 　　offset16777215/*thebeginningofthefile*/ 　　length1/*11KBaggregateblocks*/ 　　address16789560/*aggregateblock#*/

　　
在该例中，不论文件在磁盘上是否相连，要表示它至少需要两个xad结构，这是由于单个盘区的长度限制。

评论 (0) All

登陆 还没注册？