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