0

go-immutable-radix

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

Github 资源库
主要指标
  • 所有者: hashicorp/go-immutable-radix
  • 平台: Linux, Mac, Windows
  • 许可证: Mozilla Public License 2.0
  • 分类:
  • 主题:
  • 喜欢:
    0
      比较:

Github星跟踪图

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


主要指标

概览
名称与所有者hashicorp/go-immutable-radix
主编程语言Go
编程语言Go (语言数: 1)
平台Linux, Mac, Windows
许可证Mozilla Public License 2.0
所有者活动
创建于2015-06-01 19:17:46
推送于2025-06-30 16:05:48
最后一次提交2025-06-25 10:22:07
发布数7
最新版本名称v2.1.0 (发布于 )
第一版名称v1.0.0 (发布于 )
用户参与
星数1.1k
关注者数284
派生数81
提交数124
已启用问题?
问题数20
打开的问题数5
拉请求数34
打开的拉请求数11
关闭的拉请求数10
项目设置
已启用Wiki?
已存档?
是复刻?
已锁定?
是镜像?
是私有?

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