葉子也就是leaf指在網路結構中某些計算機，它們從比較靠近中心的計算機處接收信號，而不把信號傳送至較遠的計算機。葉子節點就是樹中最底段的節點，葉子節點沒有子節點。格式化葉子節點的結構比中間節點的結構稍微複雜一點。為了能夠在一個格式化葉子節點中保存多個條目，reiserfs 採用了如圖 4 所示的布局結構。
基本介紹
- 中文名：葉子節點
- 最大存儲的數據：可達 4048 KB
- 開始：以一個數據塊頭開始
- 設計 ：從兩端向中間伸展的條目頭
- 條目的含義：存儲在單個節點中的一個數據容器
節點布局,結構定義,條目類型,結構定義,目錄條目,結構定義,條目方式,存儲結構,
節點布局
從圖中可以看出，每個格式化葉子節點都以一個數據塊頭開始，然後是從兩端向中間伸展的條目頭和條目數據的數組，空閒空間保留在中間，這種設計是為了擴充方便。
所謂條目（item，或稱為項）就是可以存儲在單個節點中的一個數據容器，我們可以認為條目是由條目頭和條目數據體組成的。
結構定義
460 /* Everything in the filesystem is stored as a set of items. The
461 item head contains the key of the item, its free space (for
462 indirect items) and specifies the location of the item itself
463 within the block. */
464
465 struct item_head {
466 /* Everything in the tree is found by searching for it based on
467 * its key.*/
468 struct reiserfs_key ih_key;
469 union {
470 /* The free space in the last unformatted node of an
471 indirect item if this is an indirect item. This
472 equals 0xFFFF iff this is a direct item or stat data
473 item. Note that the key, not this field, is used to
474 determine the item type, and thus which field this
475 union contains. */
476 __le16 ih_free_space_reserved;
477 /* Iff this is a directory item, this field equals the
478 number of directory entries in the directory item. */
479 __le16 ih_entry_count;
480 } __attribute__ ((__packed__)) u;
481 __le16 ih_item_len; /* total size of the item body */
482 __le16 ih_item_location; /* an offset to the item body
483 * within the block */
484 __le16 ih_version; /* 0 for all old items, 2 for new
485 ones. Highest bit is set by fsck
486 temporary, cleaned after all
487 done */
488 } __attribute__ ((__packed__));
從 item_head 結構定義中可以看出，關鍵字已經包含在其中了。ih_item_len 和 ih_item_location 分別表示對應條目的數據體的長度和在本塊中的偏移量。請注意該結構的第 17、18 個位元組是一個聯合結構，對於不同類型的條目來說，該值的意義不同：對於 stat 數據條目（TYPE_STAT_DATA）或直接數據條目（TYPE_DIRECT），該值為 15；對於間接數據條目（TYPE_INDIRECT），該值表示最後一個未格式化數據塊中的空閒空間；對於目錄條目（TYPE_DIRENTRY），該值表示目錄條目中目錄項的個數。
目前 reiserfs 支持的條目類型有 4 種，它們是依靠關鍵字中的 type 欄位來區分的；而在舊版本的關鍵字中，則是通過 uniqueness 欄位來標識條目類型的，其定義如清單 6 所示。
條目類型
346 //
347 // there are 5 item types currently
348 //
349 #define TYPE_STAT_DATA 0
350 #define TYPE_INDIRECT 1
351 #define TYPE_DIRECT 2
352 #define TYPE_DIRENTRY 3
353 #define TYPE_MAXTYPE 3
354 #define TYPE_ANY 15 // FIXME: comment is required
355
…
509 //
510 // in old version uniqueness field shows key type
511 //
512 #define V1_SD_UNIQUENESS 0
513 #define V1_INDIRECT_UNIQUENESS 0xfffffffe
514 #define V1_DIRECT_UNIQUENESS 0xffffffff
515 #define V1_DIRENTRY_UNIQUENESS 500
516 #define V1_ANY_UNIQUENESS 555 // FIXME: comment is required
517
下面讓我們逐一來了解一下各種條目的存儲結構。
STAT 條目
stat 數據（TYPE_STAT_DATA）非常類似於 ext2 中的索引節點，其中保存了諸如檔案許可權、MAC（modified、accessed、changed）時間信息等數據。在3.6 版本的 reiserfs 中，stat 數據使用一個stat_data 結構表示，該結構大小為 44 位元組，其定義如清單 7 所示：
結構定義
835 /* Stat Data on disk (reiserfs version of UFS disk inode minus the
836 address blocks) */
837 struct stat_data {
838 __le16 sd_mode; /* file type, permissions */
839 __le16 sd_attrs; /* persistent inode flags */
840 __le32 sd_nlink; /* number of hard links */
841 __le64 sd_size; /* file size */
842 __le32 sd_uid; /* owner */
843 __le32 sd_gid; /* group */
844 __le32 sd_atime; /* time of last access */
845 __le32 sd_mtime; /* time file was last modified */
846 __le32 sd_ctime; /* time inode (stat data) was last changed */
/* (except changes to sd_atime and sd_mtime) */
847 __le32 sd_blocks;
848 union {
849 __le32 sd_rdev;
850 __le32 sd_generation;
851 //__le32 sd_first_direct_byte;
852 /* first byte of file which is stored in a
853 direct item: except that if it equals 1
854 it is a symlink and if it equals
855 ~(__u32)0 there is no direct item. The
856 existence of this field really grates
857 on me. Let's replace it with a macro
858 based on sd_size and our tail
859 suppression policy? */
860 } __attribute__ ((__packed__)) u;
861 } __attribute__ ((__packed__));
862 //
863 // this is 44 bytes long
864 //
stat_data 條目使用的關鍵字中，offset 和 type 的值總是 0，這樣就能確保 stat 數據是相同對象（object-id）中的第一個條目，從而能夠加快訪問速度。
與 ext2 的 ext2_indoe 結構對比一下就會發現，stat_data 中既沒有記錄數據塊位置的地方，也沒有記錄刪除時間，而這正是我們在 ext2/ext3 中恢復刪除檔案的基礎，因此可以猜測得到，在reiserfs 檔案系統中要想恢復已經刪除的檔案，難度會變得更大。
目錄條目
目錄條目中記錄了目錄項信息。目錄條目由目錄頭和目錄項數據（即檔案或子目錄名）組成。如果一個目錄中包含的目錄項太多，可以擴充到多個目錄條目中存儲。為了方便管理某個目錄中子目錄或檔案的增減，目錄條目也採用了與條目頭類似的設計：從兩端向中間擴充，其布局結構如圖 5 所示。
目錄條目存儲結構
目錄頭是一個 reiserfs_de_head 結構，大小為 16 位元組，其定義如清單 8 所示。
結構定義
920 /*
921 Q: How to get key of object pointed to by entry from entry?
922
923 A: Each directory entry has its header. This header has
deh_dir_id and deh_objectid fields, those are key
924 of object, entry points to */
925
926 /* NOT IMPLEMENTED:
927 Directory will someday contain stat data of object */
928
929 struct reiserfs_de_head {
930 __le32 deh_offset; /* third component of the directory entry key */
931 __le32 deh_dir_id; /* objectid of the parent directory of the object,
932 that is referenced by directory entry */
933 __le32 deh_objectid; /* objectid of the object, that is referenced */
/* by directory entry */
934 __le16 deh_location; /* offset of name in the whole item */
935 __le16 deh_state; /* whether 1) entry contains stat data (for future),
936 and 2) whether entry is hidden (unlinked) */
937 } __attribute__ ((__packed__));
reiserfs_de_head 結構中包含了 deh_dir_id 和 deh_objectid fields 這兩個欄位，它們就是其父目錄關鍵字中對應的兩個欄位。deh_offset 的 7 到 30 位是檔案名稱的 hash 值，0 到 6 位用來解決 hash 衝突的問題（reiserfs 中可以使用 3 種 hash 函式：tea、rupasov 和 r5，默認為 r5）。檔案名稱的位置保存在 deh_location 欄位中，而 deh_state 的第 2 位表示該目錄條目是否是可見的（該位為 1 則表示該目錄條目是可見的，為 0 表示不可見）。檔案名稱是一個字元串，以空字元結束，按照 8位元組對齊。
條目方式
在 reiserfs 中，檔案數據可以通過兩種方式進行存取：直接條目（direct item）和間接條目（indirect item）。對於小檔案來說，檔案數據本身和 stat 數據可以一起存儲到葉子節點中，這種條目就稱為直接條目。直接條目就採用圖 4 所示的存儲結構，不過每個條目數據體就是檔案數據本身。對於大檔案來說，單個葉子節點無法存儲下所有數據，因此會將部分數據存儲到未格式化數據塊中，並通過間接條目中存儲的指針來訪問這些數據塊。未格式化數據塊都是整塊使用的，最後一個未格式化數據塊中可能會遺留一部分剩餘空間，大小是由對應條目頭的 ih_free_space_reserved 欄位指定的。圖 6 給出了間接條目的存儲結構。
存儲結構
對於預設的 4096位元組的數據塊來說，一個間接條目所能存儲的數據最大可達 4048 KB（4096*(4096-48)/4 位元組），更大的檔案需要使用多個間接條目進行存儲，它們之間的順序是通過關鍵字中的 offset 進行標識的。
另外，檔案末尾不足一個數據塊的部分也可以像小檔案一樣存儲到直接條目中，這種技術就稱為尾部封裝（tail packing）。在這種情況下，存儲一個檔案至少需要使用一個間接條目和一個直接條目。
