.NET内存缓存优化：基于子ID快速查询父子关系

问题概述 #

给定以下对象结构：

public class Parent
{
    public int Id { get; set; }
    public string Name { get; set; }

    public IList<Child> Items { get; set; }
}

public class Child
{
    public int Id { get; set; }

    public int Position { get; set; }
}

需要实现满足以下要求的内存缓存：

• 同一个子对象可属于多个父对象，且在不同父对象中的Position可能不同
• 仅支持两类查询：按父ID获取其下所有子对象、按父ID获取父对象名称
• 核心目标：
  1. 实现按子ID的O(1)级快速查询
  2. 不能按父ID缓存整个对象结构
  3. 避免为每个子对象重复存储父ID和父名称

现有实现的问题 #

你当前的实现使用ConcurrentDictionary<long, List<ParentChildInfo>>将子ID作为键，存储该子所属的父信息列表，但存在以下明显缺陷：

1. 查询效率低下：GetChildItemsForParentId和GetParentById需要遍历整个缓存集合，时间复杂度为O(n)，缓存数据量大时性能极差
2. 数据冗余严重：每个ParentChildInfo都重复存储了ParentName，当一个父包含大量子对象时，会浪费大量内存
3. 删除操作低效：Remove方法需要遍历所有子ID对应的列表，清理关联数据，同样是O(n)的时间复杂度

优化方案：拆分缓存结构，实现双向映射 #

通过拆分三个独立的线程安全字典，实现无冗余的双向关联存储，同时保证所有核心操作的高效性：

1. _parentNames：存储父ID到父名称的映射，避免父名称重复存储
2. _parentToChildren：存储父ID到子集合的映射（子ID -> 该父下的Position），满足按父ID快速查询子列表的需求
3. _childToParents：存储子ID到父ID集合的映射，满足按子ID快速查询所属父的需求

优化后的代码实现 #

public class Parent
{
    public int Id { get; set; }
    public string Name { get; set; }
    public IList<Child> Items { get; set; }
}

public class Child
{
    public int Id { get; set; }
    public int Position { get; set; }
}

public class ChildDto
{
    public long Id { get; set; }
    public int Position { get; set; }
}

public class OptimizedCache
{
    // 存储父ID与父名称的映射，避免重复存储父名称
    private readonly ConcurrentDictionary<int, string> _parentNames = new ConcurrentDictionary<int, string>();
    // 父ID -> 子ID与对应Position的映射，用于快速按父ID查询子列表
    private readonly ConcurrentDictionary<int, ConcurrentDictionary<long, int>> _parentToChildren = new ConcurrentDictionary<int, ConcurrentDictionary<long, int>>();
    // 子ID -> 所属父ID集合，用于快速按子ID查询所属父
    private readonly ConcurrentDictionary<long, HashSet<int>> _childToParents = new ConcurrentDictionary<long, HashSet<int>>();

    public void AddOrUpdate(Parent entity)
    {
        // 先清理该父之前的所有关联数据
        Remove(entity.Id);

        // 更新父名称缓存
        _parentNames.AddOrUpdate(entity.Id, entity.Name, (_, __) => entity.Name);

        // 创建或获取该父对应的子映射
        var childMap = new ConcurrentDictionary<long, int>();
        if (!_parentToChildren.TryAdd(entity.Id, childMap))
        {
            // 容错处理：理论上Remove后不会存在，若存在则清空原有数据
            _parentToChildren.TryGetValue(entity.Id, out childMap);
            childMap.Clear();
        }

        // 填充双向关联关系
        foreach (var child in entity.Items)
        {
            // 父到子的映射：存储子ID与对应的Position
            childMap.TryAdd(child.Id, child.Position);

            // 子到父的映射：记录该子所属的父ID
            _childToParents.AddOrUpdate(child.Id, 
                new HashSet<int> { entity.Id }, 
                (_, parentsSet) => 
                {
                    parentsSet.Add(entity.Id);
                    return parentsSet;
                });
        }
    }

    public bool Remove(int parentId)
    {
        // 移除父名称缓存
        _parentNames.TryRemove(parentId, out _);

        // 获取该父对应的子映射，不存在则返回移除失败
        if (!_parentToChildren.TryRemove(parentId, out var childMap))
        {
            return false;
        }

        // 遍历所有关联的子，清理子到父的映射
        foreach (var childId in childMap.Keys)
        {
            if (_childToParents.TryGetValue(childId, out var parentsSet))
            {
                parentsSet.Remove(parentId);
                // 如果子不再属于任何父，清理该子的缓存条目
                if (parentsSet.Count == 0)
                {
                    _childToParents.TryRemove(childId, out _);
                }
            }
        }

        return true;
    }

    public IList<ChildDto> GetChildItemsForParentId(int parentId)
    {
        if (!_parentToChildren.TryGetValue(parentId, out var childMap))
        {
            return new List<ChildDto>();
        }

        // 直接从映射中转换为DTO返回，时间复杂度O(k)，k为该父下的子数量
        return childMap.Select(kv => new ChildDto { Id = kv.Key, Position = kv.Value }).ToList();
    }

    public string GetParentNameById(int parentId)
    {
        // O(1)时间复杂度获取父名称
        _parentNames.TryGetValue(parentId, out var parentName);
        return parentName;
    }

    // 按子ID快速查询所属的所有父ID，满足O(1)查询需求
    public IReadOnlyCollection<int> GetParentIdsForChildId(long childId)
    {
        _childToParents.TryGetValue(childId, out var parentsSet);
        return parentsSet?.ToList().AsReadOnly() ?? Array.Empty<int>();
    }
}

优化效果说明 #

• 无数据冗余：父名称仅存储一次，彻底避免重复存储带来的内存浪费
• 高效查询：
  • 按父ID查子列表：O(k)（k为子数量），无需遍历整个缓存
  • 按父ID查名称：O(1)直接获取
  • 按子ID查所属父：O(1)直接获取
• 高效修改/删除：所有增删操作均针对目标关联集合，时间复杂度为O(k)（k为关联的子/父数量），避免遍历整个缓存
• 线程安全：依然使用ConcurrentDictionary保证多线程环境下的安全操作

内容的提问来源于stack exchange，提问作者fwf