Search Apps Documentation Source Content File Folder Download Copy Actions Download

README.md

3.33 Kb · 88 lines
Download

v0 - Unaudited This is an initial version of this package that has not yet been formally audited. A fully audited version will be published as a subsequent release. Use in production at your own risk.

AVL Tree Package

The avl package provides a gas-efficient AVL tree implementation for storing key-value data in Gno realms.

Basic Usage

 1package myrealm
 2
 3import "gno.land/p/nt/avl/v0"
 4
 5// This AVL tree will be persisted after transaction calls
 6var tree *avl.Tree
 7
 8func Set(key string, value int) {
 9	// tree.Set takes in a string key, and a value that can be of any type
10	tree.Set(key, value)
11}
12
13func Get(key string) int {
14	// tree.Get returns the value at given key in its raw form,
15	// and a bool to signify the existence of the key-value pair
16	rawValue, exists := tree.Get(key)
17	if !exists {
18		panic("value at given key does not exist")
19	}
20
21	// rawValue needs to be converted into the proper type before returning it
22	return rawValue.(int)
23}

Storage Architecture: AVL Tree vs Map

In Gno, the choice between avl.Tree and map is fundamentally about how data is persisted in storage.

Maps are stored as a single, monolithic object. When you access any value in a map, Gno must load the entire map into memory. For a map with 1,000 entries, accessing one value means loading all 1,000 entries.

AVL trees store each node as a separate object. When you access a value, Gno only loads the nodes along the search path (typically log2(n) nodes). For a tree with 1,000 entries, accessing one value loads ~10 nodes; but a tree with 1,000,000 entries only needs to load ~20 nodes.

Storage Comparison Example

Consider a realm with 1,000 key-value pairs. Here's what happens when you access a single value:

Map storage:

Object :4 = map{
  ("0" string):("123" string),
  ("1" string):("123" string),
  ...
  ("999" string):("123" string)
}
  • Accessing map["100"] loads object :4 (contains all 1,000 pairs)
  • Gas cost is proportional to total map size (1,000 entries)
  • 1 object fetch, but massive data load

AVL tree storage:

Object :6 = Node{key="4", height=10, size=1000, left=:7, right=...}
Object :9 = Node{key="2", height=9, size=334, left=:10, right=...}
Object :11 = Node{key="14", height=8, size=112, left=:12, right=...}
Object :13 = Node{key="12", height=6, size=46, left=:14, right=...}
Object :15 = Node{key="11", height=5, size=24, left=:16, right=...}
Object :17 = Node{key="102", height=4, size=13, left=:18, right=...}
Object :19 = Node{key="100", height=3, size=5, left=:30, right=...}
Object :31 = Node{key="101", height=1, size=2, left=:32, right=...}
Object :33 = Node{key="100", value="123", height=0, size=1}
  • Accessing tree.Get("100") loads ~10 objects (the search path)
  • Gas cost is proportional to log2(n) ≈ 10 nodes
  • 10 object fetches, each containing only a single node

Further Reading