radixtree

README

radixtree

Package radixtree implements a radix tree, also known as a compressed trie or compact prefix tree. Use it to look up values by key, find values whose keys share a common prefix, or find values whose keys lie along the path to a given key.

The tree uses a radix-256 structure where each key symbol is a byte, giving up to 256 branches per node. Nodes hold only as many children as needed, keeping memory proportional to the data stored.

Read operations (Get, Iter, IterPrefix, IterPath, and Stepper methods) allocate no heap memory and are safe to call concurrently. Write operations are not synchronized; callers that mix reads and writes must coordinate access themselves.

Features

• Efficient: All operations are O(key-length). Reads allocate no heap memory.
• Ordered: Iteration visits keys in lexical order, making output deterministic.
• Nil-safe: Get distinguishes between a missing key and a key whose value is nil.
• Compact: Keys with a common prefix share storage. Well-suited for timestamps, file paths, geohashes, and network addresses.
• Iterators: Range iterators cover all key-value pairs (Iter), pairs whose keys have a given prefix (IterPrefix), or pairs whose keys are a prefix of a given key (IterPath).
• Inspectable: Nodes iterates over every node of the tree, exposing its structure for debugging and statistics.
• Stepper: Walk the tree one byte at a time for incremental lookup. Copy a Stepper to branch a search and use the copies concurrently.
• Generics: Store any value type without interface conversions.

Install

$ go get github.com/gammazero/radixtree

Example

package main

import (
    "fmt"

    "github.com/gammazero/radixtree"
)

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

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

    // Find all items whose keys start with "tom".
    for key, value := range rt.IterPrefix("tom") {
        fmt.Println(key, "=", value)
    }

    // Find all items whose keys are a prefix of "tomato".
    for key, value := range rt.IterPath("tomato") {
        fmt.Println(key, "=", value)
    }

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

    if _, found := rt.Get("tom"); !found {
        fmt.Println("tom not found")
    }
}

Output:

Found TOM
tom = TOM
tomato = TOMATO
tommy = TOMMY
tom = TOM
tomato = TOMATO
Deleted tom
tom not found

License

MIT License

Documentation

Overview

Package radixtree implements a radix tree, also called a compressed trie or compact prefix tree. Use it to look up values by key, find values whose keys share a common prefix, or find values whose keys lie along the path to a given key.

The tree uses a radix-256 structure where each key symbol is a byte, giving up to 256 branches per node. Nodes hold only as many children as needed, keeping memory proportional to the data stored.

Read operations (Get, Iter, IterPrefix, IterPath, and Stepper methods) allocate no heap memory and are safe to call concurrently. Write operations are not synchronized; callers that mix reads and writes must coordinate access themselves.

The API accepts string keys. Because strings are immutable, the tree stores them directly without copying.

Index

• type NodeInfo
• type Stepper
  • func (s *Stepper[T]) Copy() *Stepper[T]
  • func (s *Stepper[T]) Item() (string, T, bool)
  • func (s *Stepper[T]) Next(radix byte) bool
  • func (s *Stepper[T]) Value() (T, bool)
• type Tree
  • func New[T any]() *Tree[T]
  • func (t *Tree[T]) Delete(key string) bool
  • func (t *Tree[T]) DeletePrefix(prefix string) bool
  • func (t *Tree[T]) Get(key string) (T, bool)
  • func (t *Tree[T]) Iter() iter.Seq2[string, T]
  • func (t *Tree[T]) IterPath(key string) iter.Seq2[string, T]
  • func (t *Tree[T]) IterPrefix(prefix string) iter.Seq2[string, T]
  • func (t *Tree[T]) Len() int
  • func (t *Tree[T]) NewStepper() *Stepper[T]
  • func (t *Tree[T]) Nodes() iter.Seq[NodeInfo[T]]
  • func (t *Tree[T]) Put(key string, value T) bool

Examples

• Tree.Iter
• Tree.IterPath
• Tree.IterPrefix
• Tree.NewStepper
• Tree.Nodes

Types

type NodeInfo

type NodeInfo[T any] struct {
	// Link is the key byte that the parent uses to index this node. It is zero for
	// the root node, which has no parent.
	Link byte
	// Prefix is the edge label between this node and its parent, not including
	// Link.
	Prefix string
	// Key is the full key at which the node is located.
	Key string
	// Depth is the distance from the root of the tree.
	Depth int
	// Children is the number of children the node has.
	Children int
	// HasValue is true if the node holds a value.
	HasValue bool
	// Value is the value held by the node. It is the zero value if HasValue is
	// false.
	Value T
}

NodeInfo describes a single node of the tree, as yielded by Nodes.

type Stepper

type Stepper[T any] 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[T]) Copy

func (s *Stepper[T]) Copy() *Stepper[T]

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[T]) Item

func (s *Stepper[T]) Item() (string, T, bool)

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

func (*Stepper[T]) Next

func (s *Stepper[T]) 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[T]) Value

func (s *Stepper[T]) Value() (T, 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[T any] struct {
	// contains filtered or unexported fields
}

Tree is a compressed radix tree of string keys and generic values. The zero value is an empty tree ready to use.

func New

func New[T any]() *Tree[T]

New creates a new empty radix tree.

func (*Tree[T]) Delete

func (t *Tree[T]) 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[T]) DeletePrefix

func (t *Tree[T]) DeletePrefix(prefix string) bool

DeletePrefix removes all values whose key is prefixed by the given prefix. Returns true if any values were removed.

func (*Tree[T]) Get

func (t *Tree[T]) Get(key string) (T, bool)

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

func (*Tree[T]) Iter

func (t *Tree[T]) Iter() iter.Seq2[string, T]

Iter returns an iterator that visits every value in the tree, yielding the key and value of each.

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[int]()
	rt.Put("mercury", 1)
	rt.Put("venus", 2)
	rt.Put("earth", 3)
	rt.Put("mars", 4)

	// Find all items that that have a key that is a prefix of "tomato".
	for key, value := range rt.Iter() {
		fmt.Println(key, "=", value)
	}
}

Output:
earth = 3
mars = 4
mercury = 1
venus = 2

func (*Tree[T]) IterPath

func (t *Tree[T]) IterPath(key string) iter.Seq2[string, T]

IterPath returns an iterator that visits every value whose key is a prefix of the given key, yielding the key and value of each. This includes the value at the given key itself, and the value at the empty key "", if those are present. The given key does not need to be in the tree.

For example, if the tree holds the keys "t", "to", "tom", "tomb", and "tomato", then IterPath("tomatoes") visits "t", "to", "tom", and "tomato". It does not visit "tomb", which is not a prefix of "tomatoes".

Values are visited from the shortest key to the longest, following the path from the root of the tree toward the given key.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

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

	// Find all items that that have a key that is a prefix of "tomato".
	for key, value := range rt.IterPath("tomato") {
		fmt.Println(key, "=", value)
	}
}

Output:
tom = TOM
tomato = TOMATO

func (*Tree[T]) IterPrefix

func (t *Tree[T]) IterPrefix(prefix string) iter.Seq2[string, T]

IterPrefix returns an iterator that visits every value whose key starts with the given prefix, yielding the key and value of each. This includes the value at the prefix itself, if present. The prefix does not need to be a key in the tree. An empty prefix visits every value, the same as Iter.

For example, if the tree holds the keys "t", "to", "tom", "tomb", and "tomato", then IterPrefix("tom") visits "tom", "tomato", and "tomb", and IterPrefix("toma") visits "tomato". This is the reverse of IterPath, which visits the keys that are prefixes of the given key.

Values are visited in lexical order of their keys, making the output deterministic.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

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

	// Find all items whose keys start with "tom".
	for _, value := range rt.IterPrefix("tom") {
		fmt.Println(value)
	}
}

Output:
TOM
TOMATO
TOMMY

func (*Tree[T]) Len

func (t *Tree[T]) Len() int

Len returns the number of values stored in the tree.

func (*Tree[T]) NewStepper

func (t *Tree[T]) NewStepper() *Stepper[T]

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[string]()
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

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

Output:
TOM
TOMATO

func (*Tree[T]) Nodes

func (t *Tree[T]) Nodes() iter.Seq[NodeInfo[T]]

Nodes returns an iterator that visits every node of the tree, whether or not it holds a value, yielding information about each node. This allows the structure of the tree to be examined and detailed statistics to be collected.

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

Unlike the other read operations, Nodes allocates memory to build the key of each node.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

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

	// Count the nodes in the tree, and how many hold values.
	var nodes, values int
	for node := range rt.Nodes() {
		nodes++
		if node.HasValue {
			values++
		}
	}
	fmt.Println("nodes:", nodes, "values:", values)
}

Output:
nodes: 5 values: 3

func (*Tree[T]) Put

func (t *Tree[T]) Put(key string, value T) 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.