art

README

Optimistic Adaptive Radix Tree

This is a Go implementation of ART.

What is ART

As mentioned in the origin paper, ART is a powerful indexing data structure.

Its lookup performance surpasses highly tuned, read-only search trees, while supporting very efficient insertions and deletions as well. At the same time, ART is very 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. Even though ART’s performance is comparable to hash tables, it maintains the data in sorted order, which enables additional operations like range scan and prefix lookup.

Concurrent Operation

The main difference compared to other implementations (like plar/go-adaptive-radix-tree) is that this implementation support concurrent Read/Write operation.

Using the method described in V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016.

Usage

package main

import (
	"fmt"
	"github.com/bobotu/opt-art"
)

func main() {
	art := art.NewART()
	art.Put([]byte("hello"), "world")
	fmt.Println(art.Get([]byte("hello")))
	art.Delete([]byte("hello"))
}

You can check out godoc.org for more detailed documentation.

Performance

Although this is only a rough implementation, there are still some good results on the benchmarks.
Benchmarks performed on the same datasets as plar/go-adaptive-radix-tree

• Words dataset contains list of 235,886 english words.
• UUIDs dataset contains 100,000 uuids.

opt-art	#	Average time	Bytes per operation	Allocs per operation
BenchmarkPutWords-8	20	69056403 ns/op	43403024 B/op	943544 allocs/op
BenchmarkPutUUID-8	50	27332784 ns/op	18400000 B/op	400000 allocs/op
BenchmarkGetWords-8	20	88016532 ns/op	0 B/op	0 allocs/op
BenchmarkGetUUID-8	100	22887744 ns/op	0 B/op	0 allocs/op

Documentation

Overview

Package art implements the Adaptive Radix Tree, and use Optimistic Locking method to achieve thread safe concurrent operation. The ART is described in "V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: ARTful indexing for main-memory databases. In ICDE, 2013". The Optimistic Syncing is described in "V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016".

Index

• type ART
  • func NewART() *ART
  • func (t *ART) Delete(key []byte)
  • func (t *ART) Get(key []byte) (interface{}, bool)
  • func (t *ART) Max() ([]byte, interface{})
  • func (t *ART) Min() ([]byte, interface{})
  • func (t *ART) Prefix(prefix []byte, f OpFunc)
  • func (t *ART) Put(key []byte, value interface{})
  • func (t *ART) Range(begin, end []byte, includeBegin, includeEnd bool, f OpFunc)
  • func (t *ART) RangeTop(k int, begin, end []byte, includeBegin, includeEnd bool, f OpFunc)
• type OpFunc

Types

type ART

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

ART implements the Adaptive Radix Tree with Optimistic Locking. It looks like a KV data structure, which use byte slice as key. It support thread safe concurrent update and query.

func NewART

func NewART() *ART

NewART create a new empty ART.

func (*ART) Delete

func (t *ART) Delete(key []byte)

Delete delete the given key and it's value from this tree. This operation is thread safe.

func (*ART) Get

func (t *ART) Get(key []byte) (interface{}, bool)

Get lookup this tree, and return the value associate with the given key. This operation is thread safe.

func (*ART) Max

func (t *ART) Max() ([]byte, interface{})

Max return the maximal key and it's value in this tree. This operation is thread safe.

func (*ART) Min

func (t *ART) Min() ([]byte, interface{})

Min return the minimal key and it's value in this tree. This operation is thread safe.

func (*ART) Prefix

func (t *ART) Prefix(prefix []byte, f OpFunc)

Prefix find all key have the given prefix in this tree. This operation is thread safe.

func (*ART) Put

func (t *ART) Put(key []byte, value interface{})

Put put the given key and value into this tree, or replace exist key's value. This operation is thread safe.

func (*ART) Range

func (t *ART) Range(begin, end []byte, includeBegin, includeEnd bool, f OpFunc)

Range iterate the key in the given range. This operation is thread safe.

func (*ART) RangeTop

func (t *ART) RangeTop(k int, begin, end []byte, includeBegin, includeEnd bool, f OpFunc)

RangeTop is same as Range, but it will terminate after find k keys. This operation is thread safe.

type OpFunc

type OpFunc func(key []byte, value interface{}) (end bool)

OpFunc is ART query callback function. If OpFunc return true the current query will terminate immediately.