arriqaaq / art

An Adaptive Radix Tree (ART) implementation in Go

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

art's Issues

Fixing "slice bounds out of range" Runtime Error

When executing the provided below code, it results in the following runtime error:

panic: runtime error: slice bounds out of range [:19] with capacity 12

The code snippet causing this issue is as follows:

tree := NewTree()

file, err := os.Open("test/words.txt")
if err != nil {
    t.Error("Couldn't open words.txt")
}

defer file.Close()

reader := bufio.NewReader(file)
for {
    if line, err := reader.ReadBytes('\n'); err != nil {
        break
    } else {
        tree.Insert([]byte(line), []byte(line))
    }
}

actual := []string{}
leafFilter := func(n *Node) {
    if n.IsLeaf() {
        actual = append(actual, string(n.Key()))
    }
}
tree.Scan([]byte("ZyzzogetonOUTOFRANGE"), leafFilter)

if len(actual) != 0 {
    fmt.Println(len(actual))
    t.Error("Unexpected item found")
}

It appears that the error occurs when the key provided to tree.Scan is longer than the key of the current node, causing the isPrefixMatch function to return true when it should return false.

Optimize for memory usage

Right now full key is duplicated in leaf, so it's not "compact" tree as it expected. If i have keys with duplicates prefixes like user1 and user2 it will be stored like
prefix user
key user1
key user2

This lead to big overhead by memory usage.

But i expected from ART tree to store it like
prefix user
key 1
key 2

And generating full key from tree "on the fly" during search and so on

Do you have plans to optimize it?

Example output now:

func TestTreeDump(t *testing.T) {
	tree := NewTree()
	tree.Insert([]byte("10"), []byte("10"))
	tree.Insert([]byte("11"), []byte("11"))
	tree.Insert([]byte("20"), []byte("20"))
	tree.Insert([]byte("21"), []byte("21"))
	tree.Insert([]byte("22"), []byte("22"))

	t.Log(tree.String())
}

go test -run=Dump -test.v
=== RUN   TestTreeDump
    art_test.go:1063: 
        Root:
                Size:5
                Inner:&{{[0 0 0 0 0 0 0 0 0 0] 0 2} 0 [49 50 0 0] [0xc0000a1230 0xc0000a1270 <nil> <nil>]}
                Leaf:<nil>
        
        Type:Node4 Meta:{prefix:[0 0 0 0 0 0 0 0 0 0] prefixLen:0 size:2} Keys:[49 50 0 0]
                Type:Node4 Meta:{prefix:[49 0 0 0 0 0 0 0 0 0] prefixLen:0 size:2} Keys:[48 49 0 0]
                        Key:[49 48] Val:[49 48]
                        Key:[49 49] Val:[49 49]
                Type:Node4 Meta:{prefix:[0 0 0 0 0 0 0 0 0 0] prefixLen:0 size:3} Keys:[48 49 50 0]
                        Key:[50 48] Val:[50 48]
                        Key:[50 49] Val:[50 49]
                        Key:[50 50] Val:[50 50]
        Type:Node4 Meta:{prefix:[49 0 0 0 0 0 0 0 0 0] prefixLen:0 size:2} Keys:[48 49 0 0]
                Key:[49 48] Val:[49 48]
                Key:[49 49] Val:[49 49]
        Type:Node4 Meta:{prefix:[0 0 0 0 0 0 0 0 0 0] prefixLen:0 size:3} Keys:[48 49 50 0]
                Key:[50 48] Val:[50 48]
                Key:[50 49] Val:[50 49]
                Key:[50 50] Val:[50 50]
        
--- PASS: TestTreeDump (0.00s)

Stringify for tree here: #3