3s→30ms，查询提速100倍！SpringBoot树形结构优化实录

一、一个真实的性能灾难

二、传统方案为什么这么慢？

// 这段代码看起来很简单，实际上是性能杀手public List<Category> getCategoryTree() {    List<Category> roots = categoryMapper.getRootCategories(); // 1次查询    for (Category root : roots) {        loadChildren(root); // 每个节点都触发递归查询    }    return roots;}private void loadChildren(Category parent) {    List<Category> children = categoryMapper.getByParentId(parent.getId()); // N次查询    parent.setChildren(children);    for (Category child : children) {        loadChildren(child); // 递归继续    }}

三、核心解决方案：一次查询 + O(n)算法

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));

四、算法复杂度分析：O(n²) → O(n) 的关键突破

// 传统方案：时间复杂度 O(n²)，空间复杂度 O(n)public List<Category> getChildren(Long parentId) {    List<Category> children = categoryMapper.getByParentId(parentId);  // 1次查询    for (Category child : children) {                                 // 对每个子节点        child.setChildren(getChildren(child.getId()));                // 递归查询子节点    }    return children;}

// 以10000个节点为例的执行过程Root Node (id=1)├── Child1 (id=2) -> SELECT * FROM category WHERE parent_id = 2  // 第1次查询│   ├── Child1.1 (id=5) -> SELECT * FROM category WHERE parent_id = 5  // 第2次查询│   └── Child1.2 (id=6) -> SELECT * FROM category WHERE parent_id = 6  // 第3次查询├── Child2 (id=3) -> SELECT * FROM category WHERE parent_id = 3  // 第4次查询│   └── Child2.1 (id=7) -> SELECT * FROM category WHERE parent_id = 7  // 第5次查询└── Child3 (id=4) -> SELECT * FROM category WHERE parent_id = 4  // 第6次查询    └── ...继续递归，总共10000次查询

// 优化方案：时间复杂度 O(n)，空间复杂度 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：单次遍历建立父子关系 - O(n)    for (T node : nodes) {                    // 遍历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);        // 建立父子关系：O(1)            }        }    }    return rootNodes;}

// 优化后的执行过程 - 以10000个节点为例Step 1: SELECT * FROM category WHERE status = 1  // 仅1次查询获取所有数据
Step 2: 内存中构建HashMap索引 - O(n){  1 -> Node{id=1, name="根节点", parentId=null},  2 -> Node{id=2, name="子节点1", parentId=1},  3 -> Node{id=3, name="子节点2", parentId=1},  ...  10000 -> Node{id=10000, name="叶子节点", parentId=9999}}
Step 3: 单次遍历建立关系 - O(n)for (Node node : allNodes) {  // 10000次循环    Node parent = nodeMap.get(node.parentId);  // O(1)查找    parent.addChild(node);  // O(1)添加}

五、O(n)高性能树构建算法

@Componentpublic class TreeBuilder {    /**     * 高性能树构建算法 - O(n)时间复杂度     * @param nodes 所有节点列表     * @param rootValue 根节点的parent_id值（通常为null或0）     * @return 构建好的树结构     */    public <T extends TreeNode<T>> List<T> buildTree(List<T> nodes, Object rootValue) {        if (CollectionUtils.isEmpty(nodes)) {            return new ArrayList<>();        }        // 1. 建立ID->Node的快速索引，时间复杂度O(n)        Map<Object, T> nodeMap = nodes.stream()            .collect(Collectors.toMap(TreeNode::getId, node -> node));        List<T> rootNodes = new ArrayList<>();        // 2. 单次遍历建立父子关系，时间复杂度O(n)        for (T node : nodes) {            Object parentId = node.getParentId();            if (Objects.equals(parentId, rootValue)) {                // 根节点                rootNodes.add(node);            } else {                // 子节点，建立父子关系                T parent = nodeMap.get(parentId);                if (parent != null) {                    parent.addChild(node);                }            }        }        // 3. 递归排序（可选），时间复杂度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())));        // 递归排序子节点        for (T node : nodes) {            if (node.hasChildren()) {                sortTreeRecursively(node.getChildren());            }        }    }}

public interface TreeNode<T> {    Object getId();    Object getParentId();    Integer getSortOrder();    List<T> getChildren();    voidsetChildren(List<T> children);    defaultvoidaddChild(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;    // 非数据库字段    @TableField(exist = false)    private List<Category> children;    @Override    public void addChild(Category child) {        if (children == null) {            children = new ArrayList<>();        }        children.add(child);    }}

@Mapperpublic interface CategoryMapper extends BaseMapper<Category> {    /**     * 获取所有有效分类（用于构建树）     */    @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();    /**     * 根据父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. 一次性查询所有数据        List<Category> allCategories = categoryMapper.selectAllForTree();        // 2. 使用高性能算法构建树        return treeBuilder.buildTree(allCategories, null);    }    /**     * 创建分类     */    @CacheEvict(value = "category:tree", allEntries = true)    public Category createCategory(Category category) {        // 设置层级        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);    }    /**     * 创建分类     */    @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@EnableCachingpublic class MultiLevelCacheConfig {    /**     * 多级缓存管理器：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分钟过期                .recordStats());        return cacheManager;    }    private RedisCacheManager createRedisCacheManager(RedisConnectionFactory connectionFactory) {        RedisCacheConfiguration config = RedisCacheConfiguration.defaultCacheConfig()                .entryTtl(Duration.ofHours(2)) // L2缓存2小时过期                .serializeKeysWith(RedisSerializationContext.SerializationPair                        .fromSerializer(new StringRedisSerializer()))                .serializeValuesWith(RedisSerializationContext.SerializationPair                        .fromSerializer(new GenericJackson2JsonRedisSerializer()))                .disableCachingNullValues();        return RedisCacheManager.builder(connectionFactory)                .cacheDefaults(config)                .build();    }}/** * 自定义多级缓存管理器 */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;    }}/** * 多级缓存实现 */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. 先查L1缓存        ValueWrapper l1Value = l1Cache.get(key);        if (l1Value != null) {            return l1Value;        }        // 2. L1未命中，查L2缓存        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) {        // 同时写入L1和L2        l1Cache.put(key, value);        l2Cache.put(key, value);    }    @Override    public void evict(Object key) {        // 同时清除L1和L2        l1Cache.evict(key);        l2Cache.evict(key);    }    @Override    public void clear() {        l1Cache.clear();        l2Cache.clear();    }}

@Servicepublic 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";    /**     * 手动实现多级缓存     */    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. 缓存未命中，查询数据库        List<Category> allCategories = categoryMapper.selectAllForTree();        result = treeBuilder.buildTree(allCategories, null);        // 4. 同时写入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("查询数据库，构建缓存");        return result;    }    /**     * 清除多级缓存     */    @Override    public void evictCache() {        localCache.invalidate(CACHE_KEY);        redisTemplate.delete(CACHE_KEY);        log.info("清除多级缓存完成");    }}

@Componentpublic class CacheWarmUp {    @Autowired    private CategoryService categoryService;    /**     * 应用启动时预热缓存     */    @EventListener(ApplicationReadyEvent.class)    public void warmUpCache() {        log.info("开始预热分类树缓存...");        try {            categoryService.getCategoryTree();            log.info("分类树缓存预热完成");        } catch (Exception e) {            log.error("分类树缓存预热失败", e);        }    }    /**     * 定时刷新缓存     */    @Scheduled(fixedRate = 300000) // 5分钟    public void refreshCache() {        try {            categoryService.getCategoryTree();            log.debug("定时刷新分类树缓存完成");        } catch (Exception e) {            log.error("定时刷新分类树缓存失败", e);        }    }}

@Componentpublic 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;    /**     * 监控树构建性能     */    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);    }    /**     * 记录树规模     */    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)@Transactionalpublic void updateCategory(Category category) {    // 1. 先更新数据库    categoryMapper.updateById(category);    // 2. 缓存自动失效（通过@CacheEvict）    // 3. 下次查询时重新构建缓存}// 对于高并发场景，可以使用延时双删@Asyncpublic void delayedCacheEvict() {    try {        Thread.sleep(500); // 延时500ms        cacheManager.getCache("category:tree").clear();    } catch (InterruptedException e) {        Thread.currentThread().interrupt();    }}

publicvoidsortTreeIteratively(List<TreeNode> roots){    Queue<TreeNode> queue = new LinkedList<>(roots);    while (!queue.isEmpty()) {        TreeNode node = queue.poll();        if (node.hasChildren()) {            // 排序当前层级            node.getChildren().sort(Comparator.comparing(TreeNode::getSortOrder));            // 将子节点加入队列            queue.addAll(node.getChildren());        }    }}

public List<Category> getCategoryTreeLazy(int maxDepth) {    // 只加载指定深度的数据    List<Category> categories = categoryMapper.selectByMaxLevel(maxDepth);    return treeBuilder.buildTree(categories, null);}
// 按需加载子节点public List<Category> loadChildren(Long parentId) {    return categoryMapper.selectByParentId(parentId);}

九、总结：从3秒到30毫秒的核心要点