Merkle Patricia tree
Merkle树大多数是二叉树，提供spv，它的特点是可以快速重哈希，可以做轻节点扩展。
Patricia是是一种前缀树，普通的前缀树有存储空间大，查询开销大的问题，而Patricia树最大的特点是每个节点的前缀长度不是固定的，而是变长的，可以实现很高的压缩。
Merkle Patricia tree 可以结合两者的优点。
Node类型
Node类型可以分为4类：
- FullNode
FullNode struct {
Children [257]Node
hash []byte
dirty bool
}
fullnode是Patricia实现多叉树的关键，一个fullnode代表一个key的其中一个字节，因此可以看到Children的长度是257，是2的8次方加1，最后一个Child用于存完全匹配的值。
hash表示这个fullnode的hash值，它是由所有Children的hash值计算出的hash值。dirty用与表示该节点是否被写过，如果被写过，则dirty为true，在commit和获取hash时候需要将重新计算和保存。
在Patricia分叉的地方一定会有fullnode。
- ShortNode
ShortNode struct {
Key []byte
Value Node
hash []byte
dirty bool
}
shortnode是Patricia实现变长前缀的关键，可以看到key是字节数组，value是一个node接口，它的hash值是有value的hash和key值共同计算出来的。
在Patricia树存在共同前缀，且前缀长度大于1的地方一定有ShortNode。
- ValueNode
ValueNode struct {
Value []byte
hash []byte
dirty bool
}
ValueNode是树的叶子节点，真正存储value的位置。
- HashNode
HashNode []byte
HashNode也是叶子节点的一种，但是它是一种懒加载的方式，真正的数据存储在数据库中。
树拓扑
例子：put "1": "A", "12345":"B", "12346":"C", "2":"D"
FullNodeA{ ... "1"index: FullNodeB.. "2"index:ValueNodeC ...}
FullNodeB{... "2"index:ShortNodeD..., finalIndex: ValueNodeF}
ValueNodeF{value: "A"}
ShortNodeD{key: "34", value: FullNodeG}
FullNodeG{..."5"index: ValueNodeH, "6"index: ValueNodeI}
ValueNodeH{value: "B"}
ValueNodeI{value: "C"}
ValueNodeC{value: "D"}
commit和stash过程
树的表示：
type Trie struct {
oldRoot []byte
root Node
kv KVStore
lock *sync.RWMutex
}
oldRoot是上一个版本的根的hash值，可以非常方便地会滚本次改动。
- ValueNode 就是将hash，value保存。
- Fullnode就是将子孙节点commit，同时保存自己节点（hash，chaildren的hash列表）。
- ShortNode就是将valuenode commit，同时保存自己节点（hash，自己的key和Value的hash）
- HashNode是虚拟的节点，没有做过修改，无须再次保存。
Stash过程：
func (t *Trie) Stash() {
if t.oldRoot == nil {
t.root = nil
} else {
hashNode := HashNode(t.oldRoot)
t.root = &hashNode
}
}
将上一个版本的oldRoot的作为hash值赋给hashNode并作为新的root就可以实现回滚。
缺点
SPV需要的数据数目是： mlogm(n), 同时sha3数据的长度也是 mlogm(n), 其中m是fullnode的child的数目。
某些场景下，会增加验证和sha3的算法时间。 没有删除历史版本的功能
