hashicorp/go-immutable-radix
GitHub: hashicorp/go-immutable-radix
一个高性能的 Go 不可变基数树实现，提供 O(k) 复杂度的前缀匹配、有序迭代和事务批量操作。
Stars: 1105 | Forks: 81
# go-immutable-radix [](https://github.com/hashicorp/go-immutable-radix/actions/workflows/ci.yaml)
提供了实现[不可变 radix tree](http://en.wikipedia.org/wiki/Radix_tree)的 `iradix` 包。
该包仅提供了一个经过优化的单 `Tree` 实现，专为稀疏节点设计。
作为一棵 radix tree，它提供了以下特性：
* O(k) 操作。在许多情况下，这可能比哈希表更快，因为
哈希函数本身就是一个 O(k) 操作，而且哈希表的缓存局部性很差。
* 最小值 / 最大值查找
* 有序迭代
Tree 支持使用事务来批量处理多个更新（插入、删除）操作，
这比逐个执行每个操作更高效。
如需可变版本，请参见 [go-radix](https://github.com/armon/go-radix)。
# V2
go-immutable-radix 的 v2 版本引入了泛型，以提高该包用户在
编译时的类型安全性。v2 的模块名为
`github.com/hashicorp/go-immutable-radix/v2`。
# 文档
完整文档可在 [Godoc](http://godoc.org/github.com/hashicorp/go-immutable-radix) 上查阅。
# 示例
以下是一个简单的使用示例
```
// Create a tree
r := iradix.New[int]()
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")
}
```
下面是一个对 key 进行范围扫描的示例。
```
// Create a tree
r := iradix.New[int]()
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 string(key) >= "050" {
break
}
fmt.Println(string(key))
}
// Output:
// 005
// 010
```
标签：EVTX分析, Go, Ruby工具, 不可变数据结构, 基数树, 开发组件, 数据结构, 日志审计