README
¶
radixtree
Package radixtree implements multiple forms of an Adaptive Radix Tree, aka compressed trie or compact prefix tree. This data structure is useful to quickly lookup data by key, find find data whose keys have a common prefix, or find data whose keys are a prefix (i.e. found along the way) of a search key.
The implementations are 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:
- Multiple types of radix tree: Bytes, Paths
- Efficient: Operations for all types of radix tree 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. Nodes that do not branch or contain values are compressed out of the tree.
- Adaptive: This radix tree is adaptive in the sense that nodes are not constant size, having only as many children that are needed, from zero to the maximum possible number of different key segments.
- Iterators: An iterator for each type of radix tree allows a tree to be traversed one key segment at a time. This is useful for incremental lookup. Iterators 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
Documentation
¶
Overview ¶
Package radixtree implements multiple forms of 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, up to the number of different key segments to traverse to the next branch or value.
This package provides multiple types of radix tree: Bytes and Paths, where each key symbol (radix) is a byte or a path segment, respectively.
The implementations are 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.
Index ¶
- type Bytes
- func (tree *Bytes) Delete(key string) bool
- func (tree *Bytes) Get(key string) (interface{}, bool)
- func (tree *Bytes) Inspect(inspectFn InspectFunc)
- func (tree *Bytes) Iter() Iterator
- func (tree *Bytes) Len() int
- func (tree *Bytes) NewIterator() *BytesIterator
- func (tree *Bytes) Put(key string, value interface{}) bool
- func (tree *Bytes) Walk(key string, walkFn WalkFunc)
- func (tree *Bytes) WalkPath(key string, walkFn WalkFunc)
- type BytesIterator
- type InspectFunc
- type Iterator
- type Paths
- func (tree *Paths) Delete(key string) bool
- func (tree *Paths) Get(key string) (interface{}, bool)
- func (tree *Paths) Inspect(inspectFn InspectFunc)
- func (tree *Paths) Iter() Iterator
- func (tree *Paths) Len() int
- func (tree *Paths) NewIterator() *PathsIterator
- func (tree *Paths) PathSeparator() string
- func (tree *Paths) Put(key string, value interface{}) bool
- func (tree *Paths) Walk(key string, walkFn WalkFunc)
- func (tree *Paths) WalkPath(key string, walkFn WalkFunc)
- type PathsIterator
- type WalkFunc
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bytes ¶ added in v0.2.0
type Bytes struct {
// contains filtered or unexported fields
}
Bytes is a radix tree of bytes with string keys and interface{} values.
func (*Bytes) Delete ¶ added in v0.2.0
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 (*Bytes) Get ¶ added in v0.2.0
Get returns the value stored at the given key. Returns false if there is no value present for the key.
func (*Bytes) Inspect ¶ added in v0.2.0
func (tree *Bytes) 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 (*Bytes) NewIterator ¶ added in v0.2.0
func (tree *Bytes) NewIterator() *BytesIterator
NewIterator returns a new BytesIterator instance that begins iterating from 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.NewIterator()
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 (*Bytes) Put ¶ added in v0.2.0
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 (*Bytes) Walk ¶ added in v0.2.0
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.
The tree is traversed in lexical order, making the output deterministic.
Walk can be thought of as GetItemsWithPrefix(key)
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
})
}
Output:
func (*Bytes) WalkPath ¶ added in v0.2.0
WalkPath walks a path in the tree 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.
WalkPath can be thought of as GetItemsThatArePrefixOf((key)
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 BytesIterator ¶ added in v0.2.0
type BytesIterator struct {
// contains filtered or unexported fields
}
BytesIterator is a stateful iterator that traverses a Bytes radix tree one byte at a time.
Any modification to the tree invalidates the iterator.
func (*BytesIterator) Copy ¶ added in v0.2.0
func (it *BytesIterator) Copy() *BytesIterator
Copy makes a copy of the current iterator. This allows branching an iterator into two iterators that can take separate paths. These iterators do not affect each other and can be iterated concurrently.
func (*BytesIterator) Next ¶ added in v0.2.0
func (it *BytesIterator) Next(radix byte) bool
Next advances the iterator 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 iterator to advance, then true is returned. Otherwise false is returned.
When false is returned the iterator is not modified. This allows different values to be used in subsequent calls to Next, to advance the iterator from its current position.
func (*BytesIterator) Value ¶ added in v0.2.0
func (it *BytesIterator) Value() (interface{}, bool)
Value returns the value at the current iterator position, and true or false to indicate if a value is present at the position.
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 ¶ added in v0.2.5
type Iterator interface {
// Next returns the next key and value stored in the tree, and true when
// iteration is complete
Next() (key string, value interface{}, more bool)
// Copy creates a new Iterator at this iterator's state of iteration
Copy() Iterator
}
Iterator iterates all keys and values in the radixtree
Is is safe to use different iterators concurrently. Any modification to the tree that the iterator was created from invalidates the iterator.
type Paths ¶
type Paths struct {
// contains filtered or unexported fields
}
Paths is a radix tree of paths with string keys and interface{} values. Paths splits keys by separator, for example, "/a/b/c" splits to "/a", "/b", "/c". A different path separator string may be specified by calling NewPaths with the separator to use.
func NewPaths ¶
NewPaths creates a new Paths instance, specifying the path separator to use.
The pathSeparator splits a path key into separate segments. The default path separator is forward slash. This variable may be set to any string to use as a path separator, multi-character strings are OK.
func (*Paths) Delete ¶
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 (*Paths) Get ¶
Get returns the value stored at the given key. Returns false if there is no value present for the key.
func (*Paths) Inspect ¶
func (tree *Paths) 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 (*Paths) NewIterator ¶
func (tree *Paths) NewIterator() *PathsIterator
NewIterator returns a new PathsIterator instance that begins iterating from the root of the tree.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/gammazero/radixtree"
)
func main() {
pt := radixtree.NewPaths("/")
pt.Put("home/abc", "my home directory")
pt.Put("home/abc/a1.txt", "some text")
pt.Put("home/abc/Documents", "my documents")
pt.Put("home/abc/Documents/pic.png", "cat pic")
pt.Put("home/abc/Documents/stuff.pdf", "story")
// Find item in each path segment
parts := strings.Split("home/abc/Documents/pic.png", "/")
iter := pt.NewIterator()
for i, p := range parts {
if !iter.Next(p) {
break
}
if value, ok := iter.Value(); ok {
key := strings.Join(parts[:i+1], "/")
fmt.Println(key, "=>", value)
}
}
}
Output: home/abc => my home directory home/abc/Documents => my documents home/abc/Documents/pic.png => cat pic
func (*Paths) PathSeparator ¶
PathSeparator returns this Paths instance's path separator
func (*Paths) Put ¶
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 (*Paths) Walk ¶
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.
The tree is traversed in lexical order, making the output deterministic.
Walk can be thought of as GetItemsWithPrefix(key)
Example ¶
package main
import (
"fmt"
"github.com/gammazero/radixtree"
)
func main() {
pt := radixtree.NewPaths("/")
pt.Put("home/abc", "my home directory")
pt.Put("home/abc/a1.txt", "some text")
pt.Put("home/abc/Documents", "my documents")
pt.Put("home/abc/Documents/pic.png", "cat pic")
pt.Put("home/abc/Documents/stuff.pdf", "story")
// Find all items with keys that start with "home/abc/Documents"
pt.Walk("home/abc/Documents", func(key string, value interface{}) bool {
fmt.Println(value)
return false
})
}
Output:
func (*Paths) WalkPath ¶
WalkPath walks a path in the tree 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.
WalkPath can be thought of as GetItemsThatArePrefixOf((key)
Example ¶
package main
import (
"fmt"
"github.com/gammazero/radixtree"
)
func main() {
pt := radixtree.NewPaths("/")
pt.Put("home/abc", "my home directory")
pt.Put("home/abc/a1.txt", "some text")
pt.Put("home/abc/Documents", "my documents")
pt.Put("home/abc/Documents/pic.png", "cat pic")
pt.Put("home/abc/Documents/stuff.pdf", "story")
// Find item in each path segment
pt.WalkPath("home/abc/Documents/pic.png", func(key string, value interface{}) bool {
fmt.Println(key, "=>", value)
return false
})
}
Output: home/abc => my home directory home/abc/Documents => my documents home/abc/Documents/pic.png => cat pic
type PathsIterator ¶
type PathsIterator struct {
// contains filtered or unexported fields
}
PathsIterator traverses a Paths radix tree one path segment at a time.
Any modification to the tree invalidates the iterator.
func (*PathsIterator) Copy ¶
func (it *PathsIterator) Copy() *PathsIterator
Copy makes a copy of the current iterator. This allows branching an iterator into two iterators that can take separate paths. These iterators do not affect each other and can be iterated concurrently.
func (*PathsIterator) Next ¶
func (it *PathsIterator) Next(part string) bool
Next advances the iterator from its current position, to the position of given path segment in the tree, so long as the given segment is next in a path in the tree. If the segment allows the iterator to advance, then true is returned. Otherwise false is returned.
When false is returned the iterator is not modified. This allows different values to be used in subsequent calls to Next, to advance the iterator from its current position.
Any part subsequent to the first must begin with the PathSeparator.
func (*PathsIterator) Value ¶
func (it *PathsIterator) Value() (interface{}, bool)
Value returns the value at the current iterator position, and true or false to indicate if a value is present at the position.
Source Files