radixtree

README

radixtree

Package radixtree implements an Adaptive Radix Tree, aka compressed trie or prefix tree. It is adaptive in the sense that nodes are not constant size, having as few or many children as needed to branch to all subtrees.

This package implements a radix-256 tree where each key symbol (radix) is a byte, allowing up to 256 possible branches to traverse to the next node.

The implementation is optimized for Get performance and allocates 0 bytes of heap memory per Get; therefore no garbage to collect. Once the radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the radixtree. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application.

Package radixtree implements an Adaptive Radix Tree, aka compressed trie or compact prefix tree. This data structure is useful to quickly lookup data by key, find values whose keys have a common prefix, or find values whose keys are a prefix (i.e. found along the way) of a search key.

The implementation is optimized for Get performance and allocate 0 bytes of heap memory for any read operation (Get, Walk, WalkPath, etc.); therefore no garbage to collect. Once a radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the data structure. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application.

This radix tree offers the following features:

• Efficient: Operations are O(k). Zero memory allocation for all read operations.
• Compact: When values are stored using keys that have a common prefix, the common part of the key is only stored once. Consider this when keys are similar to a timestamp, OID, filepath, geohash, network address, etc. Only the minimum number of nodes are kept to branch at the points where keys differ.
• Adaptive: This radix tree is adaptive in the sense that nodes are not constant size, having only as many children that are needed. This is radix-256 tree where each key symbol (radix) is a byte, allowing from zero up to 256 branches to traverse to the next node.
• Iterator: An Iterator returns each key-value pair in the tree. A Stepper type of iterator traverses the tree one specified byte at a time. It is useful for incremental lookup, and can be copied in order to branch a search and iterate the copies concurrently.
• Able to store nil values: Get differentiates between nil value and missing value.
• Ordered iteration: Walking and iterating the tree is done in lexical order, making the output deterministic.

Install

$ go get github.com/gammazero/radixtree

Example

package main

import (
    "fmt"
    "github.com/gammazero/radixtree"
)

func main() {
    rt := radixtree.New()
    rt.Put("tomato", "TOMATO")
    rt.Put("tom", "TOM")
    rt.Put("tommy", "TOMMY")
    rt.Put("tornado", "TORNADO")

    val, found := rt.Get("tom")
    if found {
        fmt.Println("Found", val)
    }
    // Output: Found TOM

    // Find all items whose keys start with "tom"
    rt.Walk("tom", func(key string, value interface{}) bool {
        fmt.Println(value)
        return false
    })
    // Output:
    // TOM
    // TOMATO
    // TOMMY

    // Find all items whose keys are a prefix of "tomato"
    rt.WalkPath("tomato", func(key string, value interface{}) bool {
        fmt.Println(value)
        return false
    })
    // Output:
    // TOM
    // TOMATO

    if rt.Delete("tom") {
        fmt.Println("Deleted tom")
    }
    // Output: Deleted tom

    val, found = rt.Get("tom")
    if found {
        fmt.Println("Found", val)
    } else {
        fmt.Println("not found")
    }
    // Output: not found
}

License

MIT License

Documentation

Overview

Package radixtree implements an Adaptive Radix Tree, aka compressed trie or compact prefix tree. It is adaptive in the sense that nodes are not constant size, having as few or many children as needed to branch to all subtrees.

This package implements a radix-256 tree where each key symbol (radix) is a byte, allowing up to 256 possible branches to traverse to the next node.

The implementation is optimized for Get performance and allocates 0 bytes of heap memory per Get; therefore no garbage to collect. Once the radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the radixtree. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application.

The API uses string keys, since strings are immutable and therefore it is not necessary make a copy of the key provided to the radix tree.

Index

• type Bytes
• type InspectFunc
• type Iterator
  • func (it *Iterator) Copy() *Iterator
  • func (it *Iterator) Next() (key string, value interface{}, done bool)
• type Stepper
  • func (s *Stepper) Copy() *Stepper
  • func (s *Stepper) Next(radix byte) bool
  • func (s *Stepper) Value() (interface{}, bool)
• type Tree
  • func New() *Tree
  • func (t *Tree) Delete(key string) bool
  • func (t *Tree) Get(key string) (interface{}, bool)
  • func (t *Tree) Inspect(inspectFn InspectFunc)
  • func (t *Tree) Len() int
  • func (t *Tree) NewIterator() *Iterator
  • func (t *Tree) NewStepper() *Stepper
  • func (t *Tree) Put(key string, value interface{}) bool
  • func (t *Tree) Walk(key string, walkFn WalkFunc)
  • func (t *Tree) WalkPath(key string, walkFn WalkFunc)
• type WalkFunc

Examples

• Tree.NewIterator
• Tree.NewStepper
• Tree.Walk
• Tree.WalkPath

Types

type Bytes

type Bytes = Tree

Deprecated: Bytes is deprecated, use Tree.

type InspectFunc

type InspectFunc func(link, prefix, key string, depth, children int, hasValue bool, value interface{}) bool

InspectFunc is the type of the function called for each node visited by Inspect. The key argument contains the key at which the node is located, the depth is the distance from the root of the tree, and children is the number of children the node has.

If the function returns true Inspect stops immediately and returns.

type Iterator

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

Iterator iterates all keys and values in the radix tree.

Is is safe to use different Iterator instances concurrently. Any modification to the Tree that the Iterator was created from invalidates the Iterator instance.

func (*Iterator) Copy

func (it *Iterator) Copy() *Iterator

Copy creates a new Iterator at this iterator's state of iteration.

func (*Iterator) Next

func (it *Iterator) Next() (key string, value interface{}, done bool)

Next returns the next key and value stored in the Tree, and true when iteration is complete.

type Stepper

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

Stepper traverses a Tree one byte at a time.

Any modification to the tree invalidates the Stepper.

func (*Stepper) Copy

func (s *Stepper) Copy() *Stepper

Copy makes a copy of the current Stepper. This allows branching a Stepper into two that can take separate paths. These Steppers do not affect each other and can be used concurrently.

func (*Stepper) Next

func (s *Stepper) Next(radix byte) bool

Next advances the Stepper from its current position, to the position of given key symbol in the tree, so long as the given symbol is next in a path in the tree. If the symbol allows the Stepper to advance, then true is returned. Otherwise false is returned.

When false is returned the Stepper is not modified. This allows different values to be used in subsequent calls to Next.

func (*Stepper) Value

func (s *Stepper) Value() (interface{}, bool)

Value returns the value at the current Stepper position, and true or false to indicate if a value is present at the position.

type Tree

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

Tree is a radix tree of bytes keys and interface{} values.

func New

func New() *Tree

New creates a new bytes-based radix tree

func (*Tree) Delete

func (t *Tree) Delete(key string) bool

Delete removes the value associated with the given key. Returns true if there was a value stored for the key. If the node or any of its ancestors becomes childless as a result, they are removed from the tree.

func (*Tree) Get

func (t *Tree) Get(key string) (interface{}, bool)

Get returns the value stored at the given key. Returns false if there is no value present for the key.

func (*Tree) Inspect

func (t *Tree) Inspect(inspectFn InspectFunc)

Inspect walks every node of the tree, whether or not it holds a value, calling inspectFn with information about each node. This allows the structure of the tree to be examined and detailed statistics to be collected.

If inspectFn returns false, the traversal is stopped and Inspect returns.

The tree is traversed in lexical order, making the output deterministic.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of values stored in the tree.

func (*Tree) NewIterator

func (t *Tree) NewIterator() *Iterator

NewIterator returns a new Iterator.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := radixtree.New()
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	iter := rt.NewIterator()
	for {
		key, val, done := iter.Next()
		if done {
			break
		}
		fmt.Println(key, "=", val)
	}

}

Output:
tom = TOM
tomato = TOMATO
tommy = TOMMY
tornado = TORNADO

func (*Tree) NewStepper

func (t *Tree) NewStepper() *Stepper

NewStepper returns a new Stepper instance that begins at the root of the tree.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := radixtree.New()
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	iter := rt.NewStepper()
	word := "tomato"
	for i := range word {
		if !iter.Next(word[i]) {
			break
		}
		if val, ok := iter.Value(); ok {
			fmt.Println(val)
		}
	}
}

Output:
TOM
TOMATO

func (*Tree) Put

func (t *Tree) Put(key string, value interface{}) bool

Put inserts the value into the tree at the given key, replacing any existing items. It returns true if it adds a new value, false if it replaces an existing value.

func (*Tree) Walk

func (t *Tree) Walk(key string, walkFn WalkFunc)

Walk visits all nodes whose keys match or are prefixed by the specified key, calling walkFn for each value found. If walkFn returns true, Walk returns. Use empty key "" to visit all nodes starting from the root or the Tree.

The tree is traversed in lexical order, making the output deterministic.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := radixtree.New()
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	// Find all items whose keys start with "tom"
	rt.Walk("tom", func(key string, value interface{}) bool {
		fmt.Println(value)
		return false
	})
}

func (*Tree) WalkPath

func (t *Tree) WalkPath(key string, walkFn WalkFunc)

WalkPath walks each node along the path from the root to the node at the given key, calling walkFn for each node that has a value. If walkFn returns true, WalkPath returns.

The tree is traversed in lexical order, making the output deterministic.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := radixtree.New()
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	// Find all items that are a prefix of "tomato"
	rt.WalkPath("tomato", func(key string, value interface{}) bool {
		fmt.Println(value)
		return false
	})
}

Output:
TOM
TOMATO

type WalkFunc

type WalkFunc func(key string, value interface{}) bool

WalkFunc is the type of the function called for each value visited by Walk or WalkPath. The key argument contains the elements of the key at which the value is stored.

If the function returns true Walk stops immediately and returns. This applies to WalkPath as well.