// 這段代碼看起來(lái)很簡(jiǎn)單，實(shí)際上是性能殺手
public List<Category> getCategoryTree() {
    List<Category> roots = categoryMapper.getRootCategories(); // 1次查詢
    for (Category root : roots) {
        loadChildren(root); // 每個(gè)節(jié)點(diǎn)都觸發(fā)遞歸查詢
    }
    return roots;
}

private void loadChildren(Category parent) {
    List<Category> children = categoryMapper.getByParentId(parent.getId()); // N次查詢
    parent.setChildren(children);
    for (Category child : children) {
        loadChildren(child); // 遞歸繼續(xù)
    }
}

CREATE TABLE category (
    id BIGINT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id BIGINT,
    level INT NOT NULL DEFAULT 0,
    sort_order INT DEFAULT 0,
    status TINYINT DEFAULT 1,
    create_time DATETIME,
    update_time DATETIME,
    
    INDEX idx_parent_id (parent_id),
    INDEX idx_level (level),
    INDEX idx_status (status)
);

// 傳統(tǒng)方案：時(shí)間復(fù)雜度 O(n2)，空間復(fù)雜度 O(n)
public List<Category> getChildren(Long parentId) {
    List<Category> children = categoryMapper.getByParentId(parentId);  // 1次查詢
    for (Category child : children) {                                 // 對(duì)每個(gè)子節(jié)點(diǎn)
        child.setChildren(getChildren(child.getId()));                // 遞歸查詢子節(jié)點(diǎn)
    }
    return children;
}

// 優(yōu)化方案：時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(n)
public <T extends TreeNode<T>> List<T> buildTree(List<T> nodes, Object rootValue) {
    // 步驟1：建立HashMap索引 - O(n)
    Map<Object, T> nodeMap = nodes.stream()
        .collect(Collectors.toMap(TreeNode::getId, node -> node));
    
    List<T> rootNodes = new ArrayList<>();
    
    // 步驟2：?jiǎn)未伪闅v建立父子關(guān)系 - O(n)
    for (T node : nodes) {                    // 遍歷n個(gè)節(jié)點(diǎn)
        Object parentId = node.getParentId();
        if (Objects.equals(parentId, rootValue)) {
            rootNodes.add(node);
        } else {
            T parent = nodeMap.get(parentId); // HashMap查找：O(1)
            if (parent != null) {
                parent.addChild(node);        // 建立父子關(guān)系：O(1)
            }
        }
    }
    
    return rootNodes;
}

// 優(yōu)化后的執(zhí)行過(guò)程 - 以10000個(gè)節(jié)點(diǎn)為例
//Step 1: SELECT * FROM category WHERE status = 1  // 僅1次查詢獲取所有數(shù)據(jù)
//Step 2: 內(nèi)存中構(gòu)建HashMap索引 - O(n)
{
  1 -> Node{id=1, name="根節(jié)點(diǎn)", parentId=null},
  2 -> Node{id=2, name="子節(jié)點(diǎn)1", parentId=1},
  3 -> Node{id=3, name="子節(jié)點(diǎn)2", parentId=1},
  ...
  10000 -> Node{id=10000, name="葉子節(jié)點(diǎn)", parentId=9999}
}
//Step 3: 單次遍歷建立關(guān)系 - O(n)
for (Node node : allNodes) {  // 10000次循環(huán)
    Node parent = nodeMap.get(node.parentId);  // O(1)查找
    parent.addChild(node);  // O(1)添加
}

@Component
public class TreeBuilder {
    
    /**
     * 高性能樹構(gòu)建算法 - O(n)時(shí)間復(fù)雜度
     * @param nodes 所有節(jié)點(diǎn)列表
     * @param rootValue 根節(jié)點(diǎn)的parent_id值（通常為null或0）
     * @return 構(gòu)建好的樹結(jié)構(gòu)
     */
    public <T extends TreeNode<T>> List<T> buildTree(List<T> nodes, Object rootValue) {
        if (CollectionUtils.isEmpty(nodes)) {
            return new ArrayList<>();
        }
        
        // 1. 建立ID->Node的快速索引，時(shí)間復(fù)雜度O(n)
        Map<Object, T> nodeMap = nodes.stream()
            .collect(Collectors.toMap(TreeNode::getId, node -> node));
        
        List<T> rootNodes = new ArrayList<>();
        
        // 2. 單次遍歷建立父子關(guān)系，時(shí)間復(fù)雜度O(n)
        for (T node : nodes) {
            Object parentId = node.getParentId();
            
            if (Objects.equals(parentId, rootValue)) {
                // 根節(jié)點(diǎn)
                rootNodes.add(node);
            } else {
                // 子節(jié)點(diǎn)，建立父子關(guān)系
                T parent = nodeMap.get(parentId);
                if (parent != null) {
                    parent.addChild(node);
                }
            }
        }
        
        // 3. 遞歸排序（可選），時(shí)間復(fù)雜度O(n log n)
        sortTreeRecursively(rootNodes);
        
        return rootNodes;
    }
    
    private <T extends TreeNode<T>> void sortTreeRecursively(List<T> nodes) {
        if (CollectionUtils.isEmpty(nodes)) {
            return;
        }
        
        // 按sort_order排序
        nodes.sort(Comparator.comparing(TreeNode::getSortOrder, 
            Comparator.nullsLast(Comparator.naturalOrder())));
        
        // 遞歸排序子節(jié)點(diǎn)
        for (T node : nodes) {
            if (node.hasChildren()) {
                sortTreeRecursively(node.getChildren());
            }
        }
    }
}

public interface TreeNode<T> {
    Object getId();
    Object getParentId();
    Integer getSortOrder();
    List<T> getChildren();
    void setChildren(List<T> children);
    
    default void addChild(T child) {
        if (getChildren() == null) {
            setChildren(new ArrayList<>());
        }
        getChildren().add(child);
    }
    
    default boolean hasChildren() {
        return getChildren() != null && !getChildren().isEmpty();
    }
}

@Data
@TableName("category")
public class Category implements TreeNode<Category> {
    @TableId(type = IdType.AUTO)
    private Long id;
    
    private String name;
    private Long parentId;
    private Integer level;
    private Integer sortOrder;
    private Integer status;
    
    @JsonFormat(pattern = "yyyy-MM-dd HH:mm:ss")
    private LocalDateTime createTime;
    
    @JsonFormat(pattern = "yyyy-MM-dd HH:mm:ss")
    private LocalDateTime updateTime;
    
    // 非數(shù)據(jù)庫(kù)字段
    @TableField(exist = false)
    private List<Category> children;
    
    @Override
    public void addChild(Category child) {
        if (children == null) {
            children = new ArrayList<>();
        }
        children.add(child);
    }
}

@Mapper
public interface CategoryMapper extends BaseMapper<Category> {
    
    /**
     * 獲取所有有效分類（用于構(gòu)建樹）
     */
    @Select("SELECT id, name, parent_id, level, sort_order, status, " +
            "create_time, update_time FROM category WHERE status = 1 " +
            "ORDER BY level, parent_id, sort_order")
    List<Category> selectAllForTree();
    
    /**
     * 根據(jù)父ID查詢子分類
     */
    @Select("SELECT * FROM category WHERE parent_id = #{parentId} AND status = 1 " +
            "ORDER BY sort_order")
    List<Category> selectByParentId(@Param("parentId") Long parentId);
}

@Service
@Transactional(rollbackFor = Exception.class)
public class CategoryServiceImpl implements CategoryService {
    
    @Autowired
    private CategoryMapper categoryMapper;
    
    @Autowired
    private TreeBuilder treeBuilder;
    
    /**
     * 獲取分類樹（帶緩存）
     */
    @Cacheable(value = "category:tree", key = "'all'")
    public List<Category> getCategoryTree() {
        // 1. 一次性查詢所有數(shù)據(jù)
        List<Category> allCategories = categoryMapper.selectAllForTree();
        
        // 2. 使用高性能算法構(gòu)建樹
        return treeBuilder.buildTree(allCategories, null);
    }
    
    /**
     * 創(chuàng)建分類
     */
    @CacheEvict(value = "category:tree", allEntries = true)
    public Category createCategory(Category category) {
        // 設(shè)置層級(jí)
        if (category.getParentId() != null) {
            Category parent = categoryMapper.selectById(category.getParentId());
            category.setLevel(parent.getLevel() + 1);
        } else {
            category.setLevel(0);
        }
        
        category.setStatus(1);
        category.setCreateTime(LocalDateTime.now());
        category.setUpdateTime(LocalDateTime.now());
        
        categoryMapper.insert(category);
        return category;
    }
    
    /**
     * 更新分類
     */
    @CacheEvict(value = "category:tree", allEntries = true)
    public Category updateCategory(Category category) {
        category.setUpdateTime(LocalDateTime.now());
        categoryMapper.updateById(category);
        return category;
    }
    
    /**
     * 刪除分類（軟刪除）
     */
    @CacheEvict(value = "category:tree", allEntries = true)
    public void deleteCategory(Long id) {
        Category category = new Category();
        category.setId(id);
        category.setStatus(0);
        category.setUpdateTime(LocalDateTime.now());
        categoryMapper.updateById(category);
    }
}

@RestController
@RequestMapping("/api/categories")
public class CategoryController {
    
    @Autowired
    private CategoryService categoryService;
    
    /**
     * 獲取分類樹
     */
    @GetMapping("/tree")
    public Result<List<Category>> getCategoryTree() {
        List<Category> tree = categoryService.getCategoryTree();
        return Result.success(tree);
    }
    
    /**
     * 創(chuàng)建分類
     */
    @PostMapping
    public Result<Category> createCategory(@RequestBody @Valid Category category) {
        Category created = categoryService.createCategory(category);
        return Result.success(created);
    }
    
    /**
     * 更新分類
     */
    @PutMapping("/{id}")
    public Result<Category> updateCategory(@PathVariable Long id, 
                                          @RequestBody @Valid Category category) {
        category.setId(id);
        Category updated = categoryService.updateCategory(category);
        return Result.success(updated);
    }
    
    /**
     * 刪除分類
     */
    @DeleteMapping("/{id}")
    public Result<Void> deleteCategory(@PathVariable Long id) {
        categoryService.deleteCategory(id);
        return Result.success();
    }
}

@Configuration
@EnableCaching
public class MultiLevelCacheConfig {
    
    /**
     * 多級(jí)緩存管理器：L1(Caffeine) + L2(Redis)
     */
    @Bean
    @Primary
    public CacheManager multiLevelCacheManager(RedisConnectionFactory connectionFactory) {
        return new MultiLevelCacheManager(
            createCaffeineCacheManager(),
            createRedisCacheManager(connectionFactory)
        );
    }
    
    private CaffeineCacheManager createCaffeineCacheManager() {
        CaffeineCacheManager cacheManager = new CaffeineCacheManager();
        cacheManager.setCaffeine(Caffeine.newBuilder()
                .initialCapacity(100)
                .maximumSize(1000)
                .expireAfterWrite(10, TimeUnit.MINUTES) // L1緩存10分鐘過(guò)期
                .recordStats());
        return cacheManager;
    }
    
    private RedisCacheManager createRedisCacheManager(RedisConnectionFactory connectionFactory) {
        RedisCacheConfiguration config = RedisCacheConfiguration.defaultCacheConfig()
                .entryTtl(Duration.ofHours(2)) // L2緩存2小時(shí)過(guò)期
                .serializeKeysWith(RedisSerializationContext.SerializationPair
                        .fromSerializer(new StringRedisSerializer()))
                .serializeValuesWith(RedisSerializationContext.SerializationPair
                        .fromSerializer(new GenericJackson2JsonRedisSerializer()))
                .disableCachingNullValues();
        
        return RedisCacheManager.builder(connectionFactory)
                .cacheDefaults(config)
                .build();
    }
}

/**
 * 自定義多級(jí)緩存管理器
 */
public class MultiLevelCacheManager implements CacheManager {
    
    private final CacheManager l1CacheManager; // 本地緩存
    private final CacheManager l2CacheManager; // 分布式緩存
    
    public MultiLevelCacheManager(CacheManager l1CacheManager, CacheManager l2CacheManager) {
        this.l1CacheManager = l1CacheManager;
        this.l2CacheManager = l2CacheManager;
    }
    
    @Override
    public Cache getCache(String name) {
        Cache l1Cache = l1CacheManager.getCache(name);
        Cache l2Cache = l2CacheManager.getCache(name);
        return new MultiLevelCache(name, l1Cache, l2Cache);
    }
    
    @Override
    public Collection<String> getCacheNames() {
        Set<String> names = new HashSet<>();
        names.addAll(l1CacheManager.getCacheNames());
        names.addAll(l2CacheManager.getCacheNames());
        return names;
    }
}

/**
 * 多級(jí)緩存實(shí)現(xiàn)
 */
public class MultiLevelCache implements Cache {
    
    private final String name;
    private final Cache l1Cache; // 本地緩存
    private final Cache l2Cache; // 分布式緩存
    
    public MultiLevelCache(String name, Cache l1Cache, Cache l2Cache) {
        this.name = name;
        this.l1Cache = l1Cache;
        this.l2Cache = l2Cache;
    }
    
    @Override
    public String getName() {
        return name;
    }
    
    @Override
    public Object getNativeCache() {
        return this;
    }
    
    @Override
    public ValueWrapper get(Object key) {
        // 1. 先查L(zhǎng)1緩存
        ValueWrapper l1Value = l1Cache.get(key);
        if (l1Value != null) {
            return l1Value;
        }
        
        // 2. L1未命中，查L(zhǎng)2緩存
        ValueWrapper l2Value = l2Cache.get(key);
        if (l2Value != null) {
            // 3. L2命中，回寫到L1
            l1Cache.put(key, l2Value.get());
            return l2Value;
        }
        
        return null;
    }
    
    @Override
    public <T> T get(Object key, Class<T> type) {
        ValueWrapper wrapper = get(key);
        return wrapper != null ? (T) wrapper.get() : null;
    }
    
    @Override
    public <T> T get(Object key, Callable<T> valueLoader) {
        ValueWrapper wrapper = get(key);
        if (wrapper != null) {
            return (T) wrapper.get();
        }
        
        try {
            T value = valueLoader.call();
            put(key, value);
            return value;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
    
    @Override
    public void put(Object key, Object value) {
        // 同時(shí)寫入L1和L2
        l1Cache.put(key, value);
        l2Cache.put(key, value);
    }
    
    @Override
    public void evict(Object key) {
        // 同時(shí)清除L1和L2
        l1Cache.evict(key);
        l2Cache.evict(key);
    }
    
    @Override
    public void clear() {
        l1Cache.clear();
        l2Cache.clear();
    }
}

@Service
public class CategoryServiceImpl implements CategoryService {
    
    @Autowired
    private CategoryMapper categoryMapper;
    
    @Autowired
    private TreeBuilder treeBuilder;
    
    @Autowired
    private StringRedisTemplate redisTemplate;
    
    private final Cache<String, List<Category>> localCache = Caffeine.newBuilder()
            .maximumSize(100)
            .expireAfterWrite(10, TimeUnit.MINUTES)
            .build();
    
    private static final String CACHE_KEY = "category:tree:all";
    
    /**
     * 手動(dòng)實(shí)現(xiàn)多級(jí)緩存
     */
    public List<Category> getCategoryTree() {
        // 1. 查詢L1緩存（本地）
        List<Category> result = localCache.getIfPresent(CACHE_KEY);
        if (result != null) {
            log.debug("命中L1緩存");
            return result;
        }
        
        // 2. 查詢L2緩存（Redis）
        String json = redisTemplate.opsForValue().get(CACHE_KEY);
        if (StringUtils.hasText(json)) {
            try {
                result = JSON.parseArray(json, Category.class);
                // 回寫到L1緩存
                localCache.put(CACHE_KEY, result);
                log.debug("命中L2緩存，回寫L1");
                return result;
            } catch (Exception e) {
                log.warn("Redis緩存反序列化失敗", e);
            }
        }
        
        // 3. 緩存未命中，查詢數(shù)據(jù)庫(kù)
        List<Category> allCategories = categoryMapper.selectAllForTree();
        result = treeBuilder.buildTree(allCategories, null);
        
        // 4. 同時(shí)寫入L1和L2緩存
        localCache.put(CACHE_KEY, result);
        try {
            redisTemplate.opsForValue().set(CACHE_KEY, JSON.toJSONString(result), 
                    Duration.ofHours(2));
        } catch (Exception e) {
            log.warn("寫入Redis緩存失敗", e);
        }
        
        log.debug("查詢數(shù)據(jù)庫(kù)，構(gòu)建緩存");
        return result;
    }
    
    /**
     * 清除多級(jí)緩存
     */
    @Override
    public void evictCache() {
        localCache.invalidate(CACHE_KEY);
        redisTemplate.delete(CACHE_KEY);
        log.info("清除多級(jí)緩存完成");
    }
}

@Component
public class CacheWarmUp {
    
    @Autowired
    private CategoryService categoryService;
    
    /**
     * 應(yīng)用啟動(dòng)時(shí)預(yù)熱緩存
     */
    @EventListener(ApplicationReadyEvent.class)
    public void warmUpCache() {
        log.info("開始預(yù)熱分類樹緩存...");
        try {
            categoryService.getCategoryTree();
            log.info("分類樹緩存預(yù)熱完成");
        } catch (Exception e) {
            log.error("分類樹緩存預(yù)熱失敗", e);
        }
    }
    
    /**
     * 定時(shí)刷新緩存
     */
    @Scheduled(fixedRate = 300000) // 5分鐘
    public void refreshCache() {
        try {
            categoryService.getCategoryTree();
            log.debug("定時(shí)刷新分類樹緩存完成");
        } catch (Exception e) {
            log.error("定時(shí)刷新分類樹緩存失敗", e);
        }
    }
}

@Component
public class TreePerformanceMonitor {
    
    private static final String TREE_BUILD_TIMER = "tree.build.time";
    private static final String TREE_SIZE_GAUGE = "tree.size";
    
    @Autowired
    private MeterRegistry meterRegistry;
    
    /**
     * 監(jiān)控樹構(gòu)建性能
     */
    public <T> List<T> monitorTreeBuild(Supplier<List<T>> treeBuilder) {
        return Timer.Sample.start(meterRegistry)
                .stop(Timer.builder(TREE_BUILD_TIMER)
                        .description("Tree building time")
                        .register(meterRegistry))
                .recordCallable(treeBuilder::get);
    }
    
    /**
     * 記錄樹規(guī)模
     */
    public void recordTreeSize(int size) {
        Gauge.builder(TREE_SIZE_GAUGE)
                .description("Tree node count")
                .register(meterRegistry, size, s -> s);
    }
}

@CacheEvict(value = "category:tree", allEntries = true)
@Transactional
public void updateCategory(Category category) {
    // 1. 先更新數(shù)據(jù)庫(kù)
    categoryMapper.updateById(category);
    
    // 2. 緩存自動(dòng)失效（通過(guò)@CacheEvict）
    // 3. 下次查詢時(shí)重新構(gòu)建緩存
}

// 對(duì)于高并發(fā)場(chǎng)景，可以使用延時(shí)雙刪
@Async
public void delayedCacheEvict() {
    try {
        Thread.sleep(500); // 延時(shí)500ms
        cacheManager.getCache("category:tree").clear();
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}

public void sortTreeIteratively(List<TreeNode> roots) {
    Queue<TreeNode> queue = new LinkedList<>(roots);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        
        if (node.hasChildren()) {
            // 排序當(dāng)前層級(jí)
            node.getChildren().sort(Comparator.comparing(TreeNode::getSortOrder));
            // 將子節(jié)點(diǎn)加入隊(duì)列
            queue.addAll(node.getChildren());
        }
    }
}

public List<Category> getCategoryTreeLazy(int maxDepth) {
    // 只加載指定深度的數(shù)據(jù)
    List<Category> categories = categoryMapper.selectByMaxLevel(maxDepth);
    return treeBuilder.buildTree(categories, null);
}

// 按需加載子節(jié)點(diǎn)
public List<Category> loadChildren(Long parentId) {
    return categoryMapper.selectByParentId(parentId);
}