art

README

art

A simple implementation of Adaptive Radix Tree (ART) in Go. Created for use in personal projects like FlashDB.

About

• An adaptive radix tree (trie) is useful for efficient indexing in main memory.
• Its lookup performance surpasses highly tuned, read-only search trees, while supporting very efficient insertions and deletions as well.
• Space efficient and solves the problem of excessive worst-case space consumption, which plagues most radix trees, by adaptively choosing compact and efficient data structures for internal nodes.
• Maintains the data in sorted order, which enables additional operations like range scan and prefix lookup.

Usage

package main

import (
	"fmt"

	"github.com/arriqaaq/art"
)

func main() {
	tree := art.NewTree()

	// Insert
	tree.Insert([]byte("hello"), "world")
	value := tree.Search([]byte("hello"))
	fmt.Println("value=", value)

	// Delete
	tree.Insert([]byte("wonderful"), "life")
	tree.Insert([]byte("foo"), "bar")
	deleted := tree.Delete([]byte("foo"))
	fmt.Println("deleted=", deleted)

	// Search
	value = tree.Search([]byte("hello"))
	fmt.Println("value=", value)

	// Traverse (with callback function)
	tree.Each(func(node *art.Node) {
		if node.IsLeaf() {
			fmt.Println("value=", node.Value())
		}
	})

	// Iterator
	for it := tree.Iterator(); it.HasNext(); {
		value := it.Next()
		if value.IsLeaf() {
			fmt.Println("value=", value.Value())
		}
	}

	// Prefix Scan
	tree.Insert([]byte("api"), "bar")
	tree.Insert([]byte("api.com"), "bar")
	tree.Insert([]byte("api.com.xyz"), "bar")
	leafFilter := func(n *art.Node) {
		if n.IsLeaf() {
			fmt.Println("value=", string(n.Key()))
		}
	}
	tree.Scan([]byte("api"), leafFilter)
}

Benchmarks

Benchmarks are run by inserting a dictionary of 235886 words into each tree.

goos: darwin
goarch: amd64
pkg: github.com/arriqaaq/art
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz

// ART tree
BenchmarkWordsArtTreeInsert
BenchmarkWordsArtTreeInsert-16   14	  79622476 ns/op  46379858 B/op	 1604123 allocs/op
BenchmarkWordsArtTreeSearch
BenchmarkWordsArtTreeSearch-16   43	  28123512 ns/op         0 B/op	       0 allocs/op
BenchmarkUUIDsArtTreeInsert
BenchmarkUUIDsArtTreeInsert-16   20	  56691374 ns/op  20404504 B/op	  602400 allocs/op
BenchmarkUUIDsArtTreeSearch
BenchmarkUUIDsArtTreeSearch-16   34	  32183846 ns/op         0 B/op	       0 allocs/op

// Radix tree
BenchmarkWordsRadixInsert
BenchmarkWordsRadixInsert-16     12	  96886770 ns/op  50057340 B/op	 1856741 allocs/op
BenchmarkWordsRadixSearch
BenchmarkWordsRadixSearch-16     33	  40109553 ns/op         0 B/op	       0 allocs/op

// Skiplist
BenchmarkWordsSkiplistInsert
BenchmarkWordsSkiplistInsert-16   4	 271771239 ns/op  32366958 B/op	 1494019 allocs/op
BenchmarkWordsSkiplistSearch
BenchmarkWordsSkiplistSearch-16   8	 135836216 ns/op         0 B/op	       0 allocs/op

References

• The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases (Specification)
• Kelly Dunn implementation of the Adaptive Radix Tree
• Beating hash tables with trees? The ART-ful radix trie
• Pavel Larkin implementation of ART

Documentation

Index

• Constants
• type Callback
• type Iterator
• type Node
  • func (n *Node) IsLeaf() bool
  • func (n *Node) Key() []byte
  • func (n *Node) Type() int
  • func (n *Node) Value() interface{}
• type Tree
  • func NewTree() *Tree
  • func (t *Tree) Delete(key []byte) bool
  • func (t *Tree) Each(callback Callback)
  • func (t *Tree) Insert(key []byte, value interface{}) bool
  • func (t *Tree) Iterator() Iterator
  • func (t *Tree) Scan(key []byte, callback Callback)
  • func (t *Tree) Search(key []byte) interface{}
  • func (t *Tree) Size() uint64

Constants

const (
	Node4 = iota
	Node16
	Node48
	Node256
	Leaf

	Node4Min = 2
	Node4Max = 4

	Node16Min = Node4Max + 1
	Node16Max = 16

	Node48Min = Node16Max + 1
	Node48Max = 48

	Node256Min = Node48Max + 1
	Node256Max = 256

	MaxPrefixLen = 10
)

Types

type Callback

type Callback func(node *Node)

type Iterator

type Iterator interface {
	HasNext() bool
	Next() *Node
}

type Node

type Node struct {
	// contains filtered or unexported fields
}

func (*Node) IsLeaf

func (n *Node) IsLeaf() bool

func (*Node) Key

func (n *Node) Key() []byte

func (*Node) Type

func (n *Node) Type() int

func (*Node) Value

func (n *Node) Value() interface{}

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

func NewTree

func NewTree() *Tree

func (*Tree) Delete

func (t *Tree) Delete(key []byte) bool

func (*Tree) Each

func (t *Tree) Each(callback Callback)

func (*Tree) Insert

func (t *Tree) Insert(key []byte, value interface{}) bool

func (*Tree) Iterator

func (t *Tree) Iterator() Iterator

Iterator pattern

func (*Tree) Scan

func (t *Tree) Scan(key []byte, callback Callback)

Prefix search

func (*Tree) Search

func (t *Tree) Search(key []byte) interface{}

func (*Tree) Size

func (t *Tree) Size() uint64