I have just checked out these resources:
- What is a Merkle Tree? Beginner’s Guide to this Blockchain Component
- Using Merkle trees to detect inconsistencies in data
- Exploring the use of Hash Trees for Data Synchronization - Part 1
- Understanding the ethereum trie (still working on this one).
- Main specification: Merkle Patricia Trie
I sort of understand the basic diagrams such as these:
That image is in regards to Cassandra database in which it says:
Cassandra maintains a perfect compact binary hash tree of a certain depth which it can share with its replica neighbours at any time. A hash tree at its base level holds the hashes of individual rows and each parent then is the hash of its two child nodes. This could get pretty big so Cassandra compacts the tree and maintains to a limited depth with groups of rows at the base.
So that sort of makes sense. Each row is hashed, I get that, but then not sure where the parent comes in in the database, though I can imagine how a Merkle tree in this binary tree situation would store a hash of the two child nodes. I would be interested to know how they compact it, but that's a different story :).
Another image is from here:
So now it sounds like there is 1 Merkle tree per block, in this blockchain example, as opposed to the Cassandra example where it had 1 Merkle tree per table or something like that.
What I would like to clarify the following:
- Exactly what is being hashed in the database (Cassandra) example.
- What sort of performance impact this has both in terms of speed and size.
- If Ethereum uses a sort of Cassandra-like system, or if it's quite different. This is just for introduction, I have a lot more reading to do on its Merkle Patricia Trie.
In terms of (1), I am a bit confused as to what exactly is hashed. If it's like imagining a SQL database with tables, I'm wondering if they are basically literally running the table row cells individually through a hash function and then combining them into a final "hash". This seems like it would come at a significant performance penalty if you were doing massive amounts of writes like with analytics, since it would be hashing every field of every row that was written to the database, vs. if it wasn't doing that it would be what seems like orders of magnitude faster / better performance. Wondering if I'm missing something here or if it is actually this sort of a performance impact.
Which leads me to (2), which is the performance impacts of keeping a Merkle tree for the database or tables updated.