Documentation ¶
Overview ¶
Package art implements an Adapative Radix Tree(ART) in pure Go. Note that this implementation is not thread-safe but it could be really easy to implement.
The design of ART is based on "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" [1].
Usage
package main import ( "fmt" "github.com/plar/go-adaptive-radix-tree" ) func main() { tree := art.New() tree.Insert(art.Key("Hi, I'm Key"), "Nice to meet you, I'm Value") value, found := tree.Search(art.Key("Hi, I'm Key")) if found { fmt.Printf("Search value=%v\n", value) } tree.ForEach(func(node art.Node) bool { fmt.Printf("Callback value=%v\n", node.Value()) return true } for it := tree.Iterator(); it.HasNext(); { value, _ := it.Next() fmt.Printf("Iterator value=%v\n", value.Value()) } } // Output: // Search value=Nice to meet you, I'm Value // Callback value=Nice to meet you, I'm Value // Iterator value=Nice to meet you, I'm Value
Also the current implementation was inspired by [2] and [3]
[1] http://db.in.tum.de/~leis/papers/ART.pdf (Specification)
[2] https://github.com/armon/libart (C99 implementation)
[3] https://github.com/kellydunn/go-art (other Go implementation)
Index ¶
Constants ¶
const ( // Iterate only over leaf nodes. TraverseLeaf = 1 // Iterate only over non-leaf nodes. TraverseNode = 2 // Iterate over all nodes in the tree. TraverseAll = TraverseLeaf | TraverseNode )
Traverse Options.
const (
// MaxPrefixLen is maximum prefix length for internal nodes.
MaxPrefixLen = 10
)
Variables ¶
var ( ErrConcurrentModification = errors.New("Concurrent modification has been detected") ErrNoMoreNodes = errors.New("There are no more nodes in the tree") )
These errors can be returned when iteration over the tree.
Functions ¶
func DumpNode ¶
func DumpNode(root *artNode) string
DumpNode returns Tree in the human readable format:
package main import ( "fmt" "github.com/plar/go-adaptive-radix-tree" ) func main() { tree := art.New() terms := []string{"A", "a", "aa"} for _, term := range terms { tree.Insert(art.Key(term), term) } fmt.Println(tree) } Output: ─── Node4 (0xc00008a240) prefix(0): [0 0 0 0 0 0 0 0 0 0][··········] keys: [65 97 · ·] [Aa··] children(2): [0xc00008a210 0xc00008a270 <nil> <nil> <nil>] ├── Leaf (0xc00008a210) │ key(1): [65] [A] │ val: A │ ├── Node4 (0xc00008a270) │ prefix(0): [0 0 0 0 0 0 0 0 0 0][··········] │ keys: [97 · · ·] [a···] │ children(1): [0xc00008a260 <nil> <nil> <nil> 0xc00008a230] │ ├── Leaf (0xc00008a260) │ │ key(2): [97 97] [aa] │ │ val: aa │ │ │ ├── nil │ ├── nil │ ├── nil │ └── Leaf (0xc00008a230) │ key(1): [97] [a] │ val: a │ │ ├── nil ├── nil └── nil
Types ¶
type Callback ¶
Callback function type for tree traversal. if the callback function returns false then iteration is terminated.
type Iterator ¶
type Iterator interface { // Returns true if the iteration has more nodes when traversing the tree. HasNext() bool // Returns the next element in the tree and advances the iterator position. // Returns ErrNoMoreNodes error if there are no more nodes in the tree. // Check if there is a next node with HasNext method. // Returns ErrConcurrentModification error if the tree has been structurally // modified after the iterator was created. Next() (Node, error) }
Iterator iterates over nodes in key order.
type Key ¶
type Key []byte
Key Type. Key can be a set of any characters include unicode chars with null bytes.
type Node ¶
type Node interface { // Kind returns node type. Kind() Kind // Key returns leaf's key. // This method is only valid for leaf node, // if its called on non-leaf node then returns nil. Key() Key // Value returns leaf's value. // This method is only valid for leaf node, // if its called on non-leaf node then returns nil. Value() Value }
Node interface.
type Tree ¶
type Tree interface { // Insert a new key into the tree. // If the key already in the tree then return oldValue, true and nil, false otherwise. Insert(key Key, value Value) (oldValue Value, updated bool) // Delete removes a key from the tree and key's value, true is returned. // If the key does not exists then nothing is done and nil, false is returned. Delete(key Key) (value Value, deleted bool) // Search returns the value of the specific key. // If the key exists then return value, true and nil, false otherwise. Search(key Key) (value Value, found bool) // ForEach executes a provided callback once per leaf node by default. // The callback iteration is terminated if the callback function returns false. // Pass TraverseXXX as an options to execute a provided callback // once per NodeXXX type in the tree. ForEach(callback Callback, options ...int) // ForEachPrefix executes a provided callback once per leaf node that // leaf's key starts with the given keyPrefix. // The callback iteration is terminated if the callback function returns false. ForEachPrefix(keyPrefix Key, callback Callback) // Iterator returns an iterator for preorder traversal over leaf nodes by default. // Pass TraverseXXX as an options to return an iterator for preorder traversal over all NodeXXX types. Iterator(options ...int) Iterator // Minimum returns the minimum valued leaf, true if leaf is found and nil, false otherwise. Minimum() (min Value, found bool) // Maximum returns the maximum valued leaf, true if leaf is found and nil, false otherwise. Maximum() (max Value, found bool) // Returns size of the tree Size() int }
Tree is an Adaptive Radix Tree interface.