An Adaptive Radix Tree Implementation in Go ====

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

Features:

• Lookup performance surpasses highly tuned alternatives
• Support for highly 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

> Keys are sorted lexicographically based on their byte values.

• O(k) search/insert/delete operations, where k is the length of the key
• Minimum / Maximum value lookups
• Ordered iteration
• Prefix-based iteration
• Reverse iteration support
• Support for keys with null bytes, any byte array could be a key

Usage

The Go playground

package main
import ( 	"fmt" 	art "github.com/plar/go-adaptive-radix-tree/v2" )
func main() { 	// Initialize a new Adaptive Radix Tree 	tree := art.New()
// Insert key-value pairs into the tree 	tree.Insert(art.Key("apple"), "A sweet red fruit") 	tree.Insert(art.Key("banana"), "A long yellow fruit") 	tree.Insert(art.Key("cherry"), "A small red fruit") 	tree.Insert(art.Key("date"), "A sweet brown fruit")
// Search for a value by key 	if value, found := tree.Search(art.Key("banana")); found { 		fmt.Println("Found:", value) 	} else { 		fmt.Println("Key not found") 	}
// Iterate over the tree in ascending order 	fmt.Println("\nAscending order iteration:") 	tree.ForEach(func(node art.Node) bool { 		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value()) 		return true 	})
// Iterate over the tree in descending order using reverse traversal 	fmt.Println("\nDescending order iteration:") 	tree.ForEach(func(node art.Node) bool { 		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value()) 		return true 	}, art.TraverseReverse)
// Iterate over keys with a specific prefix 	fmt.Println("\nIteration with prefix 'c':") 	tree.ForEachPrefix(art.Key("c"), func(node art.Node) bool { 		fmt.Printf("Key: %s, Value: %s\n", node.Key(), node.Value()) 		return true 	}) }
// Expected Output: // Found: A long yellow fruit // // Ascending order iteration: // Key: apple, Value: A sweet red fruit // Key: banana, Value: A long yellow fruit // Key: cherry, Value: A small red fruit // Key: date, Value: A sweet brown fruit // // Descending order iteration: // Key: date, Value: A sweet brown fruit // Key: cherry, Value: A small red fruit // Key: banana, Value: A long yellow fruit // Key: apple, Value: A sweet red fruit // // Iteration with prefix 'c': // Key: cherry, Value: A small red fruit

Documentation

Check out the documentation on pkg.go.dev/github.com/plar/go-adaptive-radix-tree/v2.

Migration from v1 to v2

• update import statement

from art "github.com/plar/go-adaptive-radix-tree"
  to art "github.com/plar/go-adaptive-radix-tree/v2"

• update go module dependency

$ go get github.com/plar/go-adaptive-radix-tree/v2
$ go mod tidy

If you had implemented your own version of the Tree interface, then you need to update the following method to support options. These are the only changes in the interface.

ForEachPrefix(keyPrefix Key, callback Callback, options ...int)

Performance

plar/go-adaptive-radix-tree outperforms kellydunn/go-art by avoiding memory allocations during search operations. It also provides prefix based and reverse iteration over the tree.

Benchmarks were performed on datasets extracted from different projects:

• The "Words" dataset contains a list of 235,886 english words. [2]
• The "UUIDs" dataset contains 100,000 uuids. [2]
• The "HSK Words" dataset contains 4,995 words. [4]

|go-adaptive-radix-tree| # | Average time |Bytes per operation|Allocs per operation | |:-------------------------|---:|------------------:|------------------:|--------------------:| | Tree Insert Words | 9 | 117,888,698 ns/op | 37,942,744 B/op | 1,214,541 allocs/op | | Tree Search Words | 26 | 44,555,608 ns/op | 0 B/op | 0 allocs/op | | Tree Insert UUIDs | 18 | 59,360,135 ns/op | 18,375,723 B/op | 485,057 allocs/op | | Tree Search UUIDs | 54 | 21,265,931 ns/op | 0 B/op | 0 allocs/op | |go-art | | | | | | Tree Insert Words | 5 | 272,047,975 ns/op | 81,628,987 B/op | 2,547,316 allocs/op | | Tree Search Words | 10 | 129,011,177 ns/op | 13,272,278 B/op | 1,659,033 allocs/op | | Tree Insert UUIDs | 10 | 140,309,246 ns/op | 33,678,160 B/op | 874,561 allocs/op | | Tree Search UUIDs | 20 | 82,120,943 ns/op | 3,883,131 B/op | 485,391 allocs/op |

To see more benchmarks just run

$ ./make qa/benchmarks

References

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

[2] C99 implementation of the Adaptive Radix Tree

[3] Another Adaptive Radix Tree implementation in Go

[4] HSK Words. HSK(Hanyu Shuiping Kaoshi) - Standardized test of Standard Mandarin Chinese proficiency.