art

README

libart

This library provides a C99 implementation of the Adaptive Radix Tree or ART. The ART operates similar to a traditional radix tree but avoids the wasted space of internal nodes by changing the node size. It makes use of 4 node sizes (4, 16, 48, 256), and can guarantee that the overhead is no more than 52 bytes per key, though in practice it is much lower.

As a radix tree, it provides the following:

• O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
• Minimum / Maximum value lookups
• Prefix compression
• Ordered iteration
• Prefix based iteration

References

Related works:

• The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases

Documentation

Index

• type Leaf
  • func (l *Leaf) Data() memory.Pointer
  • func (l *Leaf) Key() memory.FatPointer
• type Tree
  • func New() (*Tree, int)
  • func (r *Tree) Delete(key memory.Pointer, size int) memory.Pointer
  • func (r *Tree) DeleteBytes(key memory.Bytes) memory.Pointer
  • func (r *Tree) Find(key memory.Pointer, size int) memory.Pointer
  • func (r *Tree) FindBytes(key memory.Bytes) memory.Pointer
  • func (r *Tree) Free()
  • func (r *Tree) Insert(key memory.Pointer, size int, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertBytes(key memory.Bytes, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertNoReplace(key memory.Pointer, size int, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertNoReplaceBytes(key memory.Bytes, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertNoReplaceSlice(key []byte, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertNoReplaceString(key string, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertSlice(key []byte, value memory.Pointer) memory.Pointer
  • func (r *Tree) InsertString(key string, value memory.Pointer) memory.Pointer
  • func (r *Tree) Maximum() *Leaf
  • func (r *Tree) Minimum() *Leaf
  • func (t *Tree) Size() int

Types

type Leaf

type Leaf C.art_leaf

func (*Leaf) Data

func (l *Leaf) Data() memory.Pointer

func (*Leaf) Key

func (l *Leaf) Key() memory.FatPointer

type Tree

type Tree C.art_tree

func New

func New() (*Tree, int)

func (*Tree) Delete

func (r *Tree) Delete(key memory.Pointer, size int) memory.Pointer

func (*Tree) DeleteBytes

func (r *Tree) DeleteBytes(key memory.Bytes) memory.Pointer

func (*Tree) Find

func (r *Tree) Find(key memory.Pointer, size int) memory.Pointer

func (*Tree) FindBytes

func (r *Tree) FindBytes(key memory.Bytes) memory.Pointer

func (*Tree) Free

func (r *Tree) Free()

func (*Tree) Insert

func (r *Tree) Insert(key memory.Pointer, size int, value memory.Pointer) memory.Pointer

func (*Tree) InsertBytes

func (r *Tree) InsertBytes(key memory.Bytes, value memory.Pointer) memory.Pointer

func (*Tree) InsertNoReplace

func (r *Tree) InsertNoReplace(key memory.Pointer, size int, value memory.Pointer) memory.Pointer

func (*Tree) InsertNoReplaceBytes

func (r *Tree) InsertNoReplaceBytes(key memory.Bytes, value memory.Pointer) memory.Pointer

func (*Tree) InsertNoReplaceSlice

func (r *Tree) InsertNoReplaceSlice(key []byte, value memory.Pointer) memory.Pointer

func (*Tree) InsertNoReplaceString

func (r *Tree) InsertNoReplaceString(key string, value memory.Pointer) memory.Pointer

func (*Tree) InsertSlice

func (r *Tree) InsertSlice(key []byte, value memory.Pointer) memory.Pointer

func (*Tree) InsertString

func (r *Tree) InsertString(key string, value memory.Pointer) memory.Pointer

func (*Tree) Maximum

func (r *Tree) Maximum() *Leaf

Maximum Returns the maximum valued leaf @return The maximum leaf or NULL

func (*Tree) Minimum

func (r *Tree) Minimum() *Leaf

func (*Tree) Size

func (t *Tree) Size() int