I've been reading about Merkel Patricia Trie and I think that I understand how it works, but it looks a bit overcomplicated to me, which suggests that I do not understand it fully.
Here is how Merkle Patricia Trie looks like:
Merkel Patricia Trie is similar to a regular Trie data structure but has three types of nodes
- Extension Node - contains a part of the key that is common for multiple nodes and contains a reference to a next node
- Branch Node - contains pointers to different nodes that have the same key prefix
- Leaf Node - contains a value and the remaining part of the key (called
key-end). A key of a leaf node is a concatenation of a prefix from all its parents and the
key-endin a leaf node.
Since an Extension Node has only a single pointer to another node, it seems that it will always point to a Branch Node. If it were pointing to a Leaf Node, these nodes could be combined into a single Leaf Node. And if it were pointing to another Extension Node, then these two Extension Nodes could be combined into a single Extension Node.
Why do we need to separate Extension Node and Branch Node? Can all branches from a Branch Node be embedded directly into an Extension Node? In this case, we would have just:
- Extension Node - that would contain a common prefix for two or more other nodes and would have pointers to other nodes
- Leaf Node - that would contain value and the remaining part of the key
If I understand it correctly this would:
- remove one level of indirection
- improve performance, since there would be fewer lookups in the LevelDB database
Am I missing something?