Skip to content
An immutable radix tree implementation in Golang
Go
Branch: master
Clone or download

Latest commit

thaJeztah gofmt all files (#27)
Signed-off-by: Sebastiaan van Stijn <github@gone.nl>
Latest commit 9621158 May 13, 2020

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.circleci Add circle config (#25) May 22, 2019
.gitignore Initial commit Jun 1, 2015
CHANGELOG.md Create CHANGELOG.md May 22, 2019
LICENSE
README.md Add circle config (#25) May 22, 2019
edges.go Move methods onto node so they are available in Txn Jun 8, 2015
go.mod Add go.mod Aug 30, 2018
go.sum Add go.mod Aug 30, 2018
iradix.go Improved doc comment for Txn.Clone Mar 18, 2020
iradix_test.go gofmt all files (#27) May 13, 2020
iter.go gofmt all files (#27) May 13, 2020
node.go Basic working SeekLowerBound to allow range scans May 10, 2019
raw_iter.go gofmt all files (#27) May 13, 2020

README.md

go-immutable-radix CircleCI

Provides the iradix package that implements an immutable radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

As a radix tree, it provides the following:

  • O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
  • Minimum / Maximum value lookups
  • Ordered iteration

A tree supports using a transaction to batch multiple updates (insert, delete) in a more efficient manner than performing each operation one at a time.

For a mutable variant, see go-radix.

Documentation

The full documentation is available on Godoc.

Example

Below is a simple example of usage

// Create a tree
r := iradix.New()
r, _, _ = r.Insert([]byte("foo"), 1)
r, _, _ = r.Insert([]byte("bar"), 2)
r, _, _ = r.Insert([]byte("foobar"), 2)

// Find the longest prefix match
m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
if string(m) != "foo" {
    panic("should be foo")
}

Here is an example of performing a range scan of the keys.

// Create a tree
r := iradix.New()
r, _, _ = r.Insert([]byte("001"), 1)
r, _, _ = r.Insert([]byte("002"), 2)
r, _, _ = r.Insert([]byte("005"), 5)
r, _, _ = r.Insert([]byte("010"), 10)
r, _, _ = r.Insert([]byte("100"), 10)

// Range scan over the keys that sort lexicographically between [003, 050)
it := r.Root().Iterator()
it.SeekLowerBound([]byte("003"))
for key, _, ok := it.Next(); ok; key, _, ok = it.Next() {
  if key >= "050" {
      break
  }
  fmt.Println(key)
}
// Output:
//  005
//  010
You can’t perform that action at this time.