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]

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.