IVAL tree

IAVL树是AVL树的变种，能够维护版本。它和patricia树相比在某些场景下sha3的计算个数更少。

它的核心思想是：通过平衡旋转来使得查询次数在log2(n)，在保存版本之后, 由于重哈希会和旋转都会改变节点的hash值，前一个版本不再被引用的节点被成为孤儿节点，也会被保存在db中。

数据结构

Node的表示：

type Node struct {
    key       []byte
    value     []byte
    version   int64
    height    int8
    size      int64
    hash      []byte
    leftHash  []byte
    leftNode  *Node
    rightHash []byte
    rightNode *Node
    persisted bool
}

height 表示节点在树中的高度，version表示该node被保存时的版本。一个经典的二叉树节点表示，出了有lefthash，righthash，version之外的属性。

type ImmutableTree struct {
    root    *Node
    ndb     *nodeDB
    version int64
}

一棵不可变树会包含db和根节点和版本号，node和tree的结合可以提供很多额外的功能，比如遍历子孙节点，寻找兄弟节点，反序列化

type MutableTree struct {
    *ImmutableTree                  // The current, working tree.
    lastSaved      *ImmutableTree   // The most recently saved tree.
    orphans        map[string]int64 // Nodes removed by changes to working tree.
    versions       map[int64]bool   // The previous, saved versions of the tree.
    ndb            *nodeDB
}

可变树可以提供快速回滚的功能，只要是有上一棵树lastSaved的备份。versions会有所有的版本，所有的当前操作都是在ImmutableTree上进行的，orphans字段则提供了额外的删除版本的功能。

删除版本

在插入/更新数据的时候，重hash会产生孤儿节点，旋转会产生孤儿节点，孤儿节点保存的格式是 'o/{节点最后应该存在的tree的版本}/{节点最开始出现的tree的版本}'，当然只有persistent的孤儿节点会保存到数据库，临时的孤儿节点没有必要保存。
在删除某个特定版本version的时候，首选会遍历所有 'o/version'开头的所有孤儿节点，同时获取version最近的前一个版本preversion，如果preversion< {节点最开始出现的tree的版本}, 说明没有任何版本再引用这个孤儿节点，则可以删除这个孤儿节点以及这个孤儿节点代表的真是节点。

RangeProof

type RangeProof struct {
    LeftPath   PathToLeaf      `json:"left_path"`
    InnerNodes []PathToLeaf    `json:"inner_nodes"`
    Leaves     []proofLeafNode `json:"leaves"`
}

RangeProof的一个好处是可以验证一个key不存在。
它的思路是根据range{startKey, endKey}，首先找出startKey的所有验证路径，然后从根节点中序遍历到叶子节点（注意遍历的过程中有对key的控制，使之不会走出去），第一次接触叶子节点后的所有节点的右子节点都添加到InnerNodes中。而在range 中的叶子节点都会添加到Leaves中。

一个 RangeProof 首先要证明它自己是合法的，需要和rootHash进行verify。Leaves[0] 需要和 LeftPath 验证rootHash，Leaves[i]和InnerNodes[i]验证hash相同。

证明一个key不存在的几种情况：

如果 LeftPath 是一路向左的，同时验证的key比Leaves的第一个的key还小，证明待验证key比所有的key都小。
如果 LeftPath 是一路向右的，同时key比Leaves的第一个的key还大，证明待验证key比所有的key都小。
否则从Leaves[i] 的第一个到最后一个比较，如果有一个key相同的，则验证失败；如果中途比任何一个key小，则证明key不存在。比较到最后，则这个proof无法证明一个key不存在。

以此放入[a-z]的key，删除i的key，查询 e-k的rangeproof：

ivamc.png