0

go-immutable-radix

在 Golang 中实现不可变的 radix 树。（An immutable radix tree implementation in Golang）

Github repo
Main metrics
  • Owner: HashiCorp point_right projecs by owner (0)
  • Platform: Linux, Mac, Windows
  • License:: Mozilla Public License 2.0
  • Category::
  • Topic:
  • Like:
    0
      Compare:

Github stars Tracking Chart

go-immutable-radix

提供 iradix 包，它实现了一个不可变的 radix 树。该包只提供了一个单一的 Tree 实现，针对稀疏节点进行了优化。

作为一个 radix 树，它提供了以下功能。

  • O(k)操作. 在许多情况下，这可以比哈希表更快，因为哈希函数是一个O(k)操作，而哈希表的缓存定位性非常差。
  • 最小值/最大值查询
  • 有序迭代

树支持使用事务以比一次执行每个操作更有效的方式批量更新（插入、删除）。

对于一个可变异的变体，请参见 go-radix。

文档

完整的文档可以在 Godoc 上找到。

例子

下面是一个简单的使用实例

// 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")
}

下面是一个对按键进行范围扫描的例子。 

// 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


Main metrics

Overview
Name With Ownerhashicorp/go-immutable-radix
Primary LanguageGo
Program languageGo (Language Count: 1)
PlatformLinux, Mac, Windows
License:Mozilla Public License 2.0
所有者活动
Created At2015-06-02 03:17:46
Pushed At2025-11-03 21:37:02
Last Commit At2025-11-03 21:37:01
Release Count7
Last Release Namev2.1.0 (Posted on )
First Release Namev1.0.0 (Posted on )
用户参与
Stargazers Count1.1k
Watchers Count282
Fork Count80
Commits Count132
Has Issues Enabled
Issues Count21
Issue Open Count5
Pull Requests Count39
Pull Requests Open Count10
Pull Requests Close Count10
项目设置
Has Wiki Enabled
Is Archived
Is Fork
Is Locked
Is Mirror
Is Private

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