wandering tree問題是log-structured 文件系統（LFS） 特有的一個問題，因為LFS的臟數據是追加更新的，所以如果一個數據塊變臟了，那么那個數據塊的直接索引塊、間接索引塊都會變臟（因為索引的地址變臟）。F2FS是如何解決這個問題呢？

我們知道F2FS中main area中共有兩種類型的block：NODE和DATA，其中NODE存儲文件的元數據，DATA存儲文件實際的數據。其中NODE類型的block包括三類元數據：inode，直接dnode，間接dnode。其中直接dnode的每一個表項指向的是一個DATA block的地址，而間接dnode的每一個表項指針指向的NAT表中的一個表項。

這是F2FS解決wandering tree問題的關鍵F2FS引入了NAT（node address table），其中每個表項的結構是：

struct f2fs_nat_entry {__u8 version;       /* latest version of cached nat entry */__le32 ino;     /* inode number */__le32 block_addr;  /* block address */
} __packed;

NAT表是個大數組，每個數組元素就是上面的f2fs_nat_entry。引入NAT表項是F2FS解決wandering tree問題的關鍵，因為這樣每當有數據塊更新的之后，只有與其直接相關的dnode才會變臟，各間接dnode是不會變臟的。怎么實現的？

上面說到，直接dnode的表項指向的是DATA block的地址，所以DATA page變臟了之后，DATA block就要變更了，所以被殃及的直接dnode當然也臟嘍。但是注意，此時火勢并不會蔓延到間接dnode上，因為間接dnode表項指針指的并不是直接dnode的block地址，而是NAT表中的一個表項，所以NAT就像防火槍一樣防止了tree任意滋生：你只要把NAT中相應的block_addr域給更新掉就可以了，我間接dnode的指針還是指向這個NAT表項，不變！巧妙！

有興趣的同學可以研究下C++中虛函數的實現，與此處異曲同工。