This library provides a Go implementation of the Adaptive Radix Tree (ART).

It presents the following:

• Lookup performance surpasses highly tuned
• Supporting very efficient insertions and deletions
• Space efficient
• Performance is comparable to hash tables
• Maintains the data in sorted order, which enables additional operations like range scan and prefix lookup
• O(k) search/insert/delete operations, where is k is the length of the key
• Minimum / Maximum value lookups
• Ordered iteration
• Prefix based iteration

package main

import (
    "fmt"
    "github.com/plar/go-adaptive-radix-tree"
)

func main() {

    tree := art.New()

    tree.Insert(art.Key("Hi, I'm Key"), "Nice to meet you, I'm Value")
    value, found := tree.Search(art.Key("Hi, I'm Key"))
    if found {
        fmt.Printf("Search value=%v\n", value)
    }

    tree.ForEach(func(node art.Node) bool {
        fmt.Printf("Callback value=%v\n", node.Value())
        return true
    })

    for it := tree.Iterator(); it.HasNext(); {
        value, _ := it.Next()
        fmt.Printf("Iterator value=%v\n", value.Value())
    }
}

// Output:
// Search value=Nice to meet you, I'm Value
// Callback value=Nice to meet you, I'm Value
// Iterator value=Nice to meet you, I'm Value

Check out the documentation on godoc.org

The go-adaptive-radix-tree library overperforms go-art library. The go-adaptive-radix-tree doesn't allocate any memory during search operations. It also provides prefix based iteration over the tree.

Benchmarks were performed on datasets extracted from the [2] project:

• Words dataset contains list of 235,886 english words.
• UUIDs dataset contains 100,000 uuids.

[1] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases (Specification)

[2] C99 implementation of the Adaptive Radix Tree

[3] Other Adaptive Radix Tree implementation in Go