A versioned, snapshottable AVL+ tree implementation in Go for persistent key-value storage with deterministic Merkle root hashes.
IAVL is a versioned, snapshottable AVL+ tree implementation written in Go. It provides persistent storage for key-value pairs with a deterministic Merkle root hash, enabling efficient state management and rollbacks. The tree is designed for applications like blockchains where immutable snapshots and cryptographic verification are critical.
Developers building blockchain systems, distributed ledgers, or applications requiring versioned, cryptographically verifiable data structures. It is particularly relevant for projects using the Cosmos SDK ecosystem.
IAVL offers a simpler alternative to Patricia tries (like Ethereum's) by avoiding key hashing and using only two node types, resulting in faster key iteration and easier implementation. Its immutable, hash-indexed nodes provide efficient snapshotting and rollback capabilities.
Merkleized IAVL+ Tree implementation in Go
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
Immutable nodes indexed by hash enable cheap staging of uncommitted transactions and instant rollback to committed states, as highlighted in the versioned and snapshottable features for blockchain state management.
Computes a consistent cryptographic hash of tree contents, essential for consensus and verification in distributed systems like blockchains, per the README's focus on Merkle root hashing.
Uses only inner and leaf nodes with values stored on leaves, making implementation straightforward and operations O(log(n)), as described in the AVL+ balancing philosophy.
Keys do not require pre-hashing for insertion, unlike Patricia tries, enabling faster iteration in the key space, which benefits applications needing efficient key traversal.
Merkle root depends on insertion order, which can be a limitation for systems requiring order-independent hashing, though the README notes it's efficiently encoded during serialization.
Frequent changes in database interfaces (e.g., from tm-db to cosmos-db) and tight coupling with Cosmos SDK versions, as shown in the version table, add integration overhead and maintenance challenges.
Requires Go 1.18+ with no official bindings for other languages, limiting adoption in polyglot environments or teams using different tech stacks.