README
¶
__
/\ \__
__ ___ __ _ __\ \ ,_\
/'_ `\ / __`\ _______ /'__`\ /\`'__\ \ \/
/\ \L\ \/\ \L\ \/\______\/\ \L\.\_\ \ \/ \ \ \_
\ \____ \ \____/\/______/\ \__/.\_\\ \_\ \ \__\
\/___L\ \/___/ \/__/\/_/ \/_/ \/__/
/\____/
\_/__/
an adaptive radix tree implementation in go
what
An Adaptive Radix Tree is an indexing data structure similar to traditional radix trees, but uses internal nodes that grow and shrink intelligently with consecutive inserts and removals.
Adaptive Radix Trees have many interesting attributes that could be seen as improvements on other indexing data structures like Hash Maps or other Prefix Trees, such as:
- Worst-case search complexity of O(k), where
kis the length of the key. - They don't have to be rebuilt due to excessive inserts.
- The structure of their inner nodes is space-efficent when compared to traditional Prefix Trees.
- They provide prefix compression, a technique where each inner node specifies how far to 'fast-forward' in the search key before traversing to the next child.
usage
Include go-art in your go pacakages with:
import( "github.com/kellydunn/go-art" )
Go nuts:
// Make an ART Tree
tree := art.NewTree()
// Insert some stuff
tree.Insert([]byte("art trees"), []byte("are rad"))
// Search for a key, and get the resultant value
res := tree.Search([]byte("art trees"))
// Inspect your result!
fmt.Printf("%s\n", res) // "are rad"
documentation
Check out the documentation on godoc.org: http://godoc.org/github.com/kellydunn/go-art
implementation details
- It's currently unclear if golang supports SIMD instructions, so Node16s make use of Binary Search for lookups instead of the originally specified manner.
- Search is currently implemented in the pessimistic variation as described in the specification linked below.
performance
Worst-case scenarios for basic operations are:
| Search | Insert | Removal |
|---|---|---|
| O(k) | O(k)+c | O(k)+c |
kis the length of the key that we wish to insert. With prefix compression, this can be faster than Hashing functions, since hashing functions are O(k) operations.cis the number of children at the parent node of insertion or removal. This accounts for the growing or shrinking of the inner node. At the worst case, this is number is 48; the maximum number of children to move when transitioning between the biggest types of inner nodes.
releated works
- http://www-db.in.tum.de/~leis/papers/ART.pdf (Specification)
- http://www-db.in.tum.de/~leis/index/ART.tgz (C++ reference Implementation)
- https://github.com/armon/libart (an ANSI C Implementation)
Documentation
¶
Overview ¶
Pacakge art provides a golang implementation of Adaptive Radix Trees
Pacakge art provides a golang implementation of Adaptive Radix Trees
Index ¶
- Constants
- type ArtNode
- func (n *ArtNode) AddChild(key byte, node *ArtNode)
- func (n *ArtNode) FindChild(key byte) **ArtNode
- func (n *ArtNode) Index(key byte) int
- func (n *ArtNode) IsFull() bool
- func (n *ArtNode) IsLeaf() bool
- func (n *ArtNode) IsMatch(key []byte) bool
- func (n *ArtNode) LongestCommonPrefix(other *ArtNode, depth int) int
- func (n *ArtNode) MaxSize() int
- func (n *ArtNode) Maximum() *ArtNode
- func (n *ArtNode) MinSize() int
- func (n *ArtNode) Minimum() *ArtNode
- func (n *ArtNode) PrefixMismatch(key []byte, depth int) int
- func (n *ArtNode) RemoveChild(key byte)
- func (n *ArtNode) Value() interface{}
- type ArtTree
Constants ¶
const ( // From the specification: Radix trees consist of two types of nodes: // Inner nodes, which map partial keys to other nodes, // and leaf nodes, which store the values corresponding to the keys. NODE4 = iota NODE16 NODE48 NODE256 LEAF // Inner nodes of type Node4 must have between 2 and 4 children. NODE4MIN = 2 NODE4MAX = 4 // Inner nodes of type Node16 must have between 5 and 16 children. NODE16MIN = 5 NODE16MAX = 16 // Inner nodes of type Node48 must have between 17 and 48 children. NODE48MIN = 17 NODE48MAX = 48 // Inner nodes of type Node256 must have between 49 and 256 children. NODE256MIN = 49 NODE256MAX = 256 MAX_PREFIX_LEN = 10 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ArtNode ¶
type ArtNode struct {
// contains filtered or unexported fields
}
Defines a single ArtNode and its attributes.
func NewLeafNode ¶
func NewNode16 ¶
func NewNode16() *ArtNode
From the specification: This node type is used for storing between 5 and 16 child pointers. Like the Node4, the keys and pointers are stored in separate arrays at corresponding positions, but both arrays have space for 16 entries. A key can be found efficiently with binary search or, on modern hardware, with parallel comparisons using SIMD instructions.
func NewNode256 ¶
func NewNode256() *ArtNode
From the specification: The largest node type is simply an array of 256 pointers and is used for storing between 49 and 256 entries. With this representation, the next node can be found very efficiently using a single lookup of the key byte in that array. No additional indirection is necessary. If most entries are not null, this representation is also very space efficient because only pointers need to be stored.
func NewNode4 ¶
func NewNode4() *ArtNode
From the specification: The smallest node type can store up to 4 child pointers and uses an array of length 4 for keys and another array of the same length for pointers. The keys and pointers are stored at corresponding positions and the keys are sorted.
func NewNode48 ¶
func NewNode48() *ArtNode
From the specification: As the number of entries in a node increases, searching the key array becomes expensive. Therefore, nodes with more than 16 pointers do not store the keys explicitly. Instead, a 256-element array is used, which can be indexed with key bytes directly. If a node has between 17 and 48 child pointers, this array stores indexes into a second array which contains up to 48 pointers.
func (*ArtNode) AddChild ¶
Adds the passed in node to the current ArtNode's children at the specified key. The current node will grow if necessary in order for the insertion to take place.
func (*ArtNode) FindChild ¶
Returns a pointer to the child that matches the passed in key, or nil if not present.
func (*ArtNode) IsMatch ¶
Returns whether or not the key stored in the leaf matches the passed in key.
func (*ArtNode) LongestCommonPrefix ¶
Returns the longest number of bytes that match between the current node's prefix and the passed in node at the specified depth.
func (*ArtNode) Maximum ¶
Returns the Maximum child at the current node. The maximum child is determined by recursively traversing down the tree by selecting the biggest possible byte in each child until a leaf has been reached.
func (*ArtNode) Minimum ¶
Returns the Minimum child at the current node. The minimum child is determined by recursively traversing down the tree by selecting the smallest possible byte in each child until a leaf has been reached.
func (*ArtNode) PrefixMismatch ¶
Returns the number of bytes that differ between the passed in key and the compressed path of the current node at the specified depth.
func (*ArtNode) RemoveChild ¶
The child indexed by the passed in key is removed if found and the current ArtNode is shrunk if it falls below its minimum size.
type ArtTree ¶
type ArtTree struct {
// contains filtered or unexported fields
}
func NewArtTree ¶
func NewArtTree() *ArtTree
Creates and returns a new Art Tree with a nil root and a size of 0.
func (*ArtTree) Insert ¶
Inserts the passed in value that is indexed by the passed in key into the ArtTree.
Source Files