数组转树形结构性能优化咨询：大数据量下生成耗时过长

Great question! When you’re dealing with large datasets, the common naive approach (like recursively scanning the entire array to find each node’s parent) ends up with a O(n²) time complexity—this is exactly why it gets slow with lots of data. The key fix here is to use a hash map (or object) to index all nodes first, so we can look up parent nodes in constant time O(1) instead of looping through the whole array every single time.

Core Optimized Approach #

The logic is straightforward:

1. First, iterate through your dataset once to store every node in a map, where the key is the node’s id and the value is the node itself. We’ll also initialize an empty children array for each node here (if it doesn’t exist already).
2. Iterate through the dataset a second time to link each node to its parent’s children array using the map for instant lookups.
3. Finally, collect all root nodes (nodes where parentId is 0, or whatever your root identifier is) to form the top of the tree.

Example Implementation (JavaScript) #

function convertToTree(data) {
  const nodeMap = new Map();
  const rootNodes = [];

  // First pass: build map of nodes and initialize children
  data.forEach(node => {
    nodeMap.set(node.id, { ...node, children: [] });
  });

  // Second pass: link children to parents
  data.forEach(node => {
    const parent = nodeMap.get(node.parentId);
    if (parent) {
      parent.children.push(nodeMap.get(node.id));
    } else {
      // If no parent exists, it's a root node
      rootNodes.push(nodeMap.get(node.id));
    }
  });

  return rootNodes;
}

// Usage with your sample data
const data = [
  { id: 1, name: 'A', parentId: 0 },
  { id: 2, name: 'B', parentId: 1 },
  { id: 3, name: 'C', parentId: 2 },
  { id: 4, name: 'D', parentId: 3 },
  { id: 5, name: 'E', parentId: 4 },
  { id: 6, name: 'F', parentId: 1 } // Example sibling to B
];

const tree = convertToTree(data);
console.log(tree);

Additional Optimizations #

• Single Pass (If Data is Sorted): If your dataset is guaranteed to have parent nodes appear before their children (e.g., root nodes first, then level 1, then level 2, etc.), you can do this in a single iteration. Check if the parent exists in the map as you go—if yes, add to its children; if not, add to root nodes. This cuts down to one loop instead of two.
• Avoid Unnecessary Copies: If you don’t need to clone the original nodes (e.g., you’re okay mutating the original data), you can skip the spread operator ({ ...node }) and just initialize children directly on the original node. This saves memory and time for very large datasets.
• Use Plain Objects Instead of Map (Optional): If your id values are strings or numbers that work well as object keys, you can use a plain JavaScript object instead of Map—performance is roughly the same, but some developers prefer object syntax.
• Lazy Initialization for Children: If most nodes don’t have children, you can avoid initializing empty children arrays upfront and only create them when a child is added. This reduces memory usage.

Why This Works #

By using a map, we eliminate the need to scan the entire array for each parent node. Each node is processed exactly twice (once to add to the map, once to link to its parent), leading to an overall O(n) time complexity—this is night and day compared to O(n²) when you have thousands or millions of nodes.

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