art

package module
v1.0.7 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 16, 2024 License: MIT Imports: 5 Imported by: 57

README

An Adaptive Radix Tree Implementation in Go

Coverage Status Go Report Card GoDoc

v1.x.x is a deprecated version. All development will be done in v2.

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
  • Support for keys with null bytes, any byte array could be a key

Usage

package main

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

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
	})

	// 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 godoc.org

Performance

plar/go-adaptive-radix-tree outperforms kellydunn/go-art by avoiding memory allocations during search operations. It also provides prefix based 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.

Documentation

Overview

Package art implements an Adapative Radix Tree(ART) in pure Go. Note that this implementation is not thread-safe but it could be really easy to implement.

The design of ART is based on "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" [1].

Usage 

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

Also the current implementation was inspired by [2] and [3]

[1] http://db.in.tum.de/~leis/papers/ART.pdf (Specification)

[2] https://github.com/armon/libart (C99 implementation)

[3] https://github.com/kellydunn/go-art (other Go implementation)

Index

Constants

View Source 
const (
	// Iterate only over leaf nodes.
	TraverseLeaf = 1

	// Iterate only over non-leaf nodes.
	TraverseNode = 2

	// Iterate over all nodes in the tree.
	TraverseAll = TraverseLeaf | TraverseNode
)

Traverse Options.

Variables

View Source 
var (
	ErrConcurrentModification = errors.New("concurrent modification has been detected")
	ErrNoMoreNodes            = errors.New("there are no more nodes in the tree")
)

These errors can be returned when iteration over the tree.

Functions

func DumpNode 

func DumpNode(root *nodeRef) string

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

func RefAddrFormatter added in v1.0.6 

func RefAddrFormatter(a *dumpNodeRef) string

RefAddrFormatter returns only the pointer address of the node (legacy).

func RefFullFormatter added in v1.0.6 

func RefFullFormatter(a *dumpNodeRef) string

RefFullFormatter returns the full address of the node, including the ID and the pointer.

func RefShortFormatter added in v1.0.6 

func RefShortFormatter(a *dumpNodeRef) string

RefShortFormatter returns only the ID of the node.

func TreeStringer added in v1.0.6 

func TreeStringer(t Tree, opts ...treeStringerOption) string

TreeStringer returns the string representation of the tree. The tree must be of type *art.tree.

func WithRefFormatter added in v1.0.6 

func WithRefFormatter(formatter refFormatter) treeStringerOption

WithRefFormatter sets the formatter for node references.

func WithStorageSize added in v1.0.6 

func WithStorageSize(size int) treeStringerOption

WithStorageSize sets the size of the storage for depth information.

Types

type Callback 

type Callback func(node Node) (cont bool)

Callback defines the function type used during tree traversal. It is invoked for each node visited in the traversal. If the callback function returns false, the iteration is terminated early.

type Iterator 

type Iterator interface {
	// HasNext returns true if there are more nodes to visit during the iteration.
	// Use this method to check for remaining nodes before calling Next.
	HasNext() bool

	// Next returns the next node in the iteration and advances the iterator's position.
	// If the iteration has no more nodes, it returns ErrNoMoreNodes error.
	// Ensure you call HasNext before invoking Next to avoid errors.
	// If the tree has been structurally modified since the iterator was created,
	// it returns an ErrConcurrentModification error.
	Next() (Node, error)
}

Iterator provides a mechanism to traverse nodes in key order within the tree.

type Key 

type Key []byte

Key represents the type used for keys in the Adaptive Radix Tree. It can consist of any byte sequence, including Unicode characters and null bytes.

type Kind 

type Kind int

Kind is a node type. 

const (
	Leaf    Kind = 0
	Node4   Kind = 1
	Node16  Kind = 2
	Node48  Kind = 3
	Node256 Kind = 4
)

Node types.

func (Kind) String 

func (k Kind) String() string

String returns string representation of the Kind value.

type Node 

type Node interface {
	// Kind returns the type of the node, distinguishing between leaf and internal nodes.
	Kind() Kind

	// Key returns the key associated with a leaf node.
	// This method should only be called on leaf nodes.
	// Calling this on a non-leaf node will return nil.
	Key() Key

	// Value returns the value stored in a leaf node.
	// This method should only be called on leaf nodes.
	// Calling this on a non-leaf node will return nil.
	Value() Value
}

Node represents a node within the Adaptive Radix Tree.

type Tree 

type Tree interface {
	// Insert adds a new key-value pair into the tree.
	// If the key already exists in the tree, it updates its value and returns the old value along with true.
	// If the key is new, it returns nil and false.
	Insert(key Key, value Value) (oldValue Value, updated bool)

	// Delete removes the specified key and its associated value from the tree.
	// If the key is found and deleted, it returns the removed value and true.
	// If the key does not exist, it returns nil and false.
	Delete(key Key) (value Value, deleted bool)

	// Search retrieves the value associated with the specified key in the tree.
	// If the key exists, it returns the value and true.
	// If the key does not exist, it returns nil and false.
	Search(key Key) (value Value, found bool)

	// ForEach iterates over all the nodes in the tree, invoking a provided callback function for each node.
	// By default, it processes leaf nodes in ascending order.
	// The iteration can be customized using options:
	// - Pass TraverseLeaf to iterate only over leaf nodes.
	// - Pass TraverseNode to iterate only over non-leaf nodes.
	// - Pass TraverseAll to iterate over all nodes in the tree.
	// The iteration stops if the callback function returns false, allowing for early termination.
	ForEach(callback Callback, options ...int)

	// ForEachPrefix iterates over all leaf nodes whose keys start with the specified keyPrefix,
	// invoking a provided callback function for each matching node.
	// By default, the iteration processes nodes in ascending order.
	// Iteration stops if the callback function returns false, allowing for early termination.
	ForEachPrefix(keyPrefix Key, callback Callback)

	// Iterator returns an iterator for traversing leaf nodes in the tree.
	// By default, the iteration occurs in ascending order.
	Iterator(options ...int) Iterator

	// Minimum retrieves the leaf node with the smallest key in the tree.
	// If such a leaf is found, it returns its value and true.
	// If the tree is empty, it returns nil and false.
	Minimum() (Value, bool)

	// Maximum retrieves the leaf node with the largest key in the tree.
	// If such a leaf is found, it returns its value and true.
	// If the tree is empty, it returns nil and false.
	Maximum() (Value, bool)

	// Size returns the number of key-value pairs stored in the tree.
	Size() int
}

Tree is an Adaptive Radix Tree interface.

func New 

func New() Tree

New creates a new adaptive radix tree.

type Value 

type Value interface{}

Value is an interface representing the value type stored in the tree. Any type of data can be stored as a Value.

Source Files

View all Source files

Directories

Path Synopsis
gtree

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.