In the backing key/value store, nodes are stored using their key/value pair key as the database key, and a binary encoding that contains the fields in the above Node structure - minus the key field since that is already implied by the database entry.
Storing nodes by key rather than by hash is an important optimization, and is the reason why inner nodes each have a key/value pair. The implication is that reading a key does not require traversing through the tree structure but only requires a single read in the backing key/value store, meaning there is practically no overhead versus using the backing store without a tree structure. Additionally, we can efficiently iterate through nodes in the tree in their in-order traversal just by iterating by key in the backing store (which RocksDB and LevelDB are optimized for).
I think this should be doable for Sparse Merkle trees too.
In this Merkle AVL implementation, the following optimisation has been made:
I think this should be doable for Sparse Merkle trees too.