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：
