Merkle Patricia tree

Merkle树大多数是二叉树，提供spv，它的特点是可以快速重哈希，可以做轻节点扩展。
Patricia是是一种前缀树，普通的前缀树有存储空间大，查询开销大的问题，而Patricia树最大的特点是每个节点的前缀长度不是固定的，而是变长的，可以实现很高的压缩。

Merkle Patricia tree 可以结合两者的优点。

Node类型

Node类型可以分为4类：

1. 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。

2. ShortNode

ShortNode struct {
    Key   []byte
    Value Node
    hash  []byte
    dirty bool
}

shortnode是Patricia实现变长前缀的关键，可以看到key是字节数组，value是一个node接口，它的hash值是有value的hash和key值共同计算出来的。
在Patricia树存在共同前缀，且前缀长度大于1的地方一定有ShortNode。

3. ValueNode

ValueNode struct {
    Value []byte
    hash  []byte
    dirty bool
}

ValueNode是树的叶子节点，真正存储value的位置。

4. 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的算法时间。 没有删除历史版本的功能

参考：
https://github.com/zllai/go-MerklePatriciaTree.git