How I Cut Category Tree Load Time from 3 Seconds to 30 Milliseconds

Problem Overview

The homepage category tree suffered severe performance degradation: loading took 3–5 seconds, the database connection pool was exhausted under peak traffic, and each optimisation only treated symptoms, increasing technical debt.

Root Cause

Traditional recursive queries caused an N+1 problem – 15 000 category nodes triggered 15 000 separate database queries.

Traditional Implementation

public List<Category> getCategoryTree() {
    List<Category> roots = categoryMapper.getRootCategories(); // 1 query
    for (Category root : roots) {
        loadChildren(root); // N queries per node
    }
    return roots;
}

private void loadChildren(Category parent) {
    List<Category> children = categoryMapper.getByParentId(parent.getId()); // N queries
    parent.setChildren(children);
    for (Category child : children) {
        loadChildren(child); // recursive
    }
}

Analysis of the N+1 issue:

10 000 nodes → 10 000 queries (≈20 s total)

Database connection pool quickly exhausted

Massive temporary object creation → high GC pressure

Performance Test Data

# Nodes | Traditional (ms) | Optimized (ms) | Speedup
---------------------------------------------------
  1,000 | 800               | 15             | 53×
  5,000 | 2,800             | 25             | 112×
 10,000 | 5,200             | 30             | 173×
 50,000 | timeout           | 45             | 1000×+

Optimized Solution: Single Query + O(n) Algorithm

Key Ideas

Replace N+1 queries with a single batch SELECT.

Build a HashMap index (O(1) look‑ups) for parent‑child relationships.

Traverse the list once to assemble the tree (O(n)).

Cache the built tree to avoid repeated computation.

Database Schema

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

Tree Building Algorithm

public <T extends TreeNode<T>> List<T> buildTree(List<T> nodes, Object rootValue) {
    // 1. Build ID → Node map (O(n))
    Map<Object, T> nodeMap = nodes.stream()
        .collect(Collectors.toMap(TreeNode::getId, node -> node));

    List<T> rootNodes = new ArrayList<>();

    // 2. Single pass to link parent and child (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);
            }
        }
    }
    return rootNodes;
}

Complexity Analysis

Time: O(n) vs. O(n²) in the recursive version.

Space: O(n) for the HashMap.

Database queries: 1 instead of n.

Cache Layer

Spring Cache Annotation

@Cacheable(value = "category:tree", key = "'all'")
public List<Category> getCategoryTree() {
    List<Category> all = categoryMapper.selectAllForTree();
    return treeBuilder.buildTree(all, null);
}

Manual Multi‑Level Cache Example

public List<Category> getCategoryTree() {
    List<Category> result = localCache.getIfPresent(CACHE_KEY);
    if (result != null) return result;

    String json = redisTemplate.opsForValue().get(CACHE_KEY);
    if (StringUtils.hasText(json)) {
        result = JSON.parseArray(json, Category.class);
        localCache.put(CACHE_KEY, result);
        return result;
    }

    List<Category> all = categoryMapper.selectAllForTree();
    result = treeBuilder.buildTree(all, null);
    localCache.put(CACHE_KEY, result);
    redisTemplate.opsForValue().set(CACHE_KEY, JSON.toJSONString(result), Duration.ofHours(2));
    return result;
}

Performance Monitoring

public <T> List<T> monitorTreeBuild(Supplier<List<T>> builder) {
    return Timer.sample(meterRegistry)
        .stop(Timer.builder("tree.build.time").register(meterRegistry))
        .recordCallable(builder::get);
}

FAQ

Cache Consistency After Updates

@CacheEvict(value = "category:tree", allEntries = true)
@Transactional
public void updateCategory(Category category) {
    categoryMapper.updateById(category);
}

Preventing Stack Overflow for Deep Trees

public void sortTreeIteratively(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());
        }
    }
}

Handling Very Large Data Sets

public List<Category> getCategoryTreeLazy(int maxDepth) {
    List<Category> categories = categoryMapper.selectByMaxLevel(maxDepth);
    return treeBuilder.buildTree(categories, null);
}

Key Takeaways

Algorithmic improvement from O(n²) to O(n) reduces response time from seconds to tens of milliseconds.

Consolidating queries from N+1 to a single batch query cuts database load dramatically.

Multi‑level caching (local + distributed) raises cache hit rate above 95 % and eliminates most database traffic.

Continuous monitoring and incremental optimisations are essential for maintaining performance at scale.