Why is ZFS stored in a binary tree structure?

Question

Apparently, in the ZFS (filesystem), there is an uberblock that points to the root of a zpool tree. Does anyone know why this tree makes things more efficient/reliable, and where the tree itself is stored?

Answer 1

The purpose of the tree is to improve data integrity, partly by storing checksums away from the data blocks those checksums protect. The entire file system hierarchy forms a self-healing hash tree, or merkle tree. Here's a simplified description I made earlier:

Going from left to right, directory 1 contains a pointer to file A, file A's checksum, and some other meta-data. But dir 1 is just another data block, which is pointed to by the uberblock. The uberblock therefore contains a checksum of dir 1, and so on. This does mean that every write to a file involves recalculating several checksums, all the way back to the root node (the uberblock). But ZFS's copy-on-write policy and transactional nature mitigate the performance penalty. Furthermore, ZFS is designed to take advantage of Moore's law: CPU cycles are cheap, but hard drives are slow.

ZFS also uses ditto blocks to replicate the more important parts of the tree (i.e., the parts closer to the root), to further protect against corruption.