本文主要是介绍5.4 以太坊:以太坊源码详解4,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
MPT(实现快速查找以节省存储空间)
背景
- Trie:用于快速检索的多叉树,查找速度快、但是需要耗费大量的存储空间
- Patricia Trie:耗费的空间更小
- Merkle Tree:Merkle树是一种用于快速验证内容完整性的数据结构,其基本原理是分别计算树的叶⼦结点的hash值,然后把叶⼦结点的hash值拼接在⼀起,再计算⼀次hash作为其⽗结点的hash值,依次向上直到根结点,根结点的hash值称为Merkle Root。 可以看出,如果想要获得相同的Merkle Root,所有⼦结点的内容都必须相同,这样就可以⽤来验证树的内容有没有被篡改
概念
- MPT:MPT融合了了上⾯面3种数据结构,但是⼜又有⼀一些细微的差别。
- MPT是⽤用来检索字节数据的,因此是16叉树,分别代表0x0~0xF。
结构
MPT定义4种结点类型:
- 空结点(NULL)
- 分⽀支结点(branch node):包含16个分⽀支,以及1个value
- 扩展结点(extension node):只有1个子结点
- 叶子结点(leaf node):没有⼦子结点,包含⼀一个value
HP编码
- MPT树中另外一个重要的
这篇关于5.4 以太坊:以太坊源码详解4的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!