Documentation
¶
Overview ¶
Package iavl implements a versioned, snapshottable (immutable) AVL+ tree for persisting key-value pairs.
Basic usage of MutableTree.
import "github.com/tendermint/iavl" import "github.com/tendermint/tendermint/libs/db" ... tree := iavl.NewMutableTree(db.NewMemDB(), 128) tree.IsEmpty() // true tree.Set([]byte("alice"), []byte("abc")) tree.SaveVersion(1) tree.Set([]byte("alice"), []byte("xyz")) tree.Set([]byte("bob"), []byte("xyz")) tree.SaveVersion(2) tree.LatestVersion() // 2 tree.GetVersioned([]byte("alice"), 1) // "abc" tree.GetVersioned([]byte("alice"), 2) // "xyz"
Proof of existence:
root := tree.Hash() val, proof, err := tree.GetVersionedWithProof([]byte("bob"), 2) // "xyz", RangeProof, nil proof.Verify([]byte("bob"), val, root) // nil
Proof of absence:
_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 2) // nil, RangeProof, nil proof.Verify([]byte("tom"), nil, root) // nil
Now we delete an old version:
tree.DeleteVersion(1) tree.VersionExists(1) // false tree.Get([]byte("alice")) // "xyz" tree.GetVersioned([]byte("alice"), 1) // nil
Can't create a proof of absence for a version we no longer have:
_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 1) // nil, nil, error
Index ¶
- Constants
- Variables
- func PrintTree(tree *ImmutableTree)
- func RegisterWire(cdc *amino.Codec)
- func WriteDOTGraph(w io.Writer, tree *ImmutableTree, paths []PathToLeaf)
- type ImmutableTree
- func (t *ImmutableTree) Get(key []byte) (index int, value []byte)
- func (t *ImmutableTree) Get64(key []byte) (index int64, value []byte)
- func (t *ImmutableTree) GetByIndex(index int) (key []byte, value []byte)
- func (t *ImmutableTree) GetByIndex64(index int64) (key []byte, value []byte)
- func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error)
- func (t *ImmutableTree) GetWithProof(key []byte) (value []byte, proof *RangeProof, err error)
- func (t *ImmutableTree) Has(key []byte) bool
- func (t *ImmutableTree) Hash() []byte
- func (t *ImmutableTree) Height() int
- func (t *ImmutableTree) Height8() int8
- func (t *ImmutableTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *ImmutableTree) IterateRangeInclusive(start, end []byte, ascending bool, ...) (stopped bool)
- func (t *ImmutableTree) Size() int
- func (t *ImmutableTree) Size64() int64
- func (t *ImmutableTree) String() string
- func (t *ImmutableTree) Version() int
- func (t *ImmutableTree) Version64() int64
- type MutableTree
- func (tree *MutableTree) DeleteVersion(version int64) error
- func (tree *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)
- func (tree *MutableTree) GetVersioned(key []byte, version int64) (index int, value []byte)
- func (tree *MutableTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) (keys, values [][]byte, proof *RangeProof, err error)
- func (tree *MutableTree) GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)
- func (tree *MutableTree) Hash() []byte
- func (tree *MutableTree) IsEmpty() bool
- func (tree *MutableTree) Load() (int64, error)
- func (tree *MutableTree) LoadVersion(targetVersion int64) (int64, error)
- func (tree *MutableTree) Remove(key []byte) ([]byte, bool)
- func (tree *MutableTree) Rollback()
- func (tree *MutableTree) SaveVersion() ([]byte, int64, error)
- func (tree *MutableTree) Set(key, value []byte) bool
- func (tree *MutableTree) String() string
- func (tree *MutableTree) VersionExists(version int64) bool
- func (tree *MutableTree) WorkingHash() []byte
- type Node
- type PathToLeaf
- type RangeProof
- func (proof *RangeProof) ComputeRootHash() []byte
- func (proof *RangeProof) Keys() (keys [][]byte)
- func (proof *RangeProof) LeftIndex() int64
- func (proof *RangeProof) String() string
- func (proof *RangeProof) StringIndented(indent string) string
- func (proof *RangeProof) Verify(root []byte) error
- func (proof *RangeProof) VerifyAbsence(key []byte) error
- func (proof *RangeProof) VerifyItem(key, value []byte) error
Constants ¶
const Version = "0.10.0"
Version of iavl.
Variables ¶
var ( // ErrInvalidProof is returned by Verify when a proof cannot be validated. ErrInvalidProof = fmt.Errorf("invalid proof") // ErrInvalidInputs is returned when the inputs passed to the function are invalid. ErrInvalidInputs = fmt.Errorf("invalid inputs") // ErrInvalidRoot is returned when the root passed in does not match the proof's. ErrInvalidRoot = fmt.Errorf("invalid root") // ErrNilRoot is returned when the root of the tree is nil. ErrNilRoot = fmt.Errorf("tree root is nil") )
var ErrVersionDoesNotExist = fmt.Errorf("version does not exist")
ErrVersionDoesNotExist is returned if a requested version does not exist.
Functions ¶
func PrintTree ¶ added in v0.8.0
func PrintTree(tree *ImmutableTree)
PrintTree prints the whole tree in an indented form.
func RegisterWire ¶ added in v0.8.0
func RegisterWire(cdc *amino.Codec)
func WriteDOTGraph ¶
func WriteDOTGraph(w io.Writer, tree *ImmutableTree, paths []PathToLeaf)
Types ¶
type ImmutableTree ¶ added in v0.10.0
type ImmutableTree struct {
// contains filtered or unexported fields
}
ImmutableTree is a container for an immutable AVL+ ImmutableTree. Changes are performed by swapping the internal root with a new one, while the container is mutable. Note that this tree is not thread-safe.
func NewImmutableTree ¶ added in v0.10.0
func NewImmutableTree(db dbm.DB, cacheSize int) *ImmutableTree
NewImmutableTree creates both in-memory and persistent instances
func (*ImmutableTree) Get ¶ added in v0.10.0
func (t *ImmutableTree) Get(key []byte) (index int, value []byte)
Get returns the index and value of the specified key if it exists, or nil and the next index, if it doesn't.
func (*ImmutableTree) Get64 ¶ added in v0.10.0
func (t *ImmutableTree) Get64(key []byte) (index int64, value []byte)
func (*ImmutableTree) GetByIndex ¶ added in v0.10.0
func (t *ImmutableTree) GetByIndex(index int) (key []byte, value []byte)
GetByIndex gets the key and value at the specified index.
func (*ImmutableTree) GetByIndex64 ¶ added in v0.10.0
func (t *ImmutableTree) GetByIndex64(index int64) (key []byte, value []byte)
func (*ImmutableTree) GetRangeWithProof ¶ added in v0.10.0
func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error)
GetRangeWithProof gets key/value pairs within the specified range and limit.
func (*ImmutableTree) GetWithProof ¶ added in v0.10.0
func (t *ImmutableTree) GetWithProof(key []byte) (value []byte, proof *RangeProof, err error)
GetWithProof gets the value under the key if it exists, or returns nil. A proof of existence or absence is returned alongside the value.
func (*ImmutableTree) Has ¶ added in v0.10.0
func (t *ImmutableTree) Has(key []byte) bool
Has returns whether or not a key exists.
func (*ImmutableTree) Hash ¶ added in v0.10.0
func (t *ImmutableTree) Hash() []byte
Hash returns the root hash.
func (*ImmutableTree) Height ¶ added in v0.10.0
func (t *ImmutableTree) Height() int
Height returns the height of the tree.
func (*ImmutableTree) Height8 ¶ added in v0.10.0
func (t *ImmutableTree) Height8() int8
func (*ImmutableTree) Iterate ¶ added in v0.10.0
func (t *ImmutableTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
Iterate iterates over all keys of the tree, in order.
func (*ImmutableTree) IterateRange ¶ added in v0.10.0
func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
IterateRange makes a callback for all nodes with key between start and end non-inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate)
func (*ImmutableTree) IterateRangeInclusive ¶ added in v0.10.0
func (t *ImmutableTree) IterateRangeInclusive(start, end []byte, ascending bool, fn func(key, value []byte, version int64) bool) (stopped bool)
IterateRangeInclusive makes a callback for all nodes with key between start and end inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate)
func (*ImmutableTree) Size ¶ added in v0.10.0
func (t *ImmutableTree) Size() int
Size returns the number of leaf nodes in the tree.
func (*ImmutableTree) Size64 ¶ added in v0.10.0
func (t *ImmutableTree) Size64() int64
func (*ImmutableTree) String ¶ added in v0.10.0
func (t *ImmutableTree) String() string
String returns a string representation of Tree.
func (*ImmutableTree) Version ¶ added in v0.10.0
func (t *ImmutableTree) Version() int
Version returns the version of the tree.
func (*ImmutableTree) Version64 ¶ added in v0.10.0
func (t *ImmutableTree) Version64() int64
type MutableTree ¶ added in v0.10.0
type MutableTree struct { *ImmutableTree // The current, working tree. // contains filtered or unexported fields }
MutableTree is a persistent tree which keeps track of versions.
func NewMutableTree ¶ added in v0.10.0
func NewMutableTree(db dbm.DB, cacheSize int) *MutableTree
NewMutableTree returns a new tree with the specified cache size and datastore.
func (*MutableTree) DeleteVersion ¶ added in v0.10.0
func (tree *MutableTree) DeleteVersion(version int64) error
DeleteVersion deletes a tree version from disk. The version can then no longer be accessed.
func (*MutableTree) GetImmutable ¶ added in v0.10.0
func (tree *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)
GetImmutable loads an ImmutableTree at a given version for querying
func (*MutableTree) GetVersioned ¶ added in v0.10.0
func (tree *MutableTree) GetVersioned(key []byte, version int64) ( index int, value []byte, )
GetVersioned gets the value at the specified key and version.
func (*MutableTree) GetVersionedRangeWithProof ¶ added in v0.10.0
func (tree *MutableTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) ( keys, values [][]byte, proof *RangeProof, err error)
GetVersionedRangeWithProof gets key/value pairs within the specified range and limit.
func (*MutableTree) GetVersionedWithProof ¶ added in v0.10.0
func (tree *MutableTree) GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)
GetVersionedWithProof gets the value under the key at the specified version if it exists, or returns nil.
func (*MutableTree) Hash ¶ added in v0.10.0
func (tree *MutableTree) Hash() []byte
Hash returns the hash of the latest saved version of the tree, as returned by SaveVersion. If no versions have been saved, Hash returns nil.
func (*MutableTree) IsEmpty ¶ added in v0.10.0
func (tree *MutableTree) IsEmpty() bool
IsEmpty returns whether or not the tree has any keys. Only trees that are not empty can be saved.
func (*MutableTree) Load ¶ added in v0.10.0
func (tree *MutableTree) Load() (int64, error)
Load the latest versioned tree from disk.
func (*MutableTree) LoadVersion ¶ added in v0.10.0
func (tree *MutableTree) LoadVersion(targetVersion int64) (int64, error)
Returns the version number of the latest version found
func (*MutableTree) Remove ¶ added in v0.10.0
func (tree *MutableTree) Remove(key []byte) ([]byte, bool)
Remove removes a key from the working tree.
func (*MutableTree) Rollback ¶ added in v0.10.0
func (tree *MutableTree) Rollback()
Rollback resets the working tree to the latest saved version, discarding any unsaved modifications.
func (*MutableTree) SaveVersion ¶ added in v0.10.0
func (tree *MutableTree) SaveVersion() ([]byte, int64, error)
SaveVersion saves a new tree version to disk, based on the current state of the tree. Returns the hash and new version number.
func (*MutableTree) Set ¶ added in v0.10.0
func (tree *MutableTree) Set(key, value []byte) bool
Set sets a key in the working tree. Nil values are not supported.
func (*MutableTree) String ¶ added in v0.10.0
func (tree *MutableTree) String() string
String returns a string representation of the tree.
func (*MutableTree) VersionExists ¶ added in v0.10.0
func (tree *MutableTree) VersionExists(version int64) bool
VersionExists returns whether or not a version exists.
func (*MutableTree) WorkingHash ¶ added in v0.10.0
func (tree *MutableTree) WorkingHash() []byte
WorkingHash returns the hash of the current working tree.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node represents a node in a Tree.
func MakeNode ¶
MakeNode constructs an *Node from an encoded byte slice.
The new node doesn't have its hash saved or set. The caller must set it afterwards.
func (*Node) PathToLeaf ¶ added in v0.8.0
func (node *Node) PathToLeaf(t *ImmutableTree, key []byte) (PathToLeaf, *Node, error)
If the key does not exist, returns the path to the next leaf left of key (w/ path), except when key is less than the least item, in which case it returns a path to the least item.
type PathToLeaf ¶ added in v0.8.0
type PathToLeaf []proofInnerNode
PathToLeaf represents an inner path to a leaf node. Note that the nodes are ordered such that the last one is closest to the root of the tree.
func (PathToLeaf) Index ¶ added in v0.9.1
func (pl PathToLeaf) Index() (idx int64)
returns -1 if invalid.
func (PathToLeaf) String ¶ added in v0.8.0
func (pl PathToLeaf) String() string
type RangeProof ¶ added in v0.8.0
type RangeProof struct { // You don't need the right path because // it can be derived from what we have. LeftPath PathToLeaf `json:"left_path"` InnerNodes []PathToLeaf `json:"inner_nodes"` Leaves []proofLeafNode `json:"leaves"` // contains filtered or unexported fields }
func (*RangeProof) ComputeRootHash ¶ added in v0.9.1
func (proof *RangeProof) ComputeRootHash() []byte
ComputeRootHash computes the root hash with leaves. Returns nil if error or proof is nil. Does not verify the root hash.
func (*RangeProof) Keys ¶ added in v0.9.1
func (proof *RangeProof) Keys() (keys [][]byte)
Keys returns all the keys in the RangeProof. NOTE: The keys here may include more keys than provided by tree.GetRangeWithProof or MutableTree.GetVersionedRangeWithProof. The keys returned there are only in the provided [startKey,endKey){limit} range. The keys returned here may include extra keys, such as: - the key before startKey if startKey is provided and doesn't exist; - the key after a queried key with tree.GetWithProof, when the key is absent.
func (*RangeProof) LeftIndex ¶ added in v0.9.1
func (proof *RangeProof) LeftIndex() int64
The index of the first leaf (of the whole tree). Returns -1 if the proof is nil.
func (*RangeProof) String ¶ added in v0.8.0
func (proof *RangeProof) String() string
String returns a string representation of the proof.
func (*RangeProof) StringIndented ¶ added in v0.8.0
func (proof *RangeProof) StringIndented(indent string) string
func (*RangeProof) Verify ¶ added in v0.8.0
func (proof *RangeProof) Verify(root []byte) error
Verify that proof is valid.
func (*RangeProof) VerifyAbsence ¶ added in v0.8.0
func (proof *RangeProof) VerifyAbsence(key []byte) error
Verify that proof is valid absence proof for key. Does not assume that the proof itself is valid. For that, use Verify(root).
func (*RangeProof) VerifyItem ¶ added in v0.8.0
func (proof *RangeProof) VerifyItem(key, value []byte) error
Also see LeftIndex(). Verify that a key has some value. Does not assume that the proof itself is valid, call Verify() first.