I'm trying to gain as granular understanding of the use of MPTs and the underlying database as possible. The following is an excerpt from the particia merkle trie article on ethereum.org

That is, you would first look up the root hash in a flat key/value DB to find the root node of the trie (which is an array of keys to other nodes), use the value at index 6 as a key (and look it up in the flat key/value DB) to get the node one level down, then pick index 4 of that to look up the next value, then pick index 6 of that, and so on, until, once you followed the path: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, you look up the value of the node that you have and return the result.

It is my understanding that Patricia (and generally radix) tries have the quality of very fast look up times. Hence its use in functionalities such as autocomplete. In Ethereum's use of the structure does it sacrifice this quality for data integrity? Doesn't the PMT architecture lose all its efficiency by having to make these 'flat' database lookups? I interpret flat to mean linear. Is this wrong? Is the DB some form of radix trie as well? There is one lookup for every new node depth. Is this an intensive process and possibly(?) one of the factors in the "trillema" equation?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.