IAVL+ Tree

Note: Requires Go 1.18+

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

The purpose of this data structure is to provide persistent storage for key-value pairs (say to store account balances) such that a deterministic merkle root hash can be computed. The tree is balanced using a variant of the AVL algorithm so all operations are O(log(n)).

Nodes of this tree are immutable and indexed by their hash. Thus any node serves as an immutable snapshot which lets us stage uncommitted transactions from the mempool cheaply, and we can instantly roll back to the last committed state to process transactions of a newly committed block (which may not be the same set of transactions as those from the mempool).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

In Ethereum, the analog is Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes -- inner nodes and leaf nodes. On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

IAVL x Cosmos SDK

IAVL	DB Interface	Cosmos SDK
v0.19.x	`tm-db`	v0.45.x, v0.46.x
v0.20.x	`cometbft-db`	v0.47.x
v1.x.x	`cosmos-db`	-

NOTE: In the past, a v0.21.x release was published, but never used in production. It was retracted to avoid confusion.

Name		Name	Last commit message	Last commit date
Latest commit History 1,255 Commits
.github		.github
.vscode		.vscode
benchmarks		benchmarks
cache		cache
cmd		cmd
db		db
docs		docs
fastnode		fastnode
internal		internal
keyformat		keyformat
mock		mock
proto		proto
testdata		testdata
v2		v2
.gitignore		.gitignore
.gitpod.yml		.gitpod.yml
.golangci.yml		.golangci.yml
.mergify.yaml		.mergify.yaml
CHANGELOG.md		CHANGELOG.md
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE		LICENSE
Makefile		Makefile
PERFORMANCE.md		PERFORMANCE.md
POEM		POEM
README.md		README.md
SECURITY.md		SECURITY.md
basic_test.go		basic_test.go
batch.go		batch.go
batch_test.go		batch_test.go
buf.gen.yaml		buf.gen.yaml
compress.go		compress.go
diff.go		diff.go
diff_test.go		diff_test.go
doc.go		doc.go
export.go		export.go
export_test.go		export_test.go
fast_iterator.go		fast_iterator.go
go.mod		go.mod
go.sum		go.sum
immutable_tree.go		immutable_tree.go
import.go		import.go
import_test.go		import_test.go
iterator.go		iterator.go
iterator_test.go		iterator_test.go
migrate_test.go		migrate_test.go
mockgen.sh		mockgen.sh
mutable_tree.go		mutable_tree.go
mutable_tree_test.go		mutable_tree_test.go
node.go		node.go
node_test.go		node_test.go
nodedb.go		nodedb.go
nodedb_test.go		nodedb_test.go
options.go		options.go
proof.go		proof.go
proof_iavl_test.go		proof_iavl_test.go
proof_ics23.go		proof_ics23.go
proof_ics23_test.go		proof_ics23_test.go
proof_path.go		proof_path.go
proof_test.go		proof_test.go
testutils_test.go		testutils_test.go
tree_dotgraph.go		tree_dotgraph.go
tree_dotgraph_test.go		tree_dotgraph_test.go
tree_fuzz_test.go		tree_fuzz_test.go
tree_random_test.go		tree_random_test.go
tree_test.go		tree_test.go
unsaved_fast_iterator.go		unsaved_fast_iterator.go
util.go		util.go
version.go		version.go
with_gcc_test.go		with_gcc_test.go

License

Kava-Labs/iavl

Folders and files

Latest commit

History

Repository files navigation

IAVL+ Tree