视频简介:谈谈区块链(12):Merkle_Patricia树。
我们研究了怎样从小白开始学习,成为区块链的高手。
Merkle Patricia Tree (MPT) 树详解。
Merkle Patricia Tree(简称MPT树,实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构,可以用来存储所有的(key,value)对。以太坊区块的头部包括一个区块头,一个交易的列表和一个uncle区块的列表。在区块头部包括了交易的hash树根,用来校验交易的列表。在p2p网络上传输的交易是一个简单的列表,它们被组装成一个叫做trie树的特殊数据结构,来计算根hash。值得注意的是,除了校验区块外,这个数据结构并不是必须的,一旦区块被验证正确,那么它在技术上是可以忽略的。但是,这意味着交易列表在本地以trie树的形式存储,发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。
Trie树也叫作Radix树,为了提高效率,以太坊在实现上对其做了一些改进。在一般的radix树中,key是从树根到对应value得真实的路径。即从根节点开始,key中的每个字符会标识走那个子节点从而到达相应value。Value被存储在叶子节点,是每条路径的终止。假如key来自一个包含N个字符的字母表,那么树中的每个节点都可能会有多达N个孩子,树的最大深度是key的最大长度。
 
1
3