浅谈以太坊MPT(Merkle Patricia Trie)

MTP(Merkle Patricia Trie)是Ethereum中一种非常重要的数据结构,理解MTP会对我们深入学习以太坊项目打下坚实的基础。

attachments-2018-03-9MDlTgOS5aa74ab46b850.png

作者:梁雁明

著权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Trie树,字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26,数字的字典是一个10

attachments-2018-04-jqCwtuKw5ad873ad93784.png


Trie树的核心思想是空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

Trie树的必要条件如下:

1 、根节点不包含字符,除根节点以外每个节点只包含一个字符。

2、从根节点到一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

3、每个节点的所有子节点包含的字符串不相同。


Trie树的优缺点

缺点:

1、当 hash 函数很好时,Trie树的查找效率会低于哈希搜索。

2、空间消耗比较大。

优点:

1、插入和查询的效率很高,都为O(m),其中 m 是待插入/查询的字符串的长度。

2、Trie树中不同的关键字不会产生冲突。

3、Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。

4、Trie树不用求 hash 值,对短字符串有更快的速度。通常,求hash值也是需要遍历字符串的。

5、Trie树可以对关键字按字典序排序。


Patricia Trie,又被称为Radix Tree或紧凑前缀树(compact prefix tree),是一种空间使用率经过优化的Trie。

与Trie不同的是,Patricia Trie里如果存在一个父节点只有一个子节点,那么这个父节点将与其子节点合并。

这样可以缩短Trie中不必要的深度,大大加快搜索节点速度。


Patricia优缺点

优点:Patricia Trie相比Trie优点明显,减少了空间的消耗。

缺点:随着后续节点的不断插入和删除,原有节点可能会发生变化,并有可能不断裂变或者合并出新的节点。

attachments-2018-04-wlaVevip5ad87b472619d.png

Merkle树,也叫Hash Tree

叶子节点是数据块的hash值。非叶节点是其对应子节点串联字符串的hash,是一种由下而上构建的数据结构,

当树里面任何一个数据发生了变动,都会导致Top Hash的值发生变化。

image

加上对以太坊节点的理解,我们知道,每个父节点的哈希值来源于所有子节点哈希值的组合,一个顶点的哈希值能够代表一整个树形结构。hashNode 加上fullNode,shortNode,valueNode,构成了一个完整的Merkle-Patricia-Trie结构,很好的融合了各种原型结构的优点,又根据Ethereum系统的实际情况,作了实际的优化和平衡。MPT这个数据结构在设计中的种种细节,的确值得好好品味。


部分资料来源:

https://github.com/ZtesoftCS/go-ethereum-code-analysis/blob/master/trie源码分析.md

https://blog.csdn.net/ddffr/article/details/78773013


文章发布只为分享区块链技术内容,版权归原作者所有,观点仅代表作者本人,绝不代表区块链兄弟赞同其观点或证实其描述。

attachments-2018-02-kL1zBfXx5a7ffd0b78798.jpg

  • 发表于 2018-04-19 19:39
  • 阅读 ( 1433 )
  • 分类:以太坊

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
梁雁明

区块链研究员

21 篇文章

作家榜 »

  1. 社区运营-小以 442 文章
  2. 社区运营-小链 245 文章
  3. 于中阳Mercina-zy 78 文章
  4. 涂晶 72 文章
  5. 李晓琼 45 文章
  6. 兄弟连区块链培训 41 文章
  7. 吴寿鹤 36 文章
  8. John-smith 26 文章