Those immutable data structures of ZFS are implemented in C and C++, where everything is mutable. You're actually confirming kadoban's point: Mutable data structures can pretend to be immutable or partially immutable, so there can never be an immutable data structure that's faster than all possible mutable data structures.
And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.
And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.