adaptive radix tree (a.k.a prefix tree or compact trie)
MIT License
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.
It is adaptive in the sense that nodes are not constant size, having only as many children, up to the maximum, 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 read performance and does not allocate heap memory for read operation (Get, Iter, IterPath, etc.). 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:
nil
values: Read operations differentiate between missing and nil
values.Stepper
type of iterator traverses the tree one specified byte at a time, and is useful for incremental lookup. A Stepper can be copied in order to branch a search and iterate the copies concurrently.$ go get github.com/gammazero/radixtree
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".
for key, value := range rt.IterAt("tom") {
fmt.Println(key, "=", value)
}
// Output:
// tom = TOM
// tomato = TOMATO
// tommy = TOMMY
// Find all items whose keys are a prefix of "tomato"
for _, value := range rt.IterPath("tomato") {
fmt.Println(value)
}
// 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
}