Golang实现分层LRU缓存 - 保障祖先完整性的go-lrutree库

这是一个非常棒的库，解决了传统LRU在处理层次化数据时的关键痛点。保障祖先节点的完整性对于文件系统、组织结构、分类目录等场景至关重要。以下是对你实现的一些技术分析和示例补充：

技术实现亮点：

1. 祖先链完整性保障：通过强制要求节点祖先必须存在，避免了数据逻辑不一致
2. 链式LRU更新：访问节点时自动更新整个祖先链的LRU状态，这是正确的设计选择
3. 线程安全设计：适合并发场景下的树形数据缓存

示例代码扩展：

// 演示并发场景下的使用
func concurrentExample() {
    cache := lrutree.NewCache[string, *FileInfo](100, 
        lrutree.WithOnEvict(func(node lrutree.CacheNode[string, *FileInfo]) {
            fmt.Printf("Evicted file: %s\n", node.Value.Path)
        }))

    // 模拟多个goroutine并发访问文件路径
    var wg sync.WaitGroup
    paths := []string{"/usr/local/bin", "/usr/local/lib", "/var/log"}
    
    for _, path := range paths {
        wg.Add(1)
        go func(p string) {
            defer wg.Done()
            
            // 分解路径并确保所有父目录被缓存
            parts := strings.Split(p, "/")
            var parentKey string
            
            for i, part := range parts {
                if part == "" {
                    continue
                }
                key := strings.Join(parts[:i+1], "/")
                if i == 0 {
                    parentKey = ""
                }
                
                cache.Add(key, &FileInfo{
                    Path: key,
                    IsDir: true,
                }, parentKey)
                
                parentKey = key
            }
        }(path)
    }
    wg.Wait()
}

// 演示批量操作
func batchOperations() {
    cache := lrutree.NewCache[int, TreeNode](50)
    
    // 批量添加树节点
    nodes := []struct{
        key int
        value TreeNode
        parent int
    }{
        {1, TreeNode{Name: "Root"}, 0},
        {2, TreeNode{Name: "Child1"}, 1},
        {3, TreeNode{Name: "Child2"}, 1},
        {4, TreeNode{Name: "Grandchild1"}, 2},
    }
    
    for _, n := range nodes {
        if n.parent == 0 {
            cache.AddRoot(n.key, n.value)
        } else {
            cache.Add(n.key, n.value, n.parent)
        }
    }
    
    // 获取子树
    if subtree, ok := cache.GetSubtree(2); ok {
        for _, node := range subtree {
            fmt.Printf("Subtree node: %v\n", node.Value)
        }
    }
}

// 类型安全的包装器示例
type CategoryCache struct {
    cache *lrutree.Cache[string, Category]
}

func NewCategoryCache(capacity int) *CategoryCache {
    return &CategoryCache{
        cache: lrutree.NewCache[string, Category](capacity),
    }
}

func (cc *CategoryCache) AddCategory(id, name string, parentID string) error {
    if parentID == "" {
        return cc.cache.AddRoot(id, Category{
            ID:   id,
            Name: name,
        })
    }
    return cc.cache.Add(id, Category{
        ID:   id,
        Name: name,
    }, parentID)
}

func (cc *CategoryCache) GetCategoryChain(id string) []Category {
    branch := cc.cache.GetBranch(id)
    result := make([]Category, len(branch))
    for i, node := range branch {
        result[i] = node.Value
    }
    return result
}

性能考虑：

// 基准测试示例
func BenchmarkCacheOperations(b *testing.B) {
    cache := lrutree.NewCache[int, string](1000)
    
    // 构建深度树
    for i := 1; i <= 1000; i++ {
        parent := i / 2
        if parent == 0 {
            cache.AddRoot(i, fmt.Sprintf("Node%d", i))
        } else {
            cache.Add(i, fmt.Sprintf("Node%d", i), parent)
        }
    }
    
    b.ResetTimer()
    
    b.Run("GetLeafNode", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            cache.Get(999)
        }
    })
    
    b.Run("AddNewNode", func(b *testing.B) {
        for i := 0; i < b.N; i++ {
            cache.Add(1000+i, "NewNode", 500)
        }
    })
}

这个库的设计很好地解决了层次化数据缓存的特殊需求。GetBranch方法特别有用，可以一次性获取完整路径。线程安全的设计也使其适合生产环境使用。