README.md
1go-immutable-radix [![Build Status](https://travis-ci.org/hashicorp/go-immutable-radix.png)](https://travis-ci.org/hashicorp/go-immutable-radix)
2=========
3
4Provides the `iradix` package that implements an immutable [radix tree](http://en.wikipedia.org/wiki/Radix_tree).
5The package only provides a single `Tree` implementation, optimized for sparse nodes.
6
7As a radix tree, it provides the following:
8 * O(k) operations. In many cases, this can be faster than a hash table since
9 the hash function is an O(k) operation, and hash tables have very poor cache locality.
10 * Minimum / Maximum value lookups
11 * Ordered iteration
12
13A tree supports using a transaction to batch multiple updates (insert, delete)
14in a more efficient manner than performing each operation one at a time.
15
16For a mutable variant, see [go-radix](https://github.com/armon/go-radix).
17
18Documentation
19=============
20
21The full documentation is available on [Godoc](http://godoc.org/github.com/hashicorp/go-immutable-radix).
22
23Example
24=======
25
26Below is a simple example of usage
27
28```go
29// Create a tree
30r := iradix.New()
31r, _, _ = r.Insert([]byte("foo"), 1)
32r, _, _ = r.Insert([]byte("bar"), 2)
33r, _, _ = r.Insert([]byte("foobar"), 2)
34
35// Find the longest prefix match
36m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
37if string(m) != "foo" {
38 panic("should be foo")
39}
40```
41
42