art

README

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
• 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"
    "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

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
• Variables
• func DumpNode(root *nodeRef) string
• func RefAddrFormatter(a *dumpNodeRef) string
• func RefFullFormatter(a *dumpNodeRef) string
• func RefShortFormatter(a *dumpNodeRef) string
• func TreeStringer(t Tree, opts ...treeStringerOption) string
• func WithRefFormatter(formatter refFormatter) treeStringerOption
• func WithStorageSize(size int) treeStringerOption
• type Callback
• type Iterator
• type Key
• type Kind
  • func (k Kind) String() string
• type Node
• type Tree
  • func New() Tree
• type Value

Constants

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

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

func RefAddrFormatter(a *dumpNodeRef) string

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

func RefFullFormatter

func RefFullFormatter(a *dumpNodeRef) string

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

func RefShortFormatter

func RefShortFormatter(a *dumpNodeRef) string

RefShortFormatter returns only the ID of the node.

func TreeStringer

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

func WithRefFormatter(formatter refFormatter) treeStringerOption

WithRefFormatter sets the formatter for node references.

func WithStorageSize

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 function type for tree traversal. if the callback function returns false then iteration is terminated.

type Iterator

type Iterator interface {
	// Returns true if the iteration has more nodes when traversing the tree.
	HasNext() bool

	// Returns the next element in the tree and advances the iterator position.
	// Returns ErrNoMoreNodes error if there are no more nodes in the tree.
	// Check if there is a next node with HasNext method.
	// Returns ErrConcurrentModification error if the tree has been structurally
	// modified after the iterator was created.
	Next() (Node, error)
}

Iterator iterates over nodes in key order.

type Key

type Key []byte

Key Type. Key can be a set of any characters include unicode chars with 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 node type.
	Kind() Kind

	// Key returns leaf's key.
	// This method is only valid for leaf node,
	// if its called on non-leaf node then returns nil.
	Key() Key

	// Value returns leaf's value.
	// This method is only valid for leaf node,
	// if its called on non-leaf node then returns nil.
	Value() Value
}

Node interface.

type Tree

type Tree interface {
	// Insert a new key into the tree.
	// If the key already in the tree then return oldValue, true and nil, false otherwise.
	Insert(key Key, value Value) (oldValue Value, updated bool)

	// Delete removes a key from the tree and key's value, true is returned.
	// If the key does not exists then nothing is done and nil, false is returned.
	Delete(key Key) (value Value, deleted bool)

	// Search returns the value of the specific key.
	// If the key exists then return value, true and nil, false otherwise.
	Search(key Key) (value Value, found bool)

	// ForEach executes a provided callback once per leaf node by default.
	// The callback iteration is terminated if the callback function returns false.
	// Pass TraverseXXX as an options to execute a provided callback
	// once per NodeXXX type in the tree.
	ForEach(callback Callback, options ...int)

	// ForEachPrefix executes a provided callback once per leaf node that
	// leaf's key starts with the given keyPrefix.
	// The callback iteration is terminated if the callback function returns false.
	ForEachPrefix(keyPrefix Key, callback Callback)

	// Iterator returns an iterator for preorder traversal over leaf nodes by default.
	// Pass TraverseXXX as an options to return an iterator for preorder traversal over all NodeXXX types.
	Iterator(options ...int) Iterator

	// Minimum returns the minimum valued leaf, true if leaf is found and nil, false otherwise.
	Minimum() (Value, bool)

	// Maximum returns the maximum valued leaf, true if leaf is found and nil, false otherwise.
	Maximum() (Value, bool)

	// Returns size of 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 type.