二叉树节点插入：如何优化20万行数据下的父节点查询性能？

数据库树结构 #

用户提交树表单时，该表会持续增长。我已通过BFS方法实现了根据给定节点值查找下一个父节点的函数，但当前存在性能问题：当数据量达20万行时，查询节点1会因遍历所有节点导致资源占用高、性能差。后续优化为单次查询拉取全量数据并在内存中处理逻辑，减少了数据库交互，但多用户查询时全量数据占用内存过大，仍需优化，当前执行时间为80秒。

原实现代码 #

public function getNodeInsertPostionByParentId($parentIds)
{
    $parent = array('status' => false);
    $results = array();

    // Fetch all data from tree
    $qry = "SELECT nodeid, nodeposition, nodeparentid FROM tree ORDER BY nodeposition";
    $stmt = $this->mysqli->prepare($qry);
    $stmt->execute();
    $stmt->bind_result($nodeid, $nodeposition, $nodeparentid);

    // Create a map to store children for each parent
    $childrenMap = array();

    // Process query results
    while ($stmt->fetch()) {
        $childrenMap[$nodeparentid][] = array('id' => $nodeid, 'position' => $nodeposition);
    }

    // Use BFS to process each parent ID
    $queue = $parentIds;

    while (!empty($queue)) {
        $currentParent = array_shift($queue);

        // Process the current parent
        $children = isset($childrenMap[$currentParent]) ? $childrenMap[$currentParent] : array();
        $count = count($children);

        if ($count == 2) {
            // Two children, recursively check each child
            foreach ($children as $child) {
                $queue[] = $child['id'];
            }
           
        } elseif ($count == 1) {
            // One child, set position to 'Right' or 'Left' based on the child's ID
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = 'Right';
            break;
        } elseif ($count == 0) {
            // No children, set position to 'Right' or 'Left' based on the current parent's ID
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = 'Left';
            break;
        }
    }

    // Return the processed results
    return $parent;
}

$yourInstance = new YourClassName();
echo '<pre>';
print_r($yourInstance->getNodeInsertPostionByParentId(array('1')));

树结构与查询预期 #

对应的树结构如下：

1 
         /        \
        2          3 
      /    \      / \
     4      5    6  7 
    / \    / \
   8   9  10

查询预期结果：

• 查询节点1时，应返回插入到节点5的Right位置
• 查询节点6时，应返回插入到节点6的Left位置
• 查询节点3时，应返回插入到节点6的Left位置
• 查询节点2时，应返回插入到节点5的Right位置

优化方案 #

1. 数据库层面：只查询目标节点的子树数据 #

全表查询是内存占用过高的核心原因，使用MySQL 8.0+支持的CTE递归查询，仅加载目标节点及其所有后代的数据：

WITH RECURSIVE subtree AS (
    SELECT nodeid, nodeposition, nodeparentid 
    FROM tree 
    WHERE nodeid = ?  -- 传入目标parentId
    UNION ALL
    SELECT t.nodeid, t.nodeposition, t.nodeparentid 
    FROM tree t
    JOIN subtree s ON t.nodeparentid = s.nodeid
)
SELECT * FROM subtree ORDER BY nodeposition;

此方式可将数据加载量从20万行降至目标子树的规模，内存占用大幅降低。

2. 遍历逻辑：用DFS替代BFS减少无效遍历 #

根据需求，我们需要找到最底层第一个有空位的节点，DFS（深度优先）可以优先遍历左子节点直达底层，比BFS更快定位目标：

public function getNodeInsertPostionByParentId($targetParentId)
{
    $parent = array('status' => false);

    // 仅查询目标节点的子树
    $qry = "WITH RECURSIVE subtree AS (
        SELECT nodeid, nodeposition, nodeparentid 
        FROM tree 
        WHERE nodeid = ?
        UNION ALL
        SELECT t.nodeid, t.nodeposition, t.nodeparentid 
        FROM tree t
        JOIN subtree s ON t.nodeparentid = s.nodeid
    )
    SELECT nodeid, nodeposition, nodeparentid FROM subtree ORDER BY nodeposition";
    
    $stmt = $this->mysqli->prepare($qry);
    $stmt->bind_param('i', $targetParentId);
    $stmt->execute();
    $stmt->bind_result($nodeid, $nodeposition, $nodeparentid);

    $childrenMap = array();
    while ($stmt->fetch()) {
        $childrenMap[$nodeparentid][] = array('id' => $nodeid, 'position' => $nodeposition);
    }

    // 栈实现DFS，优先遍历左子节点
    $stack = array($targetParentId);
    while (!empty($stack)) {
        $currentParent = array_pop($stack);
        $children = $childrenMap[$currentParent] ?? array();
        $count = count($children);

        if ($count == 0) {
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = 'Left';
            break;
        } elseif ($count == 1) {
            $parent['status'] = true;
            $parent['parentId'] = $currentParent;
            $parent['node'] = $children[0]['position'] == 'Left' ? 'Right' : 'Left';
            break;
        } else {
            // 右子节点先入栈，左子节点后入栈，保证弹出时先处理左子节点
            array_push($stack, $children[1]['id'], $children[0]['id']);
        }
    }

    return $parent;
}

3. 数据库索引优化 #

给nodeparentid字段添加索引，加速递归查询的关联操作：

CREATE INDEX idx_tree_nodeparentid ON tree(nodeparentid);

4. 缓存高频查询结果 #

对于根节点这类高频查询的节点，将其子树的childrenMap缓存到Redis或内存缓存中，数据更新时失效缓存，避免重复查询和映射构建。

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