why should you use an avl tree instead of a map?
on the first day of gno development, you're taught "use avl trees, not maps". but how is a more complex implementation better than a native map type?
gno tries to give a radical solution to storing data; and instead of having the public API to store it as some kind of database, it puts the storage right into the programming language: to store a variable, just put it as a global.
package counter // import "gno.land/r/demo/counter"
var counter int
func Increment() int {
counter++
return counter
}a simple "counter" realm.
when developing in gno, most existing realms choose to store their data in a key/value data structure, the avl.Tree - here's an example from effective gno, showing how it can be used to save data.
package blog
import "gno.land/p/demo/avl"
var tree avl.Tree
func GetPost(id string) *Post {
return tree.Get(id).(*Post)
}
func AddPost(id string, post *Post) {
tree.Set(id, post)
}but how is it possible, exactly, that an avl tree is better than a native map? to answer that, let's take a look at what happens in their under-the-hood representation.
if you're familiar with filetests, you'll know there is, among their many directives, a // Realm: directive. this one is used as a dump of the gno store's "opslog"; the opslog keeps track of all object additions, deletions and modifications, as well as when we switch from a realm to another. the // Realm: directive's content allows us to peek into how gno is storing things under the hood, so let's try to leverage its power.
by taking a look at tests/file.go, we can see it uses SprintStoreOps to print the source. so, let's use code inspired by SprintStoreOps to dump into a file what happens on each GetObjectSafe.
func (ds *defaultStore) GetObjectSafe(oid ObjectID) Object {
// check cache.
if oo, exists := ds.cacheObjects[oid]; exists {
return oo
}
// check baseStore.
if ds.baseStore != nil {
if oo := ds.loadObjectSafe(oid); oo != nil {
if debug {
if _, ok := oo.(*PackageValue); ok {
panic("packages must be fetched with GetPackage()")
}
}
if _, err := os.Stat("dump.log"); err == nil {
f, err := os.OpenFile("dump.log", os.O_RDWR|os.O_APPEND, 0644)
if err != nil {
panic(err)
}
fmt.Fprintf(f, "============== defaultStore.GetObject(%q)\n%v\n",
oid,
oo.String())
f.Close()
}
return oo
}
}
return nil
}this code makes it so each time we fetch a previously unfetched object from the store, we dump it into the file dump.log (if it exists).
let's create a sample package to aid us:
package hello
import (
"strconv"
"gno.land/p/demo/avl"
)
var hello avl.Tree
var helloMap = make(map[string]string)
func init() {
for i := 0; i < 1000; i++ {
s := strconv.Itoa(i)
hello.Set(s, "123")
helloMap[s] = "123"
}
}
func Render(s string) string {
if s == "map" {
return helloMap["100"]
}
res, _ := hello.Get("100")
return res.(string)
}
after we addpkg this, we can use our modification on GetObjectSafe to see what objects are retrieved, when we do a render:
# add the package
gnokey maketx addpkg -pkgpath gno.land/r/pkg1 -pkgdir . -gas-fee 1ugnot --gas-wanted 100000000 -broadcast test1
# let's enable the logs, creating dump.log
touch dump.log
# let's do a query!
gnokey query vm/qrender --data 'gno.land/r/pkg1:'here's the result:
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:2")
Block(ID:302e5163ca42d53def527ea18dfd0ca4ce3602ba:2,Addr:0xc0092934a0,Source:ref(gno.land/r/pkg1/:0:0),Parent:%!p(<nil>))
(RefNode names not shown)
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:5")
Block(ID:302e5163ca42d53def527ea18dfd0ca4ce3602ba:5,Addr:0xc009293680,Source:ref(gno.land/r/pkg1/a.gno:1:1),Parent:%!p(gnolang.RefValue={{{[48 46 81 99 202 66 213 61 239 82 126 161 141 253 12 164 206 54 2 186]} 2} true {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]}}))
(RefNode names not shown)
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:3")
struct{(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("26a90809de387e567a70972c32a4cc9e8d44e55f:2")
Block(ID:26a90809de387e567a70972c32a4cc9e8d44e55f:2,Addr:0xc00ee081e0,Source:ref(gno.land/p/demo/avl/:0:0),Parent:%!p(<nil>))
(RefNode names not shown)
============== defaultStore.GetObject("26a90809de387e567a70972c32a4cc9e8d44e55f:3")
Block(ID:26a90809de387e567a70972c32a4cc9e8d44e55f:3,Addr:0xc00ee083c0,Source:ref(gno.land/p/demo/avl/node.gno...,Parent:%!p(gnolang.RefValue={{{[38 169 8 9 222 56 126 86 122 112 151 44 50 164 204 158 141 68 229 95]} 2} true {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]}}))
(RefNode names not shown)
============== defaultStore.GetObject("26a90809de387e567a70972c32a4cc9e8d44e55f:4")
Block(ID:26a90809de387e567a70972c32a4cc9e8d44e55f:4,Addr:0xc00ee085a0,Source:ref(gno.land/p/demo/avl/tree.gno...,Parent:%!p(gnolang.RefValue={{{[38 169 8 9 222 56 126 86 122 112 151 44 50 164 204 158 141 68 229 95]} 2} true {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]}}))
(RefNode names not shown)
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:6")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:7) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:7")
struct{("4" string),(undefined),(12 int8),(1000 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:8")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:9) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:9")
struct{("2" string),(undefined),(10 int8),(334 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:10")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:11) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:11")
struct{("14" string),(undefined),(8 int8),(112 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:12")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:13) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:13")
struct{("12" string),(undefined),(6 int8),(46 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:14")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:15) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:15")
struct{("11" string),(undefined),(5 int8),(24 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:16")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:17) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:17")
struct{("102" string),(undefined),(4 int8),(13 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:18")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:19) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:19")
struct{("100" string),(undefined),(3 int8),(5 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:30")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:31) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:31")
struct{("101" string),(undefined),(1 int8),(2 int),(&<nil> *gno.land/p/demo/avl.Node),(&<nil> *gno.land/p/demo/avl.Node)}
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:32")
heapitem((ref(302e5163ca42d53def527ea18dfd0ca4ce3602ba:33) gno.land/p/demo/avl.Node))
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:33")
struct{("100" string),("123" string),(0 int8),(1 int),(nil *gno.land/p/demo/avl.Node),(nil *gno.land/p/demo/avl.Node)}this more or less explains how an avl.Tree fetches data; though reading the source is likely to teach you more. Get() recursively goes down the tree, choosing whether to go in the "left" or "right" leaf, based on whether the key we're looking for is < or > the key of the node being inspected. in fact, you can see the first field (which is the key) going from "4", to "2" down to "100". but there's still some nodes to traverse (this is indicated by the third field, which the "height" of the node at that point), so it picks the right path. this is why the reference jumps from :19 to :30; then it stops once the height reaches 0.
note - the hash is just a hash of the import path. 302e5163ca42d53def527ea18dfd0ca4ce3602ba is the first 20 bytes (40 hex characters) of printf 'gno.land/r/pkg1' | sha256sum. the number is a sequential counter of the objects, increased as each object is stored. together, they form the ObjectID.
now, let's see what happens when we load the map:
# clear out the log
echo > dump.log
# load the map!
gnokey query vm/qrender --data 'gno.land/r/pkg1:map'here's the result:
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:2")
Block(ID:302e5163ca42d53def527ea18dfd0ca4ce3602ba:2,Addr:0xc00acee000,Source:ref(gno.land/r/pkg1/:0:0),Parent:%!p(<nil>))
(RefNode names not shown)
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:5")
Block(ID:302e5163ca42d53def527ea18dfd0ca4ce3602ba:5,Addr:0xc00acee1e0,Source:ref(gno.land/r/pkg1/a.gno:1:1),Parent:%!p(gnolang.RefValue={{{[48 46 81 99 202 66 213 61 239 82 126 161 141 253 12 164 206 54 2 186]} 2} true {[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]}}))
(RefNode names not shown)
============== defaultStore.GetObject("302e5163ca42d53def527ea18dfd0ca4ce3602ba:4")
map{("0" string):("123" string),("1" string):("123" string),("2" string):("123" string),("3" string):("123" string),("4" string):("123" string),("5" string):("123" string),("6" string):("123" string),("7" string):("123" string),("8" string):("123" string),("9" string):("123" string),("10" string):("123" string),("11" string):("123" string),("12" string):("123" string),("13" string):("123" string),("14" string):("123" string),("15" string):("123" string),("16" string):("123" string),("17" string):("123" string),("18" string):("123" string),("19" string):("123" string),("20" string):("123" string),("21" string):("123" string),("22" string):("123" string),("23" string):("123" string),("24" string):("123" string),("25" string):("123" string),("26" string):("123" string),("27" string):("123" string),("28" string):("123" string),("29" string):("123" string),("30" string):("123" string),("31" string):("123" string),("32" string):("123" string),("33" string):("123" string),("34" string):("123" string),("35" string):("123" string),("36" string):("123" string),("37" string):("123" string),("38" string):("123" string),("39" string):("123" string),("40" string):("123" string),("41" string):("123" string),("42" string):("123" string),("43" string):("123" string),("44" string):("123" string),("45" string):("123" string),("46" string):("123" string),("47" string):("123" string),("48" string):("123" string),("49" string):("123" string),("50" string):("123" string),("51" string):("123" string),("52" string):("123" string),("53" string):("123" string),("54" string):("123" string),("55" string):("123" string),("56" string):("123" string),("57" string):("123" string),("58" string):("123" string),("59" string):("123" string),("60" string):("123" string),("61" string):("123" string),("62" string):("123" string),("63" string):("123" string),("64" string):("123" string),("65" string):("123" string),("66" string):("123" string),("67" string):("123" string),("68" string):("123" string),("69" string):("123" string),("70" string):("123" string),("71" string):("123" string),("72" string):("123" string),("73" string):("123" string),("74" string):("123" string),("75" string):("123" string),("76" string):("123" string),("77" string):("123" string),("78" string):("123" string),("79" string):("123" string),("80" string):("123" string),("81" string):("123" string),("82" string):("123" string),("83" string):("123" string),("84" string):("123" string),("85" string):("123" string),("86" string):("123" string),("87" string):("123" string),("88" string):("123" string),("89" string):("123" string),("90" string):("123" string),("91" string):("123" string),("92" string):("123" string),("93" string):("123" string),("94" string):("123" string),("95" string):("123" string),("96" string):("123" string),("97" string):("123" string),("98" string):("123" string),("99" string):("123" string),("100" string):("123" string),("101" string):("123" string),("102" string):("123" string),("103" string):("123" string),("104" string):("123" string),("105" string):("123" string),("106" string):("123" string),("107" string):("123" string),("108" string):("123" string),("109" string):("123" string),("110" string):("123" string),("111" string):("123" string),("112" string):("123" string),("113" string):("123" string),("114" string):("123" string),("115" string):("123" string),("116" string):("123" string),("117" string):("123" string),("118" string):("123" string),("119" string):("123" string),("120" string):("123" string),("121" string):("123" string),("122" string):("123" string),("123" string):("123" string),("124" string):("123" string),("125" string):("123" string),("126" string):("123" string),("127" string):("123" string),("128" string):("123" string),("129" string):("123" string),("130" string):("123" string),("131" string):("123" string),("132" string):("123" string),("133" string):("123" string),("134" string):("123" string),("135" string):("123" string),("136" string):("123" string),("137" string):("123" string),("138" string):("123" string),("139" string):("123" string),("140" string):("123" string),("141" string):("123" string),("142" string):("123" string),("143" string):("123" string),("144" string):("123" string),("145" string):("123" string),("146" string):("123" string),("147" string):("123" string),("148" string):("123" string),("149" string):("123" string),("150" string):("123" string),("151" string):("123" string),("152" string):("123" string),("153" string):("123" string),("154" string):("123" string),("155" string):("123" string),("156" string):("123" string),("157" string):("123" string),("158" string):("123" string),("159" string):("123" string),("160" string):("123" string),("161" string):("123" string),("162" string):("123" string),("163" string):("123" string),("164" string):("123" string),("165" string):("123" string),("166" string):("123" string),("167" string):("123" string),("168" string):("123" string),("169" string):("123" string),("170" string):("123" string),("171" string):("123" string),("172" string):("123" string),("173" string):("123" string),("174" string):("123" string),("175" string):("123" string),("176" string):("123" string),("177" string):("123" string),("178" string):("123" string),("179" string):("123" string),("180" string):("123" string),("181" string):("123" string),("182" string):("123" string),("183" string):("123" string),("184" string):("123" string),("185" string):("123" string),("186" string):("123" string),("187" string):("123" string),("188" string):("123" string),("189" string):("123" string),("190" string):("123" string),("191" string):("123" string),("192" string):("123" string),("193" string):("123" string),("194" string):("123" string),("195" string):("123" string),("196" string):("123" string),("197" string):("123" string),("198" string):("123" string),("199" string):("123" string),("200" string):("123" string),("201" string):("123" string),("202" string):("123" string),("203" string):("123" string),("204" string):("123" string),("205" string):("123" string),("206" string):("123" string),("207" string):("123" string),("208" string):("123" string),("209" string):("123" string),("210" string):("123" string),("211" string):("123" string),("212" string):("123" string),("213" string):("123" string),("214" string):("123" string),("215" string):("123" string),("216" string):("123" string),("217" string):("123" string),("218" string):("123" string),("219" string):("123" string),("220" string):("123" string),("221" string):("123" string),("222" string):("123" string),("223" string):("123" string),("224" string):("123" string),("225" string):("123" string),("226" string):("123" string),("227" string):("123" string),("228" string):("123" string),("229" string):("123" string),("230" string):("123" string),("231" string):("123" string),("232" string):("123" string),("233" string):("123" string),("234" string):("123" string),("235" string):("123" string),("236" string):("123" string),("237" string):("123" string),("238" string):("123" string),("239" string):("123" string),("240" string):("123" string),("241" string):("123" string),("242" string):("123" string),("243" string):("123" string),("244" string):("123" string),("245" string):("123" string),("246" string):("123" string),("247" string):("123" string),("248" string):("123" string),("249" string):("123" string),("250" string):("123" string),("251" string):("123" string),("252" string):("123" string),("253" string):("123" string),("254" string):("123" string),("255" string):("123" string),("256" string):("123" string),("257" string):("123" string),("258" string):("123" string),("259" string):("123" string),("260" string):("123" string),("261" string):("123" string),("262" string):("123" string),("263" string):("123" string),("264" string):("123" string),("265" string):("123" string),("266" string):("123" string),("267" string):("123" string),("268" string):("123" string),("269" string):("123" string),("270" string):("123" string),("271" string):("123" string),("272" string):("123" string),("273" string):("123" string),("274" string):("123" string),("275" string):("123" string),("276" string):("123" string),("277" string):("123" string),("278" string):("123" string),("279" string):("123" string),("280" string):("123" string),("281" string):("123" string),("282" string):("123" string),("283" string):("123" string),("284" string):("123" string),("285" string):("123" string),("286" string):("123" string),("287" string):("123" string),("288" string):("123" string),("289" string):("123" string),("290" string):("123" string),("291" string):("123" string),("292" string):("123" string),("293" string):("123" string),("294" string):("123" string),("295" string):("123" string),("296" string):("123" string),("297" string):("123" string),("298" string):("123" string),("299" string):("123" string),("300" string):("123" string),("301" string):("123" string),("302" string):("123" string),("303" string):("123" string),("304" string):("123" string),("305" string):("123" string),("306" string):("123" string),("307" string):("123" string),("308" string):("123" string),("309" string):("123" string),("310" string):("123" string),("311" string):("123" string),("312" string):("123" string),("313" string):("123" string),("314" string):("123" string),("315" string):("123" string),("316" string):("123" string),("317" string):("123" string),("318" string):("123" string),("319" string):("123" string),("320" string):("123" string),("321" string):("123" string),("322" string):("123" string),("323" string):("123" string),("324" string):("123" string),("325" string):("123" string),("326" string):("123" string),("327" string):("123" string),("328" string):("123" string),("329" string):("123" string),("330" string):("123" string),("331" string):("123" string),("332" string):("123" string),("333" string):("123" string),("334" string):("123" string),("335" string):("123" string),("336" string):("123" string),("337" string):("123" string),("338" string):("123" string),("339" string):("123" string),("340" string):("123" string),("341" string):("123" string),("342" string):("123" string),("343" string):("123" string),("344" string):("123" string),("345" string):("123" string),("346" string):("123" string),("347" string):("123" string),("348" string):("123" string),("349" string):("123" string),("350" string):("123" string),("351" string):("123" string),("352" string):("123" string),("353" string):("123" string),("354" string):("123" string),("355" string):("123" string),("356" string):("123" string),("357" string):("123" string),("358" string):("123" string),("359" string):("123" string),("360" string):("123" string),("361" string):("123" string),("362" string):("123" string),("363" string):("123" string),("364" string):("123" string),("365" string):("123" string),("366" string):("123" string),("367" string):("123" string),("368" string):("123" string),("369" string):("123" string),("370" string):("123" string),("371" string):("123" string),("372" string):("123" string),("373" string):("123" string),("374" string):("123" string),("375" string):("123" string),("376" string):("123" string),("377" string):("123" string),("378" string):("123" string),("379" string):("123" string),("380" string):("123" string),("381" string):("123" string),("382" string):("123" string),("383" string):("123" string),("384" string):("123" string),("385" string):("123" string),("386" string):("123" string),("387" string):("123" string),("388" string):("123" string),("389" string):("123" string),("390" string):("123" string),("391" string):("123" string),("392" string):("123" string),("393" string):("123" string),("394" string):("123" string),("395" string):("123" string),("396" string):("123" string),("397" string):("123" string),("398" string):("123" string),("399" string):("123" string),("400" string):("123" string),("401" string):("123" string),("402" string):("123" string),("403" string):("123" string),("404" string):("123" string),("405" string):("123" string),("406" string):("123" string),("407" string):("123" string),("408" string):("123" string),("409" string):("123" string),("410" string):("123" string),("411" string):("123" string),("412" string):("123" string),("413" string):("123" string),("414" string):("123" string),("415" string):("123" string),("416" string):("123" string),("417" string):("123" string),("418" string):("123" string),("419" string):("123" string),("420" string):("123" string),("421" string):("123" string),("422" string):("123" string),("423" string):("123" string),("424" string):("123" string),("425" string):("123" string),("426" string):("123" string),("427" string):("123" string),("428" string):("123" string),("429" string):("123" string),("430" string):("123" string),("431" string):("123" string),("432" string):("123" string),("433" string):("123" string),("434" string):("123" string),("435" string):("123" string),("436" string):("123" string),("437" string):("123" string),("438" string):("123" string),("439" string):("123" string),("440" string):("123" string),("441" string):("123" string),("442" string):("123" string),("443" string):("123" string),("444" string):("123" string),("445" string):("123" string),("446" string):("123" string),("447" string):("123" string),("448" string):("123" string),("449" string):("123" string),("450" string):("123" string),("451" string):("123" string),("452" string):("123" string),("453" string):("123" string),("454" string):("123" string),("455" string):("123" string),("456" string):("123" string),("457" string):("123" string),("458" string):("123" string),("459" string):("123" string),("460" string):("123" string),("461" string):("123" string),("462" string):("123" string),("463" string):("123" string),("464" string):("123" string),("465" string):("123" string),("466" string):("123" string),("467" string):("123" string),("468" string):("123" string),("469" string):("123" string),("470" string):("123" string),("471" string):("123" string),("472" string):("123" string),("473" string):("123" string),("474" string):("123" string),("475" string):("123" string),("476" string):("123" string),("477" string):("123" string),("478" string):("123" string),("479" string):("123" string),("480" string):("123" string),("481" string):("123" string),("482" string):("123" string),("483" string):("123" string),("484" string):("123" string),("485" string):("123" string),("486" string):("123" string),("487" string):("123" string),("488" string):("123" string),("489" string):("123" string),("490" string):("123" string),("491" string):("123" string),("492" string):("123" string),("493" string):("123" string),("494" string):("123" string),("495" string):("123" string),("496" string):("123" string),("497" string):("123" string),("498" string):("123" string),("499" string):("123" string),("500" string):("123" string),("501" string):("123" string),("502" string):("123" string),("503" string):("123" string),("504" string):("123" string),("505" string):("123" string),("506" string):("123" string),("507" string):("123" string),("508" string):("123" string),("509" string):("123" string),("510" string):("123" string),("511" string):("123" string),("512" string):("123" string),("513" string):("123" string),("514" string):("123" string),("515" string):("123" string),("516" string):("123" string),("517" string):("123" string),("518" string):("123" string),("519" string):("123" string),("520" string):("123" string),("521" string):("123" string),("522" string):("123" string),("523" string):("123" string),("524" string):("123" string),("525" string):("123" string),("526" string):("123" string),("527" string):("123" string),("528" string):("123" string),("529" string):("123" string),("530" string):("123" string),("531" string):("123" string),("532" string):("123" string),("533" string):("123" string),("534" string):("123" string),("535" string):("123" string),("536" string):("123" string),("537" string):("123" string),("538" string):("123" string),("539" string):("123" string),("540" string):("123" string),("541" string):("123" string),("542" string):("123" string),("543" string):("123" string),("544" string):("123" string),("545" string):("123" string),("546" string):("123" string),("547" string):("123" string),("548" string):("123" string),("549" string):("123" string),("550" string):("123" string),("551" string):("123" string),("552" string):("123" string),("553" string):("123" string),("554" string):("123" string),("555" string):("123" string),("556" string):("123" string),("557" string):("123" string),("558" string):("123" string),("559" string):("123" string),("560" string):("123" string),("561" string):("123" string),("562" string):("123" string),("563" string):("123" string),("564" string):("123" string),("565" string):("123" string),("566" string):("123" string),("567" string):("123" string),("568" string):("123" string),("569" string):("123" string),("570" string):("123" string),("571" string):("123" string),("572" string):("123" string),("573" string):("123" string),("574" string):("123" string),("575" string):("123" string),("576" string):("123" string),("577" string):("123" string),("578" string):("123" string),("579" string):("123" string),("580" string):("123" string),("581" string):("123" string),("582" string):("123" string),("583" string):("123" string),("584" string):("123" string),("585" string):("123" string),("586" string):("123" string),("587" string):("123" string),("588" string):("123" string),("589" string):("123" string),("590" string):("123" string),("591" string):("123" string),("592" string):("123" string),("593" string):("123" string),("594" string):("123" string),("595" string):("123" string),("596" string):("123" string),("597" string):("123" string),("598" string):("123" string),("599" string):("123" string),("600" string):("123" string),("601" string):("123" string),("602" string):("123" string),("603" string):("123" string),("604" string):("123" string),("605" string):("123" string),("606" string):("123" string),("607" string):("123" string),("608" string):("123" string),("609" string):("123" string),("610" string):("123" string),("611" string):("123" string),("612" string):("123" string),("613" string):("123" string),("614" string):("123" string),("615" string):("123" string),("616" string):("123" string),("617" string):("123" string),("618" string):("123" string),("619" string):("123" string),("620" string):("123" string),("621" string):("123" string),("622" string):("123" string),("623" string):("123" string),("624" string):("123" string),("625" string):("123" string),("626" string):("123" string),("627" string):("123" string),("628" string):("123" string),("629" string):("123" string),("630" string):("123" string),("631" string):("123" string),("632" string):("123" string),("633" string):("123" string),("634" string):("123" string),("635" string):("123" string),("636" string):("123" string),("637" string):("123" string),("638" string):("123" string),("639" string):("123" string),("640" string):("123" string),("641" string):("123" string),("642" string):("123" string),("643" string):("123" string),("644" string):("123" string),("645" string):("123" string),("646" string):("123" string),("647" string):("123" string),("648" string):("123" string),("649" string):("123" string),("650" string):("123" string),("651" string):("123" string),("652" string):("123" string),("653" string):("123" string),("654" string):("123" string),("655" string):("123" string),("656" string):("123" string),("657" string):("123" string),("658" string):("123" string),("659" string):("123" string),("660" string):("123" string),("661" string):("123" string),("662" string):("123" string),("663" string):("123" string),("664" string):("123" string),("665" string):("123" string),("666" string):("123" string),("667" string):("123" string),("668" string):("123" string),("669" string):("123" string),("670" string):("123" string),("671" string):("123" string),("672" string):("123" string),("673" string):("123" string),("674" string):("123" string),("675" string):("123" string),("676" string):("123" string),("677" string):("123" string),("678" string):("123" string),("679" string):("123" string),("680" string):("123" string),("681" string):("123" string),("682" string):("123" string),("683" string):("123" string),("684" string):("123" string),("685" string):("123" string),("686" string):("123" string),("687" string):("123" string),("688" string):("123" string),("689" string):("123" string),("690" string):("123" string),("691" string):("123" string),("692" string):("123" string),("693" string):("123" string),("694" string):("123" string),("695" string):("123" string),("696" string):("123" string),("697" string):("123" string),("698" string):("123" string),("699" string):("123" string),("700" string):("123" string),("701" string):("123" string),("702" string):("123" string),("703" string):("123" string),("704" string):("123" string),("705" string):("123" string),("706" string):("123" string),("707" string):("123" string),("708" string):("123" string),("709" string):("123" string),("710" string):("123" string),("711" string):("123" string),("712" string):("123" string),("713" string):("123" string),("714" string):("123" string),("715" string):("123" string),("716" string):("123" string),("717" string):("123" string),("718" string):("123" string),("719" string):("123" string),("720" string):("123" string),("721" string):("123" string),("722" string):("123" string),("723" string):("123" string),("724" string):("123" string),("725" string):("123" string),("726" string):("123" string),("727" string):("123" string),("728" string):("123" string),("729" string):("123" string),("730" string):("123" string),("731" string):("123" string),("732" string):("123" string),("733" string):("123" string),("734" string):("123" string),("735" string):("123" string),("736" string):("123" string),("737" string):("123" string),("738" string):("123" string),("739" string):("123" string),("740" string):("123" string),("741" string):("123" string),("742" string):("123" string),("743" string):("123" string),("744" string):("123" string),("745" string):("123" string),("746" string):("123" string),("747" string):("123" string),("748" string):("123" string),("749" string):("123" string),("750" string):("123" string),("751" string):("123" string),("752" string):("123" string),("753" string):("123" string),("754" string):("123" string),("755" string):("123" string),("756" string):("123" string),("757" string):("123" string),("758" string):("123" string),("759" string):("123" string),("760" string):("123" string),("761" string):("123" string),("762" string):("123" string),("763" string):("123" string),("764" string):("123" string),("765" string):("123" string),("766" string):("123" string),("767" string):("123" string),("768" string):("123" string),("769" string):("123" string),("770" string):("123" string),("771" string):("123" string),("772" string):("123" string),("773" string):("123" string),("774" string):("123" string),("775" string):("123" string),("776" string):("123" string),("777" string):("123" string),("778" string):("123" string),("779" string):("123" string),("780" string):("123" string),("781" string):("123" string),("782" string):("123" string),("783" string):("123" string),("784" string):("123" string),("785" string):("123" string),("786" string):("123" string),("787" string):("123" string),("788" string):("123" string),("789" string):("123" string),("790" string):("123" string),("791" string):("123" string),("792" string):("123" string),("793" string):("123" string),("794" string):("123" string),("795" string):("123" string),("796" string):("123" string),("797" string):("123" string),("798" string):("123" string),("799" string):("123" string),("800" string):("123" string),("801" string):("123" string),("802" string):("123" string),("803" string):("123" string),("804" string):("123" string),("805" string):("123" string),("806" string):("123" string),("807" string):("123" string),("808" string):("123" string),("809" string):("123" string),("810" string):("123" string),("811" string):("123" string),("812" string):("123" string),("813" string):("123" string),("814" string):("123" string),("815" string):("123" string),("816" string):("123" string),("817" string):("123" string),("818" string):("123" string),("819" string):("123" string),("820" string):("123" string),("821" string):("123" string),("822" string):("123" string),("823" string):("123" string),("824" string):("123" string),("825" string):("123" string),("826" string):("123" string),("827" string):("123" string),("828" string):("123" string),("829" string):("123" string),("830" string):("123" string),("831" string):("123" string),("832" string):("123" string),("833" string):("123" string),("834" string):("123" string),("835" string):("123" string),("836" string):("123" string),("837" string):("123" string),("838" string):("123" string),("839" string):("123" string),("840" string):("123" string),("841" string):("123" string),("842" string):("123" string),("843" string):("123" string),("844" string):("123" string),("845" string):("123" string),("846" string):("123" string),("847" string):("123" string),("848" string):("123" string),("849" string):("123" string),("850" string):("123" string),("851" string):("123" string),("852" string):("123" string),("853" string):("123" string),("854" string):("123" string),("855" string):("123" string),("856" string):("123" string),("857" string):("123" string),("858" string):("123" string),("859" string):("123" string),("860" string):("123" string),("861" string):("123" string),("862" string):("123" string),("863" string):("123" string),("864" string):("123" string),("865" string):("123" string),("866" string):("123" string),("867" string):("123" string),("868" string):("123" string),("869" string):("123" string),("870" string):("123" string),("871" string):("123" string),("872" string):("123" string),("873" string):("123" string),("874" string):("123" string),("875" string):("123" string),("876" string):("123" string),("877" string):("123" string),("878" string):("123" string),("879" string):("123" string),("880" string):("123" string),("881" string):("123" string),("882" string):("123" string),("883" string):("123" string),("884" string):("123" string),("885" string):("123" string),("886" string):("123" string),("887" string):("123" string),("888" string):("123" string),("889" string):("123" string),("890" string):("123" string),("891" string):("123" string),("892" string):("123" string),("893" string):("123" string),("894" string):("123" string),("895" string):("123" string),("896" string):("123" string),("897" string):("123" string),("898" string):("123" string),("899" string):("123" string),("900" string):("123" string),("901" string):("123" string),("902" string):("123" string),("903" string):("123" string),("904" string):("123" string),("905" string):("123" string),("906" string):("123" string),("907" string):("123" string),("908" string):("123" string),("909" string):("123" string),("910" string):("123" string),("911" string):("123" string),("912" string):("123" string),("913" string):("123" string),("914" string):("123" string),("915" string):("123" string),("916" string):("123" string),("917" string):("123" string),("918" string):("123" string),("919" string):("123" string),("920" string):("123" string),("921" string):("123" string),("922" string):("123" string),("923" string):("123" string),("924" string):("123" string),("925" string):("123" string),("926" string):("123" string),("927" string):("123" string),("928" string):("123" string),("929" string):("123" string),("930" string):("123" string),("931" string):("123" string),("932" string):("123" string),("933" string):("123" string),("934" string):("123" string),("935" string):("123" string),("936" string):("123" string),("937" string):("123" string),("938" string):("123" string),("939" string):("123" string),("940" string):("123" string),("941" string):("123" string),("942" string):("123" string),("943" string):("123" string),("944" string):("123" string),("945" string):("123" string),("946" string):("123" string),("947" string):("123" string),("948" string):("123" string),("949" string):("123" string),("950" string):("123" string),("951" string):("123" string),("952" string):("123" string),("953" string):("123" string),("954" string):("123" string),("955" string):("123" string),("956" string):("123" string),("957" string):("123" string),("958" string):("123" string),("959" string):("123" string),("960" string):("123" string),("961" string):("123" string),("962" string):("123" string),("963" string):("123" string),("964" string):("123" string),("965" string):("123" string),("966" string):("123" string),("967" string):("123" string),("968" string):("123" string),("969" string):("123" string),("970" string):("123" string),("971" string):("123" string),("972" string):("123" string),("973" string):("123" string),("974" string):("123" string),("975" string):("123" string),("976" string):("123" string),("977" string):("123" string),("978" string):("123" string),("979" string):("123" string),("980" string):("123" string),("981" string):("123" string),("982" string):("123" string),("983" string):("123" string),("984" string):("123" string),("985" string):("123" string),("986" string):("123" string),("987" string):("123" string),("988" string):("123" string),("989" string):("123" string),("990" string):("123" string),("991" string):("123" string),("992" string):("123" string),("993" string):("123" string),("994" string):("123" string),("995" string):("123" string),("996" string):("123" string),("997" string):("123" string),("998" string):("123" string),("999" string):("123" string)}
essentially, gno is good at storing pointers as separate "objects". so loading data from an avl tree is "expensive" computationally; as it has to traverse the tree and fetch many other different objects.
however, the alternative - the map - is not scalable, as when it is loaded, it is entirely put in memory, without partitioning. hence, the avl.Tree is suitable for storing data even of several gigabytes; while the map will eventually just make you run out gas the moment you try to use it.
for further reading, the berty team has posted a great issue reporting on the scalability of avl trees.