go-adaptive-radix-tree 高性能自适应基数树实现

go-adaptive-radix-tree (简称 ART) 是一个 Golang 实现的高性能自适应基数树库，它是基数树的一种优化变体，特别适合需要高性能键值存储的场景。

特性概述

• 自适应节点大小，根据子节点数量自动调整
• 内存效率高，比传统基数树更节省空间
• 支持并发安全操作
• 提供前缀搜索、范围查询等高级功能
• 性能优于标准哈希表和普通树结构

安装

go get github.com/plar/go-adaptive-radix-tree

基本使用示例

package main

import (
	"fmt"
	art "github.com/plar/go-adaptive-radix-tree"
)

func main() {
	// 创建新树
	tree := art.New()

	// 插入键值对
	tree.Insert(art.Key("Hello"), "World")
	tree.Insert(art.Key("Golang"), "Rocks")
	tree.Insert(art.Key("Radix"), "Tree")

	// 查找
	value, found := tree.Search(art.Key("Golang"))
	if found {
		fmt.Printf("Found: %v\n", value) // 输出: Found: Rocks
	}

	// 删除
	tree.Delete(art.Key("Hello"))

	// 遍历所有键值对
	tree.ForEach(func(node art.Node) bool {
		fmt.Printf("Key: %s, Value: %v\n", node.Key(), node.Value())
		return true
	})
}

高级功能

前缀搜索

// 插入一些测试数据
tree.Insert(art.Key("api:v1:users"), "usersV1")
tree.Insert(art.Key("api:v1:products"), "productsV1")
tree.Insert(art.Key("api:v2:users"), "usersV2")

// 搜索所有api:v1前缀的键
results := []string{}
tree.ForEachPrefix(art.Key("api:v1:"), func(node art.Node) bool {
	results = append(results, node.Value().(string))
	return true
})

fmt.Println(results) // 输出: [usersV1 productsV1]

范围查询

tree.Insert(art.Key("apple"), 1)
tree.Insert(art.Key("banana"), 2)
tree.Insert(art.Key("cherry"), 3)
tree.Insert(art.Key("date"), 4)

// 查询a-c之间的键
tree.ForEachRange(art.Key("a"), art.Key("d"), func(node art.Node) bool {
	fmt.Printf("%s: %v\n", node.Key(), node.Value())
	return true
})

并发安全使用

import "sync"

func main() {
	tree := art.New()
	var wg sync.WaitGroup

	// 并发插入
	for i := 0; i < 100; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			key := art.Key(fmt.Sprintf("key%d", i))
			tree.Insert(key, i)
		}(i)
	}

	wg.Wait()

	// 验证插入结果
	fmt.Println("Tree size:", tree.Size())
}

性能考虑

1. 批量操作：对于批量插入，考虑预排序键可以提升性能
2. 键设计：使用较短的公共前缀可以最大化ART的优势
3. 内存使用：ART比标准哈希表更节省内存，特别是键有公共前缀时

实际应用场景

1. 路由系统（如HTTP路由器）
2. 数据库索引
3. 内存键值存储
4. 自动补全系统
5. IP路由表

与标准map的对比

func benchmark() {
	// 测试数据
	keys := make([]string, 1000000)
	for i := range keys {
		keys[i] = fmt.Sprintf("key:%d:%d:%d", i, i*2, i*3)
	}

	// 标准map测试
	start := time.Now()
	m := make(map[string]interface{})
	for _, k := range keys {
		m[k] = true
	}
	fmt.Println("Map insert:", time.Since(start))

	// ART测试
	start = time.Now()
	tree := art.New()
	for _, k := range keys {
		tree.Insert(art.Key(k), true)
	}
	fmt.Println("ART insert:", time.Since(start))
}

在键具有公共前缀的情况下，ART通常表现出更好的性能，特别是随着数据量增长时。

注意事项

1. 键必须是[]byte类型，使用art.Key()进行转换
2. 默认情况下非并发安全，并发访问需要外部同步
3. 对于完全随机的键，标准哈希表可能性能更好

go-adaptive-radix-tree是一个功能强大且高效的库，特别适合处理具有公共前缀的键的场景。它的设计平衡了内存使用和查询性能，是许多高性能应用的理想选择。