Categorygithub.com/plar/go-adaptive-radix-tree/v2
modulepackage
2.0.3
Repository: https://github.com/plar/go-adaptive-radix-tree.git
Documentation: pkg.go.dev

# README

An Adaptive Radix Tree Implementation in Go

Coverage Status Go Report Card GoDoc

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 timeBytes per operationAllocs per operation
Tree Insert Words9117,888,698 ns/op37,942,744 B/op1,214,541 allocs/op
Tree Search Words2644,555,608 ns/op0 B/op0 allocs/op
Tree Insert UUIDs1859,360,135 ns/op18,375,723 B/op485,057 allocs/op
Tree Search UUIDs5421,265,931 ns/op0 B/op0 allocs/op
go-art
Tree Insert Words5272,047,975 ns/op81,628,987 B/op2,547,316 allocs/op
Tree Search Words10129,011,177 ns/op13,272,278 B/op1,659,033 allocs/op
Tree Insert UUIDs10140,309,246 ns/op33,678,160 B/op874,561 allocs/op
Tree Search UUIDs2082,120,943 ns/op3,883,131 B/op485,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.

# Packages

No description provided by the author

# Functions

DumpNode returns Tree in the human readable format: --8<-- // main.go package main import ( "fmt" art "github.com/plar/go-adaptive-radix-tree" ) func main() { tree := art.New() terms := []string{"A", "a", "aa"} for _, term := range terms { tree.Insert(art.Key(term), term) } fmt.Println(tree) } --8<-- $ go run main.go ─── Node4 (0xc00011c2d0) prefix(0): [··········] [0 0 0 0 0 0 0 0 0 0] keys: [Aa··] [65 97 · ·] children(2): [0xc00011c2a0 0xc00011c300 - -] <-> ├── Leaf (0xc00011c2a0) │ key(1): [A] [65] │ val: A │ ├── Node4 (0xc00011c300) │ prefix(0): [··········] [0 0 0 0 0 0 0 0 0 0] │ keys: [a···] [97 · · ·] │ children(1): [0xc00011c2f0 - - -] <0xc00011c2c0> │ ├── Leaf (0xc00011c2f0) │ │ key(2): [aa] [97 97] │ │ val: aa │ │ │ ├── nil │ ├── nil │ ├── nil │ └── Leaf (0xc00011c2c0) │ key(1): [a] [97] │ val: a │ │ ├── nil ├── nil └── nil */.
New creates a new adaptive radix tree.
RefAddrFormatter returns only the pointer address of the node (legacy).
RefFullFormatter returns the full address of the node, including the ID and the pointer.
RefShortFormatter returns only the ID of the node.
TreeStringer returns the string representation of the tree.
WithRefFormatter sets the formatter for node references.
WithStorageSize sets the size of the storage for depth information.

# Constants

Node types.
Node types.
Node types.
Node types.
Node types.
Iterate over all nodes in the tree.
Iterate only over leaf nodes.
Iterate only over non-leaf nodes.
Iterate in reverse order.

# Variables

These errors can be returned when iteration over the tree.
These errors can be returned when iteration over the tree.

# Interfaces

Iterator provides a mechanism to traverse nodes in key order within the tree.
Node represents a node within the Adaptive Radix Tree.
Tree is an Adaptive Radix Tree interface.
Value is an interface representing the value type stored in the tree.

# Type aliases

Callback defines the function type used during tree traversal.
Key represents the type used for keys in the Adaptive Radix Tree.
Kind is a node type.