以太坊中的Merkle Patricia Tree(2):实现分
2018-01-16 本文已影响0人
shi_qinfeng
以太坊中MPT的实现
在以太坊（ethereum）中，使用了一种特殊的十六进制前缀( hex-prefix, HP )编码，用来对key进行编码。所以 在字母表中就有16个字符 。每个节点可能有16个孩子。这其中的 一个字符为一个nibble（半个字节，4位） 。
MPT树中的节点包括 空节点 、 叶子节点 、 扩展节点 和 分支节点 :
-
空节点，简单的表示空，在代码中是一个空串。 -
叶子节点（leaf），表示为[key,value]的一个键值对** ** ，其中 key是key的一种特殊十六进制编码 ， value是value的RLP编码 。 -
分支节点（branch），因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list** ** ， 前16个元素对应着key中的16个可能的十六进制字符 ， 如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值 ，即分支节点既可以搜索路径的终止也可以是路径的中间节点。 -
扩展节点（extension），也是[key，value]的一个键值对** ** ，但是这里的 value是其他节点的hash值 ，这个 hash可以被用来查询 数据库 中的节点 。也就是说 通过hash链接到其他节点 。
因此, 有 两种[key,value]节点(叶节点和扩展节点) :
-
**NULL**** ** (represented as the empty string) -
**branch**** ** A 17-item node**[ v0 ... v15, vt ]** -
**leaf**** ** A 2-item node**[ encodedPath, value ]** -
**extension**** ** A 2-item node**[ encodedPath, key ]**
以太坊中MPT的操作举例
MPT树的特点如下:
- 叶子节点和分支节点可以保存value, 扩展节点保存key；
- 没有公共的key就成为2个叶子节点；key1=[1,2,3] key2=[2,2,3]
- 有公共的key需要提取为一个扩展节点；key1=[1,2,3] key2=[1,3,3] => ex-node=[1],下一级分支node的key
- 如果公共的key也是一个完整的key，数据保存到下一级的分支节点中；key1=[1,2] key2=[1,2,3] =>ex-node=[1,2],下一级分支node的key; 下一级分支=[3],上一级key对应的value
1 在空MPT中插入一个(key=[0x72],value="hello")
A是一个 叶子节点 ** ** :
image
注意: 7,2是key
2 继续插入一个(key=[0x73],value="world")
-
提取公共key：[7]
-
A变成
扩展节点** ** ,B变成个分支节点** ** ,C,D是叶子节点** ** -
一共两个节点:
key1=[0x72],value="hello"key2=[0x73],value="world"
image
注意: A中的B代表存储一个B节点的hash, 在数据库中通过hash找到b节点数据,
如果存储的是B节点的地址,代表是普通的Patricia树, 如果存储的是hash,那就是merkle Patricia 树
3 继续插入一个(key=[0x7234],value="sqf")
一共3个节点:
key1=[0x72],value="hello"
key2=[0x73],value="world"
key3=[0x7234],value="sqf"
image
注意: key2的value放在下一级的分支节点中
4 继续插入一个(key=[0x723456],value="sqf1")
一共4个节点:
key1=[0x72],value="hello"
key2=[0x73],value="world"
key3=[0x7234],value="sqf"
key4=[0x723456],value="sqf1"
#
5 继续插入一个(key=[0x723457],value="sqf2")
一共5个节
key1=[0x72],value="hello"
key2=[0x73],value="world"
key3=[0x7234],value="sqf"
key4=[0x723456],value="sqf1"
key5=[0x723457],value="sqf2"
image
6 继续插入一个(key=[0x723412],value="sqf3")
一共6个节点:
key1=[0x72],value="hello"
key2=[0x73],value="world"
key3=[0x7234],value="sqf"
key4=[0x723456],value="sqf1"
key5=[0x723457],value="sqf2"
key6=[0x723412],value="sqf3"
image
7 继续插入一个(key=[0x5012],value="other world")
一共7个节点:
key1=[0x72],value="hello"
key2=[0x73],value="world"
key3=[0x7234],value="sqf"
key4=[0x723456],value="sqf1"
key5=[0x723457],value="sqf2"
key6=[0x723412],value="sqf3"
key7=[0x5012],value="other world"
image
